{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T19:02:08Z","timestamp":1770750128705,"version":"3.50.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2021,7,1]],"date-time":"2021-07-01T00:00:00Z","timestamp":1625097600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,10]],"date-time":"2021-07-10T00:00:00Z","timestamp":1625875200000},"content-version":"vor","delay-in-days":9,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Deutsches Zentrum f\u00fcr Luft- und Raumfahrt e. V. (DLR)"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In order to solve real-world combinatorial optimization problems with a D-Wave quantum annealer, it is necessary to embed the problem at hand into the D-Wave hardware graph, namely Chimera or Pegasus. Most hard real-world problems exhibit a strong connectivity. For the worst-case scenario of a complete graph, there exists an efficient solution for the embedding into the ideal Chimera graph. However, since real machines almost always have broken qubits, it is necessary to find an embedding into the broken hardware graph. We present a new approach to the problem of embedding complete graphs into broken Chimera graphs. This problem can be formulated as an optimization problem, more precisely as a matching problem with additional linear constraints. Although being NP-hard in general, it is fixed-parameter tractable in the number of inaccessible vertices in the Chimera graph. We tested our exact approach on various instances of broken hardware graphs, both related to real hardware and randomly generated. For fixed runtime, we were able to embed larger complete graphs compared to previous, heuristic approaches. As an extension, we developed a fast heuristic algorithm which enables us to solve even larger instances. We compared the performance of our heuristic and exact approaches.<\/jats:p>","DOI":"10.1007\/s11128-021-03168-z","type":"journal-article","created":{"date-parts":[[2021,7,10]],"date-time":"2021-07-10T05:02:30Z","timestamp":1625893350000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Embedding of complete graphs in broken Chimera graphs"],"prefix":"10.1007","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3473-8906","authenticated-orcid":false,"given":"Elisabeth","family":"Lobe","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4180-0744","authenticated-orcid":false,"given":"Lukas","family":"Sch\u00fcrmann","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5445-8082","authenticated-orcid":false,"given":"Tobias","family":"Stollenwerk","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,10]]},"reference":[{"key":"3168_CR1","unstructured":"Boothby, K., Bunyk, P., Raymond, J., Roy, A.: Next-generation topology of D-Wave quantum processors. arXiv:2003.00133 (2020)"},{"issue":"1","key":"3168_CR2","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). https:\/\/doi.org\/10.1007\/s11128-015-1150-6","journal-title":"Quantum Inf. Process."},{"key":"3168_CR3","unstructured":"Cai, J., Macready, W.G., Roy, A.: A practical heuristic for finding graph minors. arXiv:1406.2741 (2014)"},{"issue":"3","key":"3168_CR4","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). https:\/\/doi.org\/10.1007\/s11128-010-0200-3","journal-title":"Quantum Inf. Process."},{"key":"3168_CR5","unstructured":"D-Wave Systems Inc.: D-Wave Systems documentation\u2014D-Wave QPU architecture: Topologies. https:\/\/docs.dwavesys.com\/docs\/latest\/c_gs_4.html. 2020-12-03"},{"key":"3168_CR6","unstructured":"D-Wave Systems Inc.: Technical description of the D-Wave quantum processing unit. https:\/\/docs.dwavesys.com\/docs\/latest\/_downloads\/09-1109A-V_Technical_Description_of_DW_QPU.pdf. User Manual 2020-10-06"},{"key":"3168_CR7","unstructured":"D-Wave Systems Inc.: Minorminer. GitHub repository (2020). Version 0.2.4. https:\/\/github.com\/dwavesystems\/minorminer"},{"key":"3168_CR8","unstructured":"Gleixner, Bastubbe, M., Eifler, L., Gally, T., Gamrath, G., Gottwald, R.L., Hendel, G., Hojny, C., Koch, T., L\u00fcbbecke, M.E., Maher, S.J., Miltenberger, M., M\u00fcller, B., Pfetsch, M.E., Puchert, C., Rehfeldt, D., Schl\u00f6sser, F., Schubert, C., Serrano, F., Shinano, Y., Viernickel, J.M., Walter, M., Wegscheider, F., Witt, J.T., Witzig, J.: The SCIP Optimization Suite 6.0. Technical report, Optimization Online (2018). https:\/\/optimization-online.org\/DB_HTML\/2018\/07\/6692.html"},{"issue":"5","key":"3168_CR9","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). https:\/\/doi.org\/10.1007\/s11128-018-1863-4","journal-title":"Quantum Inf. Process."},{"issue":"4","key":"3168_CR10","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). https:\/\/doi.org\/10.1007\/s11128-016-1513-7","journal-title":"Quantum Inf. Process."},{"issue":"4","key":"3168_CR11","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An $$n^{5\/2}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973). https:\/\/doi.org\/10.1137\/0202019","journal-title":"SIAM J. Comput."},{"key":"3168_CR12","unstructured":"J\u00fcnger, M., Lobe, E., Mutzel, P., Reinelt, G., Rendl, F., Rinaldi, G., Stollenwerk, T.: Performance of a quantum annealer for ising ground state computations on chimera graphs. arXiv:1904.11965 (2019)"},{"issue":"3","key":"3168_CR13","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). https:\/\/doi.org\/10.1007\/s11128-013-0683-9","journal-title":"Quantum Inf. Process."},{"key":"3168_CR14","doi-asserted-by":"publisher","unstructured":"Maher, S., Miltenberger, M., Pedroso, J.P., Rehfeldt, D., Schwarz, R., Serrano, F.: PySCIPOpt: Mathematical programming in python with the SCIP optimization suite. In: Mathematical Software\u2014ICMS 2016, pp. 301\u2013307. Springer International Publishing (2016). https:\/\/doi.org\/10.1007\/978-3-319-42432-3_37","DOI":"10.1007\/978-3-319-42432-3_37"},{"key":"3168_CR15","doi-asserted-by":"publisher","unstructured":"Pinilla, J.P., Wilton, S.J.: Layout-aware embedding for quantum annealing processors. In: International Conference on High Performance Computing, pp. 121\u2013139. Springer, Berlin (2019). https:\/\/doi.org\/10.1007\/978-3-030-20656-7_7","DOI":"10.1007\/978-3-030-20656-7_7"},{"issue":"1","key":"3168_CR16","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). https:\/\/doi.org\/10.1007\/s11128-014-0892-x","journal-title":"Quantum Inf. Process."},{"issue":"1","key":"3168_CR17","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Combin. Theory Ser. B 63(1), 65\u2013110 (1995). https:\/\/doi.org\/10.1006\/jctb.1995.1006","journal-title":"J. Combin. Theory Ser. B"},{"key":"3168_CR18","unstructured":"Serra, T., Huang, T., Raghunathan, A., Bergman, D.: Template-based minor embedding for adiabatic quantum optimization. arXiv:1910.02179 (2019)"},{"key":"3168_CR19","doi-asserted-by":"publisher","unstructured":"Stollenwerk, T., Lobe, E., Jung, M.: Flight gate assignment with a quantum annealer. In: International Workshop on Quantum Technology and Optimization Problems, pp. 99\u2013110. Springer, Berlin (2019). https:\/\/doi.org\/10.1007\/978-3-030-14082-3_9","DOI":"10.1007\/978-3-030-14082-3_9"},{"issue":"1","key":"3168_CR20","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1109\/TITS.2019.2891235","volume":"21","author":"T Stollenwerk","year":"2019","unstructured":"Stollenwerk, T., O\u2019Gorman, B., Venturelli, D., Mandr\u00e0, S., Rodionova, O., Ng, H., Sridhar, B., Rieffel, E.G., Biswas, R.: Quantum annealing applied to de-conflicting optimal trajectories for air traffic management. IEEE Trans. Intell. Transp. Syst. 21(1), 285\u2013297 (2019). https:\/\/doi.org\/10.1109\/TITS.2019.2891235","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"issue":"4","key":"3168_CR21","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1145\/322092.322093","volume":"25","author":"SL Tanimoto","year":"1978","unstructured":"Tanimoto, S.L., Itai, A., Rodeh, M.: Some matching problems for bipartite graphs. J. ACM (JACM) 25(4), 517\u2013525 (1978). https:\/\/doi.org\/10.1145\/322092.322093","journal-title":"J. ACM (JACM)"},{"key":"3168_CR22","unstructured":"Venturelli, D., Marchand, D.J., Rojo, G.: Quantum annealing implementation of job-shop scheduling. arXiv:1506.08479 (2015)"},{"issue":"5","key":"3168_CR23","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1007\/s11128-017-1569-z","volume":"16","author":"A Zaribafiyan","year":"2017","unstructured":"Zaribafiyan, A., Marchand, D.J., Rezaei, S.S.C.: Systematic and deterministic graph minor embedding for cartesian products of graphs. Quantum Inf. Process. 16(5), 136 (2017). https:\/\/doi.org\/10.1007\/s11128-017-1569-z","journal-title":"Quantum Inf. Process."},{"key":"3168_CR24","doi-asserted-by":"publisher","unstructured":"Zbinden, S., B\u00e4rtschi, A., Djidjev, H., Eidenbenz, S.: Embedding algorithms for quantum annealers with chimera and pegasus connection topologies. In: International Conference on High Performance Computing, pp. 187\u2013206. Springer, Berlin (2020). https:\/\/doi.org\/10.1007\/978-3-030-50743-5_10","DOI":"10.1007\/978-3-030-50743-5_10"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03168-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-021-03168-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03168-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,4]],"date-time":"2021-08-04T08:27:26Z","timestamp":1628065646000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-021-03168-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7]]},"references-count":24,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["3168"],"URL":"https:\/\/doi.org\/10.1007\/s11128-021-03168-z","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"value":"1570-0755","type":"print"},{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7]]},"assertion":[{"value":"24 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"234"}}