{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T09:06:17Z","timestamp":1765357577890,"version":"3.41.2"},"reference-count":56,"publisher":"Frontiers Media SA","license":[{"start":{"date-parts":[[2024,4,26]],"date-time":"2024-04-26T00:00:00Z","timestamp":1714089600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["frontiersin.org"],"crossmark-restriction":true},"short-container-title":["Front. Comput. Sci."],"abstract":"<jats:p>We introduce a method for solving a quadratic unconstrained binary optimization (QUBO) with the two-way one-hot constraints by dividing the QUBO into parts and solving it with an Ising machine. The one-hot constraint is a constraint condition in that only one binary variable takes the value one for a set of multiple binary variables. The two-way one-hot constraint imposes one-hot constraint conditions on every row and every column of a two-dimensional array of binary variables with equal numbers of rows and columns. For example, traveling salesman problems (TSPs) have two-way one-hot constraints. We propose two methods to solve a TSP by dividing the cities into clusters based on information in the QUBO matrix. The proposed methods decompose cities into clusters and solve TSPs for each cluster. We solve TSPs such that the cities are distributed in clusters and compare the results of the two proposed methods with the results of solving the problem without partitioning. The results show that the proposed methods are robust to the coefficient parameters in the Hamiltonian of QUBO and can obtain a solution closer to the optimal solution when solving the problem without partitioning is hard. We also discuss the application of the methods proposed in the TSPs to the quadratic assignment problems and to the problems of ordering things.<\/jats:p>","DOI":"10.3389\/fcomp.2024.1285244","type":"journal-article","created":{"date-parts":[[2024,4,26]],"date-time":"2024-04-26T04:31:04Z","timestamp":1714105864000},"update-policy":"https:\/\/doi.org\/10.3389\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Partitioning QUBO with two-way one-hot conditions on traveling salesman problems for city distributions with multiple clusters"],"prefix":"10.3389","volume":"6","author":[{"given":"Akihiro","family":"Yatabe","sequence":"first","affiliation":[]}],"member":"1965","published-online":{"date-parts":[[2024,4,26]]},"reference":[{"key":"B1","doi-asserted-by":"publisher","first-page":"1950042","DOI":"10.1142\/S0219749919500424","article-title":"A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing","volume":"17","author":"Abbott","year":"2019","journal-title":"Int. J. Quantum Inf"},{"key":"B2","doi-asserted-by":"publisher","first-page":"016008","DOI":"10.1103\/PhysRevD.103.016008","article-title":"Quantum computing for quantum tunneling","volume":"103","author":"Abel","year":"2021","journal-title":"Phys. Rev. D"},{"key":"B3","doi-asserted-by":"publisher","first-page":"2606","DOI":"10.1109\/TC.2021.3138629","article-title":"Hybrid annealing method based on subQUBO model extraction with multiple solution instances","volume":"71","author":"Atobe","year":"2021","journal-title":"IEEE Trans. Comput"},{"key":"B4","doi-asserted-by":"publisher","first-page":"033369","DOI":"10.1103\/PhysRevResearch.2.033369","article-title":"Probing the universality of topological defect formation in a quantum annealer: Kibble-Zurek mechanism and beyond","volume":"2","author":"Bando","year":"2020","journal-title":"Phys. Rev. Res"},{"key":"B5","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-78199-0_1","article-title":"\u201cIsing models for binary clustering via adiabatic quantum computing,","author":"Bauckhage","year":"2018"},{"key":"B6","first-page":"112","article-title":"\u201cInteger programming techniques for minor-embedding in quantum annealers,","author":"Bernal","year":"2020"},{"key":"B7","doi-asserted-by":"publisher","first-page":"14","DOI":"10.3389\/fict.2016.00014","article-title":"Mapping constrained optimization problems to quantum annealing with application to fault diagnosis","volume":"3","author":"Bian","year":"2016","journal-title":"Front. ICT"},{"key":"B8","unstructured":"BoothM.\n            ReinhardtS.\n            RoyA.\n          Partitioning optimization problems for hybrid classical\/quantum execution2017"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-34500-6_16","article-title":"\u201cOn post-processing the results of quantum optimizers,","author":"Borle","year":"2019"},{"key":"B10","doi-asserted-by":"publisher","first-page":"023024","DOI":"10.1088\/1367-2630\/aa59c4","article-title":"Modernizing quantum annealing using local searches","volume":"19","author":"Chancellor","year":"2017","journal-title":"New. J. Phys"},{"key":"B11","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1007\/s11047-022-09905-2","article-title":"Modernizing quantum annealing II: genetic algorithms with the inference primitive formalism","volume":"22","author":"Chancellor","year":"2023","journal-title":"Nat. Comput"},{"key":"B12","unstructured":"QBSOLV2021"},{"key":"B13","unstructured":"D-wave Hybrid"},{"key":"B14","unstructured":"The most connected and powerful quantum computer built for business"},{"key":"B15","doi-asserted-by":"publisher","first-page":"13","DOI":"10.3389\/fict.2019.00013","article-title":"A hybrid solution method for the capacitated vehicle routing problem using a quantum annealer","volume":"6","author":"Feld","year":"2019","journal-title":"Front. ICT"},{"key":"B16","doi-asserted-by":"publisher","first-page":"16824","DOI":"10.1038\/s41598-022-21163-x","article-title":"Molecular dynamics on quantum annealers","volume":"12","author":"Gaidai","year":"2022","journal-title":"Sci. Rep"},{"key":"B17","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1109\/TPAMI.1984.4767596","article-title":"Stochastic relaxation, gibbs distributions, and the bayesian restoration of images","volume":"6","author":"Geman","year":"1984","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell"},{"key":"B18","doi-asserted-by":"publisher","first-page":"8426","DOI":"10.1038\/s41598-021-87676-z","article-title":"Hybrid quantum annealing via molecular dynamics","volume":"11","author":"Irie","year":"2021","journal-title":"Sci. Rep"},{"key":"B19","doi-asserted-by":"publisher","first-page":"023062","DOI":"10.1103\/PhysRevResearch.4.023062","article-title":"Continuous black-box optimization with an ising machine and random subspace coding","volume":"4","author":"Izawa","year":"2022","journal-title":"Phys. Rev. Res"},{"key":"B20","doi-asserted-by":"publisher","first-page":"760783","DOI":"10.3389\/fphy.2021.760783","article-title":"Solving the traveling salesman problem on the D-wave quantum computer","volume":"9","author":"Jain","year":"2021","journal-title":"Front. Phys"},{"key":"B21","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1587\/transinf.2019EDP7254","article-title":"Solving constrained slot placement problems using an ising machine and its evaluations","author":"Kanamaru","year":"2021","journal-title":"IEICE Trans. Inf. Syst"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1508.05087","article-title":"Benchmarking a quantum annealing processor with the time-to-target metric","author":"King","year":"2015","journal-title":"arXiv"},{"key":"B23","doi-asserted-by":"publisher","first-page":"061007","DOI":"10.7566\/JPSJ.88.061007","article-title":"Quantum annealing amid local ruggedness and global frustration","volume":"88","author":"King","year":"2019","journal-title":"J. Phys. Soc. Jpn."},{"key":"B24","doi-asserted-by":"publisher","first-page":"013319","DOI":"10.1103\/PhysRevResearch.2.013319","article-title":"Designing metamaterials with quantum annealing and factorization machines","volume":"2","author":"Kitai","year":"2020","journal-title":"Phys. Rev. Res"},{"key":"B25","doi-asserted-by":"publisher","first-page":"463","DOI":"10.15803\/ijnc.11.2_463","article-title":"An external definition of the one-hot constraint and fast QUBO generation for high-performance combinatorial clustering","volume":"11","author":"Kumagai","year":"2021","journal-title":"Int. J. Netw. Comput"},{"key":"B26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10589-022-00354-2","article-title":"Leveraging special-purpose hardware for local search heuristics","volume":"82","author":"Liu","year":"2022","journal-title":"Comput. Optim. Appl"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2302.02278","article-title":"Optimization applications as quantum performance benchmarks","author":"Lubinski","year":"2023","journal-title":"arXiv"},{"key":"B28","doi-asserted-by":"publisher","first-page":"2669","DOI":"10.1038\/s41598-022-06559-z","article-title":"Distance-based clustering using QUBO formulations","volume":"12","author":"Matsumoto","year":"2022","journal-title":"Sci. Rep"},{"key":"B29","doi-asserted-by":"publisher","first-page":"4099","DOI":"10.1038\/s41598-021-83561-x","article-title":"Reduction of the molecular hamiltonian matrix using quantum community detection","volume":"11","author":"Mniszewski","year":"2021","journal-title":"Sci. Rep"},{"key":"B30","doi-asserted-by":"publisher","first-page":"1129594","DOI":"10.3389\/fphy.2023.1129594","article-title":"Quantum annealing for the adjuster routing problem","volume":"11","author":"Mori","year":"2023","journal-title":"Front. Phys"},{"key":"B31","doi-asserted-by":"publisher","first-page":"125210","DOI":"10.1063\/1.2995837","article-title":"Mathematical foundation of quantum annealing","volume":"49","author":"Morita","year":"2008","journal-title":"J. Math. Phys"},{"key":"B32","doi-asserted-by":"publisher","first-page":"025004","DOI":"10.7566\/JPSJ.90.025004","article-title":"Pattern formation simulated by an Ising machine","volume":"90","author":"Mukai","year":"2021","journal-title":"J. Phys. Soc. Jpn"},{"key":"B33","unstructured":"NEC and NEC Fielding introduce a delivery planning system for maintenance parts utilizing quantum computing technology"},{"key":"B34","unstructured":"NEC to launch simulated annealing service with up to 300,000 bits"},{"key":"B35","unstructured":"NEC and NEC Platforms introduce a production planning system for ICT equipment utilizing quantum computing technology at four NEC Platforms business sites2023"},{"key":"B36","doi-asserted-by":"publisher","first-page":"29","DOI":"10.3389\/fict.2017.00029","article-title":"Traffic flow optimization using a quantum annealer","volume":"4","author":"Neukart","year":"2017","journal-title":"Front. ICT"},{"key":"B37","doi-asserted-by":"publisher","first-page":"2","DOI":"10.3389\/fcomp.2019.00002","article-title":"Item listing optimization for E-commerce websites based on diversity","volume":"1","author":"Nishimura","year":"2019","journal-title":"Front. Comput. Sci"},{"key":"B38","doi-asserted-by":"publisher","first-page":"3126","DOI":"10.1038\/s41598-020-60022-5","article-title":"Breaking limitation of quantum annealer in solving optimization problems under constraints","volume":"1","author":"Ohzeki","year":"2020","journal-title":"Sci. Rep"},{"key":"B39","doi-asserted-by":"publisher","first-page":"9","DOI":"10.3389\/fcomp.2019.00009","article-title":"Control of automated guided vehicles without collision by quantum annealer and digital devices","volume":"1","author":"Ohzeki","year":"2019","journal-title":"Front. Comput. Sci"},{"key":"B40","doi-asserted-by":"publisher","first-page":"13036","DOI":"10.1038\/s41598-019-49539-6","article-title":"Efficient partition of integer optimization problems with one-hot encoding","volume":"9","author":"Okada","year":"","journal-title":"Sci. Rep"},{"key":"B41","doi-asserted-by":"publisher","first-page":"2098","DOI":"10.1038\/s41598-018-38388-4","article-title":"Improving solutions by embedding larger subproblems in a D-wave quantum annealer","volume":"9","author":"Okada","year":"","journal-title":"Sci. Rep"},{"key":"B42","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1109\/TC.2020.3045112","article-title":"How to reduce the bit-width of an Ising model by adding auxiliary spins","volume":"71","author":"Oku","year":"2020","journal-title":"IEEE Trans. Comput"},{"key":"B43","doi-asserted-by":"publisher","first-page":"042302","DOI":"10.1103\/PhysRevA.91.042302","article-title":"Quantum annealing correction for random ising problems","volume":"91","author":"Pudenz","year":"2015","journal-title":"Phys. Rev. A"},{"key":"B44","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/s11128-022-03421-z","article-title":"Characterization of QUBO reformulations for the maximum k-colorable subgraph problem","volume":"21","author":"Quintero","year":"2022","journal-title":"Quantum Inf. Process"},{"key":"B45","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3579368","article-title":"Hybrid quantum annealing for larger-than-QPU lattice-structured problems","volume":"4","author":"Raymond","year":"2023","journal-title":"ACM Trans. Quantum Comput"},{"key":"B46","unstructured":"pyqubo 1.4.02022"},{"key":"B47","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/s11128-021-03405-5","article-title":"Unconstrained binary models of the travelling salesman problem variants for quantum optimization","volume":"21","author":"Salehi","year":"2022","journal-title":"Quantum Inf. Process"},{"key":"B48","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1109\/MC.2019.2908942","article-title":"A hybrid approach for solving optimization problems on small quantum computers","volume":"52","author":"Shaydulin","year":"2019","journal-title":"Computer"},{"key":"B49","first-page":"2251","article-title":"\u201cEnhancing a QUBO solver via data driven multi-start and its application to vehicle routing problem,","author":"Suen","year":"2022"},{"key":"B50","unstructured":"QUBO solver for combinatorial optimization problems with constraints1520\n            TakanoF.\n            SuzukiM.\n            KobayashiY.\n            ArakiT.\n          IEICE Tech. Rep1192019"},{"key":"B51","first-page":"22","article-title":"\u201cGraph partitioning using quantum annealing on the D-wave system,","author":"Ushijima-Mwesigwa","year":"2017"},{"key":"B52","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3425607","article-title":"Multilevel combinatorial optimization across quantum architectures","volume":"2","author":"Ushijima-Mwesigwa","year":"2021","journal-title":"ACM Trans. Quantum Comput"},{"key":"B53","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s42452-019-1829-x","article-title":"Solving the traveling salesman problem on a quantum annealer","volume":"2","author":"Warren","year":"2020","journal-title":"SN Appl. Sci"},{"key":"B54","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1587\/transinf.2022EDP7017","article-title":"An efficient combined bit-width reducing method for Ising models","author":"Yachi","year":"2023","journal-title":"IEICE Trans. Inf. Syst"},{"key":"B55","doi-asserted-by":"publisher","first-page":"104001","DOI":"10.1088\/1361-6633\/ac8c54","article-title":"Quantum annealing for industry applications: introduction and review","volume":"85","author":"Yarkoni","year":"2022","journal-title":"Rep. Prog. Phys"},{"key":"B56","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1109\/TC.2021.3063618","article-title":"PyQUBO: python library for mapping combinatorial optimization problems to QUBO form","volume":"71","author":"Zaman","year":"2021","journal-title":"IEEE Trans. Comput"}],"container-title":["Frontiers in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/www.frontiersin.org\/articles\/10.3389\/fcomp.2024.1285244\/full","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,26]],"date-time":"2024-04-26T04:31:13Z","timestamp":1714105873000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.frontiersin.org\/articles\/10.3389\/fcomp.2024.1285244\/full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,26]]},"references-count":56,"alternative-id":["10.3389\/fcomp.2024.1285244"],"URL":"https:\/\/doi.org\/10.3389\/fcomp.2024.1285244","relation":{},"ISSN":["2624-9898"],"issn-type":[{"type":"electronic","value":"2624-9898"}],"subject":[],"published":{"date-parts":[[2024,4,26]]},"article-number":"1285244"}}