We apply the framework of block-encodings, introduced by Low and Chuang (under the name standard-form), to the study of quantum machine learning algorithms and derive general results that are applicable to a variety of input models, including sparse matrix oracles and matrices stored in a data structure. We develop several tools within the block-encoding framework, such as singular value estimation of a block-encoded matrix, and quantum linear system solvers using block-encodings. The presented results give new techniques for Hamiltonian simulation of non-sparse matrices, which could be relevant for certain quantum chemistry applications, and which in turn imply an exponential improvement in the dependence on precision in quantum linear systems solvers for non-sparse matrices. In addition, we develop a technique of variable-time amplitude estimation, based on Ambainis' variable-time amplitude amplification technique, which we are also able to apply within the framework. As applications, we design the following algorithms: (1) a quantum algorithm for the quantum weighted least squares problem, exhibiting a 6-th power improvement in the dependence on the condition number and an exponential improvement in the dependence on the precision over the previous best algorithm of Kerenidis and Prakash; (2) the first quantum algorithm for the quantum generalized least squares problem; and (3) quantum algorithms for estimating electrical-network quantities, including effective resistance and dissipated power, improving upon previous work.
Abstract. Many problems in linear algebra—such as those arising from non-Hermitian physics, transcorrelated quantum chemistry, and differential equations—can be solved on a quantum computer by processing eigenvalues of the non-normal input matrices. However, the existing Quantum Singular Value Transformation (QSVT) framework is ill-suited for this task because eigenvalues and singular values are different in general. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary polynomial transformations on eigenvalues of block-encoded non-normal operators and a related Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra. QEVT has query complexity to the block encoding nearly recovering that of the QSVT for a Hermitian input, and QEVE achieves the Heisenberg-limited scaling for diagonalizable input matrices. As applications, we develop a linear differential equation solver with strictly linear time query complexity for average-case diagonalizable operators, as well as a ground state preparation algorithm that upgrades previous nearly optimal results for Hermitian Hamiltonians to diagonalizable matrices with real spectra. Underpinning our algorithms is an efficient method to prepare a quantum superposition of Faber polynomials, which generalize the nearly-best uniform approximation properties of Chebyshev polynomials to the complex plane. Of independent interest, we also develop techniques to generate [Formula: see text] Fourier coefficients with [Formula: see text] gates compared to prior approaches with linear cost.
Many problems in linear algebra-such as those arising from non-Hermitian physics, transcorrelated quantum chemistry and differential equations-can be solved on a quan-tum computer by processing eigenvalues of the non-normal input matrices. However, the existing Quantum Singular Value Transformation (QSVT) framework is ill-suited to this task, as eigenvalues and singular values are different in general. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary polynomial transformations on eigenvalues of block-encoded non-normal operators, and a related Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra. QEVT has query complexity to the block encoding nearly recovering that of the QSVT for a Hermitian input, and QEVE achieves the Heisenberg-limited scaling for diagonalizable input matrices. As applications, we develop a linear differential equation solver with strictly linear time query complexity for average-case diagonalizable operators, as well as a ground state preparation algorithm that upgrades previous nearly optimal results for Hermitian Hamiltonians to diagonalizable matrices with real spectra. Underpinning our algorithms is an efficient method to prepare a quantum super-position of Faber polynomials, which generalize the nearly-best uniform approximation properties of Chebyshev polynomials to the complex plane. Of independent interest, we also develop techniques to generate
nFourier coefficients with 0 (poly log (
n)) gates compared to prior approaches with linear cost.
Quantum Signal Processing (QSP) and Quantum Singular Value Transformation (QSVT) provide an efficient framework for implementing polynomials of block-encoded matrices, and thus offer a systematic approach to quantum algorithm design. However, despite a number of recent advances, important limitations remain. In particular, QSP can only transform unitary matrices, by applying a polynomial to their eigenvalues, while QSVT is a singular-value transformation and thus one can only obtain the polynomial of Hermitian matrices. As a consequence, these techniques do not directly apply to an arbitrary non-Hermitian matrix that is not diagonalizable. In this work, we propose a simple yet powerful method to extend these ideas to arbitrary square matrices by acting on their eigenvalues. To this end, we introduce the notion of an
n-regular block encoding, namely, a block encoding whose
k-th power reproduces the
k-th power of the encoded matrix for every
0<k<n. We show that applying QSP to any unitary with this property is equivalent to applying a polynomial of degree at most
n to the block-encoded matrix, independently of its internal structure. Moreover, we provide a simple construction that transforms any block encoding into an
n-regular one using only
O(logn) ancillary qubits and operations. Finally, we show that this construction induces the desired transformation on the eigenvalues associated with the Jordan normal form of the matrix; for non-diagonalizable matrices this yields the full matrix function
P(A), whose action on each Jordan block involves the derivatives of
P, and not merely the map
λ↦P(λ).
Most quantum algorithms offering speedups over classical algorithms are based on the three techniques of phase estimation, amplitude estimation and Hamiltonian simulation. In spite of the linear algebraic nature of the postulates of quantum mechanics, until recent work by Lloyd and coauthors cite{LMR13, LMR13a, LMR13b} no quantum algorithms achieving speedups for linear algebra or machine learning had been proposed. A quantum machine learning algorithm must address three issues: encoding of classical data into a succinct quantum representation, processing the quantum representation and extraction of classically useful information from the processed quantum state. In this dissertation, we make progress on all three aspects of the quantum machine learning problem and obtain quantum algorithms for low rank approximation and regularized least squares. The oracle
QRAM, the standard model studied in quantum query complexity, requires time
O(sqrtn) to encode vectors
vinRn into quantum states. We propose simple hardware augmentations to the oracle
QRAM, that enable vectors
vinRn to be encoded in time
O(logn), with pre-processing. The augmented
QRAM incurs minimal hardware overheads, the pre-processing can be parallelized and is a flexible model that allows storage of multiple vectors and matrices. It provides a framework for designing quantum algorithms for linear algebra and machine learning. Using the augmented
QRAM for vector state preparation, we present two different algorithms for singular value estimation where given singular vector
ketv for
AinRmtimesn, the singular value
sigmai is estimated within additive error
epsilonnormAF. The first algorithm requires time
wt1/epsilon3 and uses the approach for simulating
e−irho in cite{LMR13}. However, the analysis cite{LMR13} does not establish the coherence of outputs, we provide a qualitatively different analysis that uses the quantum Zeno effect to establish coherence and reveals the probabilistic nature of the simulation technique. The second algorithm has a running time
wt1/epsilon and uses Jordan's lemma from linear algebra and the augmented
QRAM to implement reflections. We use quantum singular value estimation to obtain algorithms for low rank approximation by column selection, the algorithms are based on importance sampling from the leverage score distribution. We obtain quadratic speedups for a large class of linear algebra algorithms that rely on importance sampling from the leverage score distribution including approximate least squares and
CX and
CUR decompositions. Classical algorithms for these problems require time
O(mnlogn+poly(1/epsilon)), the quantum algorithms have running time
O(sqrtmpoly(1/epsilon,k,Delta)) where
k,Delta are the rank and spectral gap. The running time of the quantum
CX decomposition algorithm does not depend on
m, it is polynomial in problem parameters. We also provide quantum algorithms for
ell2 regularized regression problems, the quantum ridge regression algorithm requires time
wt1/mu2delta to output a quantum state that is
delta close to the solution, where
mu is the regularization parameter.
Quantum signal processing (QSP) and generalized quantum signal processing (GQSP) are essential tools for implementing the block encoding of matrix functions. The achievable polynomials of QSP have restrictions on parity, while GQSP eliminates these restrictions. But GQSP only constructs functions of unitary matrices. In this paper, we further investigate GQSP and extend it to general matrices. Compared with the quantum singular value transformation (QSVT), our proposed method relaxes the requirements on the parity of polynomials. We refer to this extension as generalized quantum singular value transformation (GQSVT). Subsequently, by utilizing the relationship between generalized matrix functions and standard matrix functions, we propose a classical-quantum hybrid quantum conjugate gradient least squares (CGLS) algorithm using GQSVT.