Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians
arXiv:2408.01516 · doi:10.22331/q-2026-01-22-1981
Abstract
Sampling from Gibbs states -- states corresponding to system in thermal equilibrium -- has recently been shown to be a task for which quantum computers are expected to achieve super-polynomial speed-up compared to classical computers, provided the locality of the Hamiltonian increases with the system size (Bergamaschi et al., arXiv: 2404.14639). We extend these results to show that this quantum advantage still occurs for Gibbs states of Hamiltonians with O(1)-local interactions at constant temperature by showing classical hardness-of-sampling and demonstrating such Gibbs states can be prepared efficiently using a quantum computer. In particular, we show hardness-of-sampling is maintained even for 5-local Hamiltonians on a 3D lattice. We additionally show that the hardness-of-sampling is robust when we are only able to make imperfect measurements.
14 pages, 6 page appendix, 1 figure
References in corpus (41)
- Characterizing Quantum Supremacy in Near-Term Devices
- Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
- Quantum Metropolis Sampling
- Average-case complexity versus approximate simulation of commuting quantum computations
- Achieving quantum supremacy with sparse and noisy commuting quantum computations
- Instantaneous Quantum Computation
- Computational advantage of quantum random sampling
- Sample-efficient learning of quantum many-body systems
- Algorithms for quantum simulation at finite energies
- Completely positive master equation for arbitrary driving and small level spacing
- Anticoncentration theorems for schemes showing a quantum speedup
- Sample complexity of device-independently certified "quantum supremacy"
- Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems
- On the complexity of quantum partition functions
- Quantum many-body systems in thermal equilibrium
- Probing finite-temperature observables in quantum simulators of spin systems with short-time dynamics
- Entanglement Theory and the Quantum Simulation of Many-Body Physics
- Szegedy Walk Unitaries for Quantum Maps
- Learning quantum many-body systems from a few copies
- Quantum Thermal State Preparation
- Local minima in quantum systems
- Estimation of Hamiltonian parameters from thermal states
- Preparing thermal states on noiseless and noisy programmable quantum processors
- Making Classical Ground State Spin Computing Fault-Tolerant
- An efficient and exact noncommutative quantum Gibbs sampler
- Quantum computational advantage with constant-temperature Gibbs sampling
- Robust Extraction of Thermal Observables from State Sampling and Real-Time Dynamics on Quantum Computers
- Fast Thermalization from the Eigenstate Thermalization Hypothesis
- Quantum algorithm for estimating volumes of convex bodies
- Efficient Algorithms for Approximating Quantum Partition Functions at Low Temperature
- Dissipative Quantum Gibbs Sampling
- Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
- Fault-tolerant compiling of classically hard IQP circuits on hypercubes
- Quantum generalizations of Glauber and Metropolis dynamics
- Low-Depth Quantum Metropolis Algorithm
- Secret extraction attacks against obfuscated IQP circuits
- Polynomial-time classical sampling of high-temperature quantum Gibbs states
- Quantum Metropolis Sampling via Weak Measurement
- Rapid Mixing of Quantum Gibbs Samplers for Weakly-Interacting Quantum Systems
- Optimizing random local Hamiltonians by dissipation
- Slow Mixing of Quantum Gibbs Samplers