Classical and quantum annealing in the median of three-satisfiability

Neuhaus T, Peschina M, Michielsen K, De Raedt H (2011)
Physical Review A 83(1).

Journal Article | Published | English

No fulltext has been uploaded

Author
; ; ;
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 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.
Publishing Year
ISSN
eISSN
PUB-ID

Cite this

Neuhaus T, Peschina M, Michielsen K, De Raedt H. Classical and quantum annealing in the median of three-satisfiability. Physical Review A. 2011;83(1).
Neuhaus, T., Peschina, M., Michielsen, K., & De Raedt, H. (2011). Classical and quantum annealing in the median of three-satisfiability. Physical Review A, 83(1).
Neuhaus, T., Peschina, M., Michielsen, K., and De Raedt, H. (2011). Classical and quantum annealing in the median of three-satisfiability. Physical Review A 83.
Neuhaus, T., et al., 2011. Classical and quantum annealing in the median of three-satisfiability. Physical Review A, 83(1).
T. Neuhaus, et al., “Classical and quantum annealing in the median of three-satisfiability”, Physical Review A, vol. 83, 2011.
Neuhaus, T., Peschina, M., Michielsen, K., De Raedt, H.: Classical and quantum annealing in the median of three-satisfiability. Physical Review A. 83, (2011).
Neuhaus, Thomas, Peschina, M., Michielsen, K., and De Raedt, H. “Classical and quantum annealing in the median of three-satisfiability”. Physical Review A 83.1 (2011).
This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Sources

arXiv 1103.3656

Search this title in

Google Scholar