{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T08:50:34Z","timestamp":1740127834633,"version":"3.37.3"},"reference-count":45,"publisher":"Proceedings of the National Academy of Sciences","issue":"7","license":[{"start":{"date-parts":[[2018,1,30]],"date-time":"2018-01-30T00:00:00Z","timestamp":1517270400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000006","name":"DOD | United States Navy | Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-17-1-2569"],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["www.pnas.org"],"crossmark-restriction":true},"short-container-title":["Proc. Natl. Acad. Sci. U.S.A."],"published-print":{"date-parts":[[2018,2,13]]},"abstract":"Significance<\/jats:title>\n Quantum annealers are physical quantum devices designed to solve optimization problems by finding low-energy configurations of an appropriate energy function by exploiting cooperative tunneling effects to escape local minima. Classical annealers use thermal fluctuations for the same computational purpose, and Markov chains based on this principle are among the most widespread optimization techniques. The fundamental mechanism underlying quantum annealing consists of exploiting a controllable quantum perturbation to generate tunneling processes. The computational potentialities of quantum annealers are still under debate, since few ad hoc positive results are known. Here, we identify a wide class of large-scale nonconvex optimization problems for which quantum annealing is efficient while classical annealing gets stuck. These problems are of central interest to machine learning.<\/jats:p>","DOI":"10.1073\/pnas.1711456115","type":"journal-article","created":{"date-parts":[[2018,1,30]],"date-time":"2018-01-30T17:05:29Z","timestamp":1517331929000},"page":"1457-1462","update-policy":"https:\/\/doi.org\/10.1073\/pnas.cm10313","source":"Crossref","is-referenced-by-count":42,"title":["Efficiency of quantum vs. classical annealing in nonconvex learning problems"],"prefix":"10.1073","volume":"115","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5451-8388","authenticated-orcid":false,"given":"Carlo","family":"Baldassi","sequence":"first","affiliation":[{"name":"Bocconi Institute for Data Science and Analytics, Bocconi University, 20136 Milan, Italy;"},{"name":"Istituto Nazionale di Fisica Nucleare, Sezione di Torino, 10125 Turin, Italy;"}]},{"given":"Riccardo","family":"Zecchina","sequence":"additional","affiliation":[{"name":"Bocconi Institute for Data Science and Analytics, Bocconi University, 20136 Milan, Italy;"},{"name":"Condensed Matter and Statistical Physics Group, International Centre for Theoretical Physics, 34151 Trieste, Italy"}]}],"member":"341","published-online":{"date-parts":[[2018,1,30]]},"reference":[{"key":"e_1_3_3_1_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.39.11828"},{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0009-2614(94)00117-0"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.58.5355"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1057726"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.80.1061"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199233212.001.0001"},{"key":"e_1_3_3_7_2","first-page":"165","article-title":"Beweis des adiabatensatzes","volume":"51","author":"Born M","year":"1928","unstructured":"M Born, V Fock, Beweis des adiabatensatzes. Zeitschrift Phys A Hadrons Nuclei 51, 165\u2013180 (1928).","journal-title":"Zeitschrift Phys A Hadrons Nuclei"},{"key":"e_1_3_3_8_2","first-page":"1","article-title":"Zur theorie der energieubertragung. II","volume":"2","author":"Landau L","year":"1932","unstructured":"L Landau, Zur theorie der energieubertragung. II. Phys Z Sowjetunion 2, 1\u201313 (1932).","journal-title":"Phys Z Sowjetunion"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1932.0165"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1002116107"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2012.10.002"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1068774"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.66.094203"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.aaa4170"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1252319"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature10012"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1038\/nphys2900"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.69.161301"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.115.128101"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1608103113"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2016\/02\/023301"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.93.052313"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1051\/jphys:0198900500200305700"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.65.1683"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.105.167204"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10909-012-0609-4"},{"key":"e_1_3_3_27_2","unstructured":"I Hubara M Courbariaux D Soudry R El-Yaniv Y Bengio Quantized neural networks: Training neural networks with low precision weights and activations. arXiv:1609.07061. (2016)."},{"key":"e_1_3_3_28_2","first-page":"3105","volume-title":"Advances in Neural Information Processing Systems","author":"Courbariaux M","year":"2015","unstructured":"M Courbariaux, Y Bengio, JP David, BinaryConnect: Training deep neural networks with binary weights during propagations. Advances in Neural Information Processing Systems (Curran Associates, Red Hook, NY) Vol 28, 3105\u20133113 (2015)."},{"key":"e_1_3_3_29_2","volume-title":"Information Theory, Inference and Learning Algorithms","author":"MacKay DJ","year":"2003","unstructured":"DJ MacKay Information Theory, Inference and Learning Algorithms (Cambridge Univ Press, Cambridge, UK, 2003)."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature14539"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1038\/nphys3272"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/15\/10\/028"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.90.052813"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01313839"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2012\/06\/P06007"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/473\/1\/012011"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/aa5335"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0700324104"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1038\/nphys1865"},{"key":"e_1_3_3_40_2","unstructured":"NS Keskar D Mudigere J Nocedal M Smelyanskiy PTP Tang On large-batch training for deep learning 1609 large-batch training for deep learning: Generalization gap and sharp minima. arXiv:1609.04836. (2016)."},{"key":"e_1_3_3_41_2","unstructured":"L Bottou FE Curtis J Nocedal Optimization methods for large-scale machine learning. arXiv:1606.04838. (2016)."},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.96.030201"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-009-9822-1"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2015\/08\/P08008"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/bs.aiq.2015.12.002"}],"container-title":["Proceedings of the National Academy of Sciences"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.pnas.org\/syndication\/doi\/10.1073\/pnas.1711456115","content-type":"unspecified","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/pnas.org\/doi\/pdf\/10.1073\/pnas.1711456115","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,13]],"date-time":"2022-04-13T06:07:36Z","timestamp":1649830056000},"score":1,"resource":{"primary":{"URL":"https:\/\/pnas.org\/doi\/full\/10.1073\/pnas.1711456115"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,30]]},"references-count":45,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2018,2,13]]}},"alternative-id":["10.1073\/pnas.1711456115"],"URL":"https:\/\/doi.org\/10.1073\/pnas.1711456115","relation":{},"ISSN":["0027-8424","1091-6490"],"issn-type":[{"type":"print","value":"0027-8424"},{"type":"electronic","value":"1091-6490"}],"subject":[],"published":{"date-parts":[[2018,1,30]]},"assertion":[{"value":"2018-01-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}