Quantum algorithms and the power of forgetting
summary
Main claim: no polynomial-query genuine rooted quantum algorithm finds an entrance→exit path in the three-colored welded-tree oracle. Proof builds an address tree to classically simulate any such quantum procedure with only polynomial overhead, then applies a classical hardness bound (extended Childs et al. welded-tree results) using color-preserving permutations and combinatorics of weld vertices. Consequence: any efficient quantum algorithm must either use vertex labels critically or forget the entrance and later rediscover it; non-rooted algorithms remain open.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:16Quantum algorithms and the power of forgetting
- 1:55Welded Tree graph
- 3:30Welded Tree oracle
- 5:05Welded Tree EXIT-finding and the power of forgetting
- 6:41Welded Tree path-finding
- 8:36Genuine Algorithms
- 10:55Structure of the proof
- 11:42Addresses
- 12:17Address Tree
- 14:48Classical simulation of genuine rooted algorithms
- 16:48Classical simulation of genuine rooted quantum algorithms
- 18:25Classical hardness of finding the EXIT or a cycle
- 19:18Color-preserving permutations.
- 20:41Conclusion
- 21:09Open questions
- 21:54References
related talks
01h 10mQuantum Advantage with Shallow Clifford Circuits
01h 06mQuantum Advantage Without Structure
46mSymmetries, Graph Properties, and Quantum Speedups
01h 36mAlgorithms for Algebraic Lattices: Classical and Quantum
31mLimits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity v
42mQuantum Learning Algorithms Imply Circuit Lower Bounds
30mHow to fault-tolerantly realize any quantum circuit with local operations
01h 01mWhat Is "Quantum" About Quantum Computing?