{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T09:45:27Z","timestamp":1753868727358,"version":"3.41.2"},"reference-count":28,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T00:00:00Z","timestamp":1736985600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Concurrency and Computation"],"published-print":{"date-parts":[[2025,2]]},"abstract":"<jats:title>ABSTRACT<\/jats:title><jats:p>An Ising model is a mathematical model defined by an objective function comprising a quadratic formula of multiple spin variables, each taking values of either  or . The task of determining a spin value assignment to these variables that minimizes the resulting value of an Ising model is a challenging optimization problem. Recently, quantum annealers, consisting of qubit cells interconnected according to principles of quantum mechanics, have emerged as a solution for tackling such problems. Ising models characterized by fewer quadratic terms are preferable as they reduce the resource requirements of quantum annealers. Additionally, it is advantageous for the absolute values of coefficients associated with linear and quadratic terms to be small to facilitate the discovery of good solutions, given the inherent limitations in the resolution of quantum annealers. The primary contribution of this article lies in presenting Ising models tailored for solving the \u2010Queens puzzle. The conventional Ising model for this puzzle involves  quadratic terms, with the maximum absolute value of coefficients being . Our novel Ising model significantly reduces the number of quadratic terms to only , with a maximum absolute coefficient of 6. Furthermore, we provide embedding results for a quantum annealer D\u2010Wave Advantage utilizing a Pegasus graph . We succeeded in embedding our novel Ising model for up to the 21\u2010Queens puzzle, while the conventional Ising model can be embedded only for up to the 14\u2010Queens puzzle.<\/jats:p>","DOI":"10.1002\/cpe.8364","type":"journal-article","created":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T23:36:30Z","timestamp":1737070590000},"update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Ising Models for Solving the N\u2010Queens Puzzle Based on the Domain\u2010Wall Vectors"],"prefix":"10.1002","volume":"37","author":[{"given":"Shunsuke","family":"Tsukiyama","sequence":"first","affiliation":[{"name":"Graduate School of Advanced Science and Engineering Hiroshima University  Higashihiroshima Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0002-2040-4032","authenticated-orcid":false,"given":"Koji","family":"Nakano","sequence":"additional","affiliation":[{"name":"Graduate School of Advanced Science and Engineering Hiroshima University  Higashihiroshima Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0003-0593-231X","authenticated-orcid":false,"given":"Yasuaki","family":"Ito","sequence":"additional","affiliation":[{"name":"Graduate School of Advanced Science and Engineering Hiroshima University  Higashihiroshima Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takumi","family":"Kato","sequence":"additional","affiliation":[{"name":"Research and Development Headquarters NTT DATA Group Corporation  Tokyo Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuya","family":"Kawamata","sequence":"additional","affiliation":[{"name":"Research and Development Headquarters NTT DATA Group Corporation  Tokyo Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2025,1,16]]},"reference":[{"key":"e_1_2_8_2_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.58.5355"},{"key":"e_1_2_8_3_1","doi-asserted-by":"publisher","DOI":"10.1088\/1361-6633\/ac8c54"},{"key":"e_1_2_8_4_1","first-page":"5","article-title":"Ising Formulations of Many NP Problems","volume":"2","author":"Lucas A.","year":"2014","journal-title":"Physics"},{"key":"e_1_2_8_5_1","doi-asserted-by":"crossref","unstructured":"M.Tao K.Nakano Y.Ito et al. \u201cA Work\u2010Time Optimal Parallel Exhaustive Search Algorithm for the QUBO and the Ising Model With GPU Implementation \u201dIn Proceedings. of International Parallel and Distributed Processing Symposium Workshops(2020):557\u2013566.","DOI":"10.1109\/IPDPSW50202.2020.00098"},{"key":"e_1_2_8_6_1","doi-asserted-by":"crossref","unstructured":"K.Nakano D.Takafuji Y.Ito et al. \u201cDiverse Adaptive BulkSearch: A Framework for Solving QUBO Problems on Multiple GPUs \u201dIn Proceedings. of International Parallel and Distributed ProcessingSymposium Workshops(2023):314\u2013325.","DOI":"10.1109\/IPDPSW59300.2023.00060"},{"key":"e_1_2_8_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2019.2908836"},{"key":"e_1_2_8_8_1","unstructured":"C.McGeochandP.Farr\u00e9 \u201cThe D\u2010Wave Advantage System: An Overview \u201d2020.D\u2010Wave Systems."},{"key":"e_1_2_8_9_1","unstructured":"K.Boothby P.Bunyk J.Raymond andA.Roy \u201cNext\u2010Generation Topology of D\u2010Wave Quantum Processors \u201d2019.Techreport 14\u20101026A\u2010C D\u2010Wave Systems."},{"key":"e_1_2_8_10_1","unstructured":"J.Cai W. G.Macready andA.Roy \u201cA practical heuristic for finding graph minors \u201d2014 https:\/\/2.zoppoz.workers.dev:443\/https\/arxiv.org\/abs\/1406.2741"},{"key":"e_1_2_8_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TQE.2021.3050449"},{"key":"e_1_2_8_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.12.043"},{"volume-title":"Structured Programming","year":"1972","author":"Dijkstra E. W.","key":"e_1_2_8_13_1"},{"key":"e_1_2_8_14_1","doi-asserted-by":"crossref","unstructured":"F.Pantekis P.James andO.Kullmann \u201cScalable N\u2010Queens Solving on GPGPUs via Interwarp Collaborations \u201din Proceedings. of Tenth International Symposium on Computing and Networking(2022): 158\u2013164.","DOI":"10.1109\/CANDAR57322.2022.00029"},{"key":"e_1_2_8_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-04148-8_11"},{"key":"e_1_2_8_16_1","doi-asserted-by":"crossref","unstructured":"S. T.Goh S.Gopalakrishnan J.Bo andH. C.Lau \u201cA Hybrid Framework Using a QUBO Solver For Permutation\u2010Based Combinatorial Optimization \u201darXiv preprint2021.","DOI":"10.1145\/3520304.3533982"},{"key":"e_1_2_8_17_1","doi-asserted-by":"crossref","unstructured":"S. T.Goh J.Bo S.Gopalakrishnan andH. C.Lau \u201cTechniques to Enhance a QUBO Solver for Permutation\u2010Based Combinatorial Optimization.\u201din Proceedings. GECCO '22: Genetic and Evolutionary Computation Conference Companion(2022): 2223\u20132231.","DOI":"10.1145\/3520304.3533982"},{"key":"e_1_2_8_18_1","unstructured":"GitHub2021 https:\/\/2.zoppoz.workers.dev:443\/https\/github.com\/dwave\u2010examples\/n\u2010queens"},{"key":"e_1_2_8_19_1","unstructured":"C. C.Villanova \u201cSolving the n\u2010queens problem with quantum annealing \u201d2021 https:\/\/2.zoppoz.workers.dev:443\/https\/medium.com\/@carlacarov\/solving\u2010the\u2010n\u2010queens\u2010problem\u2010with\u2010quantum\u2010annealing\u2010b13ee199b210"},{"key":"e_1_2_8_20_1","unstructured":"R. A.Moreno \u201cStudy and Applicationof Quantum Optimization Algorithms \u201dBachelor thesis Complutense University of Madrid 2022."},{"key":"e_1_2_8_21_1","doi-asserted-by":"publisher","DOI":"10.1088\/2058\u20109565\/ab33c2"},{"key":"e_1_2_8_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TQE.2021.3094280"},{"issue":"2241","key":"e_1_2_8_23_1","article-title":"Understanding Domain\u2010Wall Encoding Theoretically and Experimentally","volume":"381","author":"Berwald J.","year":"2022","journal-title":"Philosophical Transactions of the Royal Society A"},{"key":"e_1_2_8_24_1","doi-asserted-by":"crossref","unstructured":"P.Codognet \u201cDomain\u2010Wall \/ Unary Encoding in QUBO for Permutation Problems \u201din Proceedings. of International Conference on Quantum Computing and Engineering(2022): 167\u2013173.","DOI":"10.1109\/QCE53715.2022.00036"},{"key":"e_1_2_8_25_1","doi-asserted-by":"crossref","unstructured":"S.Tsukiyama K.Nakano Y.Ito et al. \u201cSolving the N\u2010Queens Puzzle by a QUBO Model With Quadratic Size \u201din Proceedings. of International Symposium on Computing and Networking CANDAR(2023): 59\u201367.","DOI":"10.1109\/CANDAR60563.2023.00015"},{"key":"e_1_2_8_26_1","unstructured":"F. W.GloverandG. A.Kochenberger \u201cA Tutorial on Formulating QUBO Models \u201d2018.arXiv preprint arXiv:1811.11538."},{"key":"e_1_2_8_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2022.116953"},{"key":"e_1_2_8_28_1","doi-asserted-by":"publisher","DOI":"10.3390\/technologies11050143"},{"key":"e_1_2_8_29_1","unstructured":"SymPy Development Team \u201cSymPy Documentation Release 1.12 \u201d2023 https:\/\/2.zoppoz.workers.dev:443\/https\/www.sympy.org\/en\/index.html"}],"container-title":["Concurrency and Computation: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.8364","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T02:54:31Z","timestamp":1741834471000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.8364"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,16]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["10.1002\/cpe.8364"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1002\/cpe.8364","archive":["Portico"],"relation":{},"ISSN":["1532-0626","1532-0634"],"issn-type":[{"type":"print","value":"1532-0626"},{"type":"electronic","value":"1532-0634"}],"subject":[],"published":{"date-parts":[[2025,1,16]]},"assertion":[{"value":"2024-04-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-04","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"e8364"}}