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

Physics Procedia

Statistical Analysis for Quantum Adiabatic Computations: Quantum Monte Carlo Annealing

T. Neuhaus

Published Jan 1, 2011• 0 citations
Publisher

Abstract

Quantum adiabatic computations are designed to determine the ground state configurations of an classical problem Hamiltonian H3SAT within quantum theory and at imaginary time allow statistical mechanics studies for the computational e_ciency of the ground state search. We mention a recent determination of the quantum complexity, i.e. the mass-gap _mGAP for a specific ensemble of three-satisfiability (3SAT) problems with a unique satisfiability assignment, which shows an exponential increase of the gap correlation length _GAP with _GAP = 1=_mGAP. In 3SAT we present numerical data for the behavior of quantum Monte Carlo annealing cycles in search for the ground state. The findings show, that for the specific set of realizations quantum Monte Carlo searches in 3SAT fail above a sharp cut-o_ Kcut in the complexity K, which exemplifies the intractable nature of 3SAT.

DOI
10.1016/j.phpro.2011.06.002

Related papers

Classical and quantum annealing in the median of three-satisfiability

T. Neuhaus, M. Peschina, Kristel F. L. Michielsen +1 more

We determine the classical and quantum complexities of a specific ensemble of three-satisfiability problems with a unique satisfying assignment for up to $N=100$ and $80$ variables, respectively. In the classical limit, we employ generalized ensemble techniques and measure the time that a Markovian Monte Carlo process spends in searching classical ground states. In the quantum limit, we determine the maximum finite correlation length along a quantum adiabatic trajectory determined by the linear sweep of the adiabatic control parameter in the Hamiltonian composed of the problem Hamiltonian and the constant transverse field Hamiltonian. In the median of our ensemble, both complexities diverge exponentially with the number of variables. Hence, standard, conventional adiabatic quantum computation fails to reduce the computational complexity to polynomial. Moreover, the growth-rate constant in the quantum limit is 3.8 times as large as the one in the classical limit, making classical fluctuations more beneficial than quantum fluctuations in ground-state searches.

arXiv:1103.3656•Physical Review A•Jan 18, 2011•9 citations

Classical and Quantum Annealing in the Median of Three Satisfiability

T. Neuhaus, M. Peschina, Kristel F. L. Michielsen +1 more

We determine the classical and quantum complexities of a specific ensemble of three-satisfiability problems with a unique satisfying assignment for up to N = 100 and N = 80 variables, respectively. In the classical limit we employ generalized ensemble techniques and measure the time that a Markovian Monte Carlo process spends in searching classical ground states. In the quantum limit we determine the maximum finite correlation length along a quantum adiabatic trajectory determined by the linear sweep of the adiabatic control parameter in the Hamiltonian composed of the problem Hamiltonian and the constant transverse field Hamiltonian. In the median of our ensemble both complexities diverge exponentially with the number of variables. Hence, standard, conventional adiabatic quantum computation fails to reduce the computational complexity to polynomial. Moreover, the growth-rate constant in the quantum limit is 3.8 times as large as the one in the classical limit, making classical fluctuations more beneficial than quantum fluctuations in ground-sate searches.

International Conference on Quantum Information•Jan 1, 2011•3 citations

Quantum Searches in a Hard 2SAT Ensemble

Neuhaus Thomas

Using a recently constructed ensemble of hard 2SAT realizations, that has a unique ground-state we calculate for the quantized theory the median gap correlation length values $ξ_{GAP}$ along the direction of the quantum adiabatic control parameter $λ$. We use quantum annealing (QA) with transverse field and a linear time schedule in the adiabatic control parameter $λ$. The gap correlation length diverges exponentially $ξ_{\rm GAP} \propto {\rm exp} [+r_{\rm GAP}N]$ in the median with a rate constant $r_{\rm GAP}=0.553(6)$, while the run time diverges exponentially $τ_{\rm QA} \propto {\rm exp} [+r_{\rm QA}N]$ with $r_{\rm QA}=1.184(16)$. Simulated classical annealing (SA) exhibits a run time rate constant $r_{\rm SA}=0.340(5)$ that is small and thus finds ground-states exponentially faster than QA. There are no quantum speedups in ground state searches on constant energy surfaces that have exponentially large volume. We also determine gap correlation length distribution functions $P(ξ_{\rm GAP})dξ_{\rm GAP} \approx W_k$ over the ensemble that at $N=18$ are close to Weibull functions $W_k$ with $k \approx 1.2$ i.e., the problems show thin catastrophic tails in $ξ_{\rm GAP}$. The inferred success probability distribution functions of the quantum annealer turn out to be bimodal.

arXiv:1412.5460•Dec 17, 2014•2 citations

Monte Carlo Search for Very Hard KSAT Realizations for Use in Quantum Annealing

Neuhaus Thomas

