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:0912.3912

High-performance Energy Minimization with Applications to Adiabatic Quantum Computing

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

Published Dec 19, 2009• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.0912.3912

Related papers

Spinto: high-performance energy minimization in spin glasses

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

Abstract—With the prospect of atomic-scale computing, we study cumulative energy profiles of spin-spin interactions in nonferromagnetic lattices (Ising spin-glasses)—an established topic in solid-state physics that is now becoming relevant to atomicscale EDA. Recent proposals suggest non-traditional computing devices based on nature’s ability to find min-energy states. Spinto utilizes EDA-inspired high-performance algorithms to (i) simulate natural energy minimization in spin systems and (ii) study its potential for solving hard computational problems. Unlike previous work, our algorithms are not limited to planar Ising topologies. In one CPU-day, our branch-and-bound algorithm finds min-energy (ground) states on 100 spins, while our local search approximates ground states on 1,000, 000 spins. We use this computational tool to study the significance of hyper-couplings in the context of recently implemented adiabatic quantum computers. I.

Design, Automation, and Test in Europe•Mar 8, 2010•1 citation

Spinto: High-performance energy minimization in spin glasses

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

With the prospect of atomic-scale computing, we study cumulative energy profiles of spin-spin interactions in non-ferromagnetic lattices (Ising spin-glasses)-an established topic in solid-state physics that is now becoming relevant to atomic-scale EDA. Recent proposals suggest non-traditional computing devices based on nature's ability to find min-energy states. Spinto utilizes EDA-inspired high-performance algorithms to (i) simulate natural energy minimization in spin systems and (ii) study its potential for solving hard computational problems. Unlike previous work, our algorithms are not limited to planar Ising topologies. In one CPU-day, our branch-and-bound algorithm finds min-energy (ground) states on 100 spins, while our local search approximates ground states on 1,000,000 spins. We use this computational tool to study the significance of hyper-couplings in the context of recently implemented adiabatic quantum computers.

Design, Automation, and Test in Europe•Mar 1, 2010•3 citations

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

Victor Bapst, Laura Foini, Florent Krząkała +2 more

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.

•Oct 2, 2012•123 citations

Entanglement as a resource in adiabatic quantum optimization

Bela Bauer, Lei Wang, Iztok Pižorn +1 more

We explore the role of entanglement in adiabatic quantum optimization by performing approximate simulations of the real-time evolution of a quantum system while limiting the amount of entanglement. To classically simulate the time evolution of the system with a limited amount of entanglement, we represent the quantum state using matrix-product states and projected entangled-pair states. We show that the probability of finding the ground state of an Ising spin glass on either a planar or non-planar two-dimensional graph increases rapidly as the amount of entanglement in the state is increased. Furthermore, we propose evolution in complex time as a way to improve simulated adiabatic evolution and mimic the effects of thermal cooling of the quantum annealer.

arXiv:1501.06914•Jan 27, 2015•20 citations

Decoupling of the QAOA into independent spin-boson systems and high-depth performance on pure and mixed spin glasses

Sami Boulebnane, Abid Khan, Pragna Subrahmanya +4 more

The Quantum Approximate Optimization Algorithm (QAOA) is regarded as a promising candidate for near-term quantum advantage in combinatorial optimization, yet our ability to study it at scale is limited. Exact recursive formulas have been introduced for predicting QAOA performance on large spin glasses, but the computational cost of evaluating them grows exponentially with the number of QAOA layers, preventing the study of QAOA in the promising high-depth regime. In this work, we show that for the task of computing QAOA energy on any mixed dense spin glass problem, spins approximately decouple into independent spin-boson systems. In the infinite-size limit, the decoupling becomes exact, establishing the spin-boson mapping as a natural framework for the many-body physics of QAOA. This generalized spin-boson mapping gives a recursive procedure for computing QAOA energies that can be executed at modest cost using tensor networks. As a numerical application, we optimize QAOA on pure and mixed spin glasses at depths intractable for prior techniques, observing that higher-degree problems require more layers for a comparable approximation ratio while angle optimization becomes more challenging. While decoupling enables the evaluations of QAOA energies at large size and depth, it does not enable strong simulation of QAOA; a quantum computer is required to sample the bitstring corresponding to the predicted energy.

quant-pharXiv:2609.40309•Oct 1, 2026•1 citation

Classical and Quantum Computation in Ground States and Beyond

Elizabeth Crosson

