Classical and Quantum Annealing in the Median of Three Satisfiability

T. Neuhaus, M. Peschina, K. Michielsen, H. De Raedt

Published:

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-state searches.