Classical and Quantum Annealing in the Median of Three Satisfiability
arXiv:1103.3656 · doi:10.1103/PhysRevA.83.012309
Abstract
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.
References in corpus (12)
- An efficient, multiple range random walk algorithm to calculate the density of states
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Multicanonical Ensemble: A New Approach to Simulate First-order Phase Transitions
- Parallel Tempering: Theory, Applications, and New Perspectives
- Anderson localization casts clouds over adiabatic quantum optimization
- First order phase transition in the Quantum Adiabatic Algorithm
- Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
- First Order Quantum Phase Transition in Adiabatic Quantum Computation
- First-order transitions and the performance of quantum algorithms in random optimization problems
- Adiabatic quantum algorithms as quantum phase transitions: first versus second order
- Scaling of running time of quantum adiabatic algorithm for propositional satisfiability