Variational quantum algorithms for permutation-based combinatorial problems: Optimal ansatz generation with applications to quadratic assignment problems and beyond
Summarize this article with:
AbstractWe present a quantum variational algorithm based on a novel circuit that generates all permutations that can be spanned by one- and two-qubits permutation gates. The construction of the circuits follows from group-theoretical results, most importantly the Bruhat decomposition of the group generated by the cx gates. These circuits require a number of qubits that scale logarithmically with the permutation dimension, and are therefore employable in near-term applications. We further augment the circuits with ancilla qubits to enlarge their span, and with these we build ansatze to tackle permutation-based optimization problems such as quadratic assignment problems, and graph isomorphisms. The resulting quantum algorithm, QuPer, is competitive with respect to classical heuristics and we could simulate its behavior up to a problem with 256 variables, requiring 20 qubits.► BibTeX data@article{LaplaceMermoud2026variationalquantum, doi = {10.22331/q-2026-02-09-1998}, url = {https://doi.org/10.22331/q-2026-02-09-1998}, title = {Variational quantum algorithms for permutation-based combinatorial problems: {O}ptimal ansatz generation with applications to quadratic assignment problems and beyond}, author = {Laplace Mermoud, Dylan and Simonetto, Andrea and Elloumi, Sourour}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1998}, month = feb, year = {2026} }► References [1] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, arXiv:1411.4028. arXiv:1411.4028 [2] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, Mikhail D. Lukin, Physical Review X, 10 021067 (2020), 10.1103/PhysRevX.10.021067. https://doi.org/10.1103/PhysRevX.10.021067 [3] Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J. Egger, Bruce G. Elmegreen, Nicola Franco, Filippo Fratini, Bryce Fuller, Julien Gacon, Constantin Gonciulea, Sander Gribling, Swati Gupta, Stuart Hadfield, Raoul Heese, Gerhard Kircher, Thomas Kleinert, Thorsten Koch, Georgios Korpas, Steve Lenk, Jakub Marecek, Vanio Markov, Guglielmo Mazzola, Stefano Mensa, Naeimeh Mohseni, Giacomo Nannicini, Corey O’Meara, Elena Peña Tapia, Sebastian Pokutta, Manuel Proissl, Patrick Rebentrost, Emre Sahin, Benjamin C. B. Symons, Sabine Tornow, Víctor Valls, Stefan Woerner, Mira L. Wolf-Bauwens, Jon Yard, Sheir Yarkoni, Dirk Zechiel, Sergiy Zhuk, Christa Zoufal, Nature Reviews Physics, 6 718-735 (2024), 10.1038/s42254-024-00770-9. https://doi.org/10.1038/s42254-024-00770-9 [4] Sami Boulebnane, Ashley Montanaro, PRX Quantum, 5 030348 (2024), 10.1103/prxquantum.5.030348. https://doi.org/10.1103/prxquantum.5.030348 [5] Ruslan Shaydulin, Changhao Li, Shouvanik Chakrabarti, Matthew DeCross, Dylan Herman, Niraj Kumar, Jeffrey Larson, Danylo Lykov, Pierre Minssen, Yue Sun, Yuri Alexeev, Joan M. Dreiling, John P. Gaebler, Thomas M. Gatterman, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nathan Hewitt, Chandler V. Horst, Shaohan Hu, Jacob Johansen, Mitchell Matheny, Tanner Mengle, Michael Mills, Steven A. Moses, Brian Neyenhuis, Peter Siegfried, Romina Yalovetzky, Marco Pistoia, Science Advances, 10 eadm6761 (2024), 10.1126/sciadv.adm6761. https://doi.org/10.1126/sciadv.adm6761 [6] Scott Aaronson, ``Quantum advantage for NP approximation? For REAL this time?'', Blog post (2024), https://scottaaronson.blog/?p=8375. https://scottaaronson.blog/?p=8375 [7] Dimitris Bertsimas, Jack Dunn, Machine Learning, 106 1039-1082 (2017), 10.1007/s10994-017-5633-9. https://doi.org/10.1007/s10994-017-5633-9 [8] Daniel Rehfeldt, Thorsten Koch, Yuji Shinano, Mathematical Programming Computation, 15 445-470 (2023), 10.1007/s12532-023-00236-6. https://doi.org/10.1007/s12532-023-00236-6 [9] Manuela Weigold, Johanna Barzen, Frank Leymann, Marie Salm, IET Quantum Communication, 2 141-152 (2021), 10.1049/qtc2.12032. https://doi.org/10.1049/qtc2.12032 [10] Javier Gonzalez-Conde, Thomas W. Watts, Pablo Rodriguez-Grasa, Mikel Sanz, Quantum, 8 1297 (2024), 10.22331/q-2024-03-21-1297. https://doi.org/10.22331/q-2024-03-21-1297 [11] Marko J. Rančić, Physical Review Research, 5 l012021 (2023), 10.1103/physrevresearch.5.l012021. https://doi.org/10.1103/physrevresearch.5.l012021 [12] Nicola Mariella, Andrea Simonetto, Physical Review A, 101 012320 (2020), 10.1103/physreva.101.012320. https://doi.org/10.1103/physreva.101.012320 [13] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy, Eleanor G. Rieffel, Physical Review A, 101 012320 (2020), 10.1103/physreva.101.012320. https://doi.org/10.1103/physreva.101.012320 [14] Franz Georg Fuchs, Kjetil Olsen Lye, Halvor Møll Nilsen, Alexander Johannes Stasik, Giorgio Sartor, Algorithms, 15 202 (2022), 10.3390/a15060202. https://doi.org/10.3390/a15060202 [15] Hannes Leipold, Federico M. Spedalieri, Stuart Hadfield, Eleanor Rieffel, arXiv:2407.01975. arXiv:2407.01975 [16] Samuel Marsh, Jingbo B. Wang, Physical Review Research, 2 023302 (2020), 10.1103/physrevresearch.2.023302. https://doi.org/10.1103/physrevresearch.2.023302 [17] Claudio Gambella, Andrea Simonetto, IEEE Transactions on Quantum Engineering, 1 1-22 (2020), 10.1109/tqe.2020.3033139. https://doi.org/10.1109/tqe.2020.3033139 [18] Maike Drieb-Schön, Kilian Ender, Younes Javanmard, Wolfgang Lechner, Quantum, 7 951 (2023), 10.22331/q-2023-03-17-951. https://doi.org/10.22331/q-2023-03-17-951 [19] Hyakka Nakada, Kotaro Tanahashi, Shu Tanaka, arXiv:2501.03521. https://doi.org/10.1109/ACCESS.2025.3563960 arXiv:2501.03521 [20] Josu Ceberio, Ekhine Irurozki, Alexander Mendiburu, Jose A. Lozano, Progress in Artificial Intelligence, 1 103-117 (2012), 10.1007/s13748-011-0005-3. https://doi.org/10.1007/s13748-011-0005-3 [21] Nicola Mariella, Albert Akhriev, Francesco Tacchino, Christa Zoufal, Juan Carlos Gonzalez-Espitia, Benedek Harsanyi, Eugene Koskin, Ivano Tavernelli, Stefan Woerner, Marianna Rapsomaniki, Sergiy Zhuk, Jannis Born, Quantum theory and application of contextual optimal transport, In: Proceedings of the 41st International Conference on Machine Learning (2024), 10.48550/arXiv.2402.14991. https://doi.org/10.48550/arXiv.2402.14991 [22] Fajwel Fogel, Rodolphe Jenatton, Francis Bach, Alexandre d’Aspremont, SIAM Journal on Matrix Analysis and Applications, 36 1465-1488 (2015), 10.1137/130947362. https://doi.org/10.1137/130947362 [23] Alexander Barvinok, Pure and Applied Mathematics Quarterly, 2 943-961 (2006), 10.4310/pamq.2006.v2.n4.a3. https://doi.org/10.4310/pamq.2006.v2.n4.a3 [24] Marc Bataille, Quantum Information Processing, 21 269 (2022), 10.1007/s11128-022-03577-8. https://doi.org/10.1007/s11128-022-03577-8 [25] Dmitri Maslov, Martin Roetteler, IEEE Transactions on Information Theory, 7 4729-4738 (2018), 10.1109/TIT.2018.2825602. https://doi.org/10.1109/TIT.2018.2825602 [26] Dimitri P. Bertsekas, Computational Optimization and Applications, 1 7-66 (1992), 10.1007/bf00247653. https://doi.org/10.1007/bf00247653 [27] Diederik P. Kingma, Jimmy Ba, arXiv:1412.6980. arXiv:1412.6980 [28] David Steven Dummit, Richard M. Foote, Abstract Algebra, Wiley Hoboken (2004),. [29] David Lawrence Johnson, Presentations of Groups, Cambridge University Press (1997), 10.1017/CBO9781139168410. https://doi.org/10.1017/CBO9781139168410 [30] Robert Steinberg, Lectures on Chevalley Groups, American Mathematical Society (2016), 10.1090/ulect/066. https://doi.org/10.1090/ulect/066 [31] François Bruhat, Jacques Tits, Publications Mathématiques de l'Institut des Hautes Études Scientifiques, 41 5-251 (1972), 10.1007/BF02715544. https://doi.org/10.1007/BF02715544 [32] Nicolas Bourbaki, Groupes et algèbres de Lie: Chapitres 4, 5 et 6, Springer Berlin, Heidelberg (1968), 10.1007/978-3-540-34491-9. https://doi.org/10.1007/978-3-540-34491-9 [33] Jacques Tits, Buildings of Spherical Type and Finite BN-Pairs, Springer Berlin Heidelberg (1974), 10.1007/978-3-540-38349-9. https://doi.org/10.1007/978-3-540-38349-9 [34] Emil Artin, Geometric Algebra, Wiley Classics Series (1988), 10.1002/9781118164518. https://doi.org/10.1002/9781118164518 [35] Anders Björner, Francesco Brenti, Combinatorics of Coxeter Groups, Springer (2005), 10.1007/3-540-27596-7. https://doi.org/10.1007/3-540-27596-7 [36] Elisa Bäumer, Stefan Woerner, Physical Review Research, 7 023120 (2025), 10.1103/PhysRevResearch.7.023120. https://doi.org/10.1103/PhysRevResearch.7.023120 [37] Alexander Müller-Hermes, Ion Nechita, Linear Algebra and its Applications, 557 174-187 (2018), 10.1016/j.laa.2018.07.018. https://doi.org/10.1016/j.laa.2018.07.018 [38] Mark W. Coffey, Ron Deiotte, Quantum Information Processing, 7 117-124 (2008), 10.1007/s11128-008-0077-6. https://doi.org/10.1007/s11128-008-0077-6 [39] Adam Glos, Aleksandra Krawiec, Zoltán Zimborás, npj Quantum Information, 8 39 (2022), 10.1038/s41534-022-00546-y. https://doi.org/10.1038/s41534-022-00546-y [40] Lin Chen, Li Yu, Physical Review A, 93 042331 (2016), 10.1103/physreva.93.042331. https://doi.org/10.1103/physreva.93.042331 [41] Tristan Benoist, Ion Nechita, Linear Algebra and its Applications, 521 70-103 (2017), 10.1016/j.laa.2017.01.020. https://doi.org/10.1016/j.laa.2017.01.020 [42] Maria Schuld, Alex Bocharov, Krysta M. Svore, Nathan Wiebe, Physical Review A, 101 032308 (2020), 10.1103/physreva.101.032308. https://doi.org/10.1103/physreva.101.032308 [43] Tjalling C. Koopmans, Martin Beckmann, Econometrica: Journal of the Econometric Society, 25 53-76 (1957), 10.2307/1907742. https://doi.org/10.2307/1907742 [44] Eugene L. Lawler, Management Science, 9 586-599 (1963), 10.1287/mnsc.9.4.586. https://doi.org/10.1287/mnsc.9.4.586 [45] Panos M. Pardalos, Leonidas S. Pitsoulis, Nonlinear Assignment Problems, Springer Netherlands (1999), 10.1007/978-1-4757-3155-2. https://doi.org/10.1007/978-1-4757-3155-2 [46] Zhentao Tan, Yadong Mu, Learning solution-aware transformers for efficiently solving quadratic assignment problem, In: Proceedings of the 41st International Conference on Machine Learning (2024), 10.48550/arXiv.2406.09899. https://doi.org/10.48550/arXiv.2406.09899 [47] Sartaj Sahni, Teofilo Gonzalez, Journal of the ACM, 23 555-565 (1976), 10.1145/321958.321975. https://doi.org/10.1145/321958.321975 [48] Rainer Ernst Burkard, Eranda Çela, Panos M. Pardalos, Leonidas S. Pitsoulis, The Quadratic Assignment Problem, In: Handbook of Combinatorial Optimization (1998), 10.1007/978-1-4613-0303-9_27. https://doi.org/10.1007/978-1-4613-0303-9_27 [49] Panos M. Pardalos, Franz Rendl, Henry Wolkowicz, The quadratic assignment problem: A survey and recent developments (1994), https://www.math.uwaterloo.ca/ hwolkowi/henry/reports/qapsurvey94.pdf. https://www.math.uwaterloo.ca/~hwolkowi/henry/reports/qapsurvey94.pdf [50] Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, Shahnawaz Ahmed, Vishnu Ajith, M. Sohaib Alam, Guillermo Alonso-Linaje, B. AkashNarayanan, Ali Asadi, Juan Miguel Arrazola, Utkarsh Azad, Sam Banning, Carsten Blank, Thomas R Bromley, Benjamin A. Cordier, Jack Ceroni, Alain Delgado, Olivia Di Matteo, Amintor Dusko, Tanya Garg, Diego Guala, Anthony Hayes, Ryan Hill, Aroosa Ijaz, Theodor Isacsson, David Ittah, Soran Jahangiri, Prateek Jain, Edward Jiang, Ankit Khandelwal, Korbinian Kottmann, Robert A. Lang, Christina Lee, Thomas Loke, Angus Lowe, Keri McKiernan, Johannes Jakob Meyer, J. A. Montañez-Barrera, Romain Moyard, Zeyue Niu, Lee James O'Riordan, Steven Oud, Ashish Panigrahi, Chae-Yeun Park, Daniel Polatajko, Nicolás Quesada, Chase Roberts, Nahum Sá, Isidor Schoch, Borun Shi, Shuli Shu, Sukin Sim, Arshpreet Singh, Ingrid Strandberg, Jay Soni, Antal Száva, Slimane Thabet, Rodrigo A. Vargas-Hernández, Trevor Vincent, Nicola Vitucci, Maurice Weber, David Wierichs, Roeland Wiersema, Moritz Willmann, Vincent Wong, Shaoming Zhang, Nathan Killoran, arXiv:1811.04968. arXiv:1811.04968 [51] Rainer E. Burkard, Stefan E. Karisch, Franz Rendl, Journal of Global Optimization, 10 391-403 (1997), 10.1023/a:1008293323270. https://doi.org/10.1023/a:1008293323270 [52] Joshua T. Vogelstein, John M. Conroy, Vince Lyzinski, Louis J. Podrazik, Steven G. Kratzer, Eric T. Harley, Donniell E. Fishkind, R. Jacob Vogelstein, Carey E. Priebe, PLOS ONE, 10 e0121002 (2015), 10.1371/journal.pone.0121002. https://doi.org/10.1371/journal.pone.0121002 [53] Béla Bollobás, Modern Graph Theory, Springer New York (1998), 10.1007/978-1-4612-0619-4. https://doi.org/10.1007/978-1-4612-0619-4 [54] Donatello Conte, Pasquale Foggia, Carlo Sansone, Mario Vento, International Journal of Pattern Recognition and Artificial Intelligence, 18 265-298 (2004), 10.1142/s0218001404003228. https://doi.org/10.1142/s0218001404003228 [55] Vincenzo Bonnici, Rosalba Giugno, Alfredo Pulvirenti, Dennis Shasha, Alfredo Ferro, BMC Bioinformatics, 14 S13 (2013), 10.1186/1471-2105-14-s7-s13. https://doi.org/10.1186/1471-2105-14-s7-s13 [56] Jinsoo Lee, Wook-Shin Han, Romans Kasperovics, Jeong-Hoon Lee, Proceedings of the VLDB Endowment, 6 133-144 (2012), 10.14778/2535568.2448946. https://doi.org/10.14778/2535568.2448946 [57] Vikraman Arvind, Johannes Köbler, STACS 2000, 431-442 (2000), 10.1007/3-540-46541-3_36. https://doi.org/10.1007/3-540-46541-3_36 [58] Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento, IEEE Transactions on Pattern Analysis and Machine Intelligence, 26 1367-1372 (2004), 10.1109/tpami.2004.75. https://doi.org/10.1109/tpami.2004.75 [59] Yonathan Aflalo, Alexander Bronstein, Ron Kimmel, Proceedings of the National Academy of Sciences, 112 2942-2947 (2015), 10.1073/pnas.1401651112. https://doi.org/10.1073/pnas.1401651112 [60] Chems Eddine Nabti, Subgraph Isomorphism Search in Massive Graph Data (2018), https://theses.hal.science/tel-01781831v1. https://theses.hal.science/tel-01781831v1 [61] Rawad Mezher, Ana Filipa Carvalho, Shane Mansfield, Physical Review A, 108 032405 (2023), 10.1103/physreva.108.032405. https://doi.org/10.1103/physreva.108.032405 [62] Cristian S. Calude, Michael J. Dinneen, Richard Hua, Theoretical Computer Science, 701 54-69 (2017), 10.1016/j.tcs.2017.04.016. https://doi.org/10.1016/j.tcs.2017.04.016Cited byCould not fetch Crossref cited-by data during last attempt 2026-02-09 08:38:41: Could not fetch cited-by data for 10.22331/q-2026-02-09-1998 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-02-09 08:38:48: No response from ADS or unable to decode the received json data when getting the list of citing works.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractWe present a quantum variational algorithm based on a novel circuit that generates all permutations that can be spanned by one- and two-qubits permutation gates. The construction of the circuits follows from group-theoretical results, most importantly the Bruhat decomposition of the group generated by the cx gates. These circuits require a number of qubits that scale logarithmically with the permutation dimension, and are therefore employable in near-term applications. We further augment the circuits with ancilla qubits to enlarge their span, and with these we build ansatze to tackle permutation-based optimization problems such as quadratic assignment problems, and graph isomorphisms. The resulting quantum algorithm, QuPer, is competitive with respect to classical heuristics and we could simulate its behavior up to a problem with 256 variables, requiring 20 qubits.► BibTeX data@article{LaplaceMermoud2026variationalquantum, doi = {10.22331/q-2026-02-09-1998}, url = {https://doi.org/10.22331/q-2026-02-09-1998}, title = {Variational quantum algorithms for permutation-based combinatorial problems: {O}ptimal ansatz generation with applications to quadratic assignment problems and beyond}, author = {Laplace Mermoud, Dylan and Simonetto, Andrea and Elloumi, Sourour}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1998}, month = feb, year = {2026} }► References [1] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, arXiv:1411.4028. arXiv:1411.4028 [2] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, Mikhail D. Lukin, Physical Review X, 10 021067 (2020), 10.1103/PhysRevX.10.021067. https://doi.org/10.1103/PhysRevX.10.021067 [3] Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J. Egger, Bruce G. Elmegreen, Nicola Franco, Filippo Fratini, Bryce Fuller, Julien Gacon, Constantin Gonciulea, Sander Gribling, Swati Gupta, Stuart Hadfield, Raoul Heese, Gerhard Kircher, Thomas Kleinert, Thorsten Koch, Georgios Korpas, Steve Lenk, Jakub Marecek, Vanio Markov, Guglielmo Mazzola, Stefano Mensa, Naeimeh Mohseni, Giacomo Nannicini, Corey O’Meara, Elena Peña Tapia, Sebastian Pokutta, Manuel Proissl, Patrick Rebentrost, Emre Sahin, Benjamin C. B. Symons, Sabine Tornow, Víctor Valls, Stefan Woerner, Mira L. Wolf-Bauwens, Jon Yard, Sheir Yarkoni, Dirk Zechiel, Sergiy Zhuk, Christa Zoufal, Nature Reviews Physics, 6 718-735 (2024), 10.1038/s42254-024-00770-9. https://doi.org/10.1038/s42254-024-00770-9 [4] Sami Boulebnane, Ashley Montanaro, PRX Quantum, 5 030348 (2024), 10.1103/prxquantum.5.030348. https://doi.org/10.1103/prxquantum.5.030348 [5] Ruslan Shaydulin, Changhao Li, Shouvanik Chakrabarti, Matthew DeCross, Dylan Herman, Niraj Kumar, Jeffrey Larson, Danylo Lykov, Pierre Minssen, Yue Sun, Yuri Alexeev, Joan M. Dreiling, John P. Gaebler, Thomas M. Gatterman, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nathan Hewitt, Chandler V. Horst, Shaohan Hu, Jacob Johansen, Mitchell Matheny, Tanner Mengle, Michael Mills, Steven A. Moses, Brian Neyenhuis, Peter Siegfried, Romina Yalovetzky, Marco Pistoia, Science Advances, 10 eadm6761 (2024), 10.1126/sciadv.adm6761. https://doi.org/10.1126/sciadv.adm6761 [6] Scott Aaronson, ``Quantum advantage for NP approximation? For REAL this time?'', Blog post (2024), https://scottaaronson.blog/?p=8375. https://scottaaronson.blog/?p=8375 [7] Dimitris Bertsimas, Jack Dunn, Machine Learning, 106 1039-1082 (2017), 10.1007/s10994-017-5633-9. https://doi.org/10.1007/s10994-017-5633-9 [8] Daniel Rehfeldt, Thorsten Koch, Yuji Shinano, Mathematical Programming Computation, 15 445-470 (2023), 10.1007/s12532-023-00236-6. https://doi.org/10.1007/s12532-023-00236-6 [9] Manuela Weigold, Johanna Barzen, Frank Leymann, Marie Salm, IET Quantum Communication, 2 141-152 (2021), 10.1049/qtc2.12032. https://doi.org/10.1049/qtc2.12032 [10] Javier Gonzalez-Conde, Thomas W. Watts, Pablo Rodriguez-Grasa, Mikel Sanz, Quantum, 8 1297 (2024), 10.22331/q-2024-03-21-1297. https://doi.org/10.22331/q-2024-03-21-1297 [11] Marko J. Rančić, Physical Review Research, 5 l012021 (2023), 10.1103/physrevresearch.5.l012021. https://doi.org/10.1103/physrevresearch.5.l012021 [12] Nicola Mariella, Andrea Simonetto, Physical Review A, 101 012320 (2020), 10.1103/physreva.101.012320. https://doi.org/10.1103/physreva.101.012320 [13] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy, Eleanor G. Rieffel, Physical Review A, 101 012320 (2020), 10.1103/physreva.101.012320. https://doi.org/10.1103/physreva.101.012320 [14] Franz Georg Fuchs, Kjetil Olsen Lye, Halvor Møll Nilsen, Alexander Johannes Stasik, Giorgio Sartor, Algorithms, 15 202 (2022), 10.3390/a15060202. https://doi.org/10.3390/a15060202 [15] Hannes Leipold, Federico M. Spedalieri, Stuart Hadfield, Eleanor Rieffel, arXiv:2407.01975. arXiv:2407.01975 [16] Samuel Marsh, Jingbo B. Wang, Physical Review Research, 2 023302 (2020), 10.1103/physrevresearch.2.023302. https://doi.org/10.1103/physrevresearch.2.023302 [17] Claudio Gambella, Andrea Simonetto, IEEE Transactions on Quantum Engineering, 1 1-22 (2020), 10.1109/tqe.2020.3033139. https://doi.org/10.1109/tqe.2020.3033139 [18] Maike Drieb-Schön, Kilian Ender, Younes Javanmard, Wolfgang Lechner, Quantum, 7 951 (2023), 10.22331/q-2023-03-17-951. https://doi.org/10.22331/q-2023-03-17-951 [19] Hyakka Nakada, Kotaro Tanahashi, Shu Tanaka, arXiv:2501.03521. https://doi.org/10.1109/ACCESS.2025.3563960 arXiv:2501.03521 [20] Josu Ceberio, Ekhine Irurozki, Alexander Mendiburu, Jose A. Lozano, Progress in Artificial Intelligence, 1 103-117 (2012), 10.1007/s13748-011-0005-3. https://doi.org/10.1007/s13748-011-0005-3 [21] Nicola Mariella, Albert Akhriev, Francesco Tacchino, Christa Zoufal, Juan Carlos Gonzalez-Espitia, Benedek Harsanyi, Eugene Koskin, Ivano Tavernelli, Stefan Woerner, Marianna Rapsomaniki, Sergiy Zhuk, Jannis Born, Quantum theory and application of contextual optimal transport, In: Proceedings of the 41st International Conference on Machine Learning (2024), 10.48550/arXiv.2402.14991. https://doi.org/10.48550/arXiv.2402.14991 [22] Fajwel Fogel, Rodolphe Jenatton, Francis Bach, Alexandre d’Aspremont, SIAM Journal on Matrix Analysis and Applications, 36 1465-1488 (2015), 10.1137/130947362. https://doi.org/10.1137/130947362 [23] Alexander Barvinok, Pure and Applied Mathematics Quarterly, 2 943-961 (2006), 10.4310/pamq.2006.v2.n4.a3. https://doi.org/10.4310/pamq.2006.v2.n4.a3 [24] Marc Bataille, Quantum Information Processing, 21 269 (2022), 10.1007/s11128-022-03577-8. https://doi.org/10.1007/s11128-022-03577-8 [25] Dmitri Maslov, Martin Roetteler, IEEE Transactions on Information Theory, 7 4729-4738 (2018), 10.1109/TIT.2018.2825602. https://doi.org/10.1109/TIT.2018.2825602 [26] Dimitri P. Bertsekas, Computational Optimization and Applications, 1 7-66 (1992), 10.1007/bf00247653. https://doi.org/10.1007/bf00247653 [27] Diederik P. Kingma, Jimmy Ba, arXiv:1412.6980. arXiv:1412.6980 [28] David Steven Dummit, Richard M. Foote, Abstract Algebra, Wiley Hoboken (2004),. [29] David Lawrence Johnson, Presentations of Groups, Cambridge University Press (1997), 10.1017/CBO9781139168410. https://doi.org/10.1017/CBO9781139168410 [30] Robert Steinberg, Lectures on Chevalley Groups, American Mathematical Society (2016), 10.1090/ulect/066. https://doi.org/10.1090/ulect/066 [31] François Bruhat, Jacques Tits, Publications Mathématiques de l'Institut des Hautes Études Scientifiques, 41 5-251 (1972), 10.1007/BF02715544. https://doi.org/10.1007/BF02715544 [32] Nicolas Bourbaki, Groupes et algèbres de Lie: Chapitres 4, 5 et 6, Springer Berlin, Heidelberg (1968), 10.1007/978-3-540-34491-9. https://doi.org/10.1007/978-3-540-34491-9 [33] Jacques Tits, Buildings of Spherical Type and Finite BN-Pairs, Springer Berlin Heidelberg (1974), 10.1007/978-3-540-38349-9. https://doi.org/10.1007/978-3-540-38349-9 [34] Emil Artin, Geometric Algebra, Wiley Classics Series (1988), 10.1002/9781118164518. https://doi.org/10.1002/9781118164518 [35] Anders Björner, Francesco Brenti, Combinatorics of Coxeter Groups, Springer (2005), 10.1007/3-540-27596-7. https://doi.org/10.1007/3-540-27596-7 [36] Elisa Bäumer, Stefan Woerner, Physical Review Research, 7 023120 (2025), 10.1103/PhysRevResearch.7.023120. https://doi.org/10.1103/PhysRevResearch.7.023120 [37] Alexander Müller-Hermes, Ion Nechita, Linear Algebra and its Applications, 557 174-187 (2018), 10.1016/j.laa.2018.07.018. https://doi.org/10.1016/j.laa.2018.07.018 [38] Mark W. Coffey, Ron Deiotte, Quantum Information Processing, 7 117-124 (2008), 10.1007/s11128-008-0077-6. https://doi.org/10.1007/s11128-008-0077-6 [39] Adam Glos, Aleksandra Krawiec, Zoltán Zimborás, npj Quantum Information, 8 39 (2022), 10.1038/s41534-022-00546-y. https://doi.org/10.1038/s41534-022-00546-y [40] Lin Chen, Li Yu, Physical Review A, 93 042331 (2016), 10.1103/physreva.93.042331. https://doi.org/10.1103/physreva.93.042331 [41] Tristan Benoist, Ion Nechita, Linear Algebra and its Applications, 521 70-103 (2017), 10.1016/j.laa.2017.01.020. https://doi.org/10.1016/j.laa.2017.01.020 [42] Maria Schuld, Alex Bocharov, Krysta M. Svore, Nathan Wiebe, Physical Review A, 101 032308 (2020), 10.1103/physreva.101.032308. https://doi.org/10.1103/physreva.101.032308 [43] Tjalling C. Koopmans, Martin Beckmann, Econometrica: Journal of the Econometric Society, 25 53-76 (1957), 10.2307/1907742. https://doi.org/10.2307/1907742 [44] Eugene L. Lawler, Management Science, 9 586-599 (1963), 10.1287/mnsc.9.4.586. https://doi.org/10.1287/mnsc.9.4.586 [45] Panos M. Pardalos, Leonidas S. Pitsoulis, Nonlinear Assignment Problems, Springer Netherlands (1999), 10.1007/978-1-4757-3155-2. https://doi.org/10.1007/978-1-4757-3155-2 [46] Zhentao Tan, Yadong Mu, Learning solution-aware transformers for efficiently solving quadratic assignment problem, In: Proceedings of the 41st International Conference on Machine Learning (2024), 10.48550/arXiv.2406.09899. https://doi.org/10.48550/arXiv.2406.09899 [47] Sartaj Sahni, Teofilo Gonzalez, Journal of the ACM, 23 555-565 (1976), 10.1145/321958.321975. https://doi.org/10.1145/321958.321975 [48] Rainer Ernst Burkard, Eranda Çela, Panos M. Pardalos, Leonidas S. Pitsoulis, The Quadratic Assignment Problem, In: Handbook of Combinatorial Optimization (1998), 10.1007/978-1-4613-0303-9_27. https://doi.org/10.1007/978-1-4613-0303-9_27 [49] Panos M. Pardalos, Franz Rendl, Henry Wolkowicz, The quadratic assignment problem: A survey and recent developments (1994), https://www.math.uwaterloo.ca/ hwolkowi/henry/reports/qapsurvey94.pdf. https://www.math.uwaterloo.ca/~hwolkowi/henry/reports/qapsurvey94.pdf [50] Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, Shahnawaz Ahmed, Vishnu Ajith, M. Sohaib Alam, Guillermo Alonso-Linaje, B. AkashNarayanan, Ali Asadi, Juan Miguel Arrazola, Utkarsh Azad, Sam Banning, Carsten Blank, Thomas R Bromley, Benjamin A. Cordier, Jack Ceroni, Alain Delgado, Olivia Di Matteo, Amintor Dusko, Tanya Garg, Diego Guala, Anthony Hayes, Ryan Hill, Aroosa Ijaz, Theodor Isacsson, David Ittah, Soran Jahangiri, Prateek Jain, Edward Jiang, Ankit Khandelwal, Korbinian Kottmann, Robert A. Lang, Christina Lee, Thomas Loke, Angus Lowe, Keri McKiernan, Johannes Jakob Meyer, J. A. Montañez-Barrera, Romain Moyard, Zeyue Niu, Lee James O'Riordan, Steven Oud, Ashish Panigrahi, Chae-Yeun Park, Daniel Polatajko, Nicolás Quesada, Chase Roberts, Nahum Sá, Isidor Schoch, Borun Shi, Shuli Shu, Sukin Sim, Arshpreet Singh, Ingrid Strandberg, Jay Soni, Antal Száva, Slimane Thabet, Rodrigo A. Vargas-Hernández, Trevor Vincent, Nicola Vitucci, Maurice Weber, David Wierichs, Roeland Wiersema, Moritz Willmann, Vincent Wong, Shaoming Zhang, Nathan Killoran, arXiv:1811.04968. arXiv:1811.04968 [51] Rainer E. Burkard, Stefan E. Karisch, Franz Rendl, Journal of Global Optimization, 10 391-403 (1997), 10.1023/a:1008293323270. https://doi.org/10.1023/a:1008293323270 [52] Joshua T. Vogelstein, John M. Conroy, Vince Lyzinski, Louis J. Podrazik, Steven G. Kratzer, Eric T. Harley, Donniell E. Fishkind, R. Jacob Vogelstein, Carey E. Priebe, PLOS ONE, 10 e0121002 (2015), 10.1371/journal.pone.0121002. https://doi.org/10.1371/journal.pone.0121002 [53] Béla Bollobás, Modern Graph Theory, Springer New York (1998), 10.1007/978-1-4612-0619-4. https://doi.org/10.1007/978-1-4612-0619-4 [54] Donatello Conte, Pasquale Foggia, Carlo Sansone, Mario Vento, International Journal of Pattern Recognition and Artificial Intelligence, 18 265-298 (2004), 10.1142/s0218001404003228. https://doi.org/10.1142/s0218001404003228 [55] Vincenzo Bonnici, Rosalba Giugno, Alfredo Pulvirenti, Dennis Shasha, Alfredo Ferro, BMC Bioinformatics, 14 S13 (2013), 10.1186/1471-2105-14-s7-s13. https://doi.org/10.1186/1471-2105-14-s7-s13 [56] Jinsoo Lee, Wook-Shin Han, Romans Kasperovics, Jeong-Hoon Lee, Proceedings of the VLDB Endowment, 6 133-144 (2012), 10.14778/2535568.2448946. https://doi.org/10.14778/2535568.2448946 [57] Vikraman Arvind, Johannes Köbler, STACS 2000, 431-442 (2000), 10.1007/3-540-46541-3_36. https://doi.org/10.1007/3-540-46541-3_36 [58] Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento, IEEE Transactions on Pattern Analysis and Machine Intelligence, 26 1367-1372 (2004), 10.1109/tpami.2004.75. https://doi.org/10.1109/tpami.2004.75 [59] Yonathan Aflalo, Alexander Bronstein, Ron Kimmel, Proceedings of the National Academy of Sciences, 112 2942-2947 (2015), 10.1073/pnas.1401651112. https://doi.org/10.1073/pnas.1401651112 [60] Chems Eddine Nabti, Subgraph Isomorphism Search in Massive Graph Data (2018), https://theses.hal.science/tel-01781831v1. https://theses.hal.science/tel-01781831v1 [61] Rawad Mezher, Ana Filipa Carvalho, Shane Mansfield, Physical Review A, 108 032405 (2023), 10.1103/physreva.108.032405. https://doi.org/10.1103/physreva.108.032405 [62] Cristian S. Calude, Michael J. Dinneen, Richard Hua, Theoretical Computer Science, 701 54-69 (2017), 10.1016/j.tcs.2017.04.016. https://doi.org/10.1016/j.tcs.2017.04.016Cited byCould not fetch Crossref cited-by data during last attempt 2026-02-09 08:38:41: Could not fetch cited-by data for 10.22331/q-2026-02-09-1998 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-02-09 08:38:48: No response from ADS or unable to decode the received json data when getting the list of citing works.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.