Can We Get Verifiable Quantum Advantage from Forrelation
summary
Proposes using Forrelation instantiated with degree-3 polynomials and self-dual bent functions so the quantum circuit prepares an f-phase state and a quantum device estimates the Hadamard expectation (the forrelator) efficiently while classical algorithms need ~2^{n/2} queries; a concrete resource estimate is ~8 million Toffoli gates for n≈200 and depths in the 1,000s. Adds an obfuscation-like step: pick a random Clifford from the stabilizer subgroup (size ~660 million for 6 qubits), compile to a canonical form, and rely on reductions to group membership (linked to factoring and discrete log) for classical hardness.
AI-written summary · about
chapters (6)
- 0:00Introduction
- 2:37Verifiable advantage criteria
- 9:51Forrelation problem
- 15:41Verification challenges
- 22:29Obfuscating stabilizers
- 29:40Classical hardness & future
related talks
01h 05mVerifiable quantum advantage: old and new ideas
58mSeparating Quantum from Classical with k-fold Forrelation and Friends
45mClassical Verification of Quantum Computational Advantage
21mQuantum versus Randomized Communication Complexity, with Efficient Players
01h 09mRecent Progress in Quantum Advantage
01h 10mQuantum Advantage with Shallow Clifford Circuits
51mOn constant T-depth circuits
59mQuantum cryptography and quantum complexity