Quantum Annealing Algorithms for Estimating Ising Partition Functions

Abstract

Estimating partition functions of Ising spin glasses is a cornerstone of statistical physics and computational science, yet it remains classically challenging due to its $\#$P-hard complexity. While Jarzynski's equality offers a theoretical pathway, its practical application is crippled at low temperatures by rare, divergent statistical fluctuations. Here, we introduce a quantum protocol that overcomes this fundamental limitation by synergizing reverse quantum annealing with optimized nonequilibrium initial distributions. Our method dramatically suppresses the estimator variance, achieving saturation in the low-temperature regime where existing methods fail. Numerical benchmarks on the Sherrington-Kirkpatrick spin glass and the 3-SAT problem demonstrate that our protocol reduces computational scaling exponents by over an order of magnitude (e.g., from $\sim 8.5$ to $\sim 0.5$), despite retaining exponential system-size dependence. Crucially, our protocol circumvents stringent adiabatic constraints, making it feasible for near-term quantum devices like superconducting qubits, trapped ions, and Rydberg atom arrays. This work provides a methodological framework for quantum-enhanced estimation in spin glass thermodynamics and beyond by harnessing non-adiabatic quantum dynamics to address a classically difficult problem.

7+11 pages, 3+3 figures

References in corpus (41)

• Ising formulations of many NP problems
• Noisy intermediate-scale quantum (NISQ) algorithms
• Adiabatic Quantum Computing
• Nonequilibrium fluctuations, fluctuation theorems, and counting statistics in quantum systems
• Colloquium. Quantum Fluctuation Relations: Foundations and Applications
• Determining the density of states for classical statistical models: A random walk algorithm to produce a flat histogram
• Challenges and Opportunities in Quantum Machine Learning
• Perspectives of quantum annealing: Methods and implementations
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Quantum speedup of Monte Carlo methods
• Rare events and the convergence of exponentially averaged work values
• Observation of topological phenomena in a programmable lattice of 1,800 qubits
• Feedback-optimized parallel tempering Monte Carlo
• Quantum critical dynamics in a 5000-qubit programmable spin glass
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• Demonstration of a scaling advantage for a quantum annealer over simulated annealing
• Optimizing the ensemble for equilibration in broad-histogram Monte Carlo simulations
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Performance Limitations of Flat Histogram Methods and Optimality of Wang-Landau Sampling
• Reverse annealing for the fully connected $p$-spin model
• Hiding solutions in random satisfiability problems: A statistical mechanics approach
• Modernizing Quantum Annealing using Local Searches
• A Site-Resolved 2D Quantum Simulator with Hundreds of Trapped Ions
• Dynamics of reverse annealing for the fully-connected $p$-spin model
• Reverse quantum annealing of the $p$-spin model with relaxation
• Quantum Speed-up for Approximating Partition Functions
• A perspective on protein structure prediction using quantum computers
• Programmable Quantum Annealing Architectures with Ising Quantum Wires
• Spectral gap estimates in mean field spin glasses
• Programmable Quantum Annealers as Noisy Gibbs Samplers
• Suppression of work fluctuations by optimal control: An approach based on Jarzynski's equality
• Quantum Sampling Algorithms for Near-Term Devices
• On the Quantum Computational Complexity of the Ising Spin Glass Partition Function and of Knot Invariants
• Benchmarking digital quantum simulations above hundreds of qubits using quantum critical dynamics
• Computing partition functions in the one clean qubit model
• Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions
• Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
• Quantum many-body Jarzynski equality and dissipative noise on a digital quantum computer
• Realization of programmable Ising models in a trapped-ion quantum simulator
• Boltzmann sampling with quantum annealers via fast Stein correction
• Partition Function Estimation: Quantum and Quantum-Inspired Algorithms