Abstract
Finding a good approximation of the top eigenvector of a given d × d matrix A is a basic and important computational problem, with many applications. We give a quantum algorithms that, given query access to the entries of A and assuming a constant eigenvalue gap, outputs a classical description of a good approximation of the top eigenvector with time complexity ~d^{1.5}. Our quantum algorithm provides a polynomial speed-up over the best-possible classical algorithm, which needs Ω(d^2) queries toentries of A, and hence Ω(d^2) time. More generally, our algorithm can output a classical description of the subspace spanned by the top-q eigenvectors in time ~q d^{1.5}. We also prove a nearly-optimal lower bound of Ω̃(d^{1.5}) on the quantum query complexity of approximating the top eigenvector. Our quantum algorithm can be thought of as a noisy variant of the classical power method, where we implement each matrix-vector multiplication with small and well-behaved error on a quantum computer. Our 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 algorithm. This algorithm uses an essentially minimal number ~d/ε of calls to a state-preparation unitary. We also prove a nearly-matching lower bound of Ω̃(d^{1.5}) on the quantum query complexity of approximating the top eigenvector. For learning the top-q eigensubspace we develop a time-efficient process-tomography algorithm for reflections around bounded-rank subspaces, which in turn provides a pure-state tomography algorithm that only requires a reflection about the state rather than a state preparation unitary as input.