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:1604.01746 · Physical Review A

Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics versus quantum approaches

Salvatore Mandrà, Zheng Zhu, Wenlong Wang, Alejandro Perdomo‐Ortiz, Helmut G. Katzgraber

Published Aug 29, 2016• 112 citations
arXivHTMLPDF

Abstract

To date, a conclusive detection of quantum speedup remains elusive. Recently, a team by Google Inc. [V. S. Denchev et al., Phys. Rev. X 6, 031015 (2016)] proposed a weak-strong cluster model tailored to have tall and narrow energy barriers separating local minima, with the aim to highlight the value of finite-range tunneling. More precisely, results from quantum Monte Carlo simulations as well as the D-Wave 2X quantum annealer scale considerably better than state-of-the-art simulated annealing simulations. Moreover, the D-Wave 2X quantum annealer is $\ensuremath{\sim}{10}^{8}$ times faster than simulated annealing on conventional computer hardware for problems with approximately ${10}^{3}$ variables. Here, an overview of different sequential, nontailored, as well as specialized tailored algorithms on the Google instances is given. We show that the quantum speedup is limited to sequential approaches and study the typical complexity of the benchmark problems using insights from the study of spin glasses.

DOI
10.1103/physreva.94.022337

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•9 citations

Quantum versus classical annealing of Ising spin glasses

Bettina Heim, Troels F. Rønnow, Sergei V. Isakov +1 more

Quantum annealers use quantum fluctuations to escape local minima and find low-energy configurations of a physical system. Strong evidence for superiority of quantum annealing (QA) has come from comparing QA implemented through quantum Monte Carlo (QMC) simulations to classical annealing. Motivated by recent experiments, we revisit the question of when quantum speedup may be expected. Although a better scaling is seen for QA in two-dimensional Ising spin glasses, this advantage is due to time discretization artifacts and measurements that are not possible on a physical quantum annealer. Simulations in the physically relevant continuous time limit, on the other hand, do not show superiority. Our results imply that care must be taken when using QMC simulations to assess the potential for quantum speedup.

arXiv:1411.5693•Science•Mar 12, 2015•225 citations

Quantum Annealing amid Local Ruggedness and Global Frustration

James King, Sheir Yarkoni, Jack Raymond +5 more

A recent Google study [Phys. Rev. X, 6:031015 (2016)] compared a D-Wave 2X quantum processing unit (QPU) to two classical Monte Carlo algorithms: simulated annealing (SA) and quantum Monte Carlo (QMC). The study showed the D-Wave 2X to be up to 100 million times faster than the classical algorithms. The Google inputs are designed to demonstrate the value of collective multiqubit tunneling, a resource available to D-Wave QPUs but not to simulated annealing. But the computational hardness in these inputs is highly localized in gadgets, with only a small amount of complexity coming from global interactions, meaning that the relevance to real-world problems is limited. In this study we provide a new synthetic problem class that addresses the limitations of the Google inputs while retaining their strengths. We use simple clusters instead of more complex gadgets and more emphasis is placed on creating computational hardness through frustrated global interactions like those seen in interesting real-world inputs. The logical problems used to generate these inputs can be solved in polynomial time [J. Phys. A, 15:10 (1982)]. However, for general heuristic algorithms that are unaware of the planted problem class, the frustration creates meaningful difficulty in a controlled environment ideal for study. We use these inputs to evaluate the new 2000-qubit D-Wave QPU. We include the HFS algorithm---the best performer in a broader analysis of Google inputs---and we include state-of-the-art GPU implementations of SA and QMC. The D-Wave QPU solidly outperforms the software solvers: when we consider pure annealing time (computation time), the D-Wave QPU reaches ground states up to 2600 times faster than the competition. In the task of zero-temperature Boltzmann sampling from challenging multimodal inputs, the D-Wave QPU holds a similar advantage as quantum sampling bias does not seem significant.

arXiv:1701.04579•Journal of the Physical Society of Japan•Feb 28, 2019•120 citations

A deceptive step towards quantum speedup detection

Salvatore Mandrà, Helmut G. Katzgraber

