Verifiable quantum advantage: old and new ideas
summary
Proposal: prepare an n-qubit phase state from a degree-3 polynomial made of disjoint k-bit blocks, hide the product structure by applying a random affine orthogonal change of variables A, send the resulting n^3-bit coefficient list to the device and have it estimate the sign of the forrelation. Implementation cost is roughly n cubed gates and n^2 depth (n qubits); for n≈200 that’s millions of gates. Bravyi shows a classical algorithm computes φ^2 in polytime for degree‑3, so magnitude is easy but the sign and inversion of A remain unresolved and tie to hard multivariate systems / PRG-style assumptions.
AI-written summary · about
chapters (13)
- 0:00Introduction to advantages
- 2:18History of quantum advantage
- 6:54Recent factoring developments
- 10:46Q&A on factoring developments
- 12:32Forrelation-based approach
- 17:36Self-forrelation and polynomials
- 22:48Constructing the test
- 28:02Classical simulation method
- 34:41Classical vs quantum limits
- 37:24Sign-based quantum test
- 41:46Deobfuscation security
- 47:11Security analysis and Q&A
- 58:55Final remarks and discussion
related talks
32mCan We Get Verifiable Quantum Advantage from Forrelation
01h 09mRecent Progress in Quantum Advantage
45mClassical Verification of Quantum Computational Advantage
51mOn constant T-depth circuits
52mThe Virtues of the Quantum Approximate Optimization Algorithm
28mConcentration bounds for quantum states and limitations on the QAOA from polynomial approximations
01h 08mPutting Quantum Supremacy on a Rigorous Footing
01h 02mQuantum Computing Concepts