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:2105.02208 · Quantum Information Processing

Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems

Dennis Willsch, Madita Willsch, Carlos D. Gonzalez Calaza, Fengping Jin, Hans A. De Raedt, Marika Svensson, Kristel F. L. Michielsen

Published Apr 1, 2022• 114 citations
arXivHTMLPDF

Abstract

Abstract We benchmark the quantum processing units of the largest quantum annealers to date, the $$5000+$$ 5000 + qubit quantum annealer Advantage and its 2000+ qubit predecessor D-Wave 2000Q, using tail assignment and exact cover problems from aircraft scheduling scenarios. The benchmark set contains small, intermediate, and large problems with both sparsely connected and almost fully connected instances. We find that Advantage outperforms D-Wave 2000Q for almost all problems, with a notable increase in success rate and problem size. In particular, Advantage is also able to solve the largest problems with 120 logical qubits that D-Wave 2000Q cannot solve anymore. Furthermore, problems that can still be solved by D-Wave 2000Q are solved faster by Advantage. We find, however, that D-Wave 2000Q can achieve better success rates for sparsely connected problems that do not require the many new couplers present on Advantage, so improving the connectivity of a quantum annealer does not per se improve its performance.

DOI
10.1007/s11128-022-03476-y

Related papers

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

Evaluation of Quantum Annealer Performance via the Massive MIMO Problem

Zsolt Tabi, Ádám Marosits, Zsófia Kallus +3 more

Quantum annealing offers an appealing route to handle large-scale optimization problems. Existing Quantum Annealing processing units are readily available via cloud platform access for solving Quadratic Unconstrained Binary Optimization (QUBO) problems. In particular, the novel D-Wave Advantage device has been recently released. Its performance is expected to improve upon the previous state-of-the-art D-Wave 2000Q annealer, due to higher number of qubits and the Pegasus topology. Here, we present a comparative study via an ensemble of Maximum Likelihood (ML) Channel Decoder problems for MIMO scenarios in Centralized Radio Access Network (C-RAN) architectures. The main challenge for exact optimization of ML decoders with ever-increasing demand for higher data rates is the exponential increase of the solution space with problem sizes. Since current 5G solutions mainly use approximate methodologies, Kim et al. leveraged Quantum Annealing for large MIMO problems with Phase Shift Keying and Quadrature Amplitude Modulation scenarios. Here, we extend their work and analyze experiments for more complex modulations and larger MIMO antenna array sizes. By implementing the extended QUBO formulae on the novel annealer architecture, we uncover the limits of state-of-the-art quantum optimization for the massive MIMO ML decoder. We report on the improvements and discuss the uncovered limiting factors learned from the 64-QAM extension. We include the enhanced evaluation of raw annealer sampling via implementation of post-processing methods in the comparative analysis between D-Wave 2000Q and D-Wave Advantage system.

IEEE Access•Jan 1, 2021•30 citations

On the Design and Characterization of Set Packing Problem on Quantum Annealers

M. Vénere, Giuseppe Sorrentino, Beatrice Branchini +4 more

The beginning of the quantum era has increased the hype around computationally demanding problems and, particularly, NP-complete problems. One of the most famous is the Set Packing, which has several applications in different management contexts. This work presents a solver for Set Packing Problem on quantum annealers exploiting the QUBO model. We introduce a general format to express instances of the Set Packing Problem that enables an automatic characterization, lowering the barriers to adopting quantum annealers. Finally, we compare the performance of two quantum annealer on the Set Packing, namely D-Wave 2000Q and Advantage, highlighting their pros and cons. As key evaluation indicators, this work uses spatial features, such as the number of qubits and maximum chain length, and the execution time required for a reliable problem resolution and its breakdown. In particular, we can scale the solutions to 60 and 150 subsets on 2000Q and Advantage, respectively, with 0 chain breaks. Moreover, our analysis illustrates that 2000Q has lower mean energy required but higher execution times on the same problem complexity.