In this dissertation we study classical and quantum spin systems with applications to the theory of computation. In particular, we examine computational aspects of these systems beyond their ground states by considering the effects of non-zero temperatures and excited energy states. In the first part we show that universal classical computations can be encoded into equilibrium thermal states of classical spin systems, at sufficiently low temperatures which are independent of the system size. In the second part we explore different strategies for optimization with the quantum adiabatic algorithm, and we show that it is possible to increase the success probability for hard random instances by following the counterintuitive strategy of evolving along the Hamiltonian path more rapidly. In the third part we examine the performance of simulated quantum annealing in finding the minimum of an energy function which contains a high energy barrier, and we provide evidence that simulated quantum annealing inherits some of the advantages of quantum annealing which allow it to pass through the high barrier and minimize the energy function efficiently. In the last part we show that the path-integral quantum Monte Carlo method leads to a provably efficient algorithm for approximating the partition function of any 1D generalized transverse Ising spin chain (with position-dependent local fields and frustrated interactions), at temperatures which are independent of the system size.

•Sep 29, 2015•1 citation
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.
Abstract—With the prospect of atomic-scale computing, we study cumulative energy profiles of spin-spin interactions in nonferromagnetic lattices (Ising spin-glasses)—an established topic in solid-state physics that is now becoming relevant to atomicscale EDA. Recent proposals suggest non-traditional computing devices based on nature’s ability to find min-energy states. Spinto utilizes EDA-inspired high-performance algorithms to (i) simulate natural energy minimization in spin systems and (ii) study its potential for solving hard computational problems. Unlike previous work, our algorithms are not limited to planar Ising topologies. In one CPU-day, our branch-and-bound algorithm finds min-energy (ground) states on 100 spins, while our local search approximates ground states on 1,000, 000 spins. We use this computational tool to study the significance of hyper-couplings in the context of recently implemented adiabatic quantum computers. I.
With the prospect of atomic-scale computing, we study cumulative energy profiles of spin-spin interactions in non-ferromagnetic lattices (Ising spin-glasses)-an established topic in solid-state physics that is now becoming relevant to atomic-scale EDA. Recent proposals suggest non-traditional computing devices based on nature's ability to find min-energy states. Spinto utilizes EDA-inspired high-performance algorithms to (i) simulate natural energy minimization in spin systems and (ii) study its potential for solving hard computational problems. Unlike previous work, our algorithms are not limited to planar Ising topologies. In one CPU-day, our branch-and-bound algorithm finds min-energy (ground) states on 100 spins, while our local search approximates ground states on 1,000,000 spins. We use this computational tool to study the significance of hyper-couplings in the context of recently implemented adiabatic quantum computers.
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.
We explore the role of entanglement in adiabatic quantum optimization by performing approximate simulations of the real-time evolution of a quantum system while limiting the amount of entanglement. To classically simulate the time evolution of the system with a limited amount of entanglement, we represent the quantum state using matrix-product states and projected entangled-pair states. We show that the probability of finding the ground state of an Ising spin glass on either a planar or non-planar two-dimensional graph increases rapidly as the amount of entanglement in the state is increased. Furthermore, we propose evolution in complex time as a way to improve simulated adiabatic evolution and mimic the effects of thermal cooling of the quantum annealer.
The Quantum Approximate Optimization Algorithm (QAOA) is regarded as a promising candidate for near-term quantum advantage in combinatorial optimization, yet our ability to study it at scale is limited. Exact recursive formulas have been introduced for predicting QAOA performance on large spin glasses, but the computational cost of evaluating them grows exponentially with the number of QAOA layers, preventing the study of QAOA in the promising high-depth regime. In this work, we show that for the task of computing QAOA energy on any mixed dense spin glass problem, spins approximately decouple into independent spin-boson systems. In the infinite-size limit, the decoupling becomes exact, establishing the spin-boson mapping as a natural framework for the many-body physics of QAOA. This generalized spin-boson mapping gives a recursive procedure for computing QAOA energies that can be executed at modest cost using tensor networks. As a numerical application, we optimize QAOA on pure and mixed spin glasses at depths intractable for prior techniques, observing that higher-degree problems require more layers for a comparable approximation ratio while angle optimization becomes more challenging. While decoupling enables the evaluations of QAOA energies at large size and depth, it does not enable strong simulation of QAOA; a quantum computer is required to sample the bitstring corresponding to the predicted energy.
In this dissertation we study classical and quantum spin systems with applications to the theory of computation. In particular, we examine computational aspects of these systems beyond their ground states by considering the effects of non-zero temperatures and excited energy states. In the first part we show that universal classical computations can be encoded into equilibrium thermal states of classical spin systems, at sufficiently low temperatures which are independent of the system size. In the second part we explore different strategies for optimization with the quantum adiabatic algorithm, and we show that it is possible to increase the success probability for hard random instances by following the counterintuitive strategy of evolving along the Hamiltonian path more rapidly. In the third part we examine the performance of simulated quantum annealing in finding the minimum of an energy function which contains a high energy barrier, and we provide evidence that simulated quantum annealing inherits some of the advantages of quantum annealing which allow it to pass through the high barrier and minimize the energy function efficiently. In the last part we show that the path-integral quantum Monte Carlo method leads to a provably efficient algorithm for approximating the partition function of any 1D generalized transverse Ising spin chain (with position-dependent local fields and frustrated interactions), at temperatures which are independent of the system size.