Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Evidence for a Limited Quantum Speedup on a Quantum Annealer

Tameem Albash, Daniel A. Lidar

Published May 21, 2017• 6 citations
OpenAlex

Abstract

The observation of an unequivocal quantum speedup remains an elusive objective for quantum computing. The D-Wave quantum annealing processors have been at the forefront of experimental attempts to address this goal, given their relatively large numbers of qubits and programmability. A complete determination of the optimal time-to-solution (TTS) using these processors has not been possible to date, preventing definitive conclusions about the presence of a scaling advantage. The main technical obstacle has been the inability to verify an optimal annealing time within the available range. Here we overcome this obstacle and present a class of problem instances for which we observe an optimal annealing time using a D-Wave 2000Q processor over a range spanning up to more than $2000$ qubits. This allows us to perform an optimal TTS benchmarking analysis and perform a comparison to several classical algorithms, including simulated annealing, spin-vector Monte Carlo, and discrete-time simulated quantum annealing. We establish the first example of a scaling advantage for an experimental quantum annealer over classical simulated annealing: we find that the D-Wave device exhibits certifiably better scaling than simulated annealing, with $95\%$ confidence, over the range of problem sizes that we can test. However, we do not find evidence for a quantum speedup: simulated quantum annealing exhibits the best scaling by a significant margin. Our construction of instance classes with verifiably optimal annealing times opens up the possibility of generating many new such classes, paving the way for further definitive assessments of scaling advantages using current and future quantum annealing devices.

Related papers

Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly

Helmut G. Katzgraber, Firas Hamze, Zhu, Zheng +2 more

There has been considerable progress in the design and construction of quantum annealing devices. However, a conclusive detection of quantum speedup over traditional silicon-based machines remains elusive, despite multiple careful studies. In this work we outline strategies to design hard tunable benchmark instances based on insights from the study of spin glasses - the archetypal random benchmark problem for novel algorithms and optimization devices. We propose to complement head-to-head scaling studies that compare quantum annealing machines to state-of-the-art classical codes with an approach that compares the performance of different algorithms and/or computing architectures on different classes of computationally hard tunable spin-glass instances. The advantage of such an approach lies in having to only compare the performance hit felt by a given algorithm and/or architecture when the instance complexity is increased. Furthermore, we propose a methodology that might not directly translate into the detection of quantum speedup, but might elucidate whether quantum annealing has a "`quantum advantage" over corresponding classical algorithms like simulated annealing. Our results on a 496 qubit D-Wave Two quantum annealing device are compared to recently-used state-of-the-art thermal simulated annealing codes.

•Jan 1, 2015•86 citations

Scaling Advantage in Approximate Optimization with Quantum Annealing

Humberto Munoz-Bauza, Daniel A. Lidar

Quantum annealing is a heuristic optimization algorithm that exploits quantum evolution to find low-energy states. Quantum annealers have scaled up in recent years to tackle increasingly larger and more highly connected discrete optimization and quantum simulation problems. Nevertheless, a computational quantum advantage in exact optimization using quantum annealing hardware has so far remained elusive. Here, we present evidence for a quantum annealing scaling advantage in approximate optimization. The advantage is relative to the top classical heuristic algorithm: parallel tempering with isoenergetic cluster moves (PT-ICM). The setting is a family of 2D spin-glass problems with high-precision spin-spin interactions. To achieve this advantage, we implement quantum annealing correction (QAC): an embedding of a bit-flip error-correcting code with energy penalties that leverages the properties of the D-Wave Advantage quantum annealer to yield over 1,300 error-suppressed logical qubits on a degree-5 interaction graph. We generate random spin-glass instances on this graph and benchmark their time-to-epsilon, a generalization of the time-to-solution metric for low-energy states. We demonstrate that, with QAC, quantum annealing exhibits a scaling advantage over PT-ICM at sampling low-energy states with an optimality gap of at least 1.0%. This amounts to the first demonstration of an algorithmic quantum speedup in approximate optimization.

arXiv:2401.07184•Physical Review Letters•Apr 23, 2025•35 citations

Scaling advantage in approximate optimization with quantum annealing

Daniel A. Lidar, Humberto Munoz-Bauza

Abstract Quantum annealing is a heuristic optimization algorithm that exploits quantum evolution to approximately find lowest energy states [1, 2]. Quantum annealers have scaled up in recent years to tackle increasingly larger and more highly connected discrete optimization and quantum simulation problems [3–7]. Nevertheless, despite numerous attempts, a computational quantum advantage in exact optimization using quantum annealing hardware has so far remained elusive [8– 16]. Here, we present evidence for a quantum annealing scaling advantage in approximate optimization. The advantage is relative to the top classical heuristic algorithm: parallel tempering with isoenergetic cluster moves (PT-ICM) [17]. The setting is a family of 2D spin-glass problems with high-precision spin-spin interactions. To achieve this advantage, we implement quantum annealing correction (QAC) [18]: an embedding of a bit-flip error-correcting code with energy penalties that leverages the properties of the D-Wave Advantage quantum annealer to yield over 1,300 error-suppressed logical qubits on a degree-5 interaction graph. We generate random spin-glass instances on this graph and benchmark their time-to-epsilon, a generalization of the time-to-solution metric [8] for low-energy states. We demonstrate that with QAC, quantum annealing exhibits a scaling advantage over PT-ICM at sampling low energy states with an optimality gap [19] of at least 1.0%. This amounts to the first demonstration of an algorithmic quantum speedup in approximate optimization.