Abstract There have been multiple attempts to design synthetic benchmark problems with the goal of detecting quantum speedup in current quantum annealing (QA) machines. To date, classical heuristics have consistently outperformed quantum annealing based approaches. Here we introduce a class of problems based on frustrated cluster loops—deceptive cluster loops—for which all currently known state of-the-art classical heuristics are outperformed by the DW2000Q QA machine. While there is a sizable constant speedup over all known classical heuristics, a noticeable improvement in the scaling remains elusive. These results represent the first steps towards a detection of potential quantum speedup, albeit without a scaling improvement and for synthetic benchmark problems.

arXiv:1711.01368•Quantum Science and Technology•May 30, 2018•90 citations

Efficient Combinatorial Optimization Using Quantum Annealing

Hristo N. Djidjev, Guillaume Chapuis, Georg Hahn +1 more

The recent availability of the first commercial quantum computers has provided a promising tool to tackle NP hard problems which can only be solved heuristically with present techniques. However, it is unclear if the current state of quantum computing already provides a quantum advantage over the current state of the art in classical computing. This article assesses the performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in particular clique finding and graph partitioning. For this, we provide formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing, third-party clique finding and graph splitting heuristics) on certain test sets of graphs. We demonstrate that for small graph instances, classical methods still outperform the quantum annealer in terms of computing time, even though the quality of the best solutions obtained is comparable. Nevertheless, due to the limited problem size which can be embedded on the D-Wave 2X chip, the aforementioned finding applies to most of problems of general nature solvable on the quantum annealer. For instances specifically designed to fit the D-Wave 2X architecture, we observe substantial speed-ups in computing time over classical approaches.

arXiv:1801.08653•Jan 26, 2018•65 citations

A STUDY OF QUANTUM ANNEALING DEVICES FROM A CLASSICAL PERSPECTIVE

Andrew J. Ochoa

Spin glasses are experiencing a revival due to applications in quantum information\ntheory. In particular, they are the archetypal native benchmark problem for quantum annealing\nmachines. Furthermore, they find applications in fields as diverse as satisfiability,\nneural networks, and general combinatorial optimization problems. As such, developing\nand improving algorithms and methods to study these computationally complex systems\nis of paramount importance to many disciplines. This body of work attempts to attack\nthe problem of solving combinatorial optimization problems by simulating spin glasses\nfrom three sides: classical algorithm development, suggestions for quantum annealing\ndevice design, and improving measurements in realistic physical systems with inherent\nnoise. I begin with the introduction of a cluster algorithm based on Houdayer’s cluster algorithm\nfor two-dimensional Ising spin-glasses that is applicable to any space dimension\nand speeds up thermalization by several orders of magnitude at low temperatures where\nprevious algorithms have difficulty. I show improvement for the D-Wave chimera topology\nand the three-dimensional cubic lattice that increases with the size of the problem.\nOne consequence of adding cluster moves is that for problems with degenerate solutions,\nground-state sampling is improved. I demonstrate an ergodic algorithm to sample ground\nstates through the use of simple Monte Carlo with parallel tempering and cluster moves.\nIn addition, I present a non-ergodic algorithm to generate new solutions from a bank of\nknown solutions. I compare these results against results from quantum annealing utilizing\nthe D-Wave Inc. quantum annealing device. Finally, I present an algorithm for improving\nthe recovery of ground-state solutions from problems with noise by using thermal fluctuations\nto infer the correct solution at the Nishimori temperature. While this method has been\ndemonstrated analytically and numerically for trivial ferromagnetic and Gaussian distributions, a useful metric for more complex Gaussian distributions with added Gaussian noise\nis unavailable. We show improved recovery of numerical solutions on the chimera graph\nwith a ferromagnetic distribution and added Gaussian noise. Next, I direct my focus to the\ndesign of future generations of quantum annealers. The first design is the two-dimensional\nsquare-lattice bimodal spin glass with next-nearest ferrromagnetic interactions proposed\nby Lemke and Campbell claimed to exhibit a finite-temperature spin-glass state for a particular\nrelative strength of the next-nearest to nearest neighbor interactions. Our results\nfrom finite-temperature simulations show the system is in a paramagnetic state in the thermodynamic\nlimit, thus not useful for quantum annealing device designs that would benefit\nfrom a spin-glass phase transition. The second design is the diluted next-nearest neighbor\nIsing spin-glass with Gaussian interactions in an attempt to improve the estimation\nof critical parameter with smaller system sizes by implementing averaging of observables\nover different graph dilutions. To date, this model has shown no improvement. Finally,\nI make suggestions for the choice of distributions of interactions that are robust to noise\nand present a method for using previously unaccessible continuous distributions. I begin\nwith showing the best-case performance of quantum annealing devices. I show results for\nthe resilience, the probability that the ground-state solution has changed due to inherent\nanalog noise in the device, and present strategies for developing robust instance classes.\nThe analog noise is also detrimental to interactions chosen from continuous distributions.\nUsing Gaussian quadratures, I present a method for discretizing continuous distributions\nto reduce noise effects. Simulations on the D-Wave show that the average residual of\nthe ground-state energy with the true ground-state energy is calculated and shown to be\nsmaller in the case of the discrete distribution.