IEEE EUROCON - International Conference on Computer as a Tool (EUROCON)•Jul 6, 2023•3 citations

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

Garden optimization problems for benchmarking quantum annealers

Gonzalez Calaza, Carlos D., Dennis Willsch, Kristel F. L. Michielsen

We benchmark the 5000+ qubit system Advantage coupled with the Hybrid Solver Service 2 released by D-Wave Systems Inc. in September 2020 by using a new class of optimization problems called garden optimization problems known in companion planting. These problems are scalable to an arbitrarily large number of variables and intuitively find application in real-world scenarios. We derive their QUBO formulation and illustrate their relation to the quadratic assignment problem. We demonstrate that the Advantage system and the new hybrid solver can solve larger problems in less time than their predecessors. However, we also show that the solvers based on the 2000+ qubit system DW2000Q sometimes produce more favourable results if they can solve the problems.

Quantum Information Processing•Jan 1, 2021•18 citations

Benchmark Test of Black-box Optimization Using D-Wave Quantum Annealer

Ami S. Koshikawa, Masayuki Ohzeki, Tadashi Kadowaki +1 more

In solving optimization problems, objective functions generally need to be minimized or maximized. However, objective functions cannot always be formulated explicitly in a mathematical form for complicated problem settings. Although several regression techniques infer the approximate forms of objective functions, they are at times expensive to evaluate. Optimal points of "black-box" objective functions are computed in such scenarios, while effectively using a small number of clues. Recently, an efficient method by use of inference by sparse prior for a black-box objective function with binary variables has been proposed. In this method, a surrogate model was proposed in the form of a quadratic unconstrained binary optimization (QUBO) problem, and was iteratively solved to obtain the optimal solution of the black-box objective function. In the present study, we employ the D-Wave 2000Q quantum annealer, which can solve QUBO by driving the binary variables by quantum fluctuations. The D-Wave 2000Q quantum annealer does not necessarily output the ground state at the end of the protocol due to freezing effect during the process. We investigate effects from the output of the D-Wave quantum annealer in performing black-box optimization. We demonstrate a benchmark test by employing the sparse Sherrington-Kirkpatrick (SK) model as the black-box objective function, by introducing a parameter controlling the sparseness of the interaction coefficients. Comparing the results of the D-Wave quantum annealer to those of the simulated annealing (SA) and semidefinite programming (SDP), our results by the D-Wave quantum annealer and SA exhibit superiority in black-box optimization with SDP. On the other hand, we did not find any advantage of the D-Wave quantum annealer over the simulated annealing. As far as in our case, any effects by quantum fluctuation are not found.