•Jan 16, 2024•2 citations

Demonstration of a Scaling Advantage for a Quantum Annealer over Simulated Annealing

Tameem Albash, Daniel A. Lidar

Benchmarks of a quantum information processor establish, for the first time, an advantage for a quantum annealer over classical simulated annealing, an important milestone in the development of quantum optimizers and in the journey towards demonstrating a quantum speedup over classical computers.

arXiv:1705.07452•Physical Review X•Jul 19, 2018•231 citations

Performance of a quantum annealer on range-limited constraint satisfaction problems

Andrew D. King, Lanting, Trevor, Harris, Richard

The performance of a D-Wave Vesuvius quantum annealer was recently compared to a suite of classical algorithms on a class of constraint satisfaction instances based on frustrated loops. However, the construction of these instances leads the maximum coupling strength to increase with problem size. As a result, larger instances are subject to amplified analog control error, and are effectively annealed at higher temperatures in both hardware and software. We generate similar constraint satisfaction instances with limited range of coupling strength and perform a similar comparison to classical algorithms. On these instances the D-Wave Vesuvius processor, run with a fixed 20$μ$s anneal time, shows a scaling advantage over the software solvers for the hardest regime studied. This scaling advantage opens the possibility of quantum speedup on these problems. Our results support the hypothesis that performance of D-Wave Vesuvius processors is heavily influenced by analog control error, which can be reduced and mitigated as the technology matures.

arXiv:1502.02098•Feb 7, 2015•41 citations

Benchmarking Quantum Annealing Against “Hard” Instances of the Bipartite Matching Problem

Daniel Vert, Renaud Sirdey, Stéphane Louise

Abstract This paper experimentally investigates the behavior of analog quantum computers as commercialized by D-Wave when confronted to instances of the maximum cardinality matching problem which is specifically designed to be hard to solve by means of simulated annealing. We benchmark a D-Wave “Washington” (2X) with 1098 operational qubits on various sizes of such instances and observe that for all but the most trivially small of these it fails to obtain an optimal solution. Thus, our results suggest that quantum annealing, at least as implemented in a D-Wave device, falls in the same pitfalls as simulated annealing and hence provides additional evidences suggesting that there exist polynomial-time problems that such a machine cannot solve efficiently to optimality. Additionally, we investigate the extent to which the qubits interconnection topologies explains these latter experimental results. In particular, we provide evidences that the sparsity of these topologies which, as such, lead to QUBO problems of artificially inflated sizes can partly explain the aforementioned disappointing observations. Therefore, this paper hints that denser interconnection topologies are necessary to unleash the potential of the quantum annealing approach.

