Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers
Shuvro Chowdhury, Navid Anjum Aadit, Andrea Grimaldi, Eleonora Raimondo, Atharva Raut, P. Aaron Lott, Johan H. Mentink, Marek M. Rams, Federico Ricci-Tersenghi, Massimo Chiappini, Luke S. Theogarajan, Tathagata Srimani, Giovanni Finocchio, Masoud Mohseni, Kerem Y. Camsari · 2025
Read Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers by Shuvro Chowdhury, Navid Anjum Aadit, Andrea Grimaldi, Eleonora Raimondo, Atharva Raut, P. Aaron Lott, Johan H. Mentink, Marek M. Rams, Federico Ricci-Tersenghi, Massimo Chiappini, Luke S. Theogarajan, Tathagata Srimani, Giovanni Finocchio, Masoud Mohseni, Kerem Y. Camsari (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-10302.txt.
Introduction
Shuvro Chowdhury and co-authors set a tougher classical bar for quantum advantage in hard optimization, in a 2025 paper. Their machines, called probabilistic computers, run Monte Carlo search directly in hardware tuned for the task. The testbed is three-dimensional spin glasses, a classic hard problem, and the rival is a leading quantum annealer working the same instances.
Two algorithms are compared. One mimics quantum annealing in steps and improves as more copies run, as theory predicts. The other, adaptive parallel tempering with special cluster moves, scales better still and wins overall. The authors project that custom chips could speed these methods by orders of magnitude while using far less energy, reframing what quantum machines must beat.
Catalog record
| CREATOR | Shuvro Chowdhury, Navid Anjum Aadit, Andrea Grimaldi, Eleonora Raimondo, Atharva Raut, P. Aaron Lott, Johan H. Mentink, Marek M. Rams, Federico Ricci-Tersenghi, Massimo Chiappini, Luke S. Theogarajan, Tathagata Srimani, Giovanni Finocchio, Masoud Mohseni, Kerem Y. Camsari |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 96 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-10302
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers Shuvro Chowdhury, Navid Anjum Aadit, Andrea Grimaldi, Eleonora Raimondo, Atharva Raut, P. Aaron Lott, Johan H. Mentink, Marek M. Rams, Federico Ricci-Tersenghi, Massimo Chiappini, Luke S. Theogarajan, Tathagata Srimani, Giovanni Finocchio, Masoud Mohseni, Kerem Y. Camsari 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. I Introduction Richard Feynman is widely credited with starting the field of quantum computing in a 1982 lecture [ 1 ] . In the same lecture, Feynman also introduced the notion of a probabilistic computer, one that naturally simulates probabilistic processes. Feynman’s broader vision of physical computers , or programmable physical devices that solve a problem of interest through their natural evolution, has recently inspired a growing array of physical and physics-inspired classical computing paradigms, including systems to train deep neural networks [ 2 ] , solve linear algebra problems [ 3 ] , and tackle combinatorial optimization problems [ 4 ] . Building on this vision, a key challenge is identifying scenarios where scalable and error-corrected quantum computers [ 5 ] could outperform probabilistic or classical approaches, particularly in optimization and sampling tasks. Prominent examples include Shor’s algorithm for factoring large integers [ 6 ] , sampling random quantum circuits [ 7 ] , and learning quantum data on quantum processors [ 8 , 9 ] , each offering potential exponential speedups over all known probabilistic alternatives, typically due to the interference of probability amplitudes in a high-dimensional Hilbert space. However, the scaling challenges and quantum error correction overhead might diminish or eliminate such quantum advantages [ 5 ] . Notably, while probabilistic computers can emulate quantum interference with polynomial resources, their convergence is in general believed to require exponential time [ 10 ] . This challenge is known as the sign-problem in Monte Carlo algorithms [ 11 ] . Fig. 1 : Schematic overview of the probabilistic algorithms and technological platforms: (a) Representation of a 3D Ising spin glass, where the weights connecting spins can be +1 (ferromagnetic, red) or -1 (antiferromagnetic, blue). Many real-world hard optimization problems can be mapped onto such spin-glass systems. (b, c) Two replica-based algorithms investigated in this work: discrete-time simulated quantum annealing (DT-SQA), in (b), and adaptive parallel tempering (APT) with isoenergetic cluster moves (ICM), in (c). In SQA, replicas are interconnected, and the strength of these interconnections is annealed according to a schedule. APT uses multiple replicas of the problem, each running at different temperatures, and periodically exchanges states between replicas to escape local minima. (d) The p-computing scheme, where a general-purpose CPU interfaces with a specialized probabilistic computer to efficiently implement Monte Carlo algorithms. Various implementations of probabilistic computers are shown, including CPU [ 12 , 4 ] , GPU [ 13 , 14 , 15 , 16 , 17 ] , Field Programmable Gate Arrays (FPGA) [ 4 , 18 , 19 , 20 , 21 , 22 ] , interconnected FPGAs, and monolithic CMOS + sMTJ (stochastic magnetic tunnel junction) chips [ 23 , 24 , 25 , 26 ] . Each platform offers trade-offs in sampling throughput, energy efficiency, problem size, and technological complexity. On the other hand, establishing a quantum advantage becomes much harder in cases where quantum fluctuations or quantum interference may be present, but not known to play a significant role. For example, even though quantum annealers by D-Wave operate on the transverse field Ising Hamiltonian, which does not suffer from the sign problem, empirical performance advantages have been sought to be demonstrated over the years [ 27 , 28 , 29 , 30 ] . In a similar attempt, Bernaschi et al. [ 31 ] clarified that for a 2D quantum spin glass, quantum annealing could still provide a speedup in entering the spin-glass phase under certain conditions. However, it is unclear whether these advantages extend to solving optimization problems and represent a fundamental improvement over classical algorithms, such as simulated quantum annealing (SQA) and adaptive parallel tempering (APT), or if they are primarily due to hardware acceleration. Speedups of this second type are also a feature of dedicated probabilistic computers when the hardware architecture is tailored for probabilistic algorithms [ 12 ] . Recently, King et al. [ 32 ] demonstrated another empirical scaling advantage over continuous-time simulated quantum annealing (CT-SQA) and simulated annealing (SA) in solving classical 3D cubic Ising spin glass problems (Fig. 1 (a)). Due to their hardness, 3D spin glasses have long served as canonical benchmarks for evaluating scaling behavior of various algorithms [ 33 , 34 , 35 ] . The performance reported in Ref. [ 32 ] provides a timely and valuable benchmark for the field. In this work, we use this benchmark to evaluate a powerful classical alternative: probabilistic computers co-designed with domain-specific hardware. While the quantum critical dynamics observed in that study are a significant physical finding, it is crucial to assess whether the resulting optimization performance is competitive with the most advanced classical techniques. Our study addresses this by demonstrating that p-computers, implementing state-of-the-art replica-based Monte Carlo algorithms (Fig. 1 (b, c)), can achieve a comparable, and in some cases more favorable, performance scaling on the same 3D spin glass problems. Specifically, we investigate discrete-time simulated quantum annealing (DT-SQA) and adaptive parallel tempering (APT) on various p-computer realizations (Fig. 1 (d)). Our hybrid computing platform combines a general-purpose computer with a p-computer specializing in fast Monte Carlo sampling (Fig. 1 (d)). p-computers have been implemented in CPUs [ 12 , 4 ] , GPUs [ 13 , 14 , 15 , 16 , 17 ] , Field Programmable Gate Arrays (FPGAs) [ 4 , 18 , 19 , 20 , 21 , 22 ] , and interconnected FPGAs. Specialized accelerators using single and distributed FPGAs already provide orders of magnitude performance improvements over CPUs [ 4 ] . Although small-scale p-computers using CMOS + stochastic magnetic tunnel junction technology (sMTJ) have been developed [ 23 ] , monolithically integrated CMOS + sMTJ chips hold the greatest promise in terms of energy