The Quantum Supremacy Tsirelson Inequality
summary
Proves a query lower bound for linear cross-entropy benchmarking: any polynomial-time quantum algorithm needs about 2^{n/4} queries to beat the trivial quantum score, while an algorithm using the quantum collision-finding trick achieves roughly 2^{n/3} queries and slightly improves the ideal quantum score (~2/2^n). Key tools: equivalence between a random-unitary oracle and a canonical state-preparation oracle, a 2014 simulation that replaces T queries by ~T^2 copies of the state, and a birthday-paradox collision argument.
AI-written summary · about
chapters (6)
- 0:00Bell inequality context
- 2:57Quantum supremacy task
- 5:43Defining the problem
- 8:18Why this problem is hard
- 10:32Key theoretical insights
- 17:13Conclusion and open problems
related talks
01h 08mPutting Quantum Supremacy on a Rigorous Footing
48mStatistics In Quantum Computational Supremacy
01h 09mRecent Progress in Quantum Advantage
29mParallel Repetition for Entangled Games via Fast Quantum Search
20mUnitary property testing lower bounds by polynomials
42mTests for "Quantumness"
42mQuantum Learning Algorithms Imply Circuit Lower Bounds
31mDemonstrating an Unconditional Separation Between Quantum and Classical Information Resources