arXiv:2103.12320•Journal of the Physical Society of Japan•May 11, 2021•43 citations
Abstract We benchmark the quantum processing units of the largest quantum annealers to date, the 5000+5000+5000+ 5000 + qubit quantum annealer Advantage and its 2000+ qubit predecessor D-Wave 2000Q, using tail assignment and exact cover problems from aircraft scheduling scenarios. The benchmark set contains small, intermediate, and large problems with both sparsely connected and almost fully connected instances. We find that Advantage outperforms D-Wave 2000Q for almost all problems, with a notable increase in success rate and problem size. In particular, Advantage is also able to solve the largest problems with 120 logical qubits that D-Wave 2000Q cannot solve anymore. Furthermore, problems that can still be solved by D-Wave 2000Q are solved faster by Advantage. We find, however, that D-Wave 2000Q can achieve better success rates for sparsely connected problems that do not require the many new couplers present on Advantage, so improving the connectivity of a quantum annealer does not per se improve its performance.
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.
Quantum annealing offers an appealing route to handle large-scale optimization problems. Existing Quantum Annealing processing units are readily available via cloud platform access for solving Quadratic Unconstrained Binary Optimization (QUBO) problems. In particular, the novel D-Wave Advantage device has been recently released. Its performance is expected to improve upon the previous state-of-the-art D-Wave 2000Q annealer, due to higher number of qubits and the Pegasus topology. Here, we present a comparative study via an ensemble of Maximum Likelihood (ML) Channel Decoder problems for MIMO scenarios in Centralized Radio Access Network (C-RAN) architectures. The main challenge for exact optimization of ML decoders with ever-increasing demand for higher data rates is the exponential increase of the solution space with problem sizes. Since current 5G solutions mainly use approximate methodologies, Kim et al. leveraged Quantum Annealing for large MIMO problems with Phase Shift Keying and Quadrature Amplitude Modulation scenarios. Here, we extend their work and analyze experiments for more complex modulations and larger MIMO antenna array sizes. By implementing the extended QUBO formulae on the novel annealer architecture, we uncover the limits of state-of-the-art quantum optimization for the massive MIMO ML decoder. We report on the improvements and discuss the uncovered limiting factors learned from the 64-QAM extension. We include the enhanced evaluation of raw annealer sampling via implementation of post-processing methods in the comparative analysis between D-Wave 2000Q and D-Wave Advantage system.
The beginning of the quantum era has increased the hype around computationally demanding problems and, particularly, NP-complete problems. One of the most famous is the Set Packing, which has several applications in different management contexts. This work presents a solver for Set Packing Problem on quantum annealers exploiting the QUBO model. We introduce a general format to express instances of the Set Packing Problem that enables an automatic characterization, lowering the barriers to adopting quantum annealers. Finally, we compare the performance of two quantum annealer on the Set Packing, namely D-Wave 2000Q and Advantage, highlighting their pros and cons. As key evaluation indicators, this work uses spatial features, such as the number of qubits and maximum chain length, and the execution time required for a reliable problem resolution and its breakdown. In particular, we can scale the solutions to 60 and 150 subsets on 2000Q and Advantage, respectively, with 0 chain breaks. Moreover, our analysis illustrates that 2000Q has lower mean energy required but higher execution times on the same problem complexity.
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.
We benchmark the 5000+ qubit system Advantage coupled with the Hybrid Solver Service 2 released by D-Wave Systems Inc. in September 2020 by using a new class of optimization problems called garden optimization problems known in companion planting. These problems are scalable to an arbitrarily large number of variables and intuitively find application in real-world scenarios. We derive their QUBO formulation and illustrate their relation to the quadratic assignment problem. We demonstrate that the Advantage system and the new hybrid solver can solve larger problems in less time than their predecessors. However, we also show that the solvers based on the 2000+ qubit system DW2000Q sometimes produce more favourable results if they can solve the problems.
In solving optimization problems, objective functions generally need to be minimized or maximized. However, objective functions cannot always be formulated explicitly in a mathematical form for complicated problem settings. Although several regression techniques infer the approximate forms of objective functions, they are at times expensive to evaluate. Optimal points of "black-box" objective functions are computed in such scenarios, while effectively using a small number of clues. Recently, an efficient method by use of inference by sparse prior for a black-box objective function with binary variables has been proposed. In this method, a surrogate model was proposed in the form of a quadratic unconstrained binary optimization (QUBO) problem, and was iteratively solved to obtain the optimal solution of the black-box objective function. In the present study, we employ the D-Wave 2000Q quantum annealer, which can solve QUBO by driving the binary variables by quantum fluctuations. The D-Wave 2000Q quantum annealer does not necessarily output the ground state at the end of the protocol due to freezing effect during the process. We investigate effects from the output of the D-Wave quantum annealer in performing black-box optimization. We demonstrate a benchmark test by employing the sparse Sherrington-Kirkpatrick (SK) model as the black-box objective function, by introducing a parameter controlling the sparseness of the interaction coefficients. Comparing the results of the D-Wave quantum annealer to those of the simulated annealing (SA) and semidefinite programming (SDP), our results by the D-Wave quantum annealer and SA exhibit superiority in black-box optimization with SDP. On the other hand, we did not find any advantage of the D-Wave quantum annealer over the simulated annealing. As far as in our case, any effects by quantum fluctuation are not found.