Performance of the quantum adiabatic algorithm on constraint satisfaction and spin glass problems

详细信息    查看全文

• 作者：I. Hen (1)
  A.P. Young (2)
  
  1. Information Sciences Institute ; University of Southern California ; Marina del Rey ; Marina del Rey ; California ; 90292 ; USA
  2. Department of Physics ; University of California ; Santa Cruz ; California ; 95064 ; USA
  
• 刊名：The European Physical Journal - Special Topics
• 出版年：2015
• 出版时间：February 2015
• 年：2015
• 卷：224
• 期：1
• 页码：63-73
• 全文大小：384 KB
• 参考文献：1. M.A. Nielsen, I.L. Chuang, / Quantum Computation, Quantum Information (Cambridge University Press, Cambridge, 2000)
  2. N.D. Mermin, / Quantum Computer Science (Cambridge University Press, Cambridge, 2007)
  3. P.W. Shor, 鈥淎lgorithms for quantum computing: discrete logarithms and factoring,鈥?in / Proc. 35th Symp.聽on Foundations of Computer Science, edited by S. Goldwasser, Los Alamitos CA (IEEE Computer Society Press, 1994), p. 124
  4. T. Kadowaki, H. Nishimori, Phys. Rev. E 58, 5355 (1998) CrossRef
  5. G. Santoro, R. Marto艌谩k, E. Tosatti, R. Car, Science 295, 2427 (2002) CrossRef
  6. E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, D. Preda, Science 292, 472 (2001), A longer version of the paper appeared in [arXiv:quant-ph/0104129] CrossRef
  7. G. Toulouse, Commun. Phys. 2, 115 (1977)
  8. K. Binder, A.P. Young, Rev. Mod. Phys. 58, 801 (1986) CrossRef
  9. S. Kirkpatrick, C.D. Gelatt Jr., M.P. Vecchi, Science 220, 671 (1983) CrossRef
  10. M.E.J. Newman, G.T. Barkema, / Monte Carlo Methods in Statistical Physics (Oxford University Press Inc., New York, USA, 1999)
  11. S. Boixo, et al., Nature Phys. 10, 2018 (2014) CrossRef
  12. A. Messiah, / Quantum Mechanics (Amsterdam: North-Holland, 1962)
  13. G.H. Wannier, Physics 1, 251 (1965)
  14. E. Farhi, J. Goldstone, S. Gutmann, 鈥淨uantum adiabatic algorithms versus simulated annealing鈥?[arXiv:quant-ph/0201031], (2002)
  15. M.W. Johnson, et al., Nature 473, 194 (2011) CrossRef
  16. A.J. Berkley, et al., Phys. Rev. B 87, 020502(R) (2013) CrossRef
  17. T.F. R酶nnow, Z. Wang, J. Job, S. Boixo, S.V. Isakov, D. Wecker, J.M. Martinis, D.A. Lidar, M. Troyer, Science 345, 6195 (2014) CrossRef
  18. A.M. Childs, E. Farhi, J. Preskill, Phys. Rev. A 65, 012322 (2001) CrossRef
  19. M. Amin, D.V. Averin, J.A. Nesteroff, Phys. Rev. A 79, 022107 (2009) CrossRef
  20. L. Wang et al., 鈥淐omment on 鈥淐lassical signature of quantum annealing鈥?鈥?(unpublished) (2013)
  21. A.P. Young, S. Knysh, V. Smelyanskiy, Phys. Rev. Lett. 104, 020502 (2010) CrossRef
  22. I. Hen, A.P. Young, Phys. Rev. E. 84, 061152 (2011) CrossRef
  23. E. Farhi, D. Gosset, I. Hen, A. Sandvik, P. Shor, A.P. Young, F. Zamponi, Phys. Rev. A 86, 052334 (2012) CrossRef
  24. I. Hen, A.P. Young, Phys. Rev. A. 86, 042310 (2012) CrossRef
  25. I. Hen, Phys. Rev. E. 85, 036705 (2012) CrossRef
  26. I. Hen, J. Phys. A 47, 045305 (2014) CrossRef
  27. I. Hen, J. Phys. A 47, 235304 (2014) CrossRef
  28. A. Sandvik, Phys. Rev. B 59, R14157 (1999) CrossRef
  29. A. Sandvik, J. Phys, A 25, 3667 (1992) CrossRef
  30. L. Zdeborov谩, M. M茅zard, Phys. Rev. Lett. 101, 078702 (2008) CrossRef
  31. L. Zdeborov谩, M. M茅zard, J. Stat. Mech. 12, P12004 (2008) CrossRef
  32. T. J枚rg, F. Krzakala, G. Semerjian, F. Zamponi, Phys. Rev. Lett. 104, 207206 (2010) CrossRef
  33. S. Kirkpatrick, B. Selman, Science 264, 1297 (1994) CrossRef
  34. A.P. Young, S. Knysh, V. Smelyanskiy, Phys. Rev. Lett. 101, 170503 (2008) CrossRef
  35. C.K. Thomas, H.G. Katzgraber, Phys. Rev. E 83, 046709 (2011) CrossRef
  36. M. Guidetti, A.P. Young, Phys. Rev. E 84, 011102 (2011) CrossRef
  37. For information about WALKSAT see http://www.cs.rochester.edu//kautz/walksat/
  38. T. J枚rg, F. Krzakala, J. Kurchan, A.C. Maggs, Phys. Rev. Lett. 101, 147204 (2008) CrossRef
  39. T. J枚rg, F. Krzakala, J. Kurchan, A.C. Maggs, J. Pujos, Europhys. Lett. 89, 40004 (2010) CrossRef
  40. S.F. Edwards, P.W. Anderson, J. Phys. F 5, 965 (1975) CrossRef
  41. Y. Matsuda, H. Nishimori, L. Zdeborova, J. Phys. A: Math. Theor. 44, 185002 (2007) CrossRef
  42. N. Wiebe, N.S. Babcock, New J. Phys. 14, 013024 (2012) CrossRef
  43. J. Roland, N.J. Cerf, Phys. Rev. A 65, 042308 (2002) CrossRef
  44. E. Farhi, J. Goldstone, D. Gosset, S. Gutmann, H.B. Meyer, P. Shor, Quant. Inf. Comp. 11, 181 (2009)
  45. A. Perdomo-Ortiz, S.E. Venegas-Andraca, A. Aspuru-Guzik, Quantum Inf. Process. 10, 33 (2010) CrossRef
  46. N. Dickson, et al., Nature Comm. 4, 1903 (2013) CrossRef
  47. S. Bravyi, B. Terhal, SIAM J. Comput. 39, 1462 (2009) CrossRef
  
• 刊物类别：Physics and Astronomy
• 刊物主题：Physics
  Condensed Matter
  Materials Science
  Atoms, Molecules, Clusters and Plasmas
  Electromagnetism, Optics and Lasers
  Measurement Science and Instrumentation
  Mechanics, Fluids and Thermodynamics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1951-6401

文摘

One of the major ongoing debates on the future of quantum annealers pertains to their robustness against the decohering effects of finite temperature and interactions with the environment. We argue that even in an ideal setting of very low temperatures and in the absence of a decohering environment, quantum annealers may find it challenging to solve optimization problems significantly faster than state-of-the-art heuristic classical algorithms. Here, we study the performance of the quantum adiabatic algorithm (QAA) on a variety of constraint satisfaction problems by examining the size dependence of the minimum energy gap during the evolution of the QAA. We do so by employing Quantum Monte Carlo schemes as these allow us to study these problems at much larger scales than exact methods would allow. We find that in all cases a quantum phase transition occurs and the minimum gap decreases exponentially with system size, leading to an exponentially large running time for the QAA. Based on these and other results, we discuss potential modifications to the QAA that may improve the scaling of the minimum gap, leading to faster quantum adiabatic algorithms.