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 and Kerem Y. Camsari ()
Additional contact information
Shuvro Chowdhury: University of California
Navid Anjum Aadit: University of California
Andrea Grimaldi: University of Messina
Eleonora Raimondo: University of Messina
Atharva Raut: Carnegie Mellon University
P. Aaron Lott: USRA Research Institute for Advanced Computer Science (RIACS)
Johan H. Mentink: Institute for Molecules and Materials
Marek M. Rams: Jagiellonian University
Federico Ricci-Tersenghi: Sapienza Università di Roma, and CNR-Nanotec, Rome unit and INFN
Massimo Chiappini: Istituto Nazionale di Geofisica e Vulcanologia
Luke S. Theogarajan: University of California
Tathagata Srimani: Carnegie Mellon University
Giovanni Finocchio: University of Messina
Masoud Mohseni: Hewlett Packard Labs
Kerem Y. Camsari: University of California

Nature Communications, 2025, vol. 16, issue 1, 1-10

Abstract: 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 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.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.nature.com/articles/s41467-025-64235-y Abstract (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nat:natcom:v:16:y:2025:i:1:d:10.1038_s41467-025-64235-y

Ordering information: This journal article can be ordered from
https://www.nature.com/ncomms/

DOI: 10.1038/s41467-025-64235-y

Access Statistics for this article

Nature Communications is currently edited by Nathalie Le Bot, Enda Bergin and Fiona Gillespie

More articles in Nature Communications from Nature
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().