On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm

E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, “A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem”, Science 292

2001

Earlier work this paper cites.

G. E. Santoro, R. Martoňák, E. Tosatti, and R. Car, “Theory of Quantum Annealing of an Ising Spin Glass”, Science 295

2002

Earlier work this paper cites.

J. Beirlant et al., Statistics of Extremes: Theory and Applications

2004

Cited alongside, same era.

Relsat ( http://code.google.com/p/relsat/ ) was used for enumerating solutions. ILP problems were solved using OPBDP ( http://sourceforge.net/projects/opbdp/ ) and parts of ZIB Optimizatin Suite ( http://zibopt.zib.de/ZIBopt.shtml ): SCIP (Ph.D. Thesis by T. Achterber, “Constraint Integer Programming”, Technische Universität Berlin (2007), http://opus.kobv.de/tuberlin/volltexte/2007/1611/ ) and SOPLEX (Ph.D. Thesis by R. Wunderling, “Paralleler und objecktorientierter Simplex-Algorithmus”, Technische Universität Berlin (1996), http://www.zib.de/Publications/abstracts/TR-96-09/ )

2007

Cited alongside, same era.

B. Altshuler, H. Krovi, J. Roland, “Adiabatic quantum optimization fails for random instances of NP-complete problems”, arXiv:0908.2782; also see a short paper: B. Altshuler, H. Krovi, J. Roland, “Anderson localization casts clouds over adiabatic quantum optimization”, arXiv:0912.0746

Original

Cited in the paper.

V. N. Smelyanskiy, U. v. Toussaint, and D. A. Timucin, “Dynamics of quantum adiabatic evolution algorithm for Number Partitioning”, arXiv:quant-ph/0202155; T. Jörg, F. Krząkała, G. Semerjian, and F. Zamponi, “First-order transitions for random optimization problems in a transverse field”, arXiv:0911.3438

Original

Cited in the paper.

E. Farhi, J. Goldstone, D. Gosset, S. Gutmann, H. B. Meyer, and P. Shor, “Quantum Adiabatic Algorithms, Small Gaps, and Different Paths”, arXiv:0909.4766

Original

Cited in the paper.

D. Nagaj, E. Farhi, J. Goldstone, P. Shor, and I. Sylvester, “Quantum transverse-field Ising model on an infinite tree from matrix product states”, Phys. Rev. B 77

2008

Later among the works it cites.

A. P. Young, S. Knysh, and V. N. Smelyanskiy, “First-Order Phase Transition in the Quantum Adiabatic Algorithm”, Phys. Rev. Lett. 104

2010

Closest in time.