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).

Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Zeitschriftenaufsatz | Veröffentlicht | Englisch
Autor
; ; ;
Abstract / Bemerkung
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.
Erscheinungsjahr
Zeitschriftentitel
Physical Review A
Band
83
Zeitschriftennummer
1
ISSN
eISSN
PUB-ID

Zitieren

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). doi:10.1103/PhysRevA.83.012309
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).

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Quellen

arXiv: 1103.3656

Suchen in

Google Scholar