(Sub)Exponential Advantage of Adiabatic Quantum Computation With No Sign Problem
summary
Constructs sparse, sign-problem-free Hamiltonians (adjacency matrices of large graphs) with a straight linear interpolation and inverse-polynomial spectral gap so adiabatic evolution finds an exit vertex efficiently in polynomial time. The graph uses cluster obfuscation with random matchings, uniform-degree expanders to gap out non-symmetric modes, and fractal-shaped decoration trees that shift L1 mass and foil diffusion/Monte Carlo. Result is an oracle separation: any classical randomized algorithm needs roughly 2^{n^{1/5}} queries to the sparse-Hamiltonian oracle, while the quantum adiabatic procedure succeeds.
AI-written summary · about
chapters (7)
- 0:00Start
- 4:23The underlying adiabatic path ( = poly(n))
- 6:54Step 1: obfuscation ENTRANCE
- 13:11Step 1: obfuscation (tricking path integral Monte Carlo) EXIT
- 19:23Step 2b: fractal decoration tricking every classic all attached trees have the same depth d, we can effectively filter the
- 25:48Outlook and open questions
- 30:19Step 2a: decoration tricking diffusion Monte Car
related talks
43mEfficient Quantum Algorithm for Heisenberg Spin Systems
01h 36mAlgorithms for Algebraic Lattices: Classical and Quantum
36mA Combinatorial Approach to Complexity Transitions in Quantum Physics
27mA Haskell Adiabatic DSL: Solving Classical Optimization Problems on Quantum Hardware
01h 10mQuantum Advantage with Shallow Clifford Circuits
01h 09mRecent Progress in Quantum Advantage
28mConcentration bounds for quantum states and limitations on the QAOA from polynomial approximations
01h 05mVerifiable quantum advantage: old and new ideas