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

Quantum Searches in a Hard 2SAT Ensemble

Neuhaus Thomas

Published Dec 17, 2014• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1412.5460

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

Statistical Analysis for Quantum Adiabatic Computations: Quantum Monte Carlo Annealing

T. Neuhaus

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.

Physics Procedia•Jan 1, 2011•0 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 annealing showing an exponentially small success probability despite a constant energy gap with polynomial energy

Hiroshi Hayasaka, Takashi Imoto, Yuichiro Matsuzaki +1 more

Quantum annealing (QA) is a method for solving combinatorial optimization problems. We can estimate the computational time for QA using what is referred to as the adiabatic condition derived from the adiabatic theorem. The adiabatic condition consists of two parts: an energy gap and a transition matrix. Most past studies have focused on the relationship between the energy gap and computational time. The success probability of QA is considered to decrease exponentially owing to the exponentially decreasing energy gap at the first-order phase-transition point. In this study, through a detailed analysis of the relationship between the energy gap, transition matrix, and computational cost during QA, we propose a general method for constructing counterintuitive models wherein QA with a constant annealing time fails despite a constant energy gap, based on polynomial energy. We assume that the energy of the total Hamiltonian is at most $\mathrm{\ensuremath{\Theta}}(L)$, where $L$ is the number of qubits. In our formalism, we choose a known model that exhibits an exponentially small energy gap during QA, and modify the model by adding a specific penalty term to the Hamiltonian. In the modified model, the transition matrix in the adiabatic condition becomes exponentially large as the number of qubits increases, while the energy gap remains constant. Moreover, we achieve a quadratic speedup, for which the upper bound for improvement in the adiabatic condition is determined by the polynomial energy. For concrete examples, we consider the adiabatic Grover search and the ferromagnetic $p$-spin model. In these cases, with the addition of the penalty term, although the success probability of QA on the modified models becomes exponentially small despite a constant energy gap, we are able to achieve a success probability considerably higher than that of conventional QA. Moreover, in concrete examples, we numerically show the scaling of the computational cost is quadratically improved compared to the conventional QA. Our findings pave the way for a better understanding of QA performance.

arXiv:2212.09995•Physical Review A•Aug 26, 2024•4 citations

Computational Bottlenecks of Quantum Annealing

Sergey Knysh

A promising approach to solving hard binary optimisation problems is quantum adiabatic annealing (QA) in a transverse magnetic field. An instantaneous ground state --- initially a symmetric superposition of all possible assignments of $N$ qubits --- is closely tracked as it becomes more and more localised near the global minimum of the classical energy. Regions where the energy gap to excited states is small (e.g. at the phase transition) are the algorithm's bottlenecks. Here I show how for large problems the complexity becomes dominated by $O(\log N)$ bottlenecks inside the spin glass phase, where the gap scales as a stretched exponential. For smaller $N$, only the gap at the critical point is relevant, where it scales polynomially, as long as the phase transition is second order. This phenomenon is demonstrated rigorously for the two-pattern Gaussian Hopfield Model. Qualitative comparison with the Sherrington-Kirkpatrick Model leads to similar conclusions.

arXiv:1506.08608•Jun 29, 2015•3 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
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.
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.
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 = 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.
Quantum annealing (QA) is a method for solving combinatorial optimization problems. We can estimate the computational time for QA using what is referred to as the adiabatic condition derived from the adiabatic theorem. The adiabatic condition consists of two parts: an energy gap and a transition matrix. Most past studies have focused on the relationship between the energy gap and computational time. The success probability of QA is considered to decrease exponentially owing to the exponentially decreasing energy gap at the first-order phase-transition point. In this study, through a detailed analysis of the relationship between the energy gap, transition matrix, and computational cost during QA, we propose a general method for constructing counterintuitive models wherein QA with a constant annealing time fails despite a constant energy gap, based on polynomial energy. We assume that the energy of the total Hamiltonian is at most $\mathrm{\ensuremath{\Theta}}(L)$, where LLL is the number of qubits. In our formalism, we choose a known model that exhibits an exponentially small energy gap during QA, and modify the model by adding a specific penalty term to the Hamiltonian. In the modified model, the transition matrix in the adiabatic condition becomes exponentially large as the number of qubits increases, while the energy gap remains constant. Moreover, we achieve a quadratic speedup, for which the upper bound for improvement in the adiabatic condition is determined by the polynomial energy. For concrete examples, we consider the adiabatic Grover search and the ferromagnetic ppp-spin model. In these cases, with the addition of the penalty term, although the success probability of QA on the modified models becomes exponentially small despite a constant energy gap, we are able to achieve a success probability considerably higher than that of conventional QA. Moreover, in concrete examples, we numerically show the scaling of the computational cost is quadratically improved compared to the conventional QA. Our findings pave the way for a better understanding of QA performance.
A promising approach to solving hard binary optimisation problems is quantum adiabatic annealing (QA) in a transverse magnetic field. An instantaneous ground state --- initially a symmetric superposition of all possible assignments of NNN qubits --- is closely tracked as it becomes more and more localised near the global minimum of the classical energy. Regions where the energy gap to excited states is small (e.g. at the phase transition) are the algorithm's bottlenecks. Here I show how for large problems the complexity becomes dominated by O(log⁡N)O(\log N)O(logN) bottlenecks inside the spin glass phase, where the gap scales as a stretched exponential. For smaller NNN, only the gap at the critical point is relevant, where it scales polynomially, as long as the phase transition is second order. This phenomenon is demonstrated rigorously for the two-pattern Gaussian Hopfield Model. Qualitative comparison with the Sherrington-Kirkpatrick Model leads to similar conclusions.
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.