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.
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.
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.
The discrete formulation of adiabatic quantum computing is compared with other search methods, classical and quantum, for random satisfiability (SAT) problems. With the number of steps growing only as the cube of the number of variables, the adiabatic method gives solution probabilities close to 1 for problem sizes feasible to evaluate via simulation on current computers. However, for these sizes the minimum energy gaps of most instances are fairly large, so the good performance scaling seen for small problems may not reflect asymptotic behavior where costs are dominated by tiny gaps. Moreover, the resulting search costs are much higher than for other methods. Variants of the quantum algorithm that do not match the adiabatic limit give lower costs, on average, and slower growth than the conventional GSAT heuristic method.
We study several problems related to properties of non-negative matrices that arise at the boundary between quantum and classical probabilistic computation. Our results are twofold. First, we identify a large class of quantum Hamiltonians describing systems of qubits for which the adiabatic evolution can be efficiently simulated on a classical probabilistic computer. These are stoquastic local Hamiltonians with a "frustration free" ground-state. A Hamiltonian belongs to this class iff it can be represented as
H=∑aHa where (1) every term
Ha acts non-trivially on a constant number of qubits, (2) every term
Ha has real non-positive off-diagonal matrix elements in the standard basis, and (3) the ground-state of
H is a ground-state of every term
Ha. Secondly, we generalize the Cook-Levin theorem proving NP-completeness of the satisfiability problem to the complexity class MA -- a probabilistic analogue of NP. Specifically, we construct a quantum version of the k-SAT problem which we call "stoquastic k-SAT" such that stoquastic k-SAT is contained in MA for any constant
k, and any promise problem in MA is Karp-reducible to stoquastic 6-SAT. This result provides the first non-trivial example of a MA-complete promise problem.
We study several problems related to properties of nonnegative matrices that arise at the boundary between quantum and classical probabilistic computation. Our results are twofold. First, we identify a large class of quantum Hamiltonians describing systems of qubits for which the adiabatic evolution can be efficiently simulated on a classical probabilistic computer. These are stoquastic local Hamiltonians with a “frustration-free” ground-state. A Hamiltonian belongs to this class iff it can be represented as
H=∑aHa where (1) every term
Ha acts nontrivially on a constant number of qubits, (2) every term
Ha has real nonpositive off-diagonal matrix elements in the standard basis, and (3) the ground-state of H is a ground-state of every term
Ha. Second, we generalize the Cook–Levin theorem proving NP-completeness of the satisfiability problem to the complexity class MA (Merlin–Arthur games)—a probabilistic analogue of NP. Specifically, we construct a quantum version of the k-SAT problem which we call “stoquastic k-SAT” such that stoquastic k-SAT is contained in MA for any constant k, and any promise problem in MA is Karp-reducible to stoquastic 6-SAT. This result provides the first nontrivial example of a MA-complete promise problem.