Quantum Advantage Without Structure
summary
Proves, relative to a random oracle, an NP search in BQP not BPP by encoding witnesses as codewords whose symbols each pass an oracleed validity test; classical hardness follows from list-recoverable linear code bounds while quantum easiness uses state multiplying quantum states via Fourier-domain convolution plus a decoding step that corrects ~1/2+ε random-symbol errors. Builds non-interactive proofs of quantumness and—assuming Aaronson–Ambainis—certifiable randomness; construction is sound under random-oracle (heuristically SHA-256) instantiation but is not near-term practical due to the costly quantum decoding.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 0:34Defining key terms
- 2:18Types of structure
- 5:59Overview of results
- 12:58Problem construction
- 15:44Classical hardness
- 23:04Quantum easiness
- 30:44Technical implementation
- 37:34Fourier transform details
- 45:22Cryptographic applications
- 50:52Certifiable randomness
- 59:46Practicality and Q&A
related talks
37mQuantum Pseudorandomness and Classical Complexity
59mQuantum cryptography and quantum complexity
21mQuantum versus Randomized Communication Complexity, with Efficient Players
42mQuantum Learning Algorithms Imply Circuit Lower Bounds
01h 31mLightning Talks
45mClassical Verification of Quantum Computational Advantage
13mQbC: Quantum Correctness by Construction
22mQbC: Quantum Correctness by Construction