Learning Shallow Quantum Circuits and Quantum States Prepared by Shallow Circuits in Polynomial Time
Talkat Near-Term Quantum Computers: Fault Tolerance + Benchmarking + Quantum Advantage + Quantum Algorithms · 2024-04-22..04-26·
summary
Gives polynomial time algorithms that (1) learn a constant‑depth circuit approximating an unknown lattice unitary U in small diamond distance from only random single‑qubit stabilizer inputs and random Pauli measurements (classical shadows), and (2) learn a constant‑depth preparer for copies of |ψ〉=U|0^n〉; extends to polylog(n) depth with quasi‑polynomial run time. Core tools are local inversion (disentangle, swap, undo) that reconstructs U†⊗U via U† S_i U local operators, and a layered covering scheme (k+1 colors) with ancilla to rebuild global state from local reduced densities, giving an efficient test for trivial versus topological phases.
AI-written summary · about
chapters (15)
- 0:00Shallow quantum circuits intro
- 1:49NISQ algorithm challenges
- 4:02Learning from samples
- 8:05Swap and undo technique
- 13:15Low-depth circuit reconstruction
- 15:42Simplified circuit learning
- 21:54States from measurements
- 23:17Local inversion method
- 28:45Full output state reconstruction
- 30:55Lattice geometry arrangement
- 34:08Phases of matter implications
- 36:56Beyond lattice geometry
- 37:39Ancilla qubits role
- 38:22NISQ algorithms outlook
- 39:05Summary
related talks
01h 04mLearning Beyond Stabilizer States
48mQuantum Linear Algebra Using Subspace States
01h 10mQuantum Advantage with Shallow Clifford Circuits
42mQuantum Learning Algorithms Imply Circuit Lower Bounds
01h 09mAre Random Quantum Circuits PRUs?
51mOn constant T-depth circuits
46mQuantum Learning Algorithms Imply Circuit Lower Bounds
15mScalable Equivalence Checking and Verification of Shallow Quantum Circuits