2014/12/17 by Neuhaus Thomas, Thomas, Neuhaus · 1 citation
Computer Science · #FOS: Physical sciences #Neural Networks and Reservoir Computing #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.1412.5460
openalex publication_date 2014/12/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ∝ \rm exp [+r\rm GAPN] in the median with a rate constant r\rm GAP=0.553(6), while the run time diverges exponentially τ\rm QA ∝ \rm exp [+r\rm QAN] 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 ≈ Wk over the ensemble that at N=18 are close to Weibull functions Wk with k ≈ 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.