Pushing the boundary of quantum advantage in hard combinatorial optimization with probabilistic computers
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 outperforms simulated quantum annealing. Field Programmable Gate Arrays or specialized chips can implement these algorithms in modern hardware, leveraging massive parallelism to accelerate them while improving energy efficiency. Our results establish a rigorous classical baseline for assessing practical quantum advantage and present probabilistic computers as a scalable platform for real-world optimization challenges.
Authors
- Kerem Y. Çamsarı (ORCID: https://orcid.org/0000-0002-6876-8812)
- Tathagata Srimani (ORCID: https://orcid.org/0000-0002-1238-7324)
- Giovanni Finocchio (ORCID: https://orcid.org/0000-0002-1043-3876)
- Eleonora Raimondo (ORCID: https://orcid.org/0000-0002-6512-988X)
- Navid Anjum Aadit (ORCID: https://orcid.org/0000-0001-9933-0728)
- Luke Theogarajan (ORCID: https://orcid.org/0000-0002-0320-5023)
- Marek M. Rams (ORCID: https://orcid.org/0000-0002-1235-7758)
- Johan H. Mentink (ORCID: https://orcid.org/0000-0002-4082-1984)
- Federico Ricci‐Tersenghi (ORCID: https://orcid.org/0000-0003-4970-7376)
- Shuvro Chowdhury (ORCID: https://orcid.org/0000-0002-6325-0790)
- Masoud Mohseni (ORCID: https://orcid.org/0000-0003-4065-9400)
- M. Chiappini (ORCID: https://orcid.org/0000-0001-7433-9435)
- Andrea Grimaldi (ORCID: https://orcid.org/0000-0002-8052-0764)
- P. Aaron Lott (ORCID: https://orcid.org/0000-0002-9718-9641)
- Atharva Raut (ORCID: https://orcid.org/0009-0006-0047-1090)
Institutions
- University of Messina (IT)
- Jagiellonian University (PL)
- Ames Research Center (US)
- Hewlett-Packard (United States) (US)
- Research Institute for Advanced Computer Science (US)
- Radboud University Nijmegen (NL)
- University of California, Santa Barbara (US)
- Istituto Nazionale di Geofisica e Vulcanologia (IT)
- Istituto Nazionale di Fisica Nucleare, Sezione di Roma I (IT)
- Polytechnic University of Bari (IT)
- Carnegie Mellon University (US)
Publication Details
- Journal
- Nature Communications
- Published
- 2025-10-16
- DOI
- https://doi.org/10.1038/s41467-025-64235-y
- Primary Topic
- Quantum Computing Algorithms and Architecture
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Science Foundation
- Semiconductor Research Corporation
- National Aeronautics and Space Administration
- Carnegie Mellon University
- European Commission
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek
- China Scholarship Council
- University of California, Santa Barbara
- Materials Research Science and Engineering Center, Harvard University
- Multidisciplinary University Research Initiative
- HORIZON EUROPE Framework Programme
- Office of Naval Research
- Division of Materials Research
- California NanoSystems Institute
- Army Research Laboratory