Quantum Algorithms for Approximating Partition Functions
summary
Presents a concrete, implementable route to speed up classical MCMC partition‑function estimation: convert reversible Markov chains to a unitary via Szegedy quantum walk, use a new non-destructive phase estimation (random phase + rewind) to get unbiased low‑variance expectation estimates while restoring a single coherent Gibbs copy, and stitch ratios with a cooling schedule. Claim: overall quantum time is the product of a logarithmic factor in |Ω| and a quadratic speedup over the classical MCMC cost; yields polynomial quantum speedups for problems like degree ≤5 independent‑set counting.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 0:34Classical Hamiltonian
- 1:45Why Partition Function
- 2:29Goals
- 4:00Physics
- 8:09Main result
- 10:28Timeline
- 12:26Partition Function
- 18:51Global Dynamics
- 21:16Population Functions
- 32:16Quantum Algorithm
- 49:47Open Questions
related talks
13mQuantum Algorithms for the Mean Estimation Problem
36mA Combinatorial Approach to Complexity Transitions in Quantum Physics
31mLimits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity v
01h 07mClassical algorithms for quantum Gibbs states
56mAn Overview of Quantum Algorithms
43mEfficient Quantum Algorithm for Heisenberg Spin Systems
37m(Sub)Exponential Advantage of Adiabatic Quantum Computation With No Sign Problem
18mSAQR-QC: A Logic for Scalable but Approximate Quantitative Reasoning about Quantum(…)