A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix

Understand

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 classical description 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 $\ell_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 $\Omega(d^2)$ queries to entries of $A$, and hence $\Omega(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)}$.