Continuous-time quantum walks for MAX-CUT are hot
Talkat Near-Term Quantum Computers: Fault Tolerance + Benchmarking + Quantum Advantage + Quantum Algorithms · 2024-04-22..04-26·
summary
Heuristic framework ties time-independent Hamiltonians to thermalisation and gives explicit, analytic predictions for continuous-time quantum walks solving MAX-CUT: short-time behavior follows a two-level oscillation until torsion t^-1/4; long-time observables match a Gibbs state set by conserved energy so temperature satisfies beta < 1 (high T). Density of states comes from low moments (edges, number of triangles) and is fit by an exponentially modified Gaussian; numerical tests on ~100 random 12‑node graphs show good agreement but only moderate approximation ratios (~0.5), not ground-state success.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:48What are quantum walks
- 6:34Quantum walks as search
- 8:52MAX-CUT problem and mapping
- 12:52Short-time behavior
- 18:39Long-time behavior
- 23:19Gibbs state model
- 25:52Partition function
- 28:40High-temperature prediction
- 31:56Summary
- 34:53Q&A
related talks
01h 08mFast mixing of all-to-all quantum systems at high temperatures
56mRapid quantum ground state preparation via dissipative dynamics
01h 06mQuantum Algorithms for Approximating Partition Functions
44mOptimal Learning of Quantum Hamiltonians From High-Temperature Gibbs States
01h 06mHow Hamiltonian complexity differs from quantum chemistry
46mLocal Minima in Quantum Systems
43mEfficient Quantum Algorithm for Heisenberg Spin Systems
38mQuantum Computational Advantage With Constant-Temperature Gibbs Sampling