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

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Autor*in
Neuhaus, ThomasUniBi; Peschina, M.; Michielsen, K.; De Raedt, H.
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
2011
Zeitschriftentitel
Physical Review A
Band
83
Ausgabe
1
Art.-Nr.
012309
ISSN
1050-2947
eISSN
1094-1622
Page URI
https://pub.uni-bielefeld.de/record/2003310

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): 012309.
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), 012309. 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:012309.
Neuhaus, T., et al., 2011. Classical and quantum annealing in the median of three-satisfiability. Physical Review A, 83(1): 012309.
T. Neuhaus, et al., “Classical and quantum annealing in the median of three-satisfiability”, Physical Review A, vol. 83, 2011, : 012309.
Neuhaus, T., Peschina, M., Michielsen, K., De Raedt, H.: Classical and quantum annealing in the median of three-satisfiability. Physical Review A. 83, : 012309 (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): 012309.

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