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

arXiv:1502.02098

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

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

Published Feb 7, 2015• 41 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1502.02098

Related papers

Evidence for a Limited Quantum Speedup on a Quantum Annealer

Tameem Albash, Daniel A. Lidar

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.

•May 21, 2017•6 citations

Benchmarking a quantum annealing processor with the time-to-target metric

James A. King, Sheir Yarkoni, Mayssam Mohammadi Nevisi +2 more

In the evaluation of quantum annealers, metrics based on ground state success rates have two major drawbacks. First, evaluation requires computation time for both quantum and classical processors that grows exponentially with problem size. This makes evaluation itself computationally prohibitive. Second, results are heavily dependent on the effects of analog noise on the quantum processors, which is an engineering issue that complicates the study of the underlying quantum annealing algorithm. We introduce a novel "time-to-target" metric which avoids these two issues by challenging software solvers to match the results obtained by a quantum annealer in a short amount of time. We evaluate D-Wave's latest quantum annealer, the D-Wave 2X system, on an array of problem classes and find that it performs well on several input classes relative to state of the art software solvers running single-threaded on a CPU.

arXiv:1508.05087•Aug 20, 2015•77 citations

Analog errors in quantum annealing: doom and hope

Adam Pearson, Anurag Mishra, Itay Hen +1 more

Abstract Quantum annealing has the potential to provide a speedup over classical algorithms in solving optimization problems. Just as for any other quantum device, suppressing Hamiltonian control errors will be necessary before quantum annealers can achieve speedups. Such analog control errors are known to lead to $$J$$ J -chaos, wherein the probability of obtaining the optimal solution, encoded as the ground state of the intended Hamiltonian, varies widely depending on the control error. Here, we show that $$J$$ J -chaos causes a catastrophic failure of quantum annealing, in that the scaling of the time-to-solution metric becomes worse than that of a deterministic (exhaustive) classical solver. We demonstrate this empirically using random Ising spin glass problems run on the two latest generations of the D-Wave quantum annealers. We then proceed to show that this doomsday scenario can be mitigated using a simple error suppression and correction scheme known as quantum annealing correction (QAC). By using QAC, the time-to-solution scaling of the same D-Wave devices is improved to below that of the classical upper bound, thus restoring hope in the speedup prospects of quantum annealing.

arXiv:1907.12678•npj Quantum Information•Nov 28, 2019•70 citations

Inter-generational comparison of quantum annealers in solving hard scheduling problems

Bibek Pokharel, Zoe Gonzalez Izquierdo, P. Aaron Lott +6 more

Abstract We compare the performance of four quantum annealers, the D-Wave Two, 2X, 2000Q, and Advantage in solving an identical ensemble of a parametrized family of scheduling problems. These problems are NP-complete and, in fact, equivalent to vertex coloring problems. They are also practically motivated and closely connected to planning problems from artificial intelligence. We examine factors contributing to the performance differences while separating the contributions from hardware upgrades, support for shorter anneal times, and possible optimization of ferromagnetic couplings. While shorter anneal times can improve the time to solution (TTS) at any given problem size, the scaling of TTS with respect to the problem size worsens for shorter anneal times. In contrast, optimizing the ferromagnetic coupling improves both the absolute TTS and the scaling. There is a statistically significant improvement in performance between D-Wave Two and 2X and from all older generation annealers to Advantage, even when operated under identical anneal time and ferromagnetic couplings. However, the performance improvement from 2X to 2000Q requires the anneal time and ferromagnetic couplings to be optimized. Overall, owing to these inter-generational hardware improvements and optimizations, the scaling exponent reduces from $$1.01 \pm 0.01$$ 1.01 ± 0.01 on Two to $$0.259 \pm 0.008$$ 0.259 ± 0.008 on Advantage.

arXiv:2112.00727•Quantum Information Processing•Oct 4, 2023•5 citations

Enhancing quantum annealing accuracy through replication-based error mitigation*

Hristo N. Djidjev

Abstract Quantum annealers like those manufactured by D-Wave Systems are designed to find high quality solutions to optimization problems that are typically hard for classical computers. They utilize quantum effects like tunneling to evolve toward low-energy states representing solutions to optimization problems. However, their analog nature and limited control functionalities present challenges to correcting or mitigating hardware errors. As quantum computing advances towards applications, effective error suppression is an important research goal. We propose a new approach called replication based mitigation (RBM) based on parallel quantum annealing (QA). In RBM, physical qubits representing the same logical qubit are dispersed across different copies of the problem embedded in the hardware. This mitigates hardware biases, is compatible with limited qubit connectivity in current annealers, and is well-suited for currently available noisy intermediate-scale quantum annealers. Our experimental analysis shows that RBM provides solution quality on par with previous methods while being more flexible and compatible with a wider range of hardware connectivity patterns. In comparisons against standard QA without error mitigation on larger problem instances that could not be handled by previous methods, RBM consistently gets better energies and ground state probabilities across parameterized problem sets.

Quantum Science and Technology•Aug 13, 2024•2 citations

Probing for quantum speedup in spin-glass problems with planted solutions

Itay Hen, Joshua Job, Tameem Albash +3 more

The availability of quantum annealing devices with hundreds of qubits has made the experimental demonstration of a quantum speedup for optimization problems a coveted, albeit elusive goal. Going beyond earlier studies of random Ising problems, here we introduce a method to construct a set of frustrated Ising-model optimization problems with tunable hardness. We study the performance of a D-Wave Two device (DW2) with up to 503 qubits on these problems and compare it to a suite of classical algorithms, including a highly optimized algorithm designed to compete directly with the DW2. The problems are generated around predetermined ground-state configurations, called planted solutions, which makes them particularly suitable for benchmarking purposes. The problem set exhibits properties familiar from constraint satisfaction (SAT) problems, such as a peak in the typical hardness of the problems, determined by a tunable clause density parameter. We bound the hardness regime where the DW2 device either does not or might exhibit a quantum speedup for our problem set. While we do not find evidence for a speedup for the hardest and most frustrated problems in our problem set, we cannot rule out that a speedup might exist for some of the easier, less frustrated problems. Our empirical findings pertain to the specific D-Wave processor and problem set we studied and leave open the possibility that future processors might exhibit a quantum speedup on the same problem set.

