Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909849922568192 |
|---|---|
| author | Chowdhury, Shuvro Aadit, Navid Anjum Grimaldi, Andrea Raimondo, Eleonora Raut, Atharva Lott, P. Aaron Mentink, Johan H. Rams, Marek M. Ricci-Tersenghi, Federico Chiappini, Massimo Theogarajan, Luke S. Srimani, Tathagata Finocchio, Giovanni Mohseni, Masoud Camsari, Kerem Y. |
| author_facet | Chowdhury, Shuvro Aadit, Navid Anjum Grimaldi, Andrea Raimondo, Eleonora Raut, Atharva Lott, P. Aaron Mentink, Johan H. Rams, Marek M. Ricci-Tersenghi, Federico Chiappini, Massimo Theogarajan, Luke S. Srimani, Tathagata Finocchio, Giovanni Mohseni, Masoud Camsari, Kerem Y. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_10302 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers Chowdhury, Shuvro Aadit, Navid Anjum Grimaldi, Andrea Raimondo, Eleonora Raut, Atharva Lott, P. Aaron Mentink, Johan H. Rams, Marek M. Ricci-Tersenghi, Federico Chiappini, Massimo Theogarajan, Luke S. Srimani, Tathagata Finocchio, Giovanni Mohseni, Masoud Camsari, Kerem Y. Quantum Physics Disordered Systems and Neural Networks Emerging Technologies 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. |
| title | Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers |
| topic | Quantum Physics Disordered Systems and Neural Networks Emerging Technologies |
| url | https://arxiv.org/abs/2503.10302 |