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

The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective

Victor Bapst, Laura Foini, Florent Krząkała, Guilhem Semerjian, Francesco Zamponi

Published Oct 2, 2012• 123 citations
OpenAlex

Abstract

Among various algorithms designed to exploit the specific properties of quantum computers with respect to classical ones, the quantum adiabatic algorithm is a versatile proposition to find the minimal value of an arbitrary cost function (ground state energy). Random optimization problems provide a natural testbed to compare its efficiency with that of classical algorithms. These problems correspond to mean field spin glasses that have been extensively studied in the classical case. This paper reviews recent analytical works that extended these studies to incorporate the effect of quantum fluctuations, and presents also some original results in this direction.

Related papers

High-performance Energy Minimization with Applications to Adiabatic Quantum Computing

Héctor J. García, Igor L. Markov

Energy minimization of Ising spin-glasses has played a central role in statistical and solid-state physics, facilitating studies of phase transitions and magnetism. Recent proposals suggest using Ising spin-glasses for non-traditional computing as a way to harness the nature's ability to find min-energy configurations, and to take advantage of quantum tunneling to boost combinatorial optimization. Laboratory demonstrations have been unconvincing so far and lack a non-quantum baseline for definitive comparisons. In this work we (i) design and evaluate new computational techniques to simulate natural energy minimization in spin glasses and (ii) explore their application to study design alternatives in quantum adiabatic computers. Unlike previous work, our algorithms are not limited to planar Ising topologies. In one CPU-day, our branch-and-bound algorithm finds ground states on 100 spins, while our local search approximates ground states on 1, 000, 000 spins. We use this computational tool as a simulator to study the significance of hyper-couplings in the context of recently implemented adiabatic quantum computers.

arXiv:0912.3912•Dec 19, 2009•1 citation

Quantum Annealing, Spin Glasses, Optimization and Analog Quantum Computation

Arnab Das, Bikas K. Chakrabarti

We review here the recent success in annealing or optimizing the cost functions of complex systems utilizing quantum fluctuations rather than the classical (thermal) fluctuations. These are introduced through studies of mapping of such computationally hard problems to classical spin glass problems, quantum spin glasses and consequent annealing or analog quantum computation.

Statistical science and interdisciplinary research•Nov 1, 2009•0 citations

Dynamics of quantum adiabatic evolution algorithm for Number Partitioning

Vadim Smelyanskiy, U. von Toussaint, Doǧan A. Timuçin

We have developed a general technique to study the dynamics of the quantum adiabatic evolution algorithm applied to random combinatorial optimization problems in the asymptotic limit of large problem size $n$. We use as an example the NP-complete Number Partitioning problem and map the algorithm dynamics to that of an auxilary quantum spin glass system with the slowly varying Hamiltonian. We use a Green function method to obtain the adiabatic eigenstates and the minimum excitation gap, $g_{\rm min}={\cal O}(n 2^{-n/2})$, corresponding to the exponential complexity of the algorithm for Number Partitioning. The key element of the analysis is the conditional energy distribution computed for the set of all spin configurations generated from a given (ancestor) configuration by simulteneous fipping of a fixed number of spins. For the problem in question this distribution is shown to depend on the ancestor spin configuration only via a certain parameter related to the energy of the configuration. As the result, the algorithm dynamics can be described in terms of one-dimenssional quantum diffusion in the energy space. This effect provides a general limitation on the power of a quantum adiabatic computation in random optimization problems. Analytical results are in agreement with the numerical simulation of the algorithm.

arXiv:quant-ph/0202155•Feb 26, 2002•25 citations

Adiabatic bottlenecks in quantum annealing and nonequilibrium dynamics of paramagnons

Tim Bode, Frank K. Wilhelm

The correspondence between long-range interacting quantum spin glasses and combinatorial optimization problems underpins the physical motivation for adiabatic quantum computing. On one hand, in disordered (quantum) spin systems, the focus is on exact methods such as the replica trick that allow the calculation of system quantities in the limit of infinite system and ensemble size. On the other hand, when solving a given instance of an optimization problem, disorder-averaged quantities are of no relevance, as one is solely interested in instance-specific, finite-size properties, in particular the optimal solution. Here, we apply the nonequilibrium Green's function formalism to the spin coherent-state path integral to obtain the statistical fluctuations and the collective-excitation spectrum along the annealing path. For the example of the quantum Sherrington-Kirkpatrick spin glass, by comparing to extensive numerically exact results, we show that this method provides access to the instance-specific bottlenecks of the annealing protocol.

