Closing the Quantum-Classical Scaling Gap in Approximate Optimization
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918037308833792 |
|---|---|
| author | Pawlowski, J. Tarasiuk, P. Tuziemski, J. Pawela, L. Gardas, B. |
| author_facet | Pawlowski, J. Tarasiuk, P. Tuziemski, J. Pawela, L. Gardas, B. |
| contents | In a recent study (Ref. [1]), quantum annealing was reported to exhibit a scaling advantage for approximately solving Quadratic Unconstrained Binary Optimization (QUBO). However, this claim critically depends on the choice of classical reference algorithm -- Parallel Tempering with Isoenergetic Cluster Moves (PT-ICM). Here, we reassess these findings with different classical paradigm -- Simulated Bifurcation Machine (SBM) -- that harnesses nonlinear Hamiltonian dynamics. By leveraging chaotic behavior rather than thermal fluctuations, SBM achieves comparable or superior scaling performance, effectively closing the previously reported quantum-classical gap. We show that small problem sizes analyzed in [1] are insufficient for inferring asymptotic scaling, due to sensitivity to runtime and hardware-specific factors. By extending the benchmark to larger instances -- beyond current quantum annealing capabilities -- we establish strong classical scaling behavior. And as a result, we conclude that it is unlikely that current generation of quantum annealers, can demonstrate supremacy in discrete approximate optimization under operationally meaningful conditions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_22514 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Closing the Quantum-Classical Scaling Gap in Approximate Optimization Pawlowski, J. Tarasiuk, P. Tuziemski, J. Pawela, L. Gardas, B. Quantum Physics Computational Physics In a recent study (Ref. [1]), quantum annealing was reported to exhibit a scaling advantage for approximately solving Quadratic Unconstrained Binary Optimization (QUBO). However, this claim critically depends on the choice of classical reference algorithm -- Parallel Tempering with Isoenergetic Cluster Moves (PT-ICM). Here, we reassess these findings with different classical paradigm -- Simulated Bifurcation Machine (SBM) -- that harnesses nonlinear Hamiltonian dynamics. By leveraging chaotic behavior rather than thermal fluctuations, SBM achieves comparable or superior scaling performance, effectively closing the previously reported quantum-classical gap. We show that small problem sizes analyzed in [1] are insufficient for inferring asymptotic scaling, due to sensitivity to runtime and hardware-specific factors. By extending the benchmark to larger instances -- beyond current quantum annealing capabilities -- we establish strong classical scaling behavior. And as a result, we conclude that it is unlikely that current generation of quantum annealers, can demonstrate supremacy in discrete approximate optimization under operationally meaningful conditions. |
| title | Closing the Quantum-Classical Scaling Gap in Approximate Optimization |
| topic | Quantum Physics Computational Physics |
| url | https://arxiv.org/abs/2505.22514 |