Certifying almost all quantum states with few single-qubit measurements
Talkat Near-Term Quantum Computers: Fault Tolerance + Benchmarking + Quantum Advantage + Quantum Algorithms · 2024-04-22..04-26·
summary
Claims that almost all n‑qubit target states (including ones with exponential circuit complexity) are certifiable with O(n^2) single‑qubit measurements, proven by relating certification to the mixing time of a random walk on the measurement outcome hypercube. The actual protocol: fix local single‑qubit bases, on each copy measure all qubits in that basis except one qubit measured in a random Pauli, compute the post‑measurement one‑qubit overlap (the shadow overlap) and average. Demonstrations run to 120 qubits and show advantages over XEB; applications: benchmarking, circuit optimization, and certifying ML/tensor‑network state models.
AI-written summary · about
chapters (12)
- 0:00Quantum state certification intro
- 1:05Why certification matters
- 3:58Existing methods' limits
- 8:12Challenges in protocols
- 10:18Talk outline
- 11:01Theorem: certifying almost all states
- 13:31Theorem: certifying specific states
- 22:31New certification protocol
- 28:22Benchmarking quantum devices
- 33:59Training neural quantum states
- 38:55Optimizing quantum circuits
- 43:07Conclusion and open questions
related talks
55mFew Single-Qubit Measurements Suffice to Certify Any Quantum State
33mLightning Talks
45mClassical Verification of Quantum Computational Advantage
28mThe Problem with Qubits
42mTests for "Quantumness"
01h 00mQuantum Physics for Software Developers
44mQuantum Meets Minimum Circuit Size Problem
01h 09mRecent Progress in Quantum Advantage