A Quantum Speed-Up for Approximating the Top Eigenvector of a Matrix via Improved Tomography
Explore a quantum algorithm that provides a polynomial speed-up for approximating the top eigenvector of a matrix in this 47-minute lecture by András Gilyén from the Alfréd Rényi Institute of Mathematics. Delve into the algorithm's ability to output a classical description of the top eigenvector with a time complexity of ~d^{1.5}, significantly faster than the best classical algorithm's Ω(d^2) time. Learn about the algorithm's extension to output the subspace spanned by the top-q eigenvectors and the nearly-optimal lower bound on quantum query complexity. Discover how this quantum approach implements a noisy variant of the classical power method, utilizing block-encoding techniques and a new time-efficient unbiased pure-state tomography algorithm. Examine the development of a time-efficient process-tomography algorithm for reflections around bounded-rank subspaces, which enhances pure-state tomography capabilities.