arXiv:1502.01663•Physical Review A•Oct 23, 2015•168 citations
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.
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.
In the evaluation of quantum annealers, metrics based on ground state success rates have two major drawbacks. First, evaluation requires computation time for both quantum and classical processors that grows exponentially with problem size. This makes evaluation itself computationally prohibitive. Second, results are heavily dependent on the effects of analog noise on the quantum processors, which is an engineering issue that complicates the study of the underlying quantum annealing algorithm. We introduce a novel "time-to-target" metric which avoids these two issues by challenging software solvers to match the results obtained by a quantum annealer in a short amount of time. We evaluate D-Wave's latest quantum annealer, the D-Wave 2X system, on an array of problem classes and find that it performs well on several input classes relative to state of the art software solvers running single-threaded on a CPU.
Abstract Quantum annealing has the potential to provide a speedup over classical algorithms in solving optimization problems. Just as for any other quantum device, suppressing Hamiltonian control errors will be necessary before quantum annealers can achieve speedups. Such analog control errors are known to lead to JJJ J -chaos, wherein the probability of obtaining the optimal solution, encoded as the ground state of the intended Hamiltonian, varies widely depending on the control error. Here, we show that JJJ J -chaos causes a catastrophic failure of quantum annealing, in that the scaling of the time-to-solution metric becomes worse than that of a deterministic (exhaustive) classical solver. We demonstrate this empirically using random Ising spin glass problems run on the two latest generations of the D-Wave quantum annealers. We then proceed to show that this doomsday scenario can be mitigated using a simple error suppression and correction scheme known as quantum annealing correction (QAC). By using QAC, the time-to-solution scaling of the same D-Wave devices is improved to below that of the classical upper bound, thus restoring hope in the speedup prospects of quantum annealing.
Abstract We compare the performance of four quantum annealers, the D-Wave Two, 2X, 2000Q, and Advantage in solving an identical ensemble of a parametrized family of scheduling problems. These problems are NP-complete and, in fact, equivalent to vertex coloring problems. They are also practically motivated and closely connected to planning problems from artificial intelligence. We examine factors contributing to the performance differences while separating the contributions from hardware upgrades, support for shorter anneal times, and possible optimization of ferromagnetic couplings. While shorter anneal times can improve the time to solution (TTS) at any given problem size, the scaling of TTS with respect to the problem size worsens for shorter anneal times. In contrast, optimizing the ferromagnetic coupling improves both the absolute TTS and the scaling. There is a statistically significant improvement in performance between D-Wave Two and 2X and from all older generation annealers to Advantage, even when operated under identical anneal time and ferromagnetic couplings. However, the performance improvement from 2X to 2000Q requires the anneal time and ferromagnetic couplings to be optimized. Overall, owing to these inter-generational hardware improvements and optimizations, the scaling exponent reduces from 1.01±0.011.01 \pm 0.011.01±0.01 1.01 ± 0.01 on Two to 0.259±0.0080.259 \pm 0.0080.259±0.008 0.259 ± 0.008 on Advantage.
Abstract Quantum annealers like those manufactured by D-Wave Systems are designed to find high quality solutions to optimization problems that are typically hard for classical computers. They utilize quantum effects like tunneling to evolve toward low-energy states representing solutions to optimization problems. However, their analog nature and limited control functionalities present challenges to correcting or mitigating hardware errors. As quantum computing advances towards applications, effective error suppression is an important research goal. We propose a new approach called replication based mitigation (RBM) based on parallel quantum annealing (QA). In RBM, physical qubits representing the same logical qubit are dispersed across different copies of the problem embedded in the hardware. This mitigates hardware biases, is compatible with limited qubit connectivity in current annealers, and is well-suited for currently available noisy intermediate-scale quantum annealers. Our experimental analysis shows that RBM provides solution quality on par with previous methods while being more flexible and compatible with a wider range of hardware connectivity patterns. In comparisons against standard QA without error mitigation on larger problem instances that could not be handled by previous methods, RBM consistently gets better energies and ground state probabilities across parameterized problem sets.
The availability of quantum annealing devices with hundreds of qubits has made the experimental demonstration of a quantum speedup for optimization problems a coveted, albeit elusive goal. Going beyond earlier studies of random Ising problems, here we introduce a method to construct a set of frustrated Ising-model optimization problems with tunable hardness. We study the performance of a D-Wave Two device (DW2) with up to 503 qubits on these problems and compare it to a suite of classical algorithms, including a highly optimized algorithm designed to compete directly with the DW2. The problems are generated around predetermined ground-state configurations, called planted solutions, which makes them particularly suitable for benchmarking purposes. The problem set exhibits properties familiar from constraint satisfaction (SAT) problems, such as a peak in the typical hardness of the problems, determined by a tunable clause density parameter. We bound the hardness regime where the DW2 device either does not or might exhibit a quantum speedup for our problem set. While we do not find evidence for a speedup for the hardest and most frustrated problems in our problem set, we cannot rule out that a speedup might exist for some of the easier, less frustrated problems. Our empirical findings pertain to the specific D-Wave processor and problem set we studied and leave open the possibility that future processors might exhibit a quantum speedup on the same problem set.