A Quantum Speed-Up for Approximating the Top Eigenvector of aMatrix via Improved Tomography
Talkat Near-Term Quantum Computers: Fault Tolerance + Benchmarking + Quantum Advantage + Quantum Algorithms · 2024-04-22..04-26·
summary
Claims a quantum algorithm that outputs a classical description of the top eigenvector of a d×d matrix with gap constant using block-encoding plus a new unbiased pure-state tomography routine and iterative refinement, achieving ~d^{1.5} time and extending to top-q subspace in ~q d^{1.5} time. Tomography uses an essentially minimal ~d/ε state calls to recover amplitudes with coordinatewise error ε/√d, and a matching Ω̃(d^{1.5}) quantum lower bound is proven.
AI-written summary · about
chapters (6)
- 0:00Introduction and motivation
- 4:21Algorithm framework
- 13:06Unbiased tomography
- 24:36Subspace reconstruction
- 30:44Iterative refinement
- 38:48Lower bounds and conclusion
related talks
48mQuantum Linear Algebra Using Subspace States
01h 00mSymmetry and Topological Order in Quantum States
01h 06mQuantum Algorithms for Approximating Partition Functions
01h 06mNorm Minimization, Invariant Theory, And Quantum Tomography
44mQuantum machine learning: Prospects and challenges
06mHow looking at a problem quantumly could solve it faster?
44mNo Quantum Speedup Over Gradient Descent for Non-Smooth Convex Optimization
01h 07mTwo Tensor Optimization Problems From Quantum Information