SN Computer Science•Feb 20, 2021•23 citations
The observation of an unequivocal quantum speedup remains an elusive objective for quantum computing. The D-Wave quantum annealing processors have been at the forefront of experimental attempts to address this goal, given their relatively large numbers of qubits and programmability. A complete determination of the optimal time-to-solution (TTS) using these processors has not been possible to date, preventing definitive conclusions about the presence of a scaling advantage. The main technical obstacle has been the inability to verify an optimal annealing time within the available range. Here we overcome this obstacle and present a class of problem instances for which we observe an optimal annealing time using a D-Wave 2000Q processor over a range spanning up to more than 200020002000 qubits. This allows us to perform an optimal TTS benchmarking analysis and perform a comparison to several classical algorithms, including simulated annealing, spin-vector Monte Carlo, and discrete-time simulated quantum annealing. We establish the first example of a scaling advantage for an experimental quantum annealer over classical simulated annealing: we find that the D-Wave device exhibits certifiably better scaling than simulated annealing, with 95%95\%95% confidence, over the range of problem sizes that we can test. However, we do not find evidence for a quantum speedup: simulated quantum annealing exhibits the best scaling by a significant margin. Our construction of instance classes with verifiably optimal annealing times opens up the possibility of generating many new such classes, paving the way for further definitive assessments of scaling advantages using current and future quantum annealing devices.
There has been considerable progress in the design and construction of quantum annealing devices. However, a conclusive detection of quantum speedup over traditional silicon-based machines remains elusive, despite multiple careful studies. In this work we outline strategies to design hard tunable benchmark instances based on insights from the study of spin glasses - the archetypal random benchmark problem for novel algorithms and optimization devices. We propose to complement head-to-head scaling studies that compare quantum annealing machines to state-of-the-art classical codes with an approach that compares the performance of different algorithms and/or computing architectures on different classes of computationally hard tunable spin-glass instances. The advantage of such an approach lies in having to only compare the performance hit felt by a given algorithm and/or architecture when the instance complexity is increased. Furthermore, we propose a methodology that might not directly translate into the detection of quantum speedup, but might elucidate whether quantum annealing has a "`quantum advantage" over corresponding classical algorithms like simulated annealing. Our results on a 496 qubit D-Wave Two quantum annealing device are compared to recently-used state-of-the-art thermal simulated annealing codes.
Quantum annealing is a heuristic optimization algorithm that exploits quantum evolution to find low-energy states. Quantum annealers have scaled up in recent years to tackle increasingly larger and more highly connected discrete optimization and quantum simulation problems. Nevertheless, a computational quantum advantage in exact optimization using quantum annealing hardware has so far remained elusive. Here, we present evidence for a quantum annealing scaling advantage in approximate optimization. The advantage is relative to the top classical heuristic algorithm: parallel tempering with isoenergetic cluster moves (PT-ICM). The setting is a family of 2D spin-glass problems with high-precision spin-spin interactions. To achieve this advantage, we implement quantum annealing correction (QAC): an embedding of a bit-flip error-correcting code with energy penalties that leverages the properties of the D-Wave Advantage quantum annealer to yield over 1,300 error-suppressed logical qubits on a degree-5 interaction graph. We generate random spin-glass instances on this graph and benchmark their time-to-epsilon, a generalization of the time-to-solution metric for low-energy states. We demonstrate that, with QAC, quantum annealing exhibits a scaling advantage over PT-ICM at sampling low-energy states with an optimality gap of at least 1.0%. This amounts to the first demonstration of an algorithmic quantum speedup in approximate optimization.
Abstract Quantum annealing is a heuristic optimization algorithm that exploits quantum evolution to approximately find lowest energy states [1, 2]. Quantum annealers have scaled up in recent years to tackle increasingly larger and more highly connected discrete optimization and quantum simulation problems [3–7]. Nevertheless, despite numerous attempts, a computational quantum advantage in exact optimization using quantum annealing hardware has so far remained elusive [8– 16]. Here, we present evidence for a quantum annealing scaling advantage in approximate optimization. The advantage is relative to the top classical heuristic algorithm: parallel tempering with isoenergetic cluster moves (PT-ICM) [17]. The setting is a family of 2D spin-glass problems with high-precision spin-spin interactions. To achieve this advantage, we implement quantum annealing correction (QAC) [18]: an embedding of a bit-flip error-correcting code with energy penalties that leverages the properties of the D-Wave Advantage quantum annealer to yield over 1,300 error-suppressed logical qubits on a degree-5 interaction graph. We generate random spin-glass instances on this graph and benchmark their time-to-epsilon, a generalization of the time-to-solution metric [8] for low-energy states. We demonstrate that with QAC, quantum annealing exhibits a scaling advantage over PT-ICM at sampling low energy states with an optimality gap [19] of at least 1.0%. This amounts to the first demonstration of an algorithmic quantum speedup in approximate optimization.
The performance of a D-Wave Vesuvius quantum annealer was recently compared to a suite of classical algorithms on a class of constraint satisfaction instances based on frustrated loops. However, the construction of these instances leads the maximum coupling strength to increase with problem size. As a result, larger instances are subject to amplified analog control error, and are effectively annealed at higher temperatures in both hardware and software. We generate similar constraint satisfaction instances with limited range of coupling strength and perform a similar comparison to classical algorithms. On these instances the D-Wave Vesuvius processor, run with a fixed 20μμμs anneal time, shows a scaling advantage over the software solvers for the hardest regime studied. This scaling advantage opens the possibility of quantum speedup on these problems. Our results support the hypothesis that performance of D-Wave Vesuvius processors is heavily influenced by analog control error, which can be reduced and mitigated as the technology matures.
Abstract This paper experimentally investigates the behavior of analog quantum computers as commercialized by D-Wave when confronted to instances of the maximum cardinality matching problem which is specifically designed to be hard to solve by means of simulated annealing. We benchmark a D-Wave “Washington” (2X) with 1098 operational qubits on various sizes of such instances and observe that for all but the most trivially small of these it fails to obtain an optimal solution. Thus, our results suggest that quantum annealing, at least as implemented in a D-Wave device, falls in the same pitfalls as simulated annealing and hence provides additional evidences suggesting that there exist polynomial-time problems that such a machine cannot solve efficiently to optimality. Additionally, we investigate the extent to which the qubits interconnection topologies explains these latter experimental results. In particular, we provide evidences that the sparsity of these topologies which, as such, lead to QUBO problems of artificially inflated sizes can partly explain the aforementioned disappointing observations. Therefore, this paper hints that denser interconnection topologies are necessary to unleash the potential of the quantum annealing approach.