{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T11:13:34Z","timestamp":1771845214301,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T00:00:00Z","timestamp":1769472000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T00:00:00Z","timestamp":1769472000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00174-22-1-0030"],"award-info":[{"award-number":["N00174-22-1-0030"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    The Quadratic Assignment Problem (QAP) is an NP-hard fundamental combinatorial optimization problem introduced by Koopmans and Beckmann in 1957. The problem is to assign\n                    <jats:italic>n<\/jats:italic>\n                    facilities to\n                    <jats:italic>n<\/jats:italic>\n                    different locations with the goal of minimizing the cost of the total distances between facilities weighted by the corresponding flows. We initiate the study of using Rydberg arrays to find optimal solutions to the QAP and provide a complementing circuit theory to facilitate an easy representation of other hard problems. We provide an algorithm for finding valid and optimal solutions to the QAP using Rydberg arrays.\n                  <\/jats:p>","DOI":"10.1007\/s11128-026-05066-8","type":"journal-article","created":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T08:22:09Z","timestamp":1769502129000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A systematic encoding of the quadratic assignment problem onto Rydberg arrays"],"prefix":"10.1007","volume":"25","author":[{"given":"Nathan","family":"Daly","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Krauss","sequence":"additional","affiliation":[]},{"given":"Julia","family":"Shapiro","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,1,27]]},"reference":[{"key":"5066_CR1","doi-asserted-by":"crossref","unstructured":"Koopmans, T.C., Beckmann, M.: Assignment problems and the location of economic activities. Econometrica: J. Econ. Soc., 53\u201376 (1957)","DOI":"10.2307\/1907742"},{"key":"5066_CR2","unstructured":"Carvalho\u00a0Jr, S.A.d., Rahmann, S.: Microarray layout as quadratic assignment problem. In: German Conference on Bioinformatics, pp. 11\u201320 (2006)"},{"key":"5066_CR3","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/s10479-005-3444-z","volume":"139","author":"Z Drezner","year":"2005","unstructured":"Drezner, Z., Hahn, P.M., Taillard, \u00c9.D.: Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods. Ann. Oper. Res. 139, 65\u201394 (2005)","journal-title":"Ann. Oper. Res."},{"issue":"1","key":"5066_CR4","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1137\/1003003","volume":"3","author":"L Steinberg","year":"1961","unstructured":"Steinberg, L.: The backboard wiring problem: a placement algorithm. SIAM Rev. 3(1), 37\u201350 (1961)","journal-title":"SIAM Rev."},{"key":"5066_CR5","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s10107-003-0437-z","volume":"97","author":"KM Anstreicher","year":"2003","unstructured":"Anstreicher, K.M.: Recent advances in the solution of quadratic assignment problems. Math. Program. 97, 27\u201342 (2003)","journal-title":"Math. Program."},{"issue":"1\u20134","key":"5066_CR6","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1080\/10556780108805828","volume":"16","author":"KM Anstreicher","year":"2001","unstructured":"Anstreicher, K.M., Brixius, N.W.: Solving quadratic assignment problems using convex quadratic programming relaxations. Optimiz. Methods Softw. 16(1\u20134), 49\u201368 (2001)","journal-title":"Optimiz. Methods Softw."},{"key":"5066_CR7","doi-asserted-by":"crossref","unstructured":"Finke, G., Burkard, R.E., Rendl, F.: Quadratic assignment problems. In: North-Holland Mathematics Studies vol. 132, pp. 61\u201382. Elsevier, Amsterdam, The Netherlands (1987)","DOI":"10.1016\/S0304-0208(08)73232-8"},{"issue":"1","key":"5066_CR8","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0166-218X(83)90018-5","volume":"5","author":"AM Frieze","year":"1983","unstructured":"Frieze, A.M., Yadegar, J.: On the quadratic assignment problem. Discret. Appl. Math. 5(1), 89\u201398 (1983)","journal-title":"Discret. Appl. Math."},{"key":"5066_CR9","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s11590-011-0409-9","volume":"7","author":"TP Gevezes","year":"2013","unstructured":"Gevezes, T.P., Pitsoulis, L.S.: A new greedy algorithm for the quadratic assignment problem. Optimiz. Lett. 7, 207\u2013220 (2013)","journal-title":"Optimiz. Lett."},{"issue":"4","key":"5066_CR10","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1287\/mnsc.9.4.586","volume":"9","author":"EL Lawler","year":"1963","unstructured":"Lawler, E.L.: The quadratic assignment problem. Manage. Sci. 9(4), 586\u2013599 (1963)","journal-title":"Manage. Sci."},{"issue":"1","key":"5066_CR11","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0377-2217(93)E0162-Q","volume":"81","author":"W-J Li","year":"1995","unstructured":"Li, W.-J., Smith, J.M.: An algorithm for quadratic assignment problems. Eur. J. Oper. Res. 81(1), 205\u2013216 (1995)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"5066_CR12","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1016\/j.ejor.2005.09.032","volume":"176","author":"EM Loiola","year":"2007","unstructured":"Loiola, E.M., De Abreu, N.M.M., Boaventura-Netto, P.O., Hahn, P., Querido, T.: A survey for the quadratic assignment problem. Eur. J. Oper. Res. 176(2), 657\u2013690 (2007)","journal-title":"Eur. J. Oper. Res."},{"key":"5066_CR13","doi-asserted-by":"crossref","unstructured":"Syed-Abdullah, S.S., Abdul-Rahman, S., Benjamin, A.M., Wibowo, A., Ku-Mahamud, K.-R.: Solving quadratic assignment problem with fixed assignment (qapfa) using branch and bound approach. In: IOP Conference Series: Materials Science and Engineering, vol. 300, p. 012002 (2018)","DOI":"10.1088\/1757-899X\/300\/1\/012002"},{"issue":"1","key":"5066_CR14","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0305-0548(93)E0020-T","volume":"22","author":"DM Tate","year":"1995","unstructured":"Tate, D.M., Smith, A.E.: A genetic approach to the quadratic assignment problem. Comput. Oper. Res. 22(1), 73\u201383 (1995)","journal-title":"Comput. Oper. Res."},{"key":"5066_CR15","doi-asserted-by":"crossref","unstructured":"Wang, J.-C.: Solving quadratic assignment problems by a tabu based simulated annealing algorithm. In: 2007 International Conference on Intelligent and Advanced Systems, pp. 75\u201380 (2007). IEEE","DOI":"10.1109\/ICIAS.2007.4658351"},{"issue":"1","key":"5066_CR16","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1080\/07408178708975376","volume":"19","author":"MR Wilhelm","year":"1987","unstructured":"Wilhelm, M.R., Ward, T.L.: Solving quadratic assignment problems by \u2018simulated annealing\u2019. IIE Trans. 19(1), 107\u2013119 (1987)","journal-title":"IIE Trans."},{"key":"5066_CR17","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/s10479-012-1079-4","volume":"207","author":"H Zhang","year":"2013","unstructured":"Zhang, H., Beltran-Royo, C., Ma, L.: Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers. Ann. Oper. Res. 207, 261\u2013278 (2013)","journal-title":"Ann. Oper. Res."},{"key":"5066_CR18","unstructured":"Mermoud, D.L., Simonetto, A., Elloumi, S.: Variational quantum algorithms for permutation-based combinatorial problems: Optimal ansatz generation with applications to quadratic assignment problems and beyond (2025). https:\/\/arxiv.org\/abs\/2505.05981"},{"key":"5066_CR19","doi-asserted-by":"publisher","unstructured":"Mezher, R., Carvalho, A.F., Mansfield, S.: Solving graph problems with single photons and linear optics. Phys. Rev. A 108, 032405 (2023) https:\/\/doi.org\/10.1103\/PhysRevA.108.032405","DOI":"10.1103\/PhysRevA.108.032405"},{"key":"5066_CR20","unstructured":"Mikuriya, T., Fujiwara, S., Yukiyoshi, K., Abreu, G.T.F., Ishikawa, N.: Grover adaptive search for the higher-order formulation of quadratic assignment problems (2025). https:\/\/arxiv.org\/abs\/2410.12181"},{"key":"5066_CR21","doi-asserted-by":"crossref","unstructured":"Ebadi, S., Keesling, A., Cain, M., Wang, T.T., Levine, H., Bluvstein, D., Semeghini, G., Omran, A., Liu, J.-G., Samajdar, R., Luo, X.-Z., Nash, B., Gao, X., Barak, B., Farhi, E., Sachdev, S., Gemelke, N., Zhou, L., Choi, S., Pichler, H., Wang, S.-T., Greiner, M., Vuleti\u0107, V., Lukin, M.D.: Quantum optimization of maximum independent set using Rydberg atom arrays. Science 376(6598), 1209\u20131215 (2022)","DOI":"10.1126\/science.abo6587"},{"issue":"1","key":"5066_CR22","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.4.010316","volume":"4","author":"M-T Nguyen","year":"2023","unstructured":"Nguyen, M.-T., Liu, J.-G., Wurtz, J., Lukin, M.D., Wang, S.-T., Pichler, H.: Quantum optimization with arbitrary connectivity using Rydberg atom arrays. PRX Quantum 4(1), 010316 (2023)","journal-title":"PRX Quantum"},{"key":"5066_CR23","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.3.030305","volume":"3","author":"A Byun","year":"2022","unstructured":"Byun, A., Kim, M., Ahn, J.: Finding the maximum independent sets of platonic graphs using Rydberg atoms. PRX Quantum 3, 030305 (2022)","journal-title":"PRX Quantum"},{"key":"5066_CR24","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1038\/nphys1614","volume":"6","author":"H Weimer","year":"2009","unstructured":"Weimer, H., Muller, M.M., Lesanovsky, I., Zoller, P., Buchler, H.P.: A Rydberg quantum simulator. Nat. Phys. 6, 382\u2013388 (2009)","journal-title":"Nat. Phys."},{"key":"5066_CR25","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1038\/s41567-019-0733-z","volume":"16","author":"A Browaeys","year":"2020","unstructured":"Browaeys, A., Lahaye, T.: Many-body physics with individually controlled Rydberg atoms. Nat. Phys. 16, 132\u2013142 (2020)","journal-title":"Nat. Phys."},{"issue":"7866","key":"5066_CR26","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1038\/s41586-021-03582-4","volume":"595","author":"S Ebadi","year":"2021","unstructured":"Ebadi, S., Wang, T.T., Levine, H., Keesling, A., Semeghini, G., Omran, A., Bluvstein, D., Samajdar, R., Pichler, H., Ho, W.W., Choi, S., Sachdev, S., Greiner, M., Vuleti\u0107, V., Lukin, M.D.: Quantum phases of matter on a 256-atom programmable quantum simulator. Nature 595(7866), 227\u2013232 (2021)","journal-title":"Nature"},{"key":"5066_CR27","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1038\/s41586-021-03585-1","volume":"595","author":"P Scholl","year":"2021","unstructured":"Scholl, P., Schuler, M., Williams, H.J., Eberharter, A.A., Barredo, D., Schymik, K.-N., Lienhard, V., Henry, L.-P., Lang, T.C., Lahaye, T., L\u00e4uchli, A.M., Browaeys, A.: Quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms. Nature 595, 233\u2013238 (2021)","journal-title":"Nature"},{"key":"5066_CR28","doi-asserted-by":"publisher","first-page":"2208","DOI":"10.1103\/PhysRevLett.85.2208","volume":"85","author":"D Jaksch","year":"2000","unstructured":"Jaksch, D., Cirac, J.I., Zoller, P., Rolston, S.L., C\u00f4t\u00e9, R., Lukin, M.D.: Fast quantum gates for neutral atoms. Phys. Rev. Lett. 85, 2208\u20132211 (2000)","journal-title":"Phys. Rev. Lett."},{"key":"5066_CR29","doi-asserted-by":"publisher","first-page":"2313","DOI":"10.1103\/RevModPhys.82.2313","volume":"82","author":"M Saffman","year":"2010","unstructured":"Saffman, M., Walker, T.G., M\u00f8lmer, K.: Quantum information with Rydberg atoms. Rev. Modern Phys. 82, 2313\u20132363 (2010)","journal-title":"Rev. Modern Phys."}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-026-05066-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-026-05066-8","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-026-05066-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T10:51:54Z","timestamp":1771843914000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-026-05066-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,27]]},"references-count":29,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2026,2]]}},"alternative-id":["5066"],"URL":"https:\/\/doi.org\/10.1007\/s11128-026-05066-8","relation":{},"ISSN":["1573-1332"],"issn-type":[{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,27]]},"assertion":[{"value":"2 June 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 January 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 January 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"40"}}