Closing the Quantum-Classical Scaling Gap in Approximate Optimization

• URL: http://arxiv.org/abs/2505.22514v1
• Date: Wed, 28 May 2025 16:02:57 GMT
• Title: Closing the Quantum-Classical Scaling Gap in Approximate Optimization
• Authors: J. Pawlowski, P. Tarasiuk, J. Tuziemski, L. Pawela, B. Gardas,
• Abstract summary: We reassess findings with different classical paradigm -- Simulated Bifurcation Machine (SBM)<n>By leveraging chaotic behavior rather than thermal fluctuations, SBM achieves comparable or superior scaling performance.<n>We conclude that it is unlikely that current generation of quantum annealers, can demonstrate supremacy in discrete approximate optimization.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Dynamics of discrete spacetimes with Quantum-enhanced Markov Chain Monte Carlo [0.8192907805418583]
  Causal Set Theory is a discrete, Lorentz-invariant approach to quantum gravity.<n>We introduce a quantum algorithm that investigates the dynamics of causal sets by sampling the space of causal sets.
  arXiv  Detail & Related papers  (2025-06-24T11:47:02Z)
• Challenging the Quantum Advantage Frontier with Large-Scale Classical Simulations of Annealing Dynamics [0.0]
  Recent demonstrations of D-Wave's quantum simulators have established new benchmarks for quantum computational advantage.<n>We demonstrate that time-dependent variational Monte Carlo can efficiently simulate quantum annealing of spin glasses up to system sizes.
  arXiv  Detail & Related papers  (2025-03-11T10:09:37Z)
• Quantum Annealing with chaotic driver Hamiltonians [0.0]
  We investigate driver Hamiltonians based on a bosonic spin version of the Sachdev-Ye-Kitaev (SYK) model. We find that a considerable proportion of SYK model instances demonstrate significant speedups.
  arXiv  Detail & Related papers  (2024-09-30T17:39:54Z)
• Spectral chaos bounds from scaling theory of maximally efficient quantum-dynamical scrambling [44.99833362998488]
  A key conjecture about the evolution of complex quantum systems towards an ergodic steady state, known as scrambling, is that this process acquires universal features when it is most efficient.<n>We develop a single- parameter scaling theory for the spectral statistics in this scenario, which embodies exact self-similarity of the spectral correlations along the complete scrambling dynamics.<n>We establish that scaling predictions are matched by a privileged process and serve as bounds for other dynamical scrambling scenarios, allowing one to quantify inefficient or incomplete scrambling on all time scales.
  arXiv  Detail & Related papers  (2023-10-17T15:41:50Z)
• Effectiveness of quantum annealing for continuous-variable optimization [0.0]
  We test the performance of quantum annealing applied to a one-dimensional continuous-variable function with a rugged energy landscape. We conclude that the hardware realization of quantum annealing has the potential to significantly outperform the best classical algorithms.
  arXiv  Detail & Related papers  (2023-05-11T07:59:19Z)
• Universality of critical dynamics with finite entanglement [68.8204255655161]
  We study how low-energy dynamics of quantum systems near criticality are modified by finite entanglement. Our result establishes the precise role played by entanglement in time-dependent critical phenomena.
  arXiv  Detail & Related papers  (2023-01-23T19:23:54Z)
• Quantum and classical annealing in a continuous space with multiple local minima [0.0]
  We show that quantum annealing yields a power law convergence, thus an exponential improvement over simulated annealing. We also reveal how diabatic quantum dynamics, quantum tunneling in particular, steers the systems toward the global minimum.
  arXiv  Detail & Related papers  (2022-03-22T02:02:23Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm [59.99439951055238]
  We show how (discrete-time) Lyapunov stability theory can serve as a powerful tool to aid, or even lead, in the analysis (and potential design) of optimization algorithms that are not necessarily gradient-based. The particular ML problem that this paper focuses on is that of parameter estimation in an incomplete-data Bayesian framework via the popular optimization algorithm known as maximum a posteriori expectation-maximization (MAP-EM) We show that fast convergence (linear or quadratic) is achieved, which could have been difficult to unveil without our adopted S&C approach.
  arXiv  Detail & Related papers  (2020-06-23T01:34:18Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.