arXiv:2403.11548•Physical Review A•Jul 12, 2024•6 citations

Quantum adiabatic algorithms and large spin tunnelling

A. Boulatov, Vadim Smelyanskiy

We study the quantum adiabatic evolution algorithm with different evolution paths that correspond to different control Hamiltonians $H(\ensuremath{\tau})$ sampled from a random ensemble. The algorithm is applied to a random binary optimization problem where the cost function is symmetric with respect to the permutation of individual bits. We investigate the method proposed by Farhi et al. when different evolution paths preserve the bit symmetry of the control Hamiltonians $H(\ensuremath{\tau})$ and are generated by an ensemble of random $8\ifmmode\times\else\texttimes\fi{}8$ matrices. In this case, the algorithm dynamics is completely described in terms of the motion of a spin-n/2 system. We show that different evolution paths can be parametrized by a small number of independent parameters that are expansion coefficients of $H(\ensuremath{\tau})$ in a certain universal set of operators. One of these operators is responsible for avoiding the tunnelling for the spin-n/2 system and the corresponding coefficient determines the algorithm complexity for a given problem instance. We show that any problem instance can be solved in polynomial time by applying one of the two universal path modifications (due to the possible reflection symmetry of the problem). We show that a successful evolution path of the algorithm always corresponds to the trajectory of a classical spin $n/2$ and provide a complete characterization of such paths.

arXiv:quant-ph/0309150•Physical Review A•Dec 24, 2003•19 citations

Numerical Studies of the Quantum Adiabatic Algorithm

A. P. Young, Itay Hen

Quantum annealers promise to solve practical optimization problems potentially faster than conventional classical computers. One of the major ongoing debates in this context pertains to their robustness against the decohering effects of finite temperature and interactions with the environment. We argue that even in an ideal setting of very low temperatures and in the absence of a decohering environment, quantum annealers do not necessarily perform better than classical heuristic solvers. Here, we numerically study the performance of the quantum adiabatic algorithm (QAA) on a variety of constraint satisfaction problems and a spin glass problem by studying the size dependence of the minimum energy gap during the evolution of the QAA. We do so by employing Quantum Monte Carlo schemes as these allow us to study these problems at much larger scales than exact methods would allow. We find that in all cases a quantum phase transition occurs and the minimum gap decreases exponentially with system size, leading to an exponentially large running time for the QAA. Based on these and other results, we briefly discuss potential modifications to the QAA that may improve the scaling of the minimum gap, leading to faster quantum adiabatic algorithms.

