{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T18:28:58Z","timestamp":1783103338842,"version":"3.54.6"},"reference-count":77,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T00:00:00Z","timestamp":1605657600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T00:00:00Z","timestamp":1605657600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100008902","name":"Los Alamos National Laboratory","doi-asserted-by":"crossref","award":["20180719ER"],"award-info":[{"award-number":["20180719ER"]}],"id":[{"id":"10.13039\/100008902","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100008902","name":"Los Alamos National Laboratory","doi-asserted-by":"crossref","award":["20190195ER"],"award-info":[{"award-number":["20190195ER"]}],"id":[{"id":"10.13039\/100008902","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The recent emergence of novel computational devices, such as quantum computers, coherent Ising machines, and digital annealers presents new opportunities for hardware-accelerated hybrid optimization algorithms. Unfortunately, demonstrations of unquestionable performance gains leveraging novel hardware platforms have faced significant obstacles. One key challenge is understanding the algorithmic properties that distinguish such devices from established optimization approaches. Through the careful design of contrived optimization tasks, this work provides new insights into the computation properties of quantum annealing and suggests that this model has the potential to quickly identify the structure of high-quality solutions. A meticulous comparison to a variety of algorithms spanning both complete and local search suggests that quantum annealing\u2019s performance on the proposed optimization tasks is distinct. This result provides new insights into the time scales and types of optimization problems where quantum annealing has the potential to provide notable performance gains over established optimization algorithms and suggests the development of hybrid algorithms that combine the best features of quantum annealing and state-of-the-art classical approaches.<\/jats:p>","DOI":"10.1007\/s10601-020-09315-0","type":"journal-article","created":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T07:01:52Z","timestamp":1605682912000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["The potential of quantum annealing for rapid solution structure identification"],"prefix":"10.1007","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4532-7053","authenticated-orcid":false,"given":"Yuchen","family":"Pang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3238-1699","authenticated-orcid":false,"given":"Carleton","family":"Coffrin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3269-7263","authenticated-orcid":false,"given":"Andrey Y.","family":"Lokhov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7999-9897","authenticated-orcid":false,"given":"Marc","family":"Vuffray","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,11,18]]},"reference":[{"key":"9315_CR1","unstructured":"Aaronson, S. (2017). Insert d-wave post here. Published online at http:\/\/www.scottaaronson.com\/blog\/?p=3192. Accessed 28 Apr 2017."},{"issue":"3","key":"9315_CR2","doi-asserted-by":"publisher","first-page":"035011","DOI":"10.1088\/2058-9565\/ab935a","volume":"5","author":"JI Adame","year":"2020","unstructured":"Adame, J.I., & McMahon, P.L. (2020). Inhomogeneous driving in quantum annealers can result in orders-of-magnitude improvements in performance. Quantum Science and Technology, 5(3), 035011. https:\/\/doi.org\/10.1088\/2058-9565\/ab935a. https:\/\/iopscience.iop.org\/article\/10.1088\/2058-9565\/ab935a.","journal-title":"Quantum Science and Technology"},{"issue":"1","key":"9315_CR3","doi-asserted-by":"publisher","first-page":"015,002","DOI":"10.1103\/RevModPhys.90.015002","volume":"90","author":"T Albash","year":"2018","unstructured":"Albash, T., & Lidar, D.A. (2018). Adiabatic quantum computation. Reviews of Modern Physics, 90(1), 015,002.","journal-title":"Reviews of Modern Physics"},{"issue":"031","key":"9315_CR4","doi-asserted-by":"publisher","first-page":"016","DOI":"10.1103\/PhysRevX.8.031016","volume":"8","author":"T Albash","year":"2018","unstructured":"Albash, T., & Lidar, D.A. (2018). Demonstration of a scaling advantage for a quantum annealer over simulated annealing. Physical Review X, 8(031), 016. https:\/\/doi.org\/10.1103\/PhysRevX.8.031016.","journal-title":"Physical Review X"},{"issue":"7779","key":"9315_CR5","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1038\/s41586-019-1666-5","volume":"574","author":"F Arute","year":"2019","unstructured":"Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J.C., Barends, R., Biswas, R., Boixo, S., Brandao, F.G.S.L., & et al. (2019). Quantum supremacy using a programmable superconducting processor. Nature, 574(7779), 505\u2013510. https:\/\/doi.org\/10.1038\/s41586-019-1666-5.","journal-title":"Nature"},{"key":"9315_CR6","unstructured":"Baccari, F., Gogolin, C., Wittek, P., & Ac\u00edn, A. (2018). Verification of quantum optimizers. arXiv:1808.01275\n                           1808.01275."},{"issue":"10","key":"9315_CR7","doi-asserted-by":"publisher","first-page":"3241","DOI":"10.1088\/0305-4470\/15\/10\/028","volume":"15","author":"F Barahona","year":"1982","unstructured":"Barahona, F. (1982). On the computational complexity of ising spin glass models. Journal of Physics A: Mathematical and General, 15(10), 3241.","journal-title":"Journal of Physics A: Mathematical and General"},{"key":"9315_CR8","doi-asserted-by":"publisher","first-page":"56","DOI":"10.3389\/fphy.2014.00056","volume":"2","author":"Z Bian","year":"2014","unstructured":"Bian, Z., Chudak, F., Israel, R., Lackey, B., Macready, W.G., & Roy, A. (2014). Discrete optimization using quantum annealing on sparse ising models. Frontiers in Physics, 2, 56. https:\/\/doi.org\/10.3389\/fphy.2014.00056.","journal-title":"Frontiers in Physics"},{"key":"9315_CR9","doi-asserted-by":"publisher","first-page":"14","DOI":"10.3389\/fict.2016.00014","volume":"3","author":"Z Bian","year":"2016","unstructured":"Bian, Z., Chudak, F., Israel, R.B., Lackey, B., Macready, W.G., & Roy, A. (2016). Mapping constrained optimization problems to quantum annealing with application to fault diagnosis. Frontiers in ICT, 3, 14. https:\/\/doi.org\/10.3389\/fict.2016.00014.","journal-title":"Frontiers in ICT"},{"issue":"1","key":"9315_CR10","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s10107-005-0637-9","volume":"109","author":"A Billionnet","year":"2007","unstructured":"Billionnet, A., & Elloumi, S. (2007). Using a mixed integer quadratic programming solver for the unconstrained quadratic 0-1 problem. Mathematical Programming, 109(1), 55\u201368. https:\/\/doi.org\/10.1007\/s10107-005-0637-9.","journal-title":"Mathematical Programming"},{"issue":"3","key":"9315_CR11","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1038\/nphys2900","volume":"10","author":"S Boixo","year":"2014","unstructured":"Boixo, S., Ronnow, T.F., Isakov, S.V., Wang, Z., Wecker, D., Lidar, D.A., Martinis, J.M., & Troyer, M. (2014). Evidence for quantum annealing with more than one hundred qubits. Nature Physics, 10(3), 218\u2013224. https:\/\/doi.org\/10.1038\/nphys2900.Article.","journal-title":"Nature Physics"},{"issue":"1","key":"9315_CR12","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(01)00341-9","volume":"123","author":"E Boros","year":"2002","unstructured":"Boros, E., & Hammer, P.L. (2002). Pseudo-boolean optimization. Discrete Applied Mathematics, 123 (1), 155\u2013225. https:\/\/doi.org\/10.1016\/S0166-218X(01)00341-9. http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0166218X01003419.","journal-title":"Discrete Applied Mathematics"},{"key":"9315_CR13","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1103\/RevModPhys.39.883","volume":"39","author":"SG Brush","year":"1967","unstructured":"Brush, S.G. (1967). History of the lenz-ising model. Reviews of Modern Physics, 39, 883\u2013893. https:\/\/doi.org\/10.1103\/RevModPhys.39.883.","journal-title":"Reviews of Modern Physics"},{"key":"9315_CR14","unstructured":"Chmielewski, M., Amini, J., Hudek, K., Kim, J., Mizrahi, J., Monroe, C., Wright, K., & Moehring, D. (2018). Cloud-based trapped-ion quantum computing. In APS Meeting abstracts."},{"key":"9315_CR15","doi-asserted-by":"crossref","unstructured":"Coffrin, C., Nagarajan, H., & Bent, R. (2016). Challenges and successes of solving binary quadratic programming benchmarks on the DW2x QPU. Tech. rep. Los Alamos National Laboratory (LANL).","DOI":"10.2172\/1330084"},{"key":"9315_CR16","doi-asserted-by":"crossref","unstructured":"Coffrin, C., Nagarajan, H., & Bent, R. (2019). Evaluating ising processing units with integer programming. In Rousseau, L.M., & Stergiou, K. (Eds.) Integration of constraint programming, artificial intelligence, and operations research (pp. 163\u2013181). Cham: Springer International Publishing.","DOI":"10.1007\/978-3-030-19212-9_11"},{"key":"9315_CR17","unstructured":"Coffrin, C., & Pang, Y. (2019). ising-solvers. https:\/\/github.com\/lanl-ansi\/ising-solvers."},{"key":"9315_CR18","unstructured":"Coles, P.J., Eidenbenz, S., Pakin, S., Adedoyin, A., Ambrosiano, J., Anisimov, P., Casper, W., Chennupati, G., Coffrin, C., Djidjev, H., & et al. (2018). Quantum algorithm implementations for beginners. arXiv:1804.03719."},{"key":"9315_CR19","unstructured":"Cugliandolo, L.F. (2018). Advanced statistical physics: Frustration. https:\/\/www.lpthe.jussieu.fr\/leticia\/TEACHING\/master2018\/frustration18.pdf."},{"key":"9315_CR20","unstructured":"Dash, S. (2013). A note on qubo instances defined on chimera graphs. arXiv:1306.1202."},{"issue":"5","key":"9315_CR21","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1051\/jphyslet:01985004605017300","volume":"46","author":"JA d\u2019Auriac","year":"1985","unstructured":"d\u2019Auriac, J.A., Preissmann, M., & Rammal, R. (1985). The random field ising model: algorithmic complexity and phase transition. Journal de Physique Lettres, 46(5), 173\u2013180.","journal-title":"Journal de Physique Lettres"},{"key":"9315_CR22","doi-asserted-by":"publisher","first-page":"031,015","DOI":"10.1103\/PhysRevX.6.031015","volume":"6","author":"VS Denchev","year":"2016","unstructured":"Denchev, V.S., Boixo, S., Isakov, S.V., Ding, N., Babbush, R., Smelyanskiy, V., Martinis, J., & Neven, H. (2016). What is the computational value of finite-range tunneling?. Physical Review X, 6, 031,015. https:\/\/doi.org\/10.1103\/PhysRevX.6.031015.","journal-title":"Physical Review X"},{"issue":"15","key":"9315_CR23","doi-asserted-by":"publisher","first-page":"5259","DOI":"10.1088\/0305-4470\/30\/15\/013","volume":"30","author":"D Dhar","year":"1997","unstructured":"Dhar, D., Shukla, P., & Sethna, J.P. (1997). Zero-temperature hysteresis in the random-field ising model on a bethe lattice. Journal of Physics A: Mathematical and General, 30(15), 5259.","journal-title":"Journal of Physics A: Mathematical and General"},{"key":"9315_CR24","doi-asserted-by":"crossref","unstructured":"Ding, J., Sly, A., & Sun, N. (2015). Proof of the satisfiability conjecture for large k. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pp. 59\u201368. ACM.","DOI":"10.1145\/2746539.2746619"},{"issue":"36","key":"9315_CR25","doi-asserted-by":"publisher","first-page":"15,274","DOI":"10.1073\/pnas.0900282106","volume":"106","author":"N Eagle","year":"2009","unstructured":"Eagle, N., Pentland, A.S., & Lazer, D. (2009). Inferring friendship network structure by using mobile phone data. Proceedings of the national academy of sciences, 106(36), 15,274\u201315,278.","journal-title":"Proceedings of the national academy of sciences"},{"key":"9315_CR26","unstructured":"Fabio L., & Traversa, M.D.V. (2018). Memcomputing integer linear programming. arXiv:https:\/\/arxiv.org\/abs\/1808.09999."},{"issue":"5516","key":"9315_CR27","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1126\/science.1057726","volume":"292","author":"E Farhi","year":"2001","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., & Preda, D. (2001). A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem. Science, 292(5516), 472\u2013475. https:\/\/doi.org\/10.1126\/science.1057726. http:\/\/science.sciencemag.org\/content\/292\/5516\/472.","journal-title":"Science"},{"key":"9315_CR28","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., & Sipser, M. (2018). Quantum computation by adiabatic evolution. arXiv:https:\/\/arxiv.org\/abs\/quant-ph\/0001106."},{"issue":"6","key":"9315_CR29","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/BF02650179","volume":"21","author":"RP Feynman","year":"1982","unstructured":"Feynman, R.P. (1982). Simulating physics with computers. International Journal of Theoretical Physics, 21(6), 467\u2013488.","journal-title":"International Journal of Theoretical Physics"},{"issue":"5","key":"9315_CR30","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1109\/26.768759","volume":"47","author":"MP Fossorier","year":"1999","unstructured":"Fossorier, M.P., Mihaljevic, M., & Imai, H. (1999). Reduced complexity iterative decoding of low-density parity check codes based on belief propagation. IEEE Transactions on communications, 47(5), 673\u2013680.","journal-title":"IEEE Transactions on communications"},{"key":"9315_CR31","unstructured":"Fujitsu. (2018). Digital annealer. Published online at http:\/\/www.fujitsu.com\/global\/digitalannealer\/. Accessed 26 Feb 2019."},{"key":"9315_CR32","volume-title":"Statistical mechanics: A short treatise","author":"G Gallavotti","year":"2013","unstructured":"Gallavotti, G. (2013). Statistical mechanics: A short treatise. Berlin: Springer Science & Business Media."},{"issue":"2","key":"9315_CR33","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1063\/1.1703954","volume":"4","author":"RJ Glauber","year":"1963","unstructured":"Glauber, R.J. (1963). Time-dependent statistics of the ising model. Journal of mathematical physics, 4(2), 294\u2013307.","journal-title":"Journal of mathematical physics"},{"key":"9315_CR34","doi-asserted-by":"crossref","unstructured":"Grover, L.K. (1996). A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 212\u2013219. ACM.","DOI":"10.1145\/237814.237866"},{"key":"9315_CR35","unstructured":"Gurobi Optimization, Inc. (2014). Gurobi optimizer reference manual Published online at http:\/\/www.gurobi.com."},{"issue":"5","key":"9315_CR36","doi-asserted-by":"publisher","first-page":"eaau0823","DOI":"10.1126\/sciadv.aau0823","volume":"5","author":"R Hamerly","year":"2019","unstructured":"Hamerly, R., Inagaki, T., McMahon, P.L., Venturelli, D., Marandi, A., Onodera, T., Ng, E., Langrock, C., Inaba, K., Honjo, T., & et al. (2019). Experimental investigation of performance differences between coherent ising machines and a quantum annealer. Science Advances, 5(5), eaau0823.","journal-title":"Science Advances"},{"key":"9315_CR37","unstructured":"Hamze, F., & de Freitas, N. (2004). From fields to trees. In Proceedings of the 20th conference on uncertainty in artificial intelligence, UAI \u201904, pp. 243\u2013250. AUAI Press, Arlington, Virginia, United States. http:\/\/dl.acm.org\/citation.cfm?id=1036843.1036873."},{"key":"9315_CR38","doi-asserted-by":"publisher","unstructured":"Haribara, Y., Utsunomiya, S., & Yamamoto, Y. (2016). A coherent ising machine for MAX-CUT problems: performance evaluation against semidefinite programming and simulated annealing, pp. 251\u2013262. Springer Japan, Tokyo. https:\/\/doi.org\/10.1007\/978-4-431-55756-2_12.","DOI":"10.1007\/978-4-431-55756-2_12"},{"issue":"8","key":"9315_CR39","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1073\/pnas.79.8.2554","volume":"79","author":"JJ Hopfield","year":"1982","unstructured":"Hopfield, J.J. (1982). Neural networks and physical systems with emergent collective computational abilities. Proceedings of the national academy of sciences, 79(8), 2554\u20132558.","journal-title":"Proceedings of the national academy of sciences"},{"issue":"6312","key":"9315_CR40","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1126\/science.aah4243","volume":"354","author":"T Inagaki","year":"2016","unstructured":"Inagaki, T., Haribara, Y., Igarashi, K., Sonobe, T., Tamate, S., Honjo, T., Marandi, A., McMahon, P.L., Umeki, T., Enbutsu, K., Tadanaga, O., Takenouchi, H., Aihara, K., Kawarabayashi, K.I., Inoue, K., Utsunomiya, S., & Takesue, H. (2016). A coherent ising machine for 2000-node optimization problems. Science, 354(6312), 603\u2013606. https:\/\/doi.org\/10.1126\/science.aah4243. http:\/\/science.sciencemag.org\/content\/354\/6312\/603.","journal-title":"Science"},{"key":"9315_CR41","unstructured":"International Business Machines Corporation. (2017). Ibm building first universal quantum computers for business and science. Published online at https:\/\/www-03.ibm.com\/press\/us\/en\/pressrelease\/51740.wss. Accessed 28 Apr 2017."},{"key":"9315_CR42","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/j.cpc.2015.02.015","volume":"192","author":"S Isakov","year":"2015","unstructured":"Isakov, S., Zintchenko, I., R\u00f8nnow, T., & Troyer, M. (2015). Optimised simulated annealing for ising spin glasses. Computer Physics Communications, 192, 265\u2013271. https:\/\/doi.org\/10.1016\/j.cpc.2015.02.015. http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0010465515000727.","journal-title":"Computer Physics Communications"},{"issue":"7346","key":"9315_CR43","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1038\/nature10012","volume":"473","author":"MW Johnson","year":"2011","unstructured":"Johnson, M.W., Amin, M.H., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A.J., Johansson, J., Bunyk, P., & et al. (2011). Quantum annealing with manufactured spins. Nature, 473(7346), 194\u2013198.","journal-title":"Nature"},{"key":"9315_CR44","unstructured":"J\u00fcnger, M., Lobe, E., Mutzel, P., Reinelt, G., Rendl, F., Rinaldi, G., & Stollenwerk, T. (2019). Performance of a quantum annealer for ising ground state computations on chimera graphs. arXiv:1904.11965."},{"key":"9315_CR45","doi-asserted-by":"publisher","first-page":"5355","DOI":"10.1103\/PhysRevE.58.5355","volume":"58","author":"T Kadowaki","year":"1998","unstructured":"Kadowaki, T., & Nishimori, H. (1998). Quantum annealing in the transverse ising model. Physical Review E, 58, 5355\u20135363. https:\/\/doi.org\/10.1103\/PhysRevE.58.5355.","journal-title":"Physical Review E"},{"issue":"1","key":"9315_CR46","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41598-018-35416-1","volume":"8","author":"KP Kalinin","year":"2018","unstructured":"Kalinin, K.P., & Berloff, N.G. (2018). Global optimization of spin hamiltonians with gain-dissipative systems. Scientific Reports, 8(1), 1\u20139.","journal-title":"Scientific Reports"},{"key":"9315_CR47","doi-asserted-by":"publisher","unstructured":"Kielpinski, D., Bose, R., Pelc, J., Vaerenbergh, T.V., Mendoza, G., Tezak, N., & Beausoleil, R.G. (2016). Information processing with large-scale optical integrated circuits. In 2016 IEEE International conference on rebooting computing (ICRC), pp. 1\u20134. https:\/\/doi.org\/10.1109\/ICRC.2016.7738704.","DOI":"10.1109\/ICRC.2016.7738704"},{"key":"9315_CR48","unstructured":"King, A.D., Lanting, T., & Harris, R. (2015). Performance of a quantum annealer on range-limited constraint satisfaction problems. arXiv:1502.02098."},{"key":"9315_CR49","unstructured":"King, J., Yarkoni, S., Raymond, J., Ozfidan, I., King, A.D., Nevisi, M.M., Hilton, J.P., & McGeoch, C.C. (2017). Quantum annealing amid local ruggedness and global frustration. arXiv:https:\/\/arxiv.org\/abs\/1701.04579."},{"issue":"042","key":"9315_CR50","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1103\/PhysRevA.96.042322","volume":"96","author":"T Lanting","year":"2017","unstructured":"Lanting, T., King, A.D., Evert, B., & Hoskinson, E. (2017). Experimental demonstration of perturbative anticrossing mitigation using nonuniform driver hamiltonians. Physical Review A, 96(042), 322. https:\/\/doi.org\/10.1103\/PhysRevA.96.042322.","journal-title":"Physical Review A"},{"issue":"4","key":"9315_CR51","doi-asserted-by":"publisher","first-page":"040,607","DOI":"10.1103\/PhysRevLett.122.040607","volume":"122","author":"T Leleu","year":"2019","unstructured":"Leleu, T., Yamamoto, Y., McMahon, P.L., & Aihara, K. (2019). Destabilization of local minima in analog spin systems by correction of amplitude heterogeneity. Physical Review Letters, 122(4), 040,607.","journal-title":"Physical Review Letters"},{"issue":"3","key":"9315_CR52","doi-asserted-by":"publisher","first-page":"e1700,","DOI":"10.1126\/sciadv.1700791","volume":"4","author":"AY Lokhov","year":"2018","unstructured":"Lokhov, A.Y., Vuffray, M., Misra, S., & Chertkov, M. (2018). Optimal structure and parameter learning of ising models. Science Advances, 4(3), e1700,.","journal-title":"Science Advances"},{"key":"9315_CR53","doi-asserted-by":"publisher","first-page":"5","DOI":"10.3389\/fphy.2014.00005","volume":"2","author":"A Lucas","year":"2014","unstructured":"Lucas, A. (2014). Ising formulations of many np problems. Frontiers in Physics, 2, 5. https:\/\/doi.org\/10.3389\/fphy.2014.00005.","journal-title":"Frontiers in Physics"},{"issue":"022","key":"9315_CR54","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1103\/PhysRevA.94.022337","volume":"94","author":"S Mandr\u00e0","year":"2016","unstructured":"Mandr\u00e0, S., Zhu, Z., Wang, W., Perdomo-Ortiz, A., & Katzgraber, H.G. (2016). Strengths and weaknesses of weak-strong cluster problems: a detailed overview of state-of-the-art classical heuristics versus quantum approaches. Physical Review A, 94(022), 337. https:\/\/doi.org\/10.1103\/PhysRevA.94.022337.","journal-title":"Physical Review A"},{"issue":"8","key":"9315_CR55","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1038\/nmeth.2016","volume":"9","author":"D Marbach","year":"2012","unstructured":"Marbach, D., Costello, J.C., K\u00fcffner, R., Vega, N.M., Prill, R.J., Camacho, D.M., Allison, K.R., Aderhold, A., Bonneau, R., Chen, Y., & et al. (2012). Wisdom of crowds for robust gene network inference. Nature Methods, 9(8), 796.","journal-title":"Nature Methods"},{"issue":"044","key":"9315_CR56","doi-asserted-by":"publisher","first-page":"083","DOI":"10.1103\/PhysRevApplied.11.044083","volume":"11","author":"J Marshall","year":"2019","unstructured":"Marshall, J., Venturelli, D., Hen, I., & Rieffel, E.G. (2019). Power of pausing: Advancing understanding of thermalization in experimental quantum annealers. Physical Review Applied, 11(044), 083. https:\/\/doi.org\/10.1103\/PhysRevApplied.11.044083.","journal-title":"Physical Review Applied"},{"key":"9315_CR57","unstructured":"McGeoch, C.C., King, J., Nevisi, M.M., Yarkoni, S., & Hilton, J. (2017). Optimization with clause problems. Published online at https:\/\/www.dwavesys.com\/sites\/default\/fies\/14-1001A_tr_Optimization_with_Clause_Problems.pdf. Accessed 10 Feb 2020."},{"key":"9315_CR58","doi-asserted-by":"publisher","unstructured":"McGeoch, C.C., & Wang, C. (2013). Experimental evaluation of an adiabiatic quantum system for combinatorial optimization. In Proceedings of the ACM international conference on computing frontiers, CF \u201913, pp. 23:1\u201323:11. ACM, New York, NY, USA. https:\/\/doi.org\/10.1145\/2482767.2482797.","DOI":"10.1145\/2482767.2482797"},{"key":"9315_CR59","doi-asserted-by":"crossref","unstructured":"McMahon, P.L., Marandi, A., Haribara, Y., Hamerly, R., Langrock, C., Tamate, S., Inagaki, T., Takesue, H., Utsunomiya, S., Aihara, K., & et al. (2016). A fully-programmable 100-spin coherent ising machine with all-to-all connections. Science, p aah5178.","DOI":"10.1126\/science.aah5178"},{"key":"9315_CR60","doi-asserted-by":"crossref","unstructured":"Mezard, M., Mezard, M., & Montanari, A. (2009). Information, physics, and computation. Oxford: Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001"},{"issue":"8","key":"9315_CR61","doi-asserted-by":"publisher","first-page":"1293","DOI":"10.1051\/jphys:019850046080129300","volume":"46","author":"M M\u00e9zard","year":"1985","unstructured":"M\u00e9zard, M., & Virasoro, M.A. (1985). The microstructure of ultrametricity. Journal de Physique, 46(8), 1293\u20131307.","journal-title":"Journal de Physique"},{"key":"9315_CR62","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1038\/543171a","volume":"543","author":"M Mohseni","year":"2017","unstructured":"Mohseni, M., Read, P., Neven, H., Boixo, S., Denchev, V., Babbush, R., Fowler, A., Smelyanskiy, V., & Martinis, J. (2017). Commercialize quantum technologies in five years. Nature, 543, 171\u2013174. http:\/\/www.nature.com\/news\/commercialize-quantum-technologies-in-five-years-1.21583.","journal-title":"Nature"},{"issue":"49","key":"9315_CR63","doi-asserted-by":"publisher","first-page":"E1293","DOI":"10.1073\/pnas.1111471108","volume":"108","author":"F Morcos","year":"2011","unstructured":"Morcos, F., Pagnani, A., Lunt, B., Bertolino, A., Marks, D.S., Sander, C., Zecchina, R., Onuchic, J.N., Hwa, T., & Weigt, M. (2011). Direct-coupling analysis of residue coevolution captures native contacts across many protein families. Proceedings of the National Academy of Sciences, 108(49), E1293\u2013E1301.","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"10","key":"9315_CR64","doi-asserted-by":"publisher","first-page":"939","DOI":"10.1109\/34.464559","volume":"17","author":"DK Panjwani","year":"1995","unstructured":"Panjwani, D.K., & Healey, G. (1995). Markov random field models for unsupervised segmentation of textured color images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17(10), 939\u2013954.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"9315_CR65","doi-asserted-by":"crossref","unstructured":"Parekh, O., Wendt, J., Shulenburger, L., Landahl, A., Moussa, J., & Aidun, J. (2015). Benchmarking adiabatic quantum optimization for complex network analysis. arXiv:https:\/\/arxiv.org\/abs\/1604.00319.","DOI":"10.2172\/1459086"},{"key":"9315_CR66","unstructured":"Puget, J.F. (2013). D-wave vs cplex comparison. part 2: Qubo. Published online. Accessed 28 Nov 2018."},{"issue":"1","key":"9315_CR67","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11128-014-0892-x","volume":"14","author":"EG Rieffel","year":"2015","unstructured":"Rieffel, E.G., Venturelli, D., O\u2019Gorman, B., Do, M.B., Prystay, E.M., & Smelyanskiy, V.N. (2015). A case study in programming a quantum annealer for hard operational planning problems. Quantum Information Processing, 14(1), 1\u201336. https:\/\/doi.org\/10.1007\/s11128-014-0892-x.","journal-title":"Quantum Information Processing"},{"issue":"7087","key":"9315_CR68","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1038\/nature04701","volume":"440","author":"E Schneidman","year":"2006","unstructured":"Schneidman, E., Berry II, M.J., Segev, R., & Bialek, W. (2006). Weak pairwise correlations imply strongly correlated network states in a neural population. Nature, 440(7087), 1007.","journal-title":"Nature"},{"key":"9315_CR69","unstructured":"Selby, A. (2013). Qubo-chimera. https:\/\/github.com\/alex1770\/QUBO-chimera."},{"key":"9315_CR70","unstructured":"Selby, A. (2014). Efficient subgraph-based sampling of ising-type models with frustration. https:\/\/arxiv.org\/abs\/1409.3934."},{"key":"9315_CR71","doi-asserted-by":"crossref","unstructured":"Shor, P.W. (1994). Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pp. 124\u2013134. Ieee.","DOI":"10.1109\/SFCS.1994.365700"},{"key":"9315_CR72","unstructured":"Venturelli, D., Marchand, D.J.J., & Rojo, G. (2015). Quantum annealing implementation of job-shop scheduling. arXiv:https:\/\/arxiv.org\/abs\/1506.08479."},{"key":"9315_CR73","unstructured":"Vuffray, M. (2014). The cavity method in coding theory. Tech. rep. EPFL."},{"key":"9315_CR74","unstructured":"Vuffray, M., Misra, S., Lokhov, A., & Chertkov, M. (2016). Interaction screening: Efficient and sample-optimal learning of ising models. In Lee, D.D., Sugiyama, M., Luxburg, U.V., Guyon, I., & Garnett, R. (Eds.) Advances in neural information processing systems 29. pp 2595\u20132603. Curran Associates, Inc."},{"key":"9315_CR75","unstructured":"Vuffray, M., Misra, S., & Lokhov, A.Y. (2019). Efficient learning of discrete graphical models. arXiv:1902.00600."},{"key":"9315_CR76","doi-asserted-by":"publisher","unstructured":"Yamaoka, M., Yoshimura, C., Hayashi, M., Okuyama, T., & Aoki, H. (2015). Mizuno, h.: 24.3 20k-spin ising chip for combinational optimization problem with cmos annealing. In 2015 IEEE International solid-state circuits conference - (ISSCC) digest of technical papers, pp. 1\u20133. https:\/\/doi.org\/10.1109\/ISSCC.2015.7063111.","DOI":"10.1109\/ISSCC.2015.7063111"},{"key":"9315_CR77","doi-asserted-by":"publisher","unstructured":"Yoshimura, C., Yamaoka, M., Aoki, H., & Mizuno, H. (2013). Spatial computing architecture using randomness of memory cell stability under voltage control. In 2013 European conference on circuit theory and design (ECCTD), pp. 1\u20134. https:\/\/doi.org\/10.1109\/ECCTD.2013.6662276.","DOI":"10.1109\/ECCTD.2013.6662276"}],"updated-by":[{"DOI":"10.1007\/s10601-021-09320-x","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T00:00:00Z","timestamp":1618185600000}}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-020-09315-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10601-020-09315-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-020-09315-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,14]],"date-time":"2024-10-14T16:09:30Z","timestamp":1728922170000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10601-020-09315-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,18]]},"references-count":77,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["9315"],"URL":"https:\/\/doi.org\/10.1007\/s10601-020-09315-0","relation":{"correction":[{"id-type":"doi","id":"10.1007\/s10601-021-09320-x","asserted-by":"object"}]},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,18]]},"assertion":[{"value":"15 October 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 November 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 April 2021","order":3,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":4,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":5,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s10601-021-09320-x","URL":"https:\/\/doi.org\/10.1007\/s10601-021-09320-x","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with Ethical Standards"}},{"value":"None.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Conflict of interests"}}]}}