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

ABSTRACT: Recent demonstrations on specialized benchmarks have reignited excitement for quantum computers, yet their advantage for real-world problems remains an open question. Here, we show that probabilistic computers, co-designed with hardware to implement Monte Carlo algorithms, provide a scalable classical pathway for solving hard optimization problems. We focus on two algorithms applied to three-dimensional spin glasses: discrete-time simulated quantum annealing and adaptive parallel tempering. We benchmark these methods against a leading quantum annealer. For simulated quantum annealing, increasing replicas improves residual energy scaling, consistent with extreme value theory. Adaptive parallel tempering, supported by non-local isoenergetic cluster moves, scales more favorably and outperform

SUBMITTER: Chowdhury S 

PROVIDER: S-EPMC12533262 | biostudies-literature | 2025 Oct

REPOSITORIES: biostudies-literature