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:1406.7553 · Physical Review X

Quantum Optimization of Fully Connected Spin Glasses

Davide Venturelli, Salvatore Mandrà, Sergey Knysh, Bryan O’Gorman, Rupak Biswas, Vadim Smelyanskiy

Published Sep 18, 2015• 208 citations
arXivHTMLPDF

Abstract

Quantum computing promises to be more efficient and significantly faster than today's classical computing. Researchers compare the performance of a quantum annealer with that of classical algorithms for the first time on hard spin-glass problems.
DOI
10.1103/physrevx.5.031040

Related papers

Practical engineering of hard spin-glass instances

Jeffrey Marshall, Víctor Martín-Mayor, Itay Hen

How can we tell whether a quantum processor is able to demonstrate a quantum speedup in optimization algorithms? An efficient procedure for generating hard spin-glass problems that could be used to benchmark quantum annealers is proposed.

arXiv:1605.03607•Physical Review A•Jul 14, 2016•31 citations

Colloquium : Quantum annealing and analog quantum computation

Arnab Das, Bikas K. Chakrabarti

The recent success in quantum annealing, i.e., optimization of the cost or energy functions of complex systems utilizing quantum fluctuations is reviewed here. The concept is introduced in successive steps through studying the mapping of such computationally hard problems to classical spin-glass problems, quantum spin-glass problems arising with the introduction of quantum fluctuations, and the annealing behavior of the systems as these fluctuations are reduced slowly to zero. This provides a general framework for realizing analog quantum computation.

arXiv:0801.2193•Reviews of Modern Physics•Sep 5, 2008•699 citations

Comparison between a quantum annealer and a classical approximation algorithm for computing the ground state of an Ising spin glass

Ran Yacoby, Nathan Schaar, Leon Kellerhals +3 more

Finding the ground state of an Ising spin glass on general graphs belongs to the class of NP-hard problems, widely believed to have no efficient polynomial-time algorithms to solve them. An approach developed in computer science for dealing with such problems is to devise approximation algorithms; these are algorithms, whose run time scales polynomially with the input size, that provide solutions with provable guarantees on their quality in terms of the optimal unknown solution. Recently, several algorithms for the Ising spin-glass problem on a bounded degree graph that provide different approximation guarantees were introduced. D-Wave, a Canadian-based company, has constructed a physical realization of a quantum annealer and has enabled researchers and practitioners to access it via their cloud service. D-Wave is particularly suited for computing an approximation for the ground state of an Ising spin glass on its Chimera and Pegasus graphs-both with a bounded degree. To assess the quality of D-Wave's solution, it is natural to compare it to classical approximation algorithms specifically designed to solve the same problem. In this work, we compare the performance of a recently developed approximation algorithm to solve the Ising spin-glass problem on graphs of bounded degree against the performance of the D-Wave computer. We also compared the performance of D-Wave's computer in the Chimera architecture against the performance of a heuristic tailored specifically to handle the Chimera graph. We found that the D-Wave computer was able to find better approximations for all the random instances of the problem we studied-Gaussian weights, uniform weights, and discrete binary weights. Furthermore, the convergence times of D-Wave's computer were also significantly better. These results indicate the merit of D-Wave's computer under certain specific instances. More broadly, our method is relevant to a wider class of performance comparison studies, and we suggest that it is important to compare the performance of quantum computers not only against exact classical algorithms with exponential run-time scaling, but also against approximation algorithms with polynomial run-time scaling and a provable guarantee of performance.

Physical review. E•Mar 28, 2022•10 citations

Unraveling Quantum Annealers using Classical Hardness

Victor Martin-Mayor, Itay Hen

Recent advances in quantum technology have led to the development and manufacturing of experimental programmable quantum annealing optimizers that contain hundreds of quantum bits. These optimizers, commonly referred to as 'D-Wave' chips, promise to solve practical optimization problems potentially faster than conventional 'classical' computers. Attempts to quantify the quantum nature of these chips have been met with both excitement and skepticism but have also brought up numerous fundamental questions pertaining to the distinguishability of experimental quantum annealers from their classical thermal counterparts. Inspired by recent results in spin-glass theory that recognize 'temperature chaos' as the underlying mechanism responsible for the computational intractability of hard optimization problems, we devise a general method to quantify the performance of quantum annealers on optimization problems suffering from varying degrees of temperature chaos: A superior performance of quantum annealers over classical algorithms on these may allude to the role that quantum effects play in providing speedup. We utilize our method to experimentally study the D-Wave Two chip on different temperature-chaotic problems and find, surprisingly, that its performance scales unfavorably as compared to several analogous classical algorithms. We detect, quantify and discuss several purely classical effects that possibly mask the quantum behavior of the chip.

arXiv:1502.02494•Scientific Reports•Oct 20, 2015•61 citations

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

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

While manufacturing limitations are imposing constraints on Moore's law, researchers are searching for novel computing architectures based on quantum-mechanical effects. However, it remains to be shown that quantum annealing techniques consistently outperform classical simulated annealing to minimize optimization problems.

arXiv:1505.01545•Physical Review X•Sep 1, 2015•92 citations

Quantum Annealing for Constrained Optimization

Itay Hen, Federico M. Spedalieri

