The quantum adiabatic algorithm applied to random optimization problems: The quantum spin glass perspective

Garey, 1979 Papadimitriou, 1994 Papadimitriou, 1998 Feynman, 1982, Simulating physics with computers, Internat. J. Theoret. Phys., 21, 467, 10.1007/BF02650179 Deutsch, 1985, Quantum theory, the Church-Turing principle and the universal quantum computer, Proc. R. Soc. Lond. A, 400, 97, 10.1098/rspa.1985.0070 Nielsen, 2000 Mermin, 2007, 10.1017/CBO9780511813870 2007 Deutsch, 1992, Rapid solutions of problems by quantum computation, Proc. R. Soc. Lond. A, 439, 553, 10.1098/rspa.1992.0167 D.R. Simon, On the power of quantum computation, in: Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium, 1994, p. 116. P. Shor, Algorithms for quantum computation: discrete logarithms and factoring, in: Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium, 1994, p. 124. Grover, 1997, Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett., 79, 325, 10.1103/PhysRevLett.79.325 Bernstein, 1997, Quantum complexity theory, SIAM J. Comput., 26, 1411, 10.1137/S0097539796300921 Watrous, 2000, Succinct quantum proofs for properties of finite groups Kitaev, 2002, 10.1090/gsm/047 Apolloni, 1989, Quantum stochastic optimization, Stochastics Process Appl., 33, 233, 10.1016/0304-4149(89)90040-9 Finnila, 1994, Quantum annealing: a new method for minimizing multidimensional functions, Chem. Phys. Lett., 219, 343, 10.1016/0009-2614(94)00117-0 Kadowaki, 1998, Quantum annealing in the transverse Ising model, Phys. Rev. E, 58, 5355, 10.1103/PhysRevE.58.5355 Brooke, 1999, Quantum annealing of a disordered magnet, Science, 284, 779, 10.1126/science.284.5415.779 Farhi, 2001, A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem, Science, 292, 472, 10.1126/science.1057726 Santoro, 2006, Optimization using quantum mechanics: quantum annealing through adiabatic evolution, J. Phys. A: Math. Gen., 39, R393, 10.1088/0305-4470/39/36/R01 2005 Das, 2008, Colloquium: quantum annealing and analog quantum computation, Rev. Modern Phys., 80, 1061, 10.1103/RevModPhys.80.1061 Morita, 2008, Mathematical foundation of quantum annealing, J. Math. Phys., 49, 125210, 10.1063/1.2995837 Messiah, 1962 W. van Dam, M. Mosca, U. Vazirani, How powerful is adiabatic quantum computation? in: Proc. 42nd FOCS, 2001, p. 279. W. van Dam, U. Vazirani, Limits on quantum adiabatic optimization (unpublished). Farhi, 2008, How to make the quantum adiabatic algorithm fail, Int. J. Quantum Comput., 6, 503, 10.1142/S021974990800358X Znidaric, 2006, Exponential complexity of an adiabatic algorithm for an NP-complete problem, Phys. Rev. A, 73, 022329, 10.1103/PhysRevA.73.022329 Janson, 2000 Mitchell, 1992, Hard and easy distributions for SAT problems, 459 Mézard, 1987 Sachdev, 2001 Goldschmidt, 1990, Solvable model of the quantum spin glass in a transverse field, Phys. Rev. B, 41, 4858, 10.1103/PhysRevB.41.4858 Nieuwenhuizen, 1998, Quantum phase transition in spin glasses with multi-spin interactions, Physica A, 250, 8, 10.1016/S0378-4371(97)00546-3 Biroli, 2001, Quantum Thouless-Anderson-Palmer equations for glassy systems, Phys. Rev. B, 64, 014206, 10.1103/PhysRevB.64.014206 Cugliandolo, 2001, Imaginary-time replica formalism study of a quantum spherical p-spin-glass model, Phys. Rev. B, 64, 014403, 10.1103/PhysRevB.64.014403 Jörg, 2008, Simple glass models and their quantum annealing, Phys. Rev. Lett., 101, 147204, 10.1103/PhysRevLett.101.147204 Amin, 2009, First-order quantum phase transition in adiabatic quantum computation, Phys. Rev. A, 80, 062326, 10.1103/PhysRevA.80.062326 Altshuler, 2010, Anderson localization makes adiabatic quantum optimization fail, Proc. Natl. Acad. Sci., 107, 12446, 10.1073/pnas.1002116107 Farhi, 2011, Quantum adiabatic algorithms, small gaps, and different paths, Quantum Inf. Comput., 11, 181 Choi, 2011, Different adiabatic quantum optimization algorithms for the NP-complete exact cover and 3-SAT problems, Quantum Inf. Comput., 11, 638 Dickson, 2012, Algorithmic approach to adiabatic quantum optimization, Phys. Rev. A, 85, 032303, 10.1103/PhysRevA.85.032303 Vazirani, 2001 Dziarmaga, 2010, Dynamics of a quantum phase transition and relaxation to a steady state, Adv. Phys., 59, 1063, 10.1080/00018732.2010.514702 Hastad, 2001, Some optimal inapproximability results, J. ACM, 48, 798, 10.1145/502090.502098 Foini, 2010, Solvable model of quantum random optimization problems, Phys. Rev. Lett., 105, 167204, 10.1103/PhysRevLett.105.167204 Jörg, 2010, First-order transitions and the performance of quantum algorithms in random optimization problems, Phys. Rev. Lett., 104, 207206, 10.1103/PhysRevLett.104.207206 V. Bapst, G. Semerjian, F. Zamponi, The effect of quantum fluctuations on the coloring of random graphs (in preparation). V.N. Smelyanskiy, E.G. Rieffel, S.I. Knysh, C.P. Williams, M.W. Johnson, M.C. Thom, W.G. Macready, K.L. Pudenz, A near-term quantum computing approach for hard computational problems in space exploration, 2012. arXiv:1204.2821. S. Tanaka, R. Tamura, Quantum annealing: from viewpoints of statistical physics, condensed matter physics, and computational physics, 2012. arXiv:1204.2907. M. Ohzeki, Spin glass: A bridge between quantum computation and statistical mechanics, 2012. arXiv:1204.2865. Richardson, 2008 DiVincenzo, 2000, The physical implementation of quantum computation, Fortschr. Phys., 48, 771, 10.1002/1521-3978(200009)48:9/11<771::AID-PROP771>3.0.CO;2-E C.R. Laumann, R. Moessner, A. Scardicchio, S.L. Sondhi, Statistical mechanics of classical and quantum computational complexity, 2010. arXiv:1009.1635. DiVincenzo, 1995, Two-bit gates are universal for quantum computation, Phys. Rev. A, 51, 1015, 10.1103/PhysRevA.51.1015 Deutsch, 1995, Universality in quantum computation, Proc. Math. Phys. Sci., 449, 669, 10.1098/rspa.1995.0065 Lloyd, 1995, Almost any quantum logic gate is universal, Phys. Rev. Lett., 75, 346, 10.1103/PhysRevLett.75.346 Barenco, 1995, Elementary gates for quantum computation, Phys. Rev. A, 52, 3457, 10.1103/PhysRevA.52.3457 Cleve, 1998, Quantum algorithms revisited, Proc. R. Soc. Lond. A, 454, 339, 10.1098/rspa.1998.0164 Rivest, 1978, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, 21, 120, 10.1145/359340.359342 Vandersypen, 2001, Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance, Nature, 414, 883, 10.1038/414883a Lu, 2007, Demonstration of a compiled version of Shor’s quantum factoring algorithm using photonic qubits, Phys. Rev. Lett., 99, 250504, 10.1103/PhysRevLett.99.250504 Lanyon, 2007, Experimental demonstration of a compiled version of Shor’s algorithm with quantum entanglement, Phys. Rev. Lett., 99, 250505, 10.1103/PhysRevLett.99.250505 E. Lucero, R. Barends, Y. Chen, J. Kelly, M. Mariantoni, A. Megrant, P. O’Malley, D. Sank, A. Vainsencher, J. Wenner, T. White, Y. Yin, A.N. Cleland, J.M. Martinis, Computing prime factors with a Josephson phase qubit quantum processor, 2012. arXiv:1202.5707. Agrawal, 2004, PRIMES is in P, Ann. of Math. (2), 160, 781, 10.4007/annals.2004.160.781 Bennett, 1997, Strengths and weaknesses of quantum computing, SIAM J. Comput., 26, 1510, 10.1137/S0097539796300933 Dewes, 2012, Quantum speeding-up of computation demonstrated in a superconducting two-qubit processor, Phys. Rev. B, 85, 140503, 10.1103/PhysRevB.85.140503 Harrow, 2009, Quantum algorithm for linear systems of equations, Phys. Rev. Lett., 103, 150502, 10.1103/PhysRevLett.103.150502 Ambainis, 2012, Variable time amplitude amplification and quantum algorithms for linear algebra problems, 636 Kempe, 2003, 3-local hamiltonian is QMA-complete, Quantum Inf. Comput., 3, 258 Kempe, 2006, The complexity of the local hamiltonian problem, SIAM J. Comput., 35, 1070, 10.1137/S0097539704445226 Aharonov, 2009, The power of quantum systems on a line, Comm. Math. Phys., 287, 41, 10.1007/s00220-008-0710-3 S. Bravyi, Efficient algorithm for a quantum analogue of 2-SAT, 2006. arXiv:quant-ph/0602108. S. Bravyi, C. Moore, A. Russell, Bounds on the quantum satisfiability threshold, 2009. arXiv:0907.1297. A. Ambainis, J. Kempe, O. Sattath, A quantum Lovasz local lemma, in: Proc. 42nd STOC, 2010, p. 151. Laumann, 2010, Phase transitions and random quantum satisfiability, Quantum. Inf. Comput., 10, 1 Laumann, 2010, Product, generic, and random generic quantum satisfiability, Phys. Rev. A, 81, 062345, 10.1103/PhysRevA.81.062345 Nayak, 2008, Non-abelian anyons and topological quantum computation, Rev. Modern Phys., 80, 1083, 10.1103/RevModPhys.80.1083 Raussendorf, 2001, A one-way quantum computer, Phys. Rev. Lett., 86, 5188, 10.1103/PhysRevLett.86.5188 Farhi, 1998, Quantum computation and decision trees, Phys. Rev. A, 58, 915, 10.1103/PhysRevA.58.915 Kempe, 2003, Quantum random walks: an introductory overview, Contemp. Phys., 44, 307, 10.1080/00107151031000110776 Ambainis, 2003, Quantum walks and their algorithmic applications, Int. J. Quantum Inf., 1, 507, 10.1142/S0219749903000383 Childs, 2009, Universal computation by quantum walk, Phys. Rev. Lett., 102, 180501, 10.1103/PhysRevLett.102.180501 Reitzner, 2011, Quantum walks, Acta Phys. Slovaca, 61, 603, 10.2478/v10155-011-0006-6 Kirkpatrick, 1983, Optimization by simulated annealing, Science, 220, 671, 10.1126/science.220.4598.671 Steffen, 2003, Experimental implementation of an adiabatic quantum optimization algorithm, Phys. Rev. Lett., 90, 067903, 10.1103/PhysRevLett.90.067903 Z. Bian, F. Chudak, W.G. Macready, L. Clark, F. Gaitan, Experimental determination of Ramsey numbers with quantum annealing, 2012. arXiv:1201.1842. Born, 1928, Beweis des Adiabatensatzes, Zeit. Phys. A, 51, 165, 10.1007/BF01343193 Kato, 1950, On the adiabatic theorem of quantum mechanics, J. Phys. Soc. Japan, 5, 435, 10.1143/JPSJ.5.435 Cheung, 2011, Improved error bounds for the adiabatic approximation, J. Phys. A, 44, 415302, 10.1088/1751-8113/44/41/415302 A. Elgart, G. Hagedorn, A note on the switching adiabatic theorem, 2012. arXiv:1204.2318. E. Farhi, J. Goldstone, S. Gutmann, M. Sipser, Quantum computation by adiabatic evolution, 2000. arXiv:quant-ph/0001106. Rigolin, 2012, Adiabatic theorem for quantum systems with spectral degeneracy, Phys. Rev. A, 85, 062111, 10.1103/PhysRevA.85.062111 Wilczek, 1984, Appearance of gauge structure in simple dynamical systems, Phys. Rev. Lett., 52, 2111, 10.1103/PhysRevLett.52.2111 Valiant, 1986, NP is as easy as detecting unique solutions, Theoret. Comput. Sci., 47, 85, 10.1016/0304-3975(86)90135-0 Landau, 1932, Zur Theorie der Energieubertragung. II, Phys. Soviet Union, 2, 46 Zener, 1932, Non-adiabatic crossing of energy levels, Proc. R. Soc. Lond., 137, 696, 10.1098/rspa.1932.0165 Vitanov, 1996, Landau–Zener model: effects of finite coupling duration, Phys. Rev. A, 53, 4288, 10.1103/PhysRevA.53.4288 Vitanov, 1999, Transition times in the Landau-Zener model, Phys. Rev. A, 59, 988, 10.1103/PhysRevA.59.988 Volkov, 2007, Analytical results for state-to-state transition probabilities in the multistate Landau-Zener model by nonstationary perturbation theory, Phys. Rev. A, 75, 022105, 10.1103/PhysRevA.75.022105 Santoro, 2002, Theory of quantum annealing of an Ising spin glass, Science, 295, 2427, 10.1126/science.1068774 Bapst, 2012, On quantum mean-field models and their quantum annealing, J. Stat. Mech., 2012, P06007, 10.1088/1742-5468/2012/06/P06007 Aharonov, 2007, Adiabatic quantum computation is equivalent to standard quantum computation, SIAM J. Comput., 37, 166, 10.1137/S0097539705447323 Rezakhani, 2010, Intrinsic geometry of quantum adiabatic evolution and quantum phase transitions, Phys. Rev. A, 82, 012321, 10.1103/PhysRevA.82.012321 Roland, 2002, Quantum search by local adiabatic evolution, Phys. Rev. A, 65, 042308, 10.1103/PhysRevA.65.042308 Caneva, 2009, Optimal control at the quantum speed limit, Phys. Rev. Lett., 103, 240501, 10.1103/PhysRevLett.103.240501 Caneva, 2011, Speeding up critical system dynamics through optimized evolution, Phys. Rev. A, 84, 012312, 10.1103/PhysRevA.84.012312 J. Nehrkorn, S. Montangero, A. Ekert, A. Smerzi, R. Fazio, T. Calarco, Staying adiabatic with unknown energy gap, 2011. arXiv:1105.1707. Seki, 2012, Quantum annealing with antiferromagnetic fluctuations, Phys. Rev. E, 85, 051112, 10.1103/PhysRevE.85.051112 Seoane, 2012, Many-body transverse interactions in the quantum annealing of the p-spin ferromagnet, J. Phys. A, 45, 435301, 10.1088/1751-8113/45/43/435301 Ribeiro, 2006, Adiabatic computation: a toy model, Phys. Rev. A, 74, 042333, 10.1103/PhysRevA.74.042333 Arora, 1998, Proof verification and the hardness of approximation problems, J. ACM, 45, 501, 10.1145/278298.278306 D. Aharonov, I. Arad, Z. Landau, U. Vazirani, The detectibility lemma and quantum gap amplification, in: Proc. 41st Annual ACM Symposium on Theory of Computing, vol. 287, 2009, pp. 417–426. M. Hastings, Trivial low energy states for commuting hamiltonians, and the quantum PCP conjecture, 2012. arXiv:1201.3387. S. Gharibian, J. Kempe, Approximation algorithms for QMA-complete problems, in: Proc. 26th CCC’11, 2011, p. 178. S. Gharibian, J. Kempe, Hardness of approximation for quantum problems, 2012. arXiv:1209.1055. Cheeseman, 1991, Where the really hard problems are, 331 Friedgut, 1999, Sharp thresholds of graph properties, and the k-sat problem, J. Amer. Math. Soc., 12, 1017, 10.1090/S0894-0347-99-00305-7 Franco, 2001, Results related to threshold phenomena research in satisfiability: lower bounds, Theoret. Comput. Sci., 265, 147, 10.1016/S0304-3975(01)00158-X Achlioptas, 2001, Lower bounds for random 3-SAT via differential equations., Theoret. Comput. Sci., 265, 159, 10.1016/S0304-3975(01)00159-1 Dubois, 2001, Upper bounds on the satisfiability threshold, Theoret. Comput. Sci., 265, 187, 10.1016/S0304-3975(01)00161-X Achlioptas, 2004, The threshold for random k-SAT is 2k log 2−O(k), J. Amer. Math. Soc., 17, 947, 10.1090/S0894-0347-04-00464-3 Monasson, 1997, Statistical mechanics of the random k-satisfiability model, Phys. Rev. E, 56, 1357, 10.1103/PhysRevE.56.1357 Mézard, 2002, Random k-satisfiability problem: from an analytic solution to an efficient algorithm, Phys. Rev. E, 66, 056126, 10.1103/PhysRevE.66.056126 Mézard, 2002, Analytic and algorithmic solution of random satisfiability problems, Science, 297, 812, 10.1126/science.1073287 Mertens, 2006, Threshold values of random k-SAT from the cavity method, Random Structures Algorithms, 28, 340, 10.1002/rsa.20090 Krzakala, 2004, Threshold values, stability analysis, and high-q asymptotics for the coloring problem on random graphs, Phys. Rev. E, 70, 046705, 10.1103/PhysRevE.70.046705 Biroli, 2000, A variational description of the ground state structure in random satisfiability problems, Eur. Phys. J. B, 14, 551, 10.1007/s100510051065 Krzakala, 2007, Gibbs states and the set of solutions of random constraint satisfaction problems, Proc. Natl. Acad. Sci., 104, 10318, 10.1073/pnas.0703685104 Franz, 2003, Replica bounds for optimization problems and diluted spin systems, J. Stat. Phys., 111, 535, 10.1023/A:1022885828956 Panchenko, 2004, Bounds for diluted mean-fields spin glass models, Probab. Theory Related Fields, 130, 319, 10.1007/s00440-004-0342-2 Daudé, 2008, Pairs of sat assignments and clustering in random boolean formulae, Theoret. Comput. Sci., 393, 260, 10.1016/j.tcs.2008.01.005 D. Achlioptas, F. Ricci-Tersenghi, On the solution-space geometry of random constraint satisfaction problems, in: Proc. of the 38th Annual ACM Symposium on Theory of Computing. A. Coja-Oghlan, On belief propagation guided decimation for random k-sat, in: Proc. 22nd SODA, 2011, p. 957. Monasson, 2007, Introduction to phase transitions in random optimization problems Mézard, 2009 Moore, 2011, 10.1093/acprof:oso/9780199233212.001.0001 Anderson, 1958, Absence of diffusion in certain random lattices, Phys. Rev., 109, 1492, 10.1103/PhysRev.109.1492 Derrida, 1981, Random-energy model: an exactly solvable model of disordered systems, Phys. Rev. B, 24, 2613, 10.1103/PhysRevB.24.2613 Edwards, 1975, Theory of spin-glasses, J. Phys. F, 5, 965, 10.1088/0305-4608/5/5/017 Sherrington, 1975, Solvable model of a spin-glass, Phys. Rev. Lett., 35, 1792, 10.1103/PhysRevLett.35.1792 Parisi, 1980, A sequence of approximated solutions to the S-K model for spin glasses, J. of Phys. A, 13, L115, 10.1088/0305-4470/13/4/009 Fischer, 1991 Talagrand, 2006, The Parisi formula, Ann. of Math., 163, 221, 10.4007/annals.2006.163.221 Guerra, 2002, The thermodynamic limit in mean field spin glass models, Comm. Math. Phys., 230, 71, 10.1007/s00220-002-0699-y Gross, 1984, The simplest spin glass, Nuclear Phys. B, 240, 431, 10.1016/0550-3213(84)90237-2 Viana, 1985, Phase diagrams for dilute spin glasses, J. Phys. C, 18, 3037, 10.1088/0022-3719/18/15/013 Mézard, 1985, Replicas and optimization, J. Phys., 46, L771 Fu, 1986, Application of statistical mechanics to NP-complete problems in combinatorial optimization, J. Phys. A, 19, 1605, 10.1088/0305-4470/19/9/033 Monasson, 1998, Optimization problems and replica symmetry breaking in finite connectivity spin glasses, J. Phys. A, 31, 513, 10.1088/0305-4470/31/2/012 Mézard, 2001, The Bethe lattice spin glass revisited, Eur. Phys. J. B, 20, 217, 10.1007/PL00011099 Mézard, 2003, The cavity method at zero temperature, J. Stat. Phys., 111, 1, 10.1023/A:1022221005097 Talagrand, 2003 Castellani, 2005, Spin-glass theory for pedestrians, J. Stat. Mech., 2005, P05012, 10.1088/1742-5468/2005/05/P05012 Kirkpatrick, 1987, Stable and metastable states in mean-field Potts and structural glasses, Phys. Rev. B, 36, 8552, 10.1103/PhysRevB.36.8552 Kirkpatrick, 1988, Mean-field soft-spin Potts glass model: statics and dynamics, Phys. Rev. B, 37, 5342, 10.1103/PhysRevB.37.5342 Kirkpatrick, 1987, Connections between some kinetic and equilibrium theories of the glass transition, Phys. Rev. A, 35, 3072, 10.1103/PhysRevA.35.3072 Kirkpatrick, 1989, Scaling concepts for the dynamics of viscous liquids near an ideal glassy state, Phys. Rev. A, 40, 1045, 10.1103/PhysRevA.40.1045 Lubchenko, 2007, Theory of structural glasses and supercooled liquids, Ann. Rev. Phys. Chem., 58, 235, 10.1146/annurev.physchem.58.032806.104653 Cavagna, 2009, Supercooled liquids for pedestrians, Phys. Rep., 476, 51, 10.1016/j.physrep.2009.03.003 Biroli, 2012, The Random First-Order Transition Theory of Glasses: A Critical Assessment Berthier, 2011, Theoretical perspective on the glass transition and amorphous materials, Rev. Modern Phys., 83, 587, 10.1103/RevModPhys.83.587 Götze, 2009 Kauzmann, 1948, The nature of the glassy state and the behavior of liquids at low temperatures, Chem. Rev., 43, 219, 10.1021/cr60135a002 Gardner, 1985, Spin glasses with p-spin interactions, Nuclear Phys. B, 257, 747, 10.1016/0550-3213(85)90374-8 Mézard, 2003, Two solutions to diluted p-spin models and XORSAT problems., J. Stat. Phys., 111, 505, 10.1023/A:1022886412117 Cocco, 2003, Rigorous decimation-based construction of ground pure states for spin-glass models on random lattices, Phys. Rev. Lett., 90, 047205, 10.1103/PhysRevLett.90.047205 Montanari, 2006, On the dynamics of the glass transition on Bethe lattices, J. Stat. Phys., 124, 103, 10.1007/s10955-006-9103-1 Ibrahimi, 2012, The set of solutions of random XORSAT formulae, 760 D. Achlioptas, M. Molloy, The solution space geometry of random linear equations, 2011. arXiv:1107.5550. Mora, 2008, Random subcubes as a toy model for constraint satisfaction problems, J. Stat. Phys., 131, 1121, 10.1007/s10955-008-9543-x Zdeborová, 2007, Phase transitions in the coloring of random graphs, Phys. Rev. E, 76, 031131, 10.1103/PhysRevE.76.031131 Semerjian, 2008, On the freezing of variables in random constraint satisfaction problems, J. Stat.Phys., 130, 251, 10.1007/s10955-007-9417-7 Achlioptas, 2008, Algorithmic barriers from phase transitions, 793 Alava, 2008, Circumspect descent prevails in solving random constraint satisfaction problems, Proc. Natl. Acad. Sci., 105, 15253, 10.1073/pnas.0712263105 Krzakala, 2007, Landscape analysis of constraint satisfaction problems, Phys. Rev. E, 76, 021122, 10.1103/PhysRevE.76.021122 Krzakala, 2008, Potts glass on random graphs, Europhys. Lett., 81, 57005, 10.1209/0295-5075/81/57005 Montanari, 2006, Rigorous inequalities between length and time scales in glassy systems, J. Stat. Phys., 125, 23, 10.1007/s10955-006-9175-y Gross, 1985, Mean-field theory of the Potts glass, Phys. Rev. Lett., 55, 304, 10.1103/PhysRevLett.55.304 Geman, 1984, Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images, IEEE Trans. Pattern Anal. Mach. Intell., 6, 721, 10.1109/TPAMI.1984.4767596 Monthus, 1996, Models of traps and glass phenomenology, J. Phys. A, 29, 3847, 10.1088/0305-4470/29/14/012 Arous, 2008, Universality of the REM for dynamics of mean-field spin glasses, Comm. Math. Phys., 282, 663, 10.1007/s00220-008-0565-7 Bray, 1987, Chaotic nature of the spin-glass phase, Phys. Rev. Lett., 58, 57, 10.1103/PhysRevLett.58.57 Fisher, 1988, Equilibrium behavior of the spin-glass ordered phase, Phys. Rev. B, 38, 386, 10.1103/PhysRevB.38.386 Krzakala, 2002, Chaotic temperature dependence in a model of spin glasses, Eur. Phys. J. B, 28, 199, 10.1140/epjb/e2002-00221-y Krzakala, 2010, Following Gibbs states adiabatically the energy landscape of mean-field glassy systems, Europhys. Lett., 90, 66002, 10.1209/0295-5075/90/66002 Zdeborová, 2010, Generalization of the cavity method for adiabatic evolution of Gibbs states, Phys. Rev. B, 81, 224205, 10.1103/PhysRevB.81.224205 van Mourik, 2002, Random graph coloring: statistical physics approach, Phys. Rev. E, 66, 056120, 10.1103/PhysRevE.66.056120 Ardelius, 2006, Behavior of heuristics on large and hard satisfiability problems, Phys. Rev. E, 74, 037702, 10.1103/PhysRevE.74.037702 Zdeborová, 2008, Locked constraint satisfaction problems, Phys. Rev. Lett., 101, 078702, 10.1103/PhysRevLett.101.078702 Zdeborová, 2009, Statistical physics of hard optimization problems, Acta Phys. Slovaca, 59, 169, 10.2478/v10155-010-0096-6 Braunstein, 2002, Complexity transitions in global algorithms for sparse linear systems over finite fields, J. Phys. A, 35, 7559, 10.1088/0305-4470/35/35/301 Haanpää, 2006, Hard satisfiable clause sets for benchmarking equivalence reasoning techniques, J. Sat. Boolean Model. Comput., 2, 27 Ricci-Tersenghi, 2010, Being glassy without being hard to solve, Science, 330, 1639, 10.1126/science.1189804 Zdeborová, 2011, Quiet planting in the locked constraint satisfaction problems, SIAM J. Discrete Math., 25, 750, 10.1137/090750755 Young, 2010, First-order phase transition in the quantum adiabatic algorithm, Phys. Rev. Lett., 104, 020502, 10.1103/PhysRevLett.104.020502 Foini, 2011, Quantum Biroli–Mézard model: glass transition and superfluidity in a quantum lattice glass model, Phys. Rev. B, 83, 094513, 10.1103/PhysRevB.83.094513 Botet, 1983, Large-size critical behavior of infinitely coordinated systems, Phys. Rev. B, 28, 3955, 10.1103/PhysRevB.28.3955 Dusuel, 2004, Finite-size scaling exponents of the Lipkin-Meshkov-Glick model, Phys. Rev. Lett., 93, 237204, 10.1103/PhysRevLett.93.237204 Dusuel, 2005, Continuous unitary transformations and finite-size scaling exponents in the Lipkin–Meshkov–Glick model, Phys. Rev. B, 71, 224420, 10.1103/PhysRevB.71.224420 Das, 2006, Infinite-range Ising ferromagnet in a time-dependent transverse magnetic field: quench and ac dynamics near the quantum critical point, Phys. Rev. B, 74, 144423, 10.1103/PhysRevB.74.144423 Fisher, 1995, Critical behavior of random transverse-field Ising spin chains, Phys. Rev. B, 51, 6411, 10.1103/PhysRevB.51.6411 Fisher, 1998, Distributions of gaps and end-to-end correlations in random transverse-field Ising spin chains, Phys. Rev. B, 58, 9131, 10.1103/PhysRevB.58.9131 Young, 1996, Numerical study of the random transverse-field Ising spin chain, Phys. Rev. B, 53, 8486, 10.1103/PhysRevB.53.8486 Caneva, 2007, Adiabatic quantum dynamics of a random Ising chain across its quantum critical point, Phys. Rev. B, 76, 144427, 10.1103/PhysRevB.76.144427 Bray, 1980, Replica theory of quantum spin glasses, J. Phys. C, 13, L655, 10.1088/0022-3719/13/24/005 A. Andreanov, M. Müller, Collective excitations and marginal stability of quantum Ising spin glasses, 2012. arXiv:1204.4156. Jörg, 2010, Energy gaps in quantum first-order mean-field-like transitions: the problems that quantum annealing cannot solve, EPL, 89, 40004, 10.1209/0295-5075/89/40004 Filippone, 2011, Quantum phase transitions in fully connected spin models: an entanglement perspective, Phys. Rev. A, 83, 022327, 10.1103/PhysRevA.83.022327 C. Laumann, R. Moessner, A. Scardicchio, S. Sondhi, The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transition, 2012. arXiv:1202.3646. Dobrosavljevic, 1990, 1/p expansion for a p-spin interaction spin-glass model in a transverse field, J. Phys. A, 23, L767, 10.1088/0305-4470/23/15/013 Jörg, 2010, Quantum annealing of hard problems, Progr. Theoret. Phys. Suppl., 184, 290, 10.1143/PTPS.184.290 Buccheri, 2011, Structure of typical states of a disordered Richardson model and many-body localization, Phys. Rev. B, 84, 094203, 10.1103/PhysRevB.84.094203 Dickson, 2011, Elimination of perturbative crossings in adiabatic quantum optimization, New J. Phys., 13, 073011, 10.1088/1367-2630/13/7/073011 S. Knysh, V. Smelyanskiy, On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm, 2010. arXiv:1005.3011. V. Choi, Adiabatic quantum algorithms for the NP-complete maximum-weight independent set, exact cover and 3-SAT problems, 2010. arXiv:1004.2226. V. Choi, Avoid first order quantum phase transition by changing problem hamiltonians, 2010. arXiv:1010.1220. Dickson, 2011, Does adiabatic quantum optimization fail for np-complete problems?, Phys. Rev. Lett., 106, 050502, 10.1103/PhysRevLett.106.050502 Thompson, 1976, The behavior of eigenvalues and singular values under perturbations of restricted rank, Linear Algebra Appl., 13, 69, 10.1016/0024-3795(76)90044-6 Montanari, 2008, Clusters of solutions and replica symmetry breaking in random k-satisfiability, J. Stat. Mech., 2008, P04004, 10.1088/1742-5468/2008/04/P04004 Dembo, 2010, Ising models on locally tree-like graphs, Ann. Appl. Probab., 20, 565, 10.1214/09-AAP627 Laumann, 2008, Cavity method for quantum spin glasses on the Bethe lattice, Phys. Rev. B, 78, 134424, 10.1103/PhysRevB.78.134424 Krzakala, 2008, Path-integral representation for quantum spin models: application to the quantum cavity method and monte carlo simulations, Phys. Rev. B, 78, 134428, 10.1103/PhysRevB.78.134428 Leifer, 2008, Quantum graphical models and belief propagation, Ann. Physics, 323, 1899, 10.1016/j.aop.2007.10.001 Poulin, 2008, Belief propagation algorithm for computing correlation functions in finite-temperature quantum many-body systems on loopy graphs, Phys. Rev. A, 77, 052318, 10.1103/PhysRevA.77.052318 Bilgin, 2010, Coarse-grained belief propagation for simulation of interacting quantum systems at all temperatures, Phys. Rev. B, 81, 054106, 10.1103/PhysRevB.81.054106 Poulin, 2011, Markov entropy decomposition: a variational dual for quantum belief propagation, Phys. Rev. Lett., 106, 80403, 10.1103/PhysRevLett.106.080403 Ioffe, 2010, Disorder-driven quantum phase transitions in superconductors and magnets, Phys. Rev. Lett., 105, 037001, 10.1103/PhysRevLett.105.037001 Dimitrova, 2011, The cavity method for quantum disordered systems: from transverse random field ferromagnets to directed polymers in random media, J. Stat. Mech., 2011, P01020, 10.1088/1742-5468/2011/01/P01020 Ramezanpour, 2012, Cavity approach to variational quantum mechanics, Phys. Rev. B, 85, 125131, 10.1103/PhysRevB.85.125131 Semerjian, 2009, Exact solution of the Bose–Hubbard model on the Bethe lattice, Phys. Rev. B, 80, 014524, 10.1103/PhysRevB.80.014524 Kschischang, 2001, Factor graphs and the sum-product algorithm, IEEE Trans. Inform. Theory, 47, 498, 10.1109/18.910572 Molloy, 1995, A critical point for random graphs with a given degree sequence, Random Structures Algorithms, 6, 161, 10.1002/rsa.3240060204 Monasson, 1995, Structural glass transition and the entropy of the metastable states, Phys. Rev. Lett., 75, 2847, 10.1103/PhysRevLett.75.2847 Cugliandolo, 1993, Analytical solution of the off-equilibrium dynamics of a long-range spin-glass model, Phys. Rev. Lett., 71, 173, 10.1103/PhysRevLett.71.173 Abou-Chacra, 1973, A selfconsistent theory of localization, J. Phys. C, 6, 1734, 10.1088/0022-3719/6/10/009 Arulampalam, 2002, A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking, IEEE Trans. Signal Process., 50, 174, 10.1109/78.978374 Andrea Montanari, 2004, Instability of one-step replica-symmetry-broken phase in satisfiability problems, J. Phys. A, 37, 2073, 10.1088/0305-4470/37/6/008 Ginibre, 1968, Reduced density matrices of the anisotropic Heisenberg model, Comm. Math. Phys., 10, 140, 10.1007/BF01654238 Gallavotti, 1968, Analyticity properties of the anisotropic Heisenberg model, Comm. Math. Phys, 10, 311, 10.1007/BF03399504 Farhi, 1992, The functional integral constructed directly from the Hamiltonian, Ann. Physics, 213, 182, 10.1016/0003-4916(92)90288-W Aizenman, 1994, Geometric aspects of quantum spin states, Comm. Math. Phys., 164, 17, 10.1007/BF02108805 Chayes, 2008, The phase diagram of the quantum Curie–Weiss model, J. Stat. Phys., 133, 131, 10.1007/s10955-008-9608-x Ioffe, 2009, Stochastic geometry of classical and quantum Ising models, vol. 1970, 87 Martinelli, 2012, Glauber dynamics for the quantum Ising model in a transverse field on a regular tree, J. Stat. Phys., 146, 1059, 10.1007/s10955-012-0436-7 Hastings, 2007, Quantum belief propagation: an algorithm for thermal quantum systems, Phys. Rev. B, 76, 201102, 10.1103/PhysRevB.76.201102 Feigel’man, 2010, Superconductor–insulator transition and energy localization, Phys. Rev. B, 82, 184534, 10.1103/PhysRevB.82.184534 M. Mueller, Giant positive magnetoresistance and localization in bosonic insulators, arXiv:1109.0245. Georges, 1996, Dynamical mean-field theory of strongly correlated fermion systems and the limit of infinite dimensions, Rev. Modern Phys., 68, 13, 10.1103/RevModPhys.68.13 A. Globerson, T. Jaakkola, Approximate inference using conditional entropy decompositions, in: Proc. of the 11th International Conference on Artificial Intelligence and Statistics, 2007. Jastrow, 1955, Many-body problem with strong forces, Phys. Rev., 98, 1479, 10.1103/PhysRev.98.1479 Ramezanpour, 2012, The sign problem in the Bethe approximation, Phys. Rev. B, 86, 155147, 10.1103/PhysRevB.86.155147 White, 1992, Density matrix formulation for quantum renormalization groups, Phys. Rev. Lett., 69, 2863, 10.1103/PhysRevLett.69.2863 Vidal, 2003, Efficient classical simulation of slightly entangled quantum computations, Phys. Rev. Lett., 91, 147902, 10.1103/PhysRevLett.91.147902 Nagaj, 2008, Quantum transverse-field Ising model on an infinite tree from matrix product states, Phys. Rev. B, 77, 214431, 10.1103/PhysRevB.77.214431 Shi, 2006, Classical simulation of quantum many-body systems with a tree tensor network, Phys. Rev. A, 74, 022320, 10.1103/PhysRevA.74.022320 Nagy, 2012, Simulating quantum systems on the Bethe lattice by translationally invariant infinite-tree tensor network, Ann. Physics, 327, 542, 10.1016/j.aop.2011.11.012 W. Li, J. von Delft, T. Xiang, Efficient simulation of infinite tree tensor network states on the Bethe lattice, 2012. arXiv:1209.2387. Vidal, 2007, Classical simulation of infinite-size quantum lattice systems in one spatial dimension, Phys. Rev. Lett., 98, 70201, 10.1103/PhysRevLett.98.070201 Lepetit, 2000, Density-matrix renormalization study of the Hubbard model on a Bethe lattice, Eur. Phys. J. B, 13, 421, 10.1007/s100510050053 Hatano, 2005, Finding exponential product formulas of higher orders, Optimization, 22 Huyghebaert, 1990, Product formula methods for time-dependent schrodinger problems, J. Phys. A, 23, 5777, 10.1088/0305-4470/23/24/019 Poulin, 2011, Quantum simulation of time-dependent hamiltonians and the convenient illusion of hilbert space, Phys. Rev. Lett., 106, 170501, 10.1103/PhysRevLett.106.170501 Cazalilla, 2002, Time-dependent density-matrix renormalization group: a systematic method for the study of quantum many-body out-of-equilibrium systems, Phys. Rev. Lett., 88, 256403, 10.1103/PhysRevLett.88.256403 White, 2004, Real-time evolution using the density matrix renormalization group, Phys. Rev. Lett., 93, 76401, 10.1103/PhysRevLett.93.076401 Daley, 2004, Time-dependent density-matrix renormalization-group using adaptive effective hilbert spaces, J. Stat. Mech., 2004, P04005, 10.1088/1742-5468/2004/04/P04005 Ceperley, 1995, Path integrals in the theory of condensed helium, Rev. Mod. Phys., 67, 279, 10.1103/RevModPhys.67.279 Krauth, 1991, Superfluid-insulator transition in disordered boson systems, Phys. Rev. Lett., 67, 2307, 10.1103/PhysRevLett.67.2307 Rieger, 1994, Zero-temperature quantum phase transition of a two-dimensional Ising spin glass, Phys. Rev. Lett., 72, 4141, 10.1103/PhysRevLett.72.4141 Batrouni, 1996, World line simulations of the bosonic Hubbard model in the ground state, Comput. Phys. Comm., 97, 63, 10.1016/0010-4655(96)00022-7 Beard, 1996, Simulations of discrete quantum systems in continuous euclidean time, Phys. Rev. Lett., 77, 5130, 10.1103/PhysRevLett.77.5130 Prokof’ev, 1998, “Worm” algorithm in quantum Monte Carlo simulations, Phys. Lett. A, 238, 253, 10.1016/S0375-9601(97)00957-2 Rieger, 1999, Application of a continuous time cluster algorithm to the two-dimensional random quantum Ising ferromagnet, Eur. Phys. J. B, 9, 233, 10.1007/s100510050761 Farhi, 2011, A quantum Monte Carlo method at fixed energy, Comput. Phys. Comm., 182, 1663, 10.1016/j.cpc.2011.04.021 Sandvik, 1999, Stochastic series expansion method with operator-loop update, Phys. Rev. B, 59, R14157, 10.1103/PhysRevB.59.R14157 Hen, 2011, Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems, Phys. Rev. E, 84, 061152, 10.1103/PhysRevE.84.061152 Young, 2008, Size dependence of the minimum excitation gap in the quantum adiabatic algorithm, Phys. Rev. Lett., 101, 170503, 10.1103/PhysRevLett.101.170503 Hen, 2012, Excitation gap from optimized correlation functions in quantum Monte Carlo simulations, Phys. Rev. E, 85, 036705, 10.1103/PhysRevE.85.036705 Markland, 2010, The quantum liquid-glass transition, Nat. Phys., 7, 134, 10.1038/nphys1865 Guidetti, 2011, Complexity of several constraint-satisfaction problems using the heuristic classical algorithm walksat, Phys. Rev. E, 84, 011102, 10.1103/PhysRevE.84.011102 E. Farhi, D. Gosset, I. Hen, A. Sandvik, P. Shor, A. Young, F. Zamponi, The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs, 2012. arXiv:1208.3757. Franz, 2001, Exact solutions for diluted spin glasses and optimization problems, Phys. Rev. Lett., 87, 127209, 10.1103/PhysRevLett.87.127209 Franz, 2001, A ferromagnet with a glass transition, Europhys. Lett., 55, 465, 10.1209/epl/i2001-00438-4 http://code.google.com/p/relsat. http://www.laria.u-picardie.fr/~cli/maxsatz2009.c. D. Gosset, Ph.D. Thesis, Case Studies in Quantum Adiabatic Optimization, 2011. B. Olmos, I. Lesanovsky, J. Garrahan, Facilitated spin models of dissipative quantum glasses, 2012. arXiv:1203.6585. Carleo, 2009, Bose–Einstein condensation in quantum glasses, Phys. Rev. Lett., 103, 215302, 10.1103/PhysRevLett.103.215302 Childs, 2001, Robustness of adiabatic quantum computation, Phys. Rev. A, 65, 012322, 10.1103/PhysRevA.65.012322 Roland, 2005, Noise resistance of adiabatic quantum computation using random matrix theory, Phys. Rev. A, 71, 032330, 10.1103/PhysRevA.71.032330 Sarandy, 2005, Adiabatic quantum computation in open systems, Phys. Rev. Lett., 95, 250503, 10.1103/PhysRevLett.95.250503