Using powerful Multicanonical Ensemble Monte Carlo methods from statistical physics we explore the realization space of random K satisfiability (KSAT) in search for computational hard problems, most likely the 'hardest problems'. We search for realizations with unique satisfying assignments (USA) at ratio of clause to spin number $α=M/N$ that is minimal. USA realizations are found for $α$-values that approach $α=1$ from above with increasing number of spins $N$. We consider small spin numbers in $2 \le N \le 18$. The ensemble mean exhibits very special properties. We find that the density of states of the first excited state with energy one $Ω_1=g(E=1)$ is consistent with an exponential divergence in $N$: $Ω_1 \propto {\rm exp} [+rN]$. The rate constants for $K=2,3,4,5$ and $K=6$ of KSAT with USA realizations at $α=1$ are determined numerically to be in the interval $r=0.348$ at $K=2$ and $r=0.680$ at $K=6$. These approach the unstructured search value ${\rm ln}2$ with increasing $K$. Our ensemble of hard problems is expected to provide a test bed for studies of quantum searches with Hamiltonians that have the form of general Ising models.

arXiv:1412.5361•Dec 17, 2014•4 citations

Comments on Adiabatic Quantum Algorithms

Mary Beth Ruskai

Recently a method for adiabatic quantum computation has been proposed and there has been considerable speculation about its efficiency for NP-complete problems. Heuristic arguments in its favor are based on the unproven assumption of an eigenvalue gap. We show that, even without the assumption of an eigenvalue gap, other standard arguments can be used to show that a large class of Hamiltonians proposed for adiabatic quantum computation have unique ground states. We also discuss some of the issues which arise in trying to analyze the behavior of the eigenvalue gap. In particular, we propose several mechanisms for modifying to final Hamiltonian to perform an adiabatic search with efficiency comparable to that for 3-SAT. We also propose the use of randomly defined final Hamiltonians as a mechanism for analyzing the generic spectral behavior of the interpolating Hamiltonians associated with problems which lack sufficent structure to be amenable to efficient classical algorithms.

arXiv:quant-ph/0203127•Mar 26, 2002•0 citations

Optimization using quantum mechanics: quantum annealing through adiabatic evolution

Giuseppe E. Santoro, Erio Tosatti

We review here some recent work in the field of quantum annealing, alias adiabatic quantum computation. The idea of quantum annealing is to perform optimization by a quantum adiabatic evolution which tracks the ground state of a suitable time-dependent Hamiltonian, where 'ℏ' is slowly switched off. We illustrate several applications of quantum annealing strategies, starting from textbook toy-models—double-well potentials and other one-dimensional examples, with and without disorder. These examples display in a clear way the crucial differences between classical and quantum annealing. We then discuss applications of quantum annealing to challenging hard optimization problems, such as the random Ising model, the travelling salesman problem and Boolean satisfiability problems. The techniques used to implement quantum annealing are either deterministic Schrödinger's evolutions, for the toy models, or path-integral Monte Carlo and Green's function Monte Carlo approaches, for the hard optimization problems. The crucial role played by disorder and the associated non-trivial Landau–Zener tunnelling phenomena is discussed and emphasized.

