Quantum Linear Algebra Using Subspace States
summary
Claims an implemented circuit family that prepares subspace states and yields a polynomial determinantal-sampling speedup: a quantum algorithm using Clifford loader circuits and FBS gates runs in O(N·D) gate count and D·log N depth (so D~N gives N^2 vs classical N^3), with provable action as Givens rotations on subspace amplitudes. Also shows a quantum routine for compound matrix SVD (singular-value estimation for Kth compounds) with potential exponential advantage over classical N^K costs, and a log-depth Dirac embedding for TDA.
AI-written summary · about
chapters (27)
- 0:00Intro
- 0:35QUANTUM SPEEDUPS CRITERIA
- 2:10EXPONENTIAL QML SPEEDUPS?
- 4:09READ THE FINE PRINT!
- 5:15TOWARDS END-TO-END QML
- 7:19NETFLIX PROBLEM
- 7:56QRS/DEQUANTIZATION
- 8:41QML POST DEQUANTIZATION
- 11:44DETERMINANT SAMPLING
- 19:252. COMPOUND MATRICES
- 23:013. TOPOLOGICAL DATA ANALYSIS
- 27:12SUBSPACE STATES FOR QML
- 28:25QUANTUM OPERATIONS ON SUBSPACE STATES
- 30:49CLIFFORD ALGEBRAS
- 32:38THE GAMMA MAP
- 34:13CLIFFORD LOADERS
- 35:22UNARY DATA LOADERS
- 36:13FERMIONIC BEAM SPLITTER (FBS) GATES
- 36:58CLIFFORD LOADER CONSTRUCTION
- 37:57ROTATIONS ON SUBSPACE STATES
- 38:25QUANTUM GIVENS ROTATIONS
- 39:14COMPOUND MATRIX SVD
- 39:34THE ACTION OF A GIVENS CIRCUIT
- 40:06DIRAC OPERATOR EMBEDDING
- 40:44NEW QUANTUM SPEEDUPS
- 41:34RESEARCH QUESTIONS
- 42:11SOME TAKEAWAYS
related talks
01h 10mQuantum Advantage with Shallow Clifford Circuits
42mLearning Shallow Quantum Circuits and Quantum States Prepared by Shallow Circuits in Polynomial Time
51mOn constant T-depth circuits
44mQuantum machine learning: Prospects and challenges
02h 41mLightning Talks
01h 36mAlgorithms for Algebraic Lattices: Classical and Quantum
32mCan We Get Verifiable Quantum Advantage from Forrelation
01h 04mLearning Beyond Stabilizer States