Quantum computers can perform certain tasks much faster than classical computers. An example is $q\phantom{\rule{0}{0ex}}u\phantom{\rule{0}{0ex}}a\phantom{\rule{0}{0ex}}n\phantom{\rule{0}{0ex}}t\phantom{\rule{0}{0ex}}u\phantom{\rule{0}{0ex}}m$ $a\phantom{\rule{0}{0ex}}n\phantom{\rule{0}{0ex}}n\phantom{\rule{0}{0ex}}e\phantom{\rule{0}{0ex}}a\phantom{\rule{0}{0ex}}l\phantom{\rule{0}{0ex}}i\phantom{\rule{0}{0ex}}n\phantom{\rule{0}{0ex}}g$, an operation that permits the exploration of energy landscapes to find global minima $i.e.$, optimal solutions) for problems that are classically intractable. This permits simultaneous exploration of enormous computational spaces, as is necessary for complex problems in economics, network design, and nonlinear control. The authors show how suitably engineered quantum annealers can efficiently guide and focus the quantum wave function towards the solutions of constrained optimization problems.

arXiv:1508.04212•Physical Review Applied•Mar 11, 2016•114 citations
The recent success in quantum annealing, i.e., optimization of the cost or energy functions of complex systems utilizing quantum fluctuations is reviewed here. The concept is introduced in successive steps through studying the mapping of such computationally hard problems to classical spin-glass problems, quantum spin-glass problems arising with the introduction of quantum fluctuations, and the annealing behavior of the systems as these fluctuations are reduced slowly to zero. This provides a general framework for realizing analog quantum computation.
Finding the ground state of an Ising spin glass on general graphs belongs to the class of NP-hard problems, widely believed to have no efficient polynomial-time algorithms to solve them. An approach developed in computer science for dealing with such problems is to devise approximation algorithms; these are algorithms, whose run time scales polynomially with the input size, that provide solutions with provable guarantees on their quality in terms of the optimal unknown solution. Recently, several algorithms for the Ising spin-glass problem on a bounded degree graph that provide different approximation guarantees were introduced. D-Wave, a Canadian-based company, has constructed a physical realization of a quantum annealer and has enabled researchers and practitioners to access it via their cloud service. D-Wave is particularly suited for computing an approximation for the ground state of an Ising spin glass on its Chimera and Pegasus graphs-both with a bounded degree. To assess the quality of D-Wave's solution, it is natural to compare it to classical approximation algorithms specifically designed to solve the same problem. In this work, we compare the performance of a recently developed approximation algorithm to solve the Ising spin-glass problem on graphs of bounded degree against the performance of the D-Wave computer. We also compared the performance of D-Wave's computer in the Chimera architecture against the performance of a heuristic tailored specifically to handle the Chimera graph. We found that the D-Wave computer was able to find better approximations for all the random instances of the problem we studied-Gaussian weights, uniform weights, and discrete binary weights. Furthermore, the convergence times of D-Wave's computer were also significantly better. These results indicate the merit of D-Wave's computer under certain specific instances. More broadly, our method is relevant to a wider class of performance comparison studies, and we suggest that it is important to compare the performance of quantum computers not only against exact classical algorithms with exponential run-time scaling, but also against approximation algorithms with polynomial run-time scaling and a provable guarantee of performance.
Recent advances in quantum technology have led to the development and manufacturing of experimental programmable quantum annealing optimizers that contain hundreds of quantum bits. These optimizers, commonly referred to as 'D-Wave' chips, promise to solve practical optimization problems potentially faster than conventional 'classical' computers. Attempts to quantify the quantum nature of these chips have been met with both excitement and skepticism but have also brought up numerous fundamental questions pertaining to the distinguishability of experimental quantum annealers from their classical thermal counterparts. Inspired by recent results in spin-glass theory that recognize 'temperature chaos' as the underlying mechanism responsible for the computational intractability of hard optimization problems, we devise a general method to quantify the performance of quantum annealers on optimization problems suffering from varying degrees of temperature chaos: A superior performance of quantum annealers over classical algorithms on these may allude to the role that quantum effects play in providing speedup. We utilize our method to experimentally study the D-Wave Two chip on different temperature-chaotic problems and find, surprisingly, that its performance scales unfavorably as compared to several analogous classical algorithms. We detect, quantify and discuss several purely classical effects that possibly mask the quantum behavior of the chip.
Quantum computers can perform certain tasks much faster than classical computers. An example is $q\phantom{\rule{0}{0ex}}u\phantom{\rule{0}{0ex}}a\phantom{\rule{0}{0ex}}n\phantom{\rule{0}{0ex}}t\phantom{\rule{0}{0ex}}u\phantom{\rule{0}{0ex}}m$ $a\phantom{\rule{0}{0ex}}n\phantom{\rule{0}{0ex}}n\phantom{\rule{0}{0ex}}e\phantom{\rule{0}{0ex}}a\phantom{\rule{0}{0ex}}l\phantom{\rule{0}{0ex}}i\phantom{\rule{0}{0ex}}n\phantom{\rule{0}{0ex}}g$, an operation that permits the exploration of energy landscapes to find global minima i.e.i.e.i.e., optimal solutions) for problems that are classically intractable. This permits simultaneous exploration of enormous computational spaces, as is necessary for complex problems in economics, network design, and nonlinear control. The authors show how suitably engineered quantum annealers can efficiently guide and focus the quantum wave function towards the solutions of constrained optimization problems.