Pushing the boundary of quantum advantage in hard combinatorial optimization with probabilistic computers.

Area of Science:

• Computational physics
• Quantum computing
• Optimization algorithms

Background:

• Quantum computing shows promise but lacks real-world advantage.
• Classical methods are needed to solve complex optimization problems.

Purpose of the Study:

• To present probabilistic computers as a scalable classical solution for optimization.
• To benchmark classical algorithms against quantum annealers.

Main Methods:

• Co-designing probabilistic computers with hardware for Monte Carlo algorithms.
• Implementing discrete-time simulated quantum annealing and adaptive parallel tempering.
• Benchmarking against a leading quantum annealer for 3D spin glasses.

Main Results:

• Simulated quantum annealing shows improved scaling with increasing replicas.
• Adaptive parallel tempering scales favorably and outperforms simulated quantum annealing.
• Field-Programmable Gate Arrays (FPGAs) and specialized chips accelerate algorithms and improve energy efficiency.

Conclusions:

• Probabilistic computers provide a scalable classical pathway for hard optimization problems.
• Rigorous classical baselines are established for assessing practical quantum advantage.
• Adaptive parallel tempering is a promising algorithm for real-world optimization challenges.