Phase transitions and random quantum satisfiability

M. R. Garey and D. S. Johnson, Computers and Intractability : A Guide to the Theory of NP-Completeness , Series of Books in the Mathematical Sciences (W. H. Freeman & Co Ltd, 1979)

1979

Earlier work this paper cites.

S. Kirkpatrick and B. Selman, Science 264

1994

Earlier work this paper cites.

R. Monasson and R. Zecchina, Phys. Rev. E 56

1997

Earlier work this paper cites.

S. L. Sondhi, S. M. Girvin, J. P. Carini, and D. Shahar, Rev. Mod. Phys. 69

1997

Earlier work this paper cites.

A. Y. Kitaev, in AQIP’99 (DePaul University, 1999)

1999

Earlier work this paper cites.

R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky, Nature 400

1999

Earlier work this paper cites.

S. Sachdev, Quantum Phase Transitions (Cambridge University Press, Cambridge, UK, 2001)

2001

Cited alongside, same era.

E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, Science 292

2001

Cited alongside, same era.

A. Y. Kitaev, A. Shen, and M. N. Vyalyi, Classical and quantum computation , vol. 47 of Graduate studies in mathematics (American Mathematical Society, Providence, R.I., 2002)

2002

Cited alongside, same era.

M. Mezard, G. Parisi, and R. Zecchina, Science 297

2002

Cited alongside, same era.

M. Mézard, F. Ricci-Tersenghi, and R. Zecchina, J. Stat. Phys. 111

2003

Cited alongside, same era.

M. Molloy, Random Struct. Algorithms 27

2005

Cited alongside, same era.

S. Bravyi, arXiv (2006), eprint quant-ph/0602108

2006

Later among the works it cites.

F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborová, Proceedings of the National Academy of Sciences 104

2007

Later among the works it cites.

M. B. Hastings, Phys. Rev. B 76

2007

Later among the works it cites.

C. Laumann, A. Scardicchio, and S. L. Sondhi, Phys. Rev. B 78

2008

Later among the works it cites.

M. Leifer and D. Poulin, Ann. Phys. 323

2008

Later among the works it cites.

F. Altarelli, R. Monasson, G. Semerjian, and F. Zamponi, in Handbook of Satisfiability (IOS press, 2009), vol. 185 of Frontiers in Artificial Intelligence and Applications , eprint arXiv:0802.1829

Original

2009