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.
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.
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
ξGAP∝exp[+rGAPN] in the median with a rate constant
rGAP=0.553(6), while the run time diverges exponentially
τQA∝exp[+rQAN] with
rQA=1.184(16). Simulated classical annealing (SA) exhibits a run time rate constant
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≈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
ξGAP. The inferred success probability distribution functions of the quantum annealer turn out to be bimodal.
Recently a method for adiabatic quantum computation has been proposed and there has been considerable speculation about its efficiency for NP-complete problems. Heuristic arguments in its favor are based on the unproven assumption of an eigenvalue gap. We show that, even without the assumption of an eigenvalue gap, other standard arguments can be used to show that a large class of Hamiltonians proposed for adiabatic quantum computation have unique ground states. We also discuss some of the issues which arise in trying to analyze the behavior of the eigenvalue gap. In particular, we propose several mechanisms for modifying to final Hamiltonian to perform an adiabatic search with efficiency comparable to that for 3-SAT. We also propose the use of randomly defined final Hamiltonians as a mechanism for analyzing the generic spectral behavior of the interpolating Hamiltonians associated with problems which lack sufficent structure to be amenable to efficient classical algorithms.
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≤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) is consistent with an exponential divergence in
N:
Ω1∝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
ln2 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.
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.