•Dec 7, 2017•1 citation
To date, a conclusive detection of quantum speedup remains elusive. Recently, a team by Google Inc. [V. S. Denchev et al., Phys. Rev. X 6, 031015 (2016)] proposed a weak-strong cluster model tailored to have tall and narrow energy barriers separating local minima, with the aim to highlight the value of finite-range tunneling. More precisely, results from quantum Monte Carlo simulations as well as the D-Wave 2X quantum annealer scale considerably better than state-of-the-art simulated annealing simulations. Moreover, the D-Wave 2X quantum annealer is \ensuremath∼108\ensuremath{\sim}{10}^{8}\ensuremath∼108 times faster than simulated annealing on conventional computer hardware for problems with approximately 103{10}^{3}103 variables. Here, an overview of different sequential, nontailored, as well as specialized tailored algorithms on the Google instances is given. We show that the quantum speedup is limited to sequential approaches and study the typical complexity of the benchmark problems using insights from the study of spin glasses.
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.
Quantum annealers use quantum fluctuations to escape local minima and find low-energy configurations of a physical system. Strong evidence for superiority of quantum annealing (QA) has come from comparing QA implemented through quantum Monte Carlo (QMC) simulations to classical annealing. Motivated by recent experiments, we revisit the question of when quantum speedup may be expected. Although a better scaling is seen for QA in two-dimensional Ising spin glasses, this advantage is due to time discretization artifacts and measurements that are not possible on a physical quantum annealer. Simulations in the physically relevant continuous time limit, on the other hand, do not show superiority. Our results imply that care must be taken when using QMC simulations to assess the potential for quantum speedup.
A recent Google study [Phys. Rev. X, 6:031015 (2016)] compared a D-Wave 2X quantum processing unit (QPU) to two classical Monte Carlo algorithms: simulated annealing (SA) and quantum Monte Carlo (QMC). The study showed the D-Wave 2X to be up to 100 million times faster than the classical algorithms. The Google inputs are designed to demonstrate the value of collective multiqubit tunneling, a resource available to D-Wave QPUs but not to simulated annealing. But the computational hardness in these inputs is highly localized in gadgets, with only a small amount of complexity coming from global interactions, meaning that the relevance to real-world problems is limited. In this study we provide a new synthetic problem class that addresses the limitations of the Google inputs while retaining their strengths. We use simple clusters instead of more complex gadgets and more emphasis is placed on creating computational hardness through frustrated global interactions like those seen in interesting real-world inputs. The logical problems used to generate these inputs can be solved in polynomial time [J. Phys. A, 15:10 (1982)]. However, for general heuristic algorithms that are unaware of the planted problem class, the frustration creates meaningful difficulty in a controlled environment ideal for study. We use these inputs to evaluate the new 2000-qubit D-Wave QPU. We include the HFS algorithm---the best performer in a broader analysis of Google inputs---and we include state-of-the-art GPU implementations of SA and QMC. The D-Wave QPU solidly outperforms the software solvers: when we consider pure annealing time (computation time), the D-Wave QPU reaches ground states up to 2600 times faster than the competition. In the task of zero-temperature Boltzmann sampling from challenging multimodal inputs, the D-Wave QPU holds a similar advantage as quantum sampling bias does not seem significant.
Abstract There have been multiple attempts to design synthetic benchmark problems with the goal of detecting quantum speedup in current quantum annealing (QA) machines. To date, classical heuristics have consistently outperformed quantum annealing based approaches. Here we introduce a class of problems based on frustrated cluster loops—deceptive cluster loops—for which all currently known state of-the-art classical heuristics are outperformed by the DW2000Q QA machine. While there is a sizable constant speedup over all known classical heuristics, a noticeable improvement in the scaling remains elusive. These results represent the first steps towards a detection of potential quantum speedup, albeit without a scaling improvement and for synthetic benchmark problems.
The recent availability of the first commercial quantum computers has provided a promising tool to tackle NP hard problems which can only be solved heuristically with present techniques. However, it is unclear if the current state of quantum computing already provides a quantum advantage over the current state of the art in classical computing. This article assesses the performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in particular clique finding and graph partitioning. For this, we provide formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing, third-party clique finding and graph splitting heuristics) on certain test sets of graphs. We demonstrate that for small graph instances, classical methods still outperform the quantum annealer in terms of computing time, even though the quality of the best solutions obtained is comparable. Nevertheless, due to the limited problem size which can be embedded on the D-Wave 2X chip, the aforementioned finding applies to most of problems of general nature solvable on the quantum annealer. For instances specifically designed to fit the D-Wave 2X architecture, we observe substantial speed-ups in computing time over classical approaches.
Spin glasses are experiencing a revival due to applications in quantum information\ntheory. In particular, they are the archetypal native benchmark problem for quantum annealing\nmachines. Furthermore, they find applications in fields as diverse as satisfiability,\nneural networks, and general combinatorial optimization problems. As such, developing\nand improving algorithms and methods to study these computationally complex systems\nis of paramount importance to many disciplines. This body of work attempts to attack\nthe problem of solving combinatorial optimization problems by simulating spin glasses\nfrom three sides: classical algorithm development, suggestions for quantum annealing\ndevice design, and improving measurements in realistic physical systems with inherent\nnoise. I begin with the introduction of a cluster algorithm based on Houdayer’s cluster algorithm\nfor two-dimensional Ising spin-glasses that is applicable to any space dimension\nand speeds up thermalization by several orders of magnitude at low temperatures where\nprevious algorithms have difficulty. I show improvement for the D-Wave chimera topology\nand the three-dimensional cubic lattice that increases with the size of the problem.\nOne consequence of adding cluster moves is that for problems with degenerate solutions,\nground-state sampling is improved. I demonstrate an ergodic algorithm to sample ground\nstates through the use of simple Monte Carlo with parallel tempering and cluster moves.\nIn addition, I present a non-ergodic algorithm to generate new solutions from a bank of\nknown solutions. I compare these results against results from quantum annealing utilizing\nthe D-Wave Inc. quantum annealing device. Finally, I present an algorithm for improving\nthe recovery of ground-state solutions from problems with noise by using thermal fluctuations\nto infer the correct solution at the Nishimori temperature. While this method has been\ndemonstrated analytically and numerically for trivial ferromagnetic and Gaussian distributions, a useful metric for more complex Gaussian distributions with added Gaussian noise\nis unavailable. We show improved recovery of numerical solutions on the chimera graph\nwith a ferromagnetic distribution and added Gaussian noise. Next, I direct my focus to the\ndesign of future generations of quantum annealers. The first design is the two-dimensional\nsquare-lattice bimodal spin glass with next-nearest ferrromagnetic interactions proposed\nby Lemke and Campbell claimed to exhibit a finite-temperature spin-glass state for a particular\nrelative strength of the next-nearest to nearest neighbor interactions. Our results\nfrom finite-temperature simulations show the system is in a paramagnetic state in the thermodynamic\nlimit, thus not useful for quantum annealing device designs that would benefit\nfrom a spin-glass phase transition. The second design is the diluted next-nearest neighbor\nIsing spin-glass with Gaussian interactions in an attempt to improve the estimation\nof critical parameter with smaller system sizes by implementing averaging of observables\nover different graph dilutions. To date, this model has shown no improvement. Finally,\nI make suggestions for the choice of distributions of interactions that are robust to noise\nand present a method for using previously unaccessible continuous distributions. I begin\nwith showing the best-case performance of quantum annealing devices. I show results for\nthe resilience, the probability that the ground-state solution has changed due to inherent\nanalog noise in the device, and present strategies for developing robust instance classes.\nThe analog noise is also detrimental to interactions chosen from continuous distributions.\nUsing Gaussian quadratures, I present a method for discretizing continuous distributions\nto reduce noise effects. Simulations on the D-Wave show that the average residual of\nthe ground-state energy with the true ground-state energy is calculated and shown to be\nsmaller in the case of the discrete distribution.