Symmetries, Graph Properties, and Quantum Speedups
summary
Shows three concrete claims: graphs described by an adjacency matrix admit at most a 6th power bound (more generally a 3K power for K‑uniform hypergraph properties) between randomized and quantum bounded‑error query complexity; permutation groups with large base size (primitive groups) force at most polynomial quantum speedups; yet in the adjacency list model there is an explicit welded trees–based graph property testing construction that quantum walks solve in polynomial time while any randomized algorithm provably needs exponential queries.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 1:33Power of Quantum Computers
- 3:09Query Complexity
- 5:04Promise Problems
- 11:29Symmetries
- 13:24Graph Properties
- 15:11Property Testing
- 19:14Summary
- 32:58Quantum Advice
- 34:12Classical Tests
- 35:57Open Questions
- 38:09Query Complexity Separation
- 38:52Uniform Hyper graphs
related talks
31mLimits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity v
01h 10mQuantum Advantage with Shallow Clifford Circuits
44mQuantum Complexity of Clique Homology
24mQuantum Distributed Algorithms for Detection of Cliques
15mClassical algorithms and quantum limitations for maximum cut on high-girth graphs
22mQuantum algorithms and the power of forgetting
56mAn Overview of Quantum Algorithms
34mA NASA Perspective on Quantum Computing, with Emphasis on Recent Results in Distributed Computing