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.5361

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

Neuhaus Thomas

Published Dec 17, 2014• 4 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1412.5361

Related papers

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 $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

Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses

Mingyou Wu

The random k-SAT instances undergo a "phase transition" from being generally satisfiable to unsatisfiable as the clause number m passes a critical threshold, $r_k n$. This causes a drastic reduction in the number of satisfying assignments, shifting the problem from being generally solvable on classical computers to typically insolvable. Beyond this threshold, it is challenging to comprehend the computational complexity of random k-SAT. In quantum computing, Grover's search still yields exponential time requirements due to the neglect of structural information. Leveraging the structure inherent in search problems, we propose the k-local quantum search algorithm, which extends quantum search to structured scenarios. Grover's search, by contrast, addresses the unstructured case where k=n. Given that the search algorithm necessitates the presence of a target, we specifically focus on the problem of searching the interpretation of satisfiable instances of k-SAT, denoted as max-k-SSAT. If this problem is solvable in polynomial time, then k-SAT can also be solved within the same complexity. We demonstrate that, for small $k \ge 3$, any small $ε>0$ and sufficiently large n: $\cdot$ k-local quantum search achieves general efficiency on random instances of max-k-SSAT with $m=Ω(n^{2+δ+ε})$ using $\mathcal{O}(n)$ iterations, and $\cdot$ k-local adiabatic quantum search enhances the bound to $m=Ω(n^{1+δ+ε})$ within an evolution time of $\mathcal{O}(n^2)$. In both cases, the circuit complexity of each iteration is $\mathcal{O}(n^k)$, and the efficiency is assured with overwhelming probability $1 - \mathcal{O}(\mathrm{erfc}(n^{δ/2}))$. By modifying this algorithm capable of solving all instances of max-k-SSAT, we further prove that max-k-SSAT is polynomial on average when $m=Ω(n^{2+ε})$ based on the average-case complexity theory.

arXiv:2403.03237•Mar 5, 2024•1 citation

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

Random quantum satisfiability

Chris R. Laumann, Roderich Moessner, A. Scarddichio +1 more

Alongside the effort underway to build quantum computers, it is important to better understand which classes of problems they will find easy and which others even they will find intractable. We study random ensembles of the QMA$_1$-complete quantum satisfiability (QSAT) problem introduced by Bravyi \cite{Bravyi:2006p4315}. QSAT appropriately generalizes the NP-complete classical satisfiability (SAT) problem. We show that, as the density of clauses/projectors is varied, the ensembles exhibit quantum phase transitions between phases that are satisfiable and unsatisfiable. Remarkably, almost all instances of QSAT for \emph{any} hypergraph exhibit the same dimension of the satisfying manifold. This establishes the QSAT decision problem as equivalent to a, potentially new, graph theoretic problem and that the hardest typical instances are likely to be localized in a bounded range of clause density.

Quantum Information and Computation•Jan 1, 2010•19 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
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.
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.
Local Quantum Search Algorithm for Random kkk-SAT with Ω(n1+ε)Ω(n^{1+ε})Ω(n1+ε) Clauses
The random k-SAT instances undergo a "phase transition" from being generally satisfiable to unsatisfiable as the clause number m passes a critical threshold, rknr_k nrk​n. This causes a drastic reduction in the number of satisfying assignments, shifting the problem from being generally solvable on classical computers to typically insolvable. Beyond this threshold, it is challenging to comprehend the computational complexity of random k-SAT. In quantum computing, Grover's search still yields exponential time requirements due to the neglect of structural information. Leveraging the structure inherent in search problems, we propose the k-local quantum search algorithm, which extends quantum search to structured scenarios. Grover's search, by contrast, addresses the unstructured case where k=n. Given that the search algorithm necessitates the presence of a target, we specifically focus on the problem of searching the interpretation of satisfiable instances of k-SAT, denoted as max-k-SSAT. If this problem is solvable in polynomial time, then k-SAT can also be solved within the same complexity. We demonstrate that, for small k≥3k \ge 3k≥3, any small ε>0ε>0ε>0 and sufficiently large n: ⋅\cdot⋅ k-local quantum search achieves general efficiency on random instances of max-k-SSAT with m=Ω(n2+δ+ε)m=Ω(n^{2+δ+ε})m=Ω(n2+δ+ε) using O(n)\mathcal{O}(n)O(n) iterations, and ⋅\cdot⋅ k-local adiabatic quantum search enhances the bound to m=Ω(n1+δ+ε)m=Ω(n^{1+δ+ε})m=Ω(n1+δ+ε) within an evolution time of O(n2)\mathcal{O}(n^2)O(n2). In both cases, the circuit complexity of each iteration is O(nk)\mathcal{O}(n^k)O(nk), and the efficiency is assured with overwhelming probability 1−O(erfc(nδ/2))1 - \mathcal{O}(\mathrm{erfc}(n^{δ/2}))1−O(erfc(nδ/2)). By modifying this algorithm capable of solving all instances of max-k-SSAT, we further prove that max-k-SSAT is polynomial on average when m=Ω(n2+ε)m=Ω(n^{2+ε})m=Ω(n2+ε) based on the average-case complexity theory.
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.
Alongside the effort underway to build quantum computers, it is important to better understand which classes of problems they will find easy and which others even they will find intractable. We study random ensembles of the QMA1_11​-complete quantum satisfiability (QSAT) problem introduced by Bravyi \cite{Bravyi:2006p4315}. QSAT appropriately generalizes the NP-complete classical satisfiability (SAT) problem. We show that, as the density of clauses/projectors is varied, the ensembles exhibit quantum phase transitions between phases that are satisfiable and unsatisfiable. Remarkably, almost all instances of QSAT for \emph{any} hypergraph exhibit the same dimension of the satisfying manifold. This establishes the QSAT decision problem as equivalent to a, potentially new, graph theoretic problem and that the hardest typical instances are likely to be localized in a bounded range of clause density.
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.