Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

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_{\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 $\tau_{\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(\xi_{\rm GAP})d\xi_{\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
$\xi_{\rm GAP}$. The inferred success probability distribution functions of the
quantum annealer turn out to be bimodal.