A quantum speed-up for approximating the top eigenvectors of a matrix

Finding a good approximation of the top eigenvector of a given $d \times d$ matrix $A$ is a basic and important computational problem, with many applications. We give two different quantum algorithms that, given query access to the entries of a Hermitian matrix $A$ and assuming a constant eigenvalue gap, output a classicaldescription of a good approximation of the top eigenvector: one algorithm with time complexity $\mathcal{\tilde{O}}(d^{1.75})$ and one with time complexity $d^{1.5+o(1)}$ (the first algorithm has a slightly better dependence on the $ℓ2$-error of the approximating vector than the second, and uses different techniques of independent interest). Both of our quantum algorithms provide a polynomial speed-up over the best-possible classical algorithm, which needs $Ω(d^2)$ queries to entries of $A$, and hence $Ω(d^2)$ time. We extend this to a quantum algorithm that outputs a classical description of the subspace spanned by the top-$q$ eigenvectors in time $qd^{1.5+o(1)}$. We also prove a nearly-optimal lower bound of $\tilde{Ω}(d^{1.5})$ on the quantum query complexity of approximating the top eigenvector. Our quantum algorithms run a version of the classical power method that is robust to certain benign kinds of errors, where we implement each matrix-vector multiplication with small and well-behaved error on a quantum computer, in different ways for the two algorithms. Our first algorithm estimates the matrix-vector product one entry at a time, using a new "Gaussian phase estimation" procedure. Our second algorithm uses block-encoding techniques to compute the matrix-vector product as a quantum state, from which we obtain a classical description by a new time-efficient unbiased pure-state tomography procedure. This procedure uses an essentially optimal number $\mathcal{\tilde{O}}(d \text{log} (d)/\epsilon^2)$ of "conditional sample states"; if we have a state-preparation unitary available rather than just copies of the state, then this $\epsilon$-dependence can be improved further quadratically.Our procedure comes with improved statistical properties and faster runtime compared to earlier pure-state tomography algorithms. We also develop an almost optimal time-efficient process-tomography algorithm for reflections around bounded-rank subspaces, providing the basis for our top-eigensubspace estimation algorithm, and in turn providing a pure-state tomography algorithm that only requires a reflection about the state rather than a state preparation unitary as input.

• View at Publisher

Full Text ( Final Version , 1mb )

See Also
techReport A Quantum Speed-Up for approximating the top eigenvectors of a matrix Y. Chen (Yanlin), A.P. Gilyén (András) and R.M. de Wolf (Ronald)