Journal of Physics A Mathematical and General•Aug 18, 2006•354 citations
Quantum adiabatic computations are designed to determine the ground state configurations of an classical problem Hamiltonian H3SAT within quantum theory and at imaginary time allow statistical mechanics studies for the computational e_ciency of the ground state search. We mention a recent determination of the quantum complexity, i.e. the mass-gap _mGAP for a specific ensemble of three-satisfiability (3SAT) problems with a unique satisfiability assignment, which shows an exponential increase of the gap correlation length _GAP with _GAP = 1=mGAP. In 3SAT we present numerical data for the behavior of quantum Monte Carlo annealing cycles in search for the ground state. The findings show, that for the specific set of realizations quantum Monte Carlo searches in 3SAT fail above a sharp cut-o Kcut in the complexity K, which exemplifies the intractable nature of 3SAT.
We determine the classical and quantum complexities of a specific ensemble of three-satisfiability problems with a unique satisfying assignment for up to N=100N=100N=100 and 808080 variables, respectively. In the classical limit, we employ generalized ensemble techniques and measure the time that a Markovian Monte Carlo process spends in searching classical ground states. In the quantum limit, we determine the maximum finite correlation length along a quantum adiabatic trajectory determined by the linear sweep of the adiabatic control parameter in the Hamiltonian composed of the problem Hamiltonian and the constant transverse field Hamiltonian. In the median of our ensemble, both complexities diverge exponentially with the number of variables. Hence, standard, conventional adiabatic quantum computation fails to reduce the computational complexity to polynomial. Moreover, the growth-rate constant in the quantum limit is 3.8 times as large as the one in the classical limit, making classical fluctuations more beneficial than quantum fluctuations in ground-state searches.
We determine the classical and quantum complexities of a specific ensemble of three-satisfiability problems with a unique satisfying assignment for up to N = 100 and N = 80 variables, respectively. In the classical limit we employ generalized ensemble techniques and measure the time that a Markovian Monte Carlo process spends in searching classical ground states. In the quantum limit we determine the maximum finite correlation length along a quantum adiabatic trajectory determined by the linear sweep of the adiabatic control parameter in the Hamiltonian composed of the problem Hamiltonian and the constant transverse field Hamiltonian. In the median of our ensemble both complexities diverge exponentially with the number of variables. Hence, standard, conventional adiabatic quantum computation fails to reduce the computational complexity to polynomial. Moreover, the growth-rate constant in the quantum limit is 3.8 times as large as the one in the classical limit, making classical fluctuations more beneficial than quantum fluctuations in ground-sate searches.
Using a recently constructed ensemble of hard 2SAT realizations, that has a unique ground-state we calculate for the quantized theory the median gap correlation length values ξGAPξ_{GAP}ξGAP​ along the direction of the quantum adiabatic control parameter λλλ. We use quantum annealing (QA) with transverse field and a linear time schedule in the adiabatic control parameter λλλ. The gap correlation length diverges exponentially ξGAP∝exp[+rGAPN]ξ_{\rm GAP} \propto {\rm exp} [+r_{\rm GAP}N]ξGAP​∝exp[+rGAP​N] in the median with a rate constant rGAP=0.553(6)r_{\rm GAP}=0.553(6)rGAP​=0.553(6), while the run time diverges exponentially τQA∝exp[+rQAN]τ_{\rm QA} \propto {\rm exp} [+r_{\rm QA}N]τQA​∝exp[+rQA​N] with rQA=1.184(16)r_{\rm QA}=1.184(16)rQA​=1.184(16). Simulated classical annealing (SA) exhibits a run time rate constant rSA=0.340(5)r_{\rm SA}=0.340(5)rSA​=0.340(5) that is small and thus finds ground-states exponentially faster than QA. There are no quantum speedups in ground state searches on constant energy surfaces that have exponentially large volume. We also determine gap correlation length distribution functions P(ξGAP)dξGAP≈WkP(ξ_{\rm GAP})dξ_{\rm GAP} \approx W_kP(ξGAP​)dξGAP​≈Wk​ over the ensemble that at N=18N=18N=18 are close to Weibull functions WkW_kWk​ with k≈1.2k \approx 1.2k≈1.2 i.e., the problems show thin catastrophic tails in ξGAPξ_{\rm GAP}ξGAP​. The inferred success probability distribution functions of the quantum annealer turn out to be bimodal.
Using powerful Multicanonical Ensemble Monte Carlo methods from statistical physics we explore the realization space of random K satisfiability (KSAT) in search for computational hard problems, most likely the 'hardest problems'. We search for realizations with unique satisfying assignments (USA) at ratio of clause to spin number α=M/Nα=M/Nα=M/N that is minimal. USA realizations are found for ααα-values that approach α=1α=1α=1 from above with increasing number of spins NNN. We consider small spin numbers in 2≤N≤182 \le N \le 182≤N≤18. The ensemble mean exhibits very special properties. We find that the density of states of the first excited state with energy one Ω1=g(E=1)Ω_1=g(E=1)Ω1​=g(E=1) is consistent with an exponential divergence in NNN: Ω1∝exp[+rN]Ω_1 \propto {\rm exp} [+rN]Ω1​∝exp[+rN]. The rate constants for K=2,3,4,5K=2,3,4,5K=2,3,4,5 and K=6K=6K=6 of KSAT with USA realizations at α=1α=1α=1 are determined numerically to be in the interval r=0.348r=0.348r=0.348 at K=2K=2K=2 and r=0.680r=0.680r=0.680 at K=6K=6K=6. These approach the unstructured search value ln2{\rm ln}2ln2 with increasing KKK. Our ensemble of hard problems is expected to provide a test bed for studies of quantum searches with Hamiltonians that have the form of general Ising models.
Recently a method for adiabatic quantum computation has been proposed and there has been considerable speculation about its efficiency for NP-complete problems. Heuristic arguments in its favor are based on the unproven assumption of an eigenvalue gap. We show that, even without the assumption of an eigenvalue gap, other standard arguments can be used to show that a large class of Hamiltonians proposed for adiabatic quantum computation have unique ground states. We also discuss some of the issues which arise in trying to analyze the behavior of the eigenvalue gap. In particular, we propose several mechanisms for modifying to final Hamiltonian to perform an adiabatic search with efficiency comparable to that for 3-SAT. We also propose the use of randomly defined final Hamiltonians as a mechanism for analyzing the generic spectral behavior of the interpolating Hamiltonians associated with problems which lack sufficent structure to be amenable to efficient classical algorithms.
We review here some recent work in the field of quantum annealing, alias adiabatic quantum computation. The idea of quantum annealing is to perform optimization by a quantum adiabatic evolution which tracks the ground state of a suitable time-dependent Hamiltonian, where 'ℏ' is slowly switched off. We illustrate several applications of quantum annealing strategies, starting from textbook toy-models—double-well potentials and other one-dimensional examples, with and without disorder. These examples display in a clear way the crucial differences between classical and quantum annealing. We then discuss applications of quantum annealing to challenging hard optimization problems, such as the random Ising model, the travelling salesman problem and Boolean satisfiability problems. The techniques used to implement quantum annealing are either deterministic Schrödinger's evolutions, for the toy models, or path-integral Monte Carlo and Green's function Monte Carlo approaches, for the hard optimization problems. The crucial role played by disorder and the associated non-trivial Landau–Zener tunnelling phenomena is discussed and emphasized.