Quantum Searches in a Hard 2SAT Ensemble

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 ${\xi }_{GAP}$ along the direction of the quantum adiabatic control parameter $\lambda$. We use quantum annealing (QA) with transverse field and a linear time schedule in the adiabatic control parameter $\lambda$. The gap correlation length diverges exponentially ${\xi }_{\mathrm{GAP}}\propto \exp [+r_{\mathrm{GAP}}N]$ in the median with a rate constant $r_{\mathrm{GAP}}=0.553(6)$, while the run time diverges exponentially ${\tau }_{\mathrm{QA}}\propto \exp [+r_{\mathrm{QA}}N]$ with $r_{\mathrm{QA}}=1.184(16)$. Simulated classical annealing (SA) exhibits a run time rate constant $r_{\mathrm{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({\xi }_{\mathrm{GAP}})d{\xi }_{\mathrm{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 ${\xi }_{\mathrm{GAP}}$. The inferred success probability distribution functions of the quantum annealer turn out to be bimodal.

arXiv commentnone

References in corpus (9)

• Anderson localization casts clouds over adiabatic quantum optimization
• The Scaling Window of the 2-SAT Transition
• Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
• Consistency Tests of Classical and Quantum Models for a Quantum Annealer
• How "Quantum" is the D-Wave Machine?
• Adiabatic Quantum Algorithms for the NP-Complete Maximum-Weight Independent Set, Exact Cover and 3SAT Problems
• Classical signature of quantum annealing
• Monte Carlo Search for Very Hard KSAT Realizations for Use in Quantum Annealing
• Single-solution Random 3-SAT Instances

Cited by in corpus (1)

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