Classical Verification of Quantum Computational Advantage
summary
A concrete interactive protocol shows a classical verifier can certify quantum advantage by having the prover commit to a TCF superposition, condensing the two preimages into a single qubit via a random inner product and then running a one-player CHSH condensation measurement; this removes the need for an adaptive hard‑core bit and works under standard TCFs (X^2 mod N, LWE, DDH). Experiments use trapped‑ion partial measurements, the raw fidelity threshold is ~83% but post‑selection redundancy pushes it toward ~1%, and a 1024‑bit Karatsuba X^2 mod N circuit costs ~10^6 Toffoli.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 1:50Blackbox Proofs
- 5:00Two Broad Paths
- 6:30Sampling Problems
- 8:48Interactive Proof
- 12:06Original Protocol
- 20:30Partial Measurements
- 21:49PostSelection
- 23:54TCF
- 25:30Garbage Bits
- 28:47Paths Forward
- 34:52Cost Function
- 37:17Space Complexity
- 38:44Q A
related talks
01h 09mRecent Progress in Quantum Advantage
32mBeating Classical Impossibility of Position Verification
16mQuantum Information Meets Cryptography
42mTests for "Quantumness"
22mEfficient Formal Verification of Quantum Error Correcting Programs
29mEfficiently Verifying Quantum Programs with Few T Gates
32mCan We Get Verifiable Quantum Advantage from Forrelation
01h 10mQuantum Advantage with Shallow Clifford Circuits