Fetching the paper…

Reading the bibliography…

Classical and Quantum Annealing in the Median of Three Satisfiability · Around

2011

Classical and Quantum Annealing in the Median of Three Satisfiability

Neuhaus, T., Peschina, M., Michielsen, K. et al.

Original
PDF
Post on X

Understand

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.

Built on

L. D. Landau, Phys. Z. Sowjetunion 2
1932
Earlier work this paper cites.
S. A. Cook, Proc. Third Annual ACM Symposium on the Theory of Computing, (ACM, New York, 1971) 151
1971
Earlier work this paper cites.
M. Suzuki, S. Miyashita, and A. Kuroda, Prog. Theor. Phys. 58
1977
Earlier work this paper cites.
S. Coleman, The Uses of Instantons
Original
1977
Earlier work this paper cites.
K. Binder, Phys. Rev. A 25
1982
Earlier work this paper cites.
B. A. Berg and T. Neuhaus, Phys. Rev. Lett. 68
1992
Earlier work this paper cites.
T. Kadowaki and H. Nishimori, Phys. Rev. E 58
1998
Earlier work this paper cites.

Similar

R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky, Nature 400
1999
Cited alongside, same era.
L. K. Grover, Am. J. Phys. 69
2001
Cited alongside, same era.
E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, arXiv:quant-ph/0001106, (2001); E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, Science 292
2001
Cited alongside, same era.
F. Wang and D. P. Landau, Phys. Rev. Lett. 86
2001
Cited alongside, same era.
W. van Dam, M. Mosca, and U. Vazirani, How Powerful is Adiabatic Quantum Computation?
2001
Cited alongside, same era.
M. Z̆nidaric̆, Phys. Rev. A 71
2005
Cited alongside, same era.

Then

D. J. Earl and M. W. Deem, Phys. Chem. Chem. Phys. 7
2005
Later among the works it cites.
R. Schützhold and G. Schaller, Phys. Rev. A 74
2006
Later among the works it cites.
M. H. S. Amin and V. Choi, Phys. Rev. A 80
2009
Later among the works it cites.
T. Jörg, F. Krzakala, G. Semerjian, and F. Zamponi, Phys. Rev. Lett. 104
2010
Later among the works it cites.
B. Altshuler, H. Krovi, and J. Roland, PNAS 107
2010
Later among the works it cites.
A. P. Young, S. Knysh, and V. N. Smelyanskiy, Phys. Rev. Lett. 101
2010
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…