Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers
arXiv:2503.10302 · doi:10.1038/s41467-025-64235-y
Abstract
Recent demonstrations on specialized benchmarks have reignited excitement for quantum computers, yet whether they can deliver an advantage for practical real-world problems remains an open question. Here, we show that probabilistic computers (p-computers), when co-designed with hardware to implement powerful Monte Carlo algorithms, provide a compelling and scalable classical pathway for solving hard optimization problems. We focus on two key algorithms applied to 3D spin glasses: discrete-time simulated quantum annealing (DT-SQA) and adaptive parallel tempering (APT). We benchmark these methods against the performance of a leading quantum annealer on the same problem instances. For DT-SQA, we find that increasing the number of replicas improves residual energy scaling, in line with expectations from extreme value theory. We then show that APT, when supported by non-local isoenergetic cluster moves, exhibits a more favorable scaling and ultimately outperforms DT-SQA. We demonstrate these algorithms are readily implementable in modern hardware, projecting that custom Field Programmable Gate Arrays (FPGA) or specialized chips can leverage massive parallelism to accelerate these algorithms by orders of magnitude while drastically improving energy efficiency. Our results establish a new, rigorous classical baseline, clarifying the landscape for assessing a practical quantum advantage and presenting p-computers as a scalable platform for real-world optimization challenges.
Codes are openly available at https://github.com/OPUSLab/3DSpinGlassWithPbits.git
References in corpus (35)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantum principal component analysis
- Parallel Tempering: Theory, Applications, and New Perspectives
- Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations
- Deep physical neural networks enabled by a backpropagation algorithm for arbitrary physical systems
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum advantage in learning from experiments
- Feedback-optimized parallel tempering Monte Carlo
- Quantum critical dynamics in a 5000-qubit programmable spin glass
- Massively Parallel Probabilistic Computing with Sparse Ising Machines
- Quantum versus Classical Annealing of Ising Spin Glasses
- Probing for quantum speedup in spin glass problems with planted solutions
- Optimized simulated annealing for Ising spin glasses
- Scaling advantage in quantum simulation of geometrically frustrated magnets
- A Cluster Monte Carlo Algorithm for 2-Dimensional Spin Glasses
- Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
- Multi-GPU Accelerated Multi-Spin Monte Carlo Simulations of the 2D Ising Model
- CMOS + stochastic nanomagnets: heterogeneous computers for probabilistic inference and learning
- Autonomous Probabilistic Coprocessing with Petaflips per Second
- Janus II: a new generation application-driven computer for spin-system simulations
- Training Deep Boltzmann Networks with Sparse Ising Machines
- Scalable Emulation of Sign-ProblemFree Hamiltonians with Room Temperature p-bits
- From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
- Spintronics-compatible approach to solving maximum satisfiability problems with probabilistic computing, invertible logic and parallel tempering
- The Quantum Transition of the Two-Dimensional Ising Spin Glass: A Tale of Two Gaps
- Accelerated Quantum Monte Carlo with Probabilistic Computers
- All-to-all reconfigurability with sparse and higher-order Ising machines
- Dynamic Variational Study of Chaos: Spin Glasses in Three Dimensions
- Parallel Tempering Simulation of the three-dimensional Edwards-Anderson Model with Compact Asynchronous Multispin Coding on GPU
- Quantum-Assisted Genetic Algorithm
- Physics-inspired Ising Computing with Ring Oscillator Activated p-bits
- Noise-augmented Chaotic Ising Machines for Combinatorial Optimization and Sampling
- Emulating Quantum Interference with Generalized Ising Machines
- How to Build a Quantum Supercomputer: Scaling from Hundreds to Millions of Qubits
- GPU-accelerated simulated annealing based on p-bits with real-world device-variability modeling