Physics – Condensed Matter – Statistical Mechanics
Scientific paper
2011-03-18
Phys. Rev. A 83, 012309 (2011)
Physics
Condensed Matter
Statistical Mechanics
Scientific paper
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.
Michielsen Kristel
Neuhaus Thomas
Peschina M.
Raedt Hans de
No associations
LandOfFree
Classical and Quantum Annealing in the Median of Three Satisfiability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Classical and Quantum Annealing in the Median of Three Satisfiability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Classical and Quantum Annealing in the Median of Three Satisfiability will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-185595