{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T21:10:01Z","timestamp":1768684201160,"version":"3.49.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,3,19]],"date-time":"2020-03-19T00:00:00Z","timestamp":1584576000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,3,19]],"date-time":"2020-03-19T00:00:00Z","timestamp":1584576000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Mach. Intell."],"published-print":{"date-parts":[[2020,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this work, we investigate the capabilities of a hybrid quantum-classical procedure to explore the solution space using the D-Wave 2000<jats:italic>Q<\/jats:italic><jats:sup><jats:italic>T<\/jats:italic><jats:italic>M<\/jats:italic><\/jats:sup>quantum annealer device. Here, we study the ability of the quantum hardware to solve the number partitioning problem, a well-known NP-hard optimization model that poses some challenges typical of those encountered in real-world applications. This represents one of the most complex scenario in terms of qubits connectivity and, by increasing the input problem size, we analyze the scaling properties of the quantum-classical workflow. We find remarkable results in most instances of the model; for the most complex ones, we investigate further the D-Wave Hybrid suite. Specifically, we were able to find the optimal solutions even in the worst cases by fine-tuning the parameters that schedule the annealing time and allowing a pause in the annealing cycle.<\/jats:p>","DOI":"10.1007\/s42484-020-00014-w","type":"journal-article","created":{"date-parts":[[2020,3,19]],"date-time":"2020-03-19T16:04:00Z","timestamp":1584633840000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Accuracy and minor embedding in subqubo decomposition with fully connected large problems: a case study about the number partitioning problem"],"prefix":"10.1007","volume":"2","author":[{"given":"Luca","family":"Asproni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Davide","family":"Caputo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Blanca","family":"Silva","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giovanni","family":"Fazzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Magagnini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,3,19]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"Booth KE, Do M, Beck JC, Rieffel E, Venturelli D, Frank J (2018) Comparing and integrating constraint programming and temporal planning for quantum circuit compilation. In: Twenty-Eighth international conference on automated planning and scheduling","DOI":"10.1609\/icaps.v28i1.13920"},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"Chancellor N, Szoke S, Vinci W, Aeppli G, Warburton PA (2016a) Maximum-entropy inference with a programmable annealer. Sci Rep 6:22318. EP \u2013. Article","DOI":"10.1038\/srep22318"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Chancellor N, Zohren S, Warburton PA, Benjamin SC, Roberts S (2016b) A direct mapping of max k-sat and high order parity checks to a chimera graph. Sci Rep 6:37107. EP \u2013. Article","DOI":"10.1038\/srep37107"},{"key":"14_CR4","first-page":"031015","volume":"6","author":"VS Denchev","year":"2016","unstructured":"Denchev VS, Boixo S, Isakov SV, Ding N, Babbush R, Smelyanskiy V, Martinis J, Neven H (2016) What is the computational value of finite-range tunneling?. Phys Rev X 6:031015","journal-title":"Phys Rev X"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Hamerly R, Inagaki T, McMahon PL, Venturelli D, Marandi A, Onodera T, Ng E, Langrock C, Inaba K, Honjo T, Enbutsu K, Umeki T, Kasahara R, Utsunomiya S, Kako S, Kawarabayashi K-i, Byer RL, Fejer M, Mabuchi H, Englund D, Rieffel E, Takesue H, Yamamoto Y (2019) Experimental investigation of performance differences between coherent ising machines and a quantum annealer. Sci Adv 5(5)","DOI":"10.1126\/sciadv.aau0823"},{"issue":"4","key":"14_CR6","doi-asserted-by":"publisher","first-page":"043303","DOI":"10.1103\/PhysRevE.97.043303","volume":"97","author":"F Hamze","year":"2018","unstructured":"Hamze F, Jacob DC, Ochoa AJ, Perera D, Wang W, Katzgraber HG (2018) From near to eternity: spin-glass planting, tiling puzzles, and constraint-satisfaction problems. Phys Rev E 97(4):043303","journal-title":"Phys Rev E"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Harpes C, Kramer GG, Massey JL (1995) A generalization of linear cryptanalysis and the applicability of matsui\u2019s piling-up lemma. In: Guillou LC, Quisquater J-J (eds) Advances in Cryptology \u2014 EUROCRYPT \u201995. Springer, Berlin, pp 24\u201338","DOI":"10.1007\/3-540-49264-X_3"},{"key":"14_CR8","unstructured":"James K, Sheir Y, Mayssam MN, Jeremy PH, Catherine CM (2015) Benchmarking a quantum annealing processor with the time-to-target metric. arXiv:1508.05087"},{"issue":"1","key":"14_CR9","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1137\/1035026","volume":"35","author":"AHGR Kan","year":"1993","unstructured":"Kan AHGR, van Vliet A (1993) Probabilistic analysis of packing and partitioning algorithms (e. g. coffman, jr. and george s. lueker). SIAM Rev 35(1):153\u2013154","journal-title":"SIAM Rev"},{"issue":"1","key":"14_CR10","doi-asserted-by":"publisher","first-page":"014001","DOI":"10.1088\/2058-9565\/aada1f","volume":"4","author":"A Khoshaman","year":"2018","unstructured":"Khoshaman A, Vinci W, Denis B, Andriyash E, Amin MH (2018) Quantum variational autoencoder. Quantum Sci Technol 4(1):014001","journal-title":"Quantum Sci Technol"},{"issue":"2","key":"14_CR11","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s11128-017-1809-2","volume":"17","author":"V Kumar","year":"2018","unstructured":"Kumar V, Bass G, Tomlin C, Dulny J (2018) Quantum annealing for combinatorial clustering. Quantum Inf Process 17(2):39","journal-title":"Quantum Inf Process"},{"issue":"3","key":"14_CR12","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1016\/j.cor.2006.04.002","volume":"35","author":"M Lewis","year":"2008","unstructured":"Lewis M, Kochenberger G, Alidaee B (2008) A new modeling and solution approach for the set-partitioning problem. Comput Oper Res 35(3):807\u2013813","journal-title":"Comput Oper Res"},{"key":"14_CR13","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. Front Phys 2:5","journal-title":"Front Phys"},{"key":"14_CR14","doi-asserted-by":"publisher","first-page":"044083","DOI":"10.1103\/PhysRevApplied.11.044083","volume":"11","author":"J Marshall","year":"2019","unstructured":"Marshall J, Venturelli D, Hen I, Rieffel E (2019) Power of pausing: advancing understanding of thermalization in experimental quantum annealers. Phys Rev Appl 11:044083","journal-title":"Phys Rev Appl"},{"key":"14_CR15","unstructured":"McGeoch CC, Bernoudy W, King J (2018) Comment on\u201d scaling advantages of all-to-all connectivity in physical annealers: the coherent ising machine vs d-wave 2000q. arXiv:1807.00089"},{"key":"14_CR16","unstructured":"McKiernan KA, Davis E, Alam MS, Rigetti C (2019) Automated quantum programming via reinforcement learning for combinatorial optimization. arXiv:1908.08054"},{"issue":"2","key":"14_CR17","first-page":"125","volume":"125","author":"S Mertens","year":"2006","unstructured":"Mertens S (2006) The easiest hard problem: number partitioning. Computational Complexity and Statistical Physics 125(2):125\u2013139","journal-title":"Computational Complexity and Statistical Physics"},{"key":"14_CR18","doi-asserted-by":"publisher","first-page":"29","DOI":"10.3389\/fict.2017.00029","volume":"4","author":"F Neukart","year":"2017","unstructured":"Neukart F, Compostella G, Seidel C, von Dollen D, Yarkoni S, Parney B (2017) Traffic flow optimization using a quantum annealer. Frontiers in ICT 4:29","journal-title":"Frontiers in ICT"},{"key":"14_CR19","unstructured":"Ojas P, Jeremy W, Luke S, Andrew L, Jonathan M, Aidun J (2016) Benchmarking adiabatic quantum optimization for complex network analysis. arXiv:1604.00319"},{"issue":"12","key":"14_CR20","doi-asserted-by":"publisher","first-page":"e0206653","DOI":"10.1371\/journal.pone.0206653","volume":"13","author":"D O\u2019Malley","year":"2018","unstructured":"O\u2019Malley D, Vesselinov VV, Alexandrov BS, Alexandrov LB (2018) Nonnegative\/binary matrix factorization with a d-wave quantum annealer. PloS One 13(12):e0206653","journal-title":"PloS One"},{"key":"14_CR21","unstructured":"Ottaviani D, Amendola A (2018) Low rank non-negative matrix factorization with d-wave 2000q. arXiv preprint arXiv:1808.08721"},{"key":"14_CR22","doi-asserted-by":"publisher","first-page":"3243","DOI":"10.1038\/ncomms4243","volume":"5","author":"KL Pudenz","year":"2014","unstructured":"Pudenz KL, Albash T, Lidar DA (2014) Error-corrected quantum annealing with hundreds of qubits. Nat Commun 5:3243. EP \u2013. Article","journal-title":"Nat Commun"},{"key":"14_CR23","doi-asserted-by":"crossref","unstructured":"Stollenwerk T, O\u2019Gorman B, Venturelli D, Mandr\u00e0 S, Rodionova O, Ng H, Sridhar B, Rieffel EG, Biswas R (2019) Quantum annealing applied to de-conflicting optimal trajectories for air traffic management. IEEE transactions on intelligent transportation systems","DOI":"10.1109\/TITS.2019.2891235"},{"issue":"20","key":"14_CR24","doi-asserted-by":"publisher","first-page":"5438","DOI":"10.1109\/TSP.2018.2866382","volume":"66","author":"H Sun","year":"2018","unstructured":"Sun H, Chen X, Shi Q, Hong M, Fu X, Sidiropoulos ND (2018) Learning to optimize: training deep neural networks for interference management. IEEE Trans Signal Process 66(20):5438\u20135453","journal-title":"IEEE Trans Signal Process"},{"key":"14_CR25","unstructured":"Vahdat A (2017) Toward robustness against label noise in training deep discriminative neural networks. In: Guyon I, Luxburg UV, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R (eds) Advances in Neural Information Processing Systems 30, Curran Associates, Inc., pp 5596\u20135605"},{"issue":"2","key":"14_CR26","doi-asserted-by":"publisher","first-page":"025004","DOI":"10.1088\/2058-9565\/aaa331","volume":"3","author":"D Venturelli","year":"2018","unstructured":"Venturelli D, Do M, Rieffel E, Frank J (2018) Compiling quantum circuits to realistic hardware architectures using temporal planners. Quantum Sci Technol 3(2):025004","journal-title":"Quantum Sci Technol"},{"key":"14_CR27","first-page":"031040","volume":"5","author":"D Venturelli","year":"2015","unstructured":"Venturelli D, Mandr\u00e0 S, Knysh S, O\u2019Gorman B, Biswas R, Smelyanskiy V (2015) Quantum optimization of fully connected spin glasses. Phys Rev X 5:031040","journal-title":"Phys Rev X"},{"issue":"1","key":"14_CR28","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1038\/s41534-017-0048-9","volume":"3","author":"Y Yamamoto","year":"2017","unstructured":"Yamamoto Y, Aihara K, Leleu T, Kawarabayashi K-i, Kako S, Fejer M, Inoue K, Takesue H (2017) Coherent ising machines-optical neural networks operating at the quantum limit. npj Quantum Inf 3(1):49","journal-title":"npj Quantum Inf"}],"container-title":["Quantum Machine Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-020-00014-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s42484-020-00014-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-020-00014-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,19]],"date-time":"2022-10-19T06:34:33Z","timestamp":1666161273000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s42484-020-00014-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,19]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["14"],"URL":"https:\/\/doi.org\/10.1007\/s42484-020-00014-w","relation":{},"ISSN":["2524-4906","2524-4914"],"issn-type":[{"value":"2524-4906","type":"print"},{"value":"2524-4914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,19]]},"assertion":[{"value":"27 August 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"4"}}