{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T05:55:04Z","timestamp":1791352504299,"version":"4.3.1"},"reference-count":55,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,3,5]],"date-time":"2019-03-05T00:00:00Z","timestamp":1551744000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,3,5]],"date-time":"2019-03-05T00:00:00Z","timestamp":1551744000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s11128-019-2236-3","type":"journal-article","created":{"date-parts":[[2019,3,5]],"date-time":"2019-03-05T20:19:04Z","timestamp":1551817144000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":65,"title":["Efficiently embedding QUBO problems on adiabatic quantum computers"],"prefix":"10.1007","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1664-069X","authenticated-orcid":false,"given":"Prasanna","family":"Date","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Patton","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Catherine","family":"Schuman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Potok","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,3,5]]},"reference":[{"key":"2236_CR1","unstructured":"Adachi, S.H., Davenport, D.M., Henderson, M.P.: Quantum-assisted training of neural networks. US Patent App. 14\/702,203 (2015)"},{"issue":"1","key":"2236_CR2","doi-asserted-by":"publisher","first-page":"015002","DOI":"10.1103\/RevModPhys.90.015002","volume":"90","author":"T Albash","year":"2018","unstructured":"Albash, T., Lidar, D.A.: Adiabatic quantum computation. Rev. Modern Phys. 90(1), 015002 (2018)","journal-title":"Rev. Modern Phys."},{"key":"2236_CR3","unstructured":"Amin, M.H.: Methods of adiabatic quantum computation. US Patent 8,504,497 (2013)"},{"key":"2236_CR4","unstructured":"Amin, M.H., Steininger, M.F.: Adiabatic quantum computation with superconducting qubits. US Patent 7,135,701 (2006)"},{"key":"2236_CR5","volume-title":"The Traveling Salesman Problem: A Computational Study","author":"DL Applegate","year":"2006","unstructured":"Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton (2006)"},{"issue":"7606","key":"2236_CR6","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1038\/nature17658","volume":"534","author":"R Barends","year":"2016","unstructured":"Barends, R., Shabani, A., Lamata, L., Kelly, J., Mezzacapo, A., Las Heras, U., Babbush, R., Fowler, A.G., Campbell, B., Chen, Y., et al.: Digitized adiabatic quantum computing with a superconducting circuit. Nature 534(7606), 222 (2016)","journal-title":"Nature"},{"key":"2236_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08696-5","volume-title":"Multiprocessor Scheduling for Real-time Systems","author":"S Baruah","year":"2015","unstructured":"Baruah, S., Bertogna, M., Buttazzo, G.: Multiprocessor Scheduling for Real-time Systems. Springer, Berlin (2015)"},{"key":"2236_CR8","unstructured":"Biamonte, J.D., Berkley, A.J., Amin, M.: Physical realizations of a universal adiabatic quantum computer. US Patent 8,234,103 (2012)"},{"key":"2236_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.: Mapping constrained optimization problems to quantum annealing with application to fault diagnosis. Front. ICT 3, 14 (2016)","journal-title":"Front. ICT"},{"key":"2236_CR10","doi-asserted-by":"crossref","unstructured":"Bian, Z., Chudak, F., Macready, W., Roy, A., Sebastiani, R., Varotti, S.: Solving sat and maxsat with a quantum annealer: foundations and a preliminary report. In: International Symposium on Frontiers of Combining Systems, pp. 153\u2013171. Springer, Berlin (2017)","DOI":"10.1007\/978-3-319-66167-4_9"},{"key":"2236_CR11","unstructured":"Blum, A., Rivest, R.L.: Training a 3-node neural network is NP-complete. In: Advances in Neural Information Processing Systems, pp. 494\u2013501 (1989)"},{"issue":"1","key":"2236_CR12","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/s11128-015-1150-6","volume":"15","author":"T Boothby","year":"2016","unstructured":"Boothby, T., King, A.D., Roy, A.: Fast clique minor generation in chimera qubit connectivity graphs. Quantum Inf. Process. 15(1), 495\u2013508 (2016)","journal-title":"Quantum Inf. Process."},{"issue":"3","key":"2236_CR13","first-page":"39","volume":"13","author":"KA Britt","year":"2017","unstructured":"Britt, K.A., Humble, T.S.: High-performance computing with quantum processing units. ACM J. Emerg. Technol. Comput. Syst. (JETC) 13(3), 39 (2017)","journal-title":"ACM J. Emerg. Technol. Comput. Syst. (JETC)"},{"key":"2236_CR14","unstructured":"Cai, J., Macready, W.G., Roy, A.: A practical heuristic for finding graph minors. Preprint (2014). arXiv:1406.2741"},{"issue":"5","key":"2236_CR15","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1137\/0148063","volume":"48","author":"H Carrillo","year":"1988","unstructured":"Carrillo, H., Lipman, D.: The multiple sequence alignment problem in biology. SIAM J. Appl. Math. 48(5), 1073\u20131082 (1988)","journal-title":"SIAM J. Appl. Math."},{"key":"2236_CR16","unstructured":"Chickering, D.M., Geiger, D., Heckerman, D., et\u00a0al.: Learning Bayesian networks is NP-hard. Technical Report, Citeseer (1994)"},{"issue":"5","key":"2236_CR17","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s11128-008-0082-9","volume":"7","author":"V Choi","year":"2008","unstructured":"Choi, V.: Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Inf. Process. 7(5), 193\u2013209 (2008)","journal-title":"Quantum Inf. Process."},{"issue":"3","key":"2236_CR18","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s11128-010-0200-3","volume":"10","author":"V Choi","year":"2011","unstructured":"Choi, V.: Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quantum Inf. Process. 10(3), 343\u2013353 (2011)","journal-title":"Quantum Inf. Process."},{"key":"2236_CR19","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, pp. 151\u2013158. ACM, New York (1971)","DOI":"10.1145\/800157.805047"},{"key":"2236_CR20","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801389","volume-title":"An Introduction to Support Vector Machines and Other Kernel-based Learning Methods","author":"N Cristianini","year":"2000","unstructured":"Cristianini, N., Shawe-Taylor, J., et al.: An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press, Cambridge (2000)"},{"key":"2236_CR21","unstructured":"Dasgupta, S.: The hardness of $$k$$-means clustering. Department of Computer Science and Engineering, University of California, San Diego (2008)"},{"issue":"6110","key":"2236_CR22","doi-asserted-by":"publisher","first-page":"1042","DOI":"10.1126\/science.1219021","volume":"338","author":"KA Dill","year":"2012","unstructured":"Dill, K.A., MacCallum, J.L.: The protein-folding problem, 50 years on. Science 338(6110), 1042\u20131046 (2012)","journal-title":"Science"},{"key":"2236_CR23","first-page":"248","volume":"1","author":"O Dubois","year":"2001","unstructured":"Dubois, O., Dequen, G.: A backbone-search heuristic for efficient solving of hard 3-sat formulae. IJCAI 1, 248\u2013253 (2001)","journal-title":"IJCAI"},{"key":"2236_CR24","unstructured":"Esteve, D., Vion, D., Devoret, M., Urbina, C., Joyez, P., Pothier, H., Orfila, P.F., Aassime, A., Cottet, A.: Superconducting quantum-bit device based on josephson junctions. US Patent 6,838,694 (2005)"},{"issue":"2","key":"2236_CR25","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1287\/trsc.19.2.127","volume":"19","author":"MM Etschmaier","year":"1985","unstructured":"Etschmaier, M.M., Mathaisel, D.F.: Airline scheduling: an overview. Transp. Sci. 19(2), 127\u2013138 (1985)","journal-title":"Transp. Sci."},{"issue":"5","key":"2236_CR26","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/s11128-018-1863-4","volume":"17","author":"TD Goodrich","year":"2018","unstructured":"Goodrich, T.D., Sullivan, B.D., Humble, T.S.: Optimizing adiabatic quantum program compilation using a graph-theoretic framework. Quantum Inf. Process. 17(5), 118 (2018)","journal-title":"Quantum Inf. Process."},{"key":"2236_CR27","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 212\u2013219. ACM, New York (1996)","DOI":"10.1145\/237814.237866"},{"issue":"4","key":"2236_CR28","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/s11128-016-1513-7","volume":"16","author":"KE Hamilton","year":"2017","unstructured":"Hamilton, K.E., Humble, T.S.: Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets. Quantum Inf. Process. 16(4), 94 (2017)","journal-title":"Quantum Inf. Process."},{"issue":"1","key":"2236_CR29","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s41019-016-0030-0","volume":"2","author":"W Huang","year":"2017","unstructured":"Huang, W., Yu, J.X.: Investigating TSP heuristics for location-based services. Data Sci. Eng. 2(1), 71\u201393 (2017)","journal-title":"Data Sci. Eng."},{"issue":"20","key":"2236_CR30","doi-asserted-by":"publisher","first-page":"4204","DOI":"10.1103\/PhysRevLett.83.4204","volume":"83","author":"A Imamog","year":"1999","unstructured":"Imamog, A., Awschalom, D.D., Burkard, G., DiVincenzo, D.P., Loss, D., Sherwin, M., Small, A., et al.: Quantum information processing using quantum dot spins and cavity QED. Phys. Rev. Lett. 83(20), 4204 (1999)","journal-title":"Phys. Rev. Lett."},{"issue":"6681","key":"2236_CR31","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1038\/30156","volume":"393","author":"BE Kane","year":"1998","unstructured":"Kane, B.E.: A silicon-based nuclear spin quantum computer. Nature 393(6681), 133 (1998)","journal-title":"Nature"},{"issue":"5","key":"2236_CR32","doi-asserted-by":"publisher","first-page":"052314","DOI":"10.1103\/PhysRevA.87.052314","volume":"87","author":"T Keating","year":"2013","unstructured":"Keating, T., Goyal, K., Jau, Y.Y., Biedermann, G.W., Landahl, A.J., Deutsch, I.H.: Adiabatic quantum computation with Rydberg-dressed atoms. Phys. Rev. A 87(5), 052314 (2013)","journal-title":"Phys. Rev. A"},{"key":"2236_CR33","unstructured":"King, A.D., Israel, R.B., Bunyk, P.I., Boothby, T.J., Reinhardt, S.P., Roy, A.P., King, J.A., Lanting, T.M., Evert, A.J.: Systems and methods for embedding problems into an analog processor. US Patent App. 15\/487,295 (2017)"},{"key":"2236_CR34","volume-title":"Algorithm Design","author":"J Kleinberg","year":"2006","unstructured":"Kleinberg, J., Tardos, E.: Algorithm Design. Pearson Education India, Noida (2006)"},{"issue":"3","key":"2236_CR35","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1007\/s11128-013-0683-9","volume":"13","author":"C Klymko","year":"2014","unstructured":"Klymko, C., Sullivan, B.D., Humble, T.S.: Adiabatic quantum programming: minor embedding with hard faults. Quantum Inf. Process. 13(3), 709\u2013729 (2014)","journal-title":"Quantum Inf. Process."},{"key":"2236_CR36","unstructured":"Landahl, A.: Adiabatic quantum computing. In: APS Four Corners Section Meeting Abstracts (2012)"},{"issue":"2","key":"2236_CR37","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1002\/net.21751","volume":"70","author":"M Lewis","year":"2017","unstructured":"Lewis, M., Glover, F.: Quadratic unconstrained binary optimization problem preprocessing: theory and empirical analysis. Networks 70(2), 79\u201397 (2017)","journal-title":"Networks"},{"key":"2236_CR38","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1146\/annurev.genom.9.081307.164242","volume":"10","author":"Y Li","year":"2009","unstructured":"Li, Y., Willer, C., Sanna, S., Abecasis, G.: Genotype imputation. Ann. Rev. Genom. Hum. Genet. 10, 387\u2013406 (2009)","journal-title":"Ann. Rev. Genom. Hum. Genet."},{"key":"2236_CR39","unstructured":"Macready, W., Roy, A.P.: Systems and methods that formulate problems for solving by a quantum processor using hardware graph decomposition. US Patent 9,875,215 (2018)"},{"key":"2236_CR40","doi-asserted-by":"crossref","unstructured":"Nielsen, M.A., Chuang, I.: Quantum Computation and Quantum Information. AAPT (2002)","DOI":"10.1119\/1.1463744"},{"key":"2236_CR41","volume-title":"Computational Complexity","author":"CH Papadimitriou","year":"2003","unstructured":"Papadimitriou, C.H.: Computational Complexity. Wiley, London (2003)"},{"issue":"6","key":"2236_CR42","doi-asserted-by":"publisher","first-page":"062311","DOI":"10.1103\/PhysRevA.64.062311","volume":"64","author":"T Pittman","year":"2001","unstructured":"Pittman, T., Jacobs, B., Franson, J.: Probabilistic quantum logic operations using polarizing beam splitters. Phys. Rev. A 64(6), 062311 (2001)","journal-title":"Phys. Rev. A"},{"issue":"7417","key":"2236_CR43","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1038\/nature11449","volume":"489","author":"JJ Pla","year":"2012","unstructured":"Pla, J.J., Tan, K.Y., Dehollain, J.P., Lim, W.H., Morton, J.J., Jamieson, D.N., Dzurak, A.S., Morello, A.: A single-atom electron spin qubit in silicon. Nature 489(7417), 541 (2012)","journal-title":"Nature"},{"key":"2236_CR44","doi-asserted-by":"crossref","unstructured":"Potok, T.E., Schuman, C.D., Young, S.R., Patton, R.M., Spedalieri, F., Liu, J., Yao, K.T., Rose, G., Chakma, G.: A study of complex deep learning networks on high performance, neuromorphic, and quantum computers. In: Workshop on Machine Learning in HPC Environments (MLHPC), pp. 47\u201355. IEEE, New York (2016)","DOI":"10.1109\/MLHPC.2016.009"},{"issue":"1","key":"2236_CR45","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.: A case study in programming a quantum annealer for hard operational planning problems. Quantum Inf. Process. 14(1), 1\u201336 (2015)","journal-title":"Quantum Inf. Process."},{"key":"2236_CR46","unstructured":"Roy, A.P.: Systems and methods that formulate embeddings of problems for solving by a quantum processor. US Patent 9,501,747 (2016)"},{"issue":"1","key":"2236_CR47","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1186\/1471-2105-6-30","volume":"6","author":"A Shmygelska","year":"2005","unstructured":"Shmygelska, A., Hoos, H.H.: An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem. BMC Bioinformat. 6(1), 30 (2005)","journal-title":"BMC Bioinformat."},{"key":"2236_CR48","unstructured":"Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 1994 Proceedings., 35th Annual Symposium on Foundations of Computer Science, pp. 124\u2013134. IEEE, New York (1994)"},{"issue":"2","key":"2236_CR49","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1137\/S0036144598347011","volume":"41","author":"PW Shor","year":"1999","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303\u2013332 (1999)","journal-title":"SIAM Rev."},{"key":"2236_CR50","unstructured":"Thom, M.C., Roy, A.P., Chudak, F.A., Bian, Z., Macready, W.G., Israel, R.B., Boothby, T.J., Yarkoni, S., Xue, Y., Korenkevych, D., et\u00a0al.: Systems and methods for analog processing of problem graphs having arbitrary size and\/or connectivity. US Patent App. 15\/448,361 (2017)"},{"issue":"1","key":"2236_CR51","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1112\/plms\/s2-43.6.544","volume":"2","author":"AM Turing","year":"1938","unstructured":"Turing, A.M.: On computable numbers, with an application to the entscheidungsproblem. a correction. Proc. Lond. Math. Soc. 2(1), 544\u2013546 (1938)","journal-title":"Proc. Lond. Math. Soc."},{"issue":"3","key":"2236_CR52","first-page":"031040","volume":"5","author":"D Venturelli","year":"2015","unstructured":"Venturelli, D., Mandra, S., Knysh, S., O\u2019Gorman, B., Biswas, R., Smelyanskiy, V.: Quantum optimization of fully connected spin glasses. Phys. Rev. X 5(3), 031040 (2015)","journal-title":"Phys. Rev. X"},{"key":"2236_CR53","unstructured":"Zagoskin, A.M.: Qubit using a josephson junction between s-wave and d-wave superconductors. US Patent 6,459,097 (2002)"},{"key":"2236_CR54","unstructured":"Zagoskin, A.M.: Quantum computing method using magnetic flux states at a Josephson junction. US Patent 6,563,311 (2003)"},{"key":"2236_CR55","unstructured":"Zaribafiyan, A., Marchand, D., REZAEI, S.S.C.: Method and system for generating an embedding pattern used for solving a quadratic binary optimization problem. US Patent App. 15\/344,054 (2017)"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-019-2236-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11128-019-2236-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-019-2236-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,13]],"date-time":"2022-09-13T01:12:29Z","timestamp":1663031549000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11128-019-2236-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,5]]},"references-count":55,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["2236"],"URL":"https:\/\/doi.org\/10.1007\/s11128-019-2236-3","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"value":"1570-0755","type":"print"},{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,5]]},"assertion":[{"value":"20 September 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 February 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 March 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"117"}}