Journal of Physics Conference Series•Sep 28, 2015•0 citations
Among various algorithms designed to exploit the specific properties of quantum computers with respect to classical ones, the quantum adiabatic algorithm is a versatile proposition to find the minimal value of an arbitrary cost function (ground state energy). Random optimization problems provide a natural testbed to compare its efficiency with that of classical algorithms. These problems correspond to mean field spin glasses that have been extensively studied in the classical case. This paper reviews recent analytical works that extended these studies to incorporate the effect of quantum fluctuations, and presents also some original results in this direction.
Energy minimization of Ising spin-glasses has played a central role in statistical and solid-state physics, facilitating studies of phase transitions and magnetism. Recent proposals suggest using Ising spin-glasses for non-traditional computing as a way to harness the nature's ability to find min-energy configurations, and to take advantage of quantum tunneling to boost combinatorial optimization. Laboratory demonstrations have been unconvincing so far and lack a non-quantum baseline for definitive comparisons. In this work we (i) design and evaluate new computational techniques to simulate natural energy minimization in spin glasses and (ii) explore their application to study design alternatives in quantum adiabatic computers. Unlike previous work, our algorithms are not limited to planar Ising topologies. In one CPU-day, our branch-and-bound algorithm finds ground states on 100 spins, while our local search approximates ground states on 1, 000, 000 spins. We use this computational tool as a simulator to study the significance of hyper-couplings in the context of recently implemented adiabatic quantum computers.
We have developed a general technique to study the dynamics of the quantum adiabatic evolution algorithm applied to random combinatorial optimization problems in the asymptotic limit of large problem size nnn. We use as an example the NP-complete Number Partitioning problem and map the algorithm dynamics to that of an auxilary quantum spin glass system with the slowly varying Hamiltonian. We use a Green function method to obtain the adiabatic eigenstates and the minimum excitation gap, gmin=O(n2−n/2)g_{\rm min}={\cal O}(n 2^{-n/2})gmin​=O(n2−n/2), corresponding to the exponential complexity of the algorithm for Number Partitioning. The key element of the analysis is the conditional energy distribution computed for the set of all spin configurations generated from a given (ancestor) configuration by simulteneous fipping of a fixed number of spins. For the problem in question this distribution is shown to depend on the ancestor spin configuration only via a certain parameter related to the energy of the configuration. As the result, the algorithm dynamics can be described in terms of one-dimenssional quantum diffusion in the energy space. This effect provides a general limitation on the power of a quantum adiabatic computation in random optimization problems. Analytical results are in agreement with the numerical simulation of the algorithm.
The correspondence between long-range interacting quantum spin glasses and combinatorial optimization problems underpins the physical motivation for adiabatic quantum computing. On one hand, in disordered (quantum) spin systems, the focus is on exact methods such as the replica trick that allow the calculation of system quantities in the limit of infinite system and ensemble size. On the other hand, when solving a given instance of an optimization problem, disorder-averaged quantities are of no relevance, as one is solely interested in instance-specific, finite-size properties, in particular the optimal solution. Here, we apply the nonequilibrium Green's function formalism to the spin coherent-state path integral to obtain the statistical fluctuations and the collective-excitation spectrum along the annealing path. For the example of the quantum Sherrington-Kirkpatrick spin glass, by comparing to extensive numerically exact results, we show that this method provides access to the instance-specific bottlenecks of the annealing protocol.
We study the quantum adiabatic evolution algorithm with different evolution paths that correspond to different control Hamiltonians $H(\ensuremath{\tau})$ sampled from a random ensemble. The algorithm is applied to a random binary optimization problem where the cost function is symmetric with respect to the permutation of individual bits. We investigate the method proposed by Farhi et al. when different evolution paths preserve the bit symmetry of the control Hamiltonians $H(\ensuremath{\tau})$ and are generated by an ensemble of random $8\ifmmode\times\else\texttimes\fi{}8$ matrices. In this case, the algorithm dynamics is completely described in terms of the motion of a spin-n/2 system. We show that different evolution paths can be parametrized by a small number of independent parameters that are expansion coefficients of $H(\ensuremath{\tau})$ in a certain universal set of operators. One of these operators is responsible for avoiding the tunnelling for the spin-n/2 system and the corresponding coefficient determines the algorithm complexity for a given problem instance. We show that any problem instance can be solved in polynomial time by applying one of the two universal path modifications (due to the possible reflection symmetry of the problem). We show that a successful evolution path of the algorithm always corresponds to the trajectory of a classical spin n/2n/2n/2 and provide a complete characterization of such paths.
Quantum annealers promise to solve practical optimization problems potentially faster than conventional classical computers. One of the major ongoing debates in this context pertains to their robustness against the decohering effects of finite temperature and interactions with the environment. We argue that even in an ideal setting of very low temperatures and in the absence of a decohering environment, quantum annealers do not necessarily perform better than classical heuristic solvers. Here, we numerically study the performance of the quantum adiabatic algorithm (QAA) on a variety of constraint satisfaction problems and a spin glass problem by studying the size dependence of the minimum energy gap during the evolution of the QAA. We do so by employing Quantum Monte Carlo schemes as these allow us to study these problems at much larger scales than exact methods would allow. We find that in all cases a quantum phase transition occurs and the minimum gap decreases exponentially with system size, leading to an exponentially large running time for the QAA. Based on these and other results, we briefly discuss potential modifications to the QAA that may improve the scaling of the minimum gap, leading to faster quantum adiabatic algorithms.