quantum-computing

Quantum Max d-Cut via qudit swap operators

Igor Klep, Tea Štrekelj, and Jurij Volčič

21 min read

0 likes

⚡ Quantum Brief

For a large class of complete bipartite graphs, exact solutions for the $d$-QMC problem are derived using the representation theory of symmetric groups and Littlewood-Richardson coefficients. The Quantum Max $d$-Cut ($d$-QMC) problem asks for the largest eigenvalue of a Hamiltonian on a graph with $n$ vertices whose edges correspond to swap operators acting on $(\mathbb C^d)^{\otimes n}$. Lastly, the paper addresses a refined $d$-QMC problem focused on finding the largest eigenvalue within each isotypic component (irreducible block) of the graph Hamiltonian. Olshanski, Kerov’s central limit theorem for the Plancherel measure on Young diagrams, Symmetric Functions 2001: Surveys of Developments and Perspectives, NATO Science Series 74, Springer, Dordrecht, 2002.

AI Audio Summary

0:00 / 0:00

Click to play

Quantum News · Media Library

Understand this faster with AI

Ask ChatGPT

Research with Perplexity

Explain with Claude

Discuss on Grok

AbstractQuantum Max Cut (QMC) problem for systems of qubits is an example of a 2-local Hamiltonian problem, and a prominent paradigm in computational complexity theory. This paper investigates the algebraic structure of a higher-dimensional analog of the QMC problem for systems of qudits.

The Quantum Max $d$-Cut ($d$-QMC) problem asks for the largest eigenvalue of a Hamiltonian on a graph with $n$ vertices whose edges correspond to swap operators acting on $(\mathbb C^d)^{\otimes n}$. The algebra generated by the swap operators is identified as a quotient of a free algebra modulo symmetric group relations and a single additional relation of degree $d$. This presentation leads to a tailored hierarchy of semidefinite programs, leveraging noncommutative polynomial optimization (NPO) methods, that converges to the solution of the $d$-QMC problem. For a large class of complete bipartite graphs, exact solutions for the $d$-QMC problem are derived using the representation theory of symmetric groups and Littlewood-Richardson coefficients. Lastly, the paper addresses a refined $d$-QMC problem focused on finding the largest eigenvalue within each isotypic component (irreducible block) of the graph Hamiltonian. It is shown that the spectrum of the star graph Hamiltonian distinguishes between isotypic components of the $3$-QMC problem. For general $d$, low-degree relations for separating isotypic components are presented, enabling adaptation of the global NPO hierarchy to efficiently compute the largest eigenvalue in each isotypic component.Popular summaryFinding the extremal energy states of interacting quantum systems — the local Hamiltonian problem — is a cornerstone of quantum computational complexity and many-body physics. While earlier research predominantly focused on systems of two-level qubits, modern quantum technologies increasingly exploit higher-dimensional particles known as qudits. In this work, we investigate the Quantum Max d-Cut problem, which seeks the maximum energy of network Hamiltonians built from qudit swap interactions. We identify the fundamental algebraic relations defining these qudit swap operators and formulate the problem using noncommutative polynomial optimization. This yields a tailored hierarchy of semidefinite programs that efficiently computes upper bounds on the maximum energy while bypassing the exponential matrix scaling common in quantum simulations. Combining these algebraic structures with representation theory, we derive exact analytical solutions for key graph families—such as complete, star, and bipartite networks—and introduce algebraic constraints that allow researchers to target and evaluate specific particle symmetry sectors directly.► BibTeX data@article{Klep2026quantummaxdcutvia, doi = {10.22331/q-2026-09-03-2203}, url = {https://doi.org/10.22331/q-2026-09-03-2203}, title = {Quantum {M}ax d-{C}ut via qudit swap operators}, author = {Klep, Igor and {\v{S}}trekelj, Tea and Vol{\v{c}}i{\v{c}}, Jurij}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2203}, month = sep, year = {2026} }► References [1] R. Allerstorfer, M. Christandl, D. Grinko, I. Nechita, M. Ozols, D. Rochette, P. Verduyn Lunel, Monogamy of highly symmetric states, preprint arXiv:2309.16655. https://doi.org/10.48550/arXiv.2309.16655. https://doi.org/10.48550/arXiv.2309.16655 arXiv:2309.16655 [2] A. Anshu, D. Gosset, K. Morenz, Beyond Product State Approximations for a Quantum Analogue of Max Cut, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), Leibniz International Proceedings in Informatics 158, 7:1–7:15, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.TQC.2020.7. https://doi.org/10.4230/LIPIcs.TQC.2020.7 [3] A. Auerbach, Interacting electrons and quantum magnetism, Springer-Verlag, New York, 1994. https://doi.org/10.1007/978-1-4612-0869-3. https://doi.org/10.1007/978-1-4612-0869-3 [4] K. S. D. Beach, F. Alet, M. Mambrini, S. Capponi, ${\rm SU}(N)$ Heisenberg model on the square lattice: A continuous-$N$ quantum Monte Carlo study, Phys. Rev. B 80 (2009) 184401. https://doi.org/10.1103/PhysRevB.80.184401. https://doi.org/10.1103/PhysRevB.80.184401 [5] G. Blekherman, P.A. Parrilo, R.R. Thomas, Rekha R. (ed.), Semidefinite optimization and convex algebraic geometry, Society for Industrial and Applied Mathematics (SIAM), 2013. https://doi.org/10.1137/1.9781611972290. https://doi.org/10.1137/1.9781611972290 [6] I. Bloch, J. Dalibard, W. Zwerger, Many-body physics with ultracold gases, Rev. Mod. Phys. 80 (2008) 885. https://doi.org/10.1103/RevModPhys.80.885. https://doi.org/10.1103/RevModPhys.80.885 [7] A. Bene Watts, A. Chowdhury, A. Epperly, J. W. Helton, I. Klep, Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators, Quantum 8 (2024) 1352, 88pp. https://doi.org/10.22331/q-2024-05-22-1352. https://doi.org/10.22331/q-2024-05-22-1352 [8] W. Bosma, J. Cannon, C. Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997) 235–265. https://doi.org/10.1006/jsco.1996.0125. https://doi.org/10.1006/jsco.1996.0125 [9] S. Bravyi, D. Gosset, R. König, K. Temme, Approximation algorithms for quantum many-body problems, J. Math. Phys. 60 (2019) 032203. https://doi.org/10.1063/1.5085428. https://doi.org/10.1063/1.5085428 [10] F. G. S. L. Brandao, A. W. Harrow, Product-state approximations to quantum ground states, Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing (2013) 871–880. https://doi.org/10.1145/2488608.2488719. https://doi.org/10.1145/2488608.2488719 [11] S. Burgdorf, I. Klep, J. Povh, Optimization of polynomials in non-commuting variables, Springer, 2016. https://doi.org/10.1007/978-3-319-33338-0. https://doi.org/10.1007/978-3-319-33338-0 [12] C. Carlson, Z. Jorquera, A. Kolla, S. Kordonowy, S. Wayland, Approximation Algorithms for Quantum Max-$d$-Cut, preprint arXiv:2309.10957. https://doi.org/10.48550/arXiv.2309.10957. https://doi.org/10.48550/arXiv.2309.10957 arXiv:2309.10957 [13] C. de Concini, C. Procesi: A characteristic free approach to invariant theory, Adv. Math. 21 (1976) 330–354. https://doi.org/10.1016/S0001-8708(76)80003-5. https://doi.org/10.1016/S0001-8708(76)80003-5 [14] A. C. Doherty, Y.-C. Liang, B. Toner, S. Wehner: The quantum moment problem and bounds on entangled multi-prover games, in Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity, 199–210, IEEE Computer Society, 2008. https://doi.org/10.1109/CCC.2008.26. https://doi.org/10.1109/CCC.2008.26 [15] A. Frieze, M. Jerrum, Improved approximation algorithms for MAX $k$-CUT and MAX BISECTION, Algorithmica 18 (1997), 67–81. https://doi.org/10.1007/BF02523688. https://doi.org/10.1007/BF02523688 [16] G. Frobenius, Über die Charaktere der symmetrischen Gruppe, Berl. Ber. (1900) 516–534. https://archive.org/details/sitzungsberichte1900deut. https://archive.org/details/sitzungsberichte1900deut [17] W. Fulton, J. Harris, Representation theory. A first course, Grad. Texts in Math., Read. Math. 129, Springer-Verlag, New York, 1991. https://doi.org/10.1007/978-1-4612-0979-9. https://doi.org/10.1007/978-1-4612-0979-9 [18] S. Gharibian, C. Hecht, Hardness of approximation for ground state problems, preprint arXiv:2411.04874. https://doi.org/10.48550/arXiv.2411.04874. https://doi.org/10.48550/arXiv.2411.04874 arXiv:2411.04874 [19] S. Gharibian, J. Kempe, Approximation algorithms for QMA complete problems, SIAM J. Comput. 41 (2012) 1028–1050. https://doi.org/10.1137/110842272. https://doi.org/10.1137/110842272 [20] S. Gharibian, O. Parekh, Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), Leibniz International Proceedings in Informatics 145, 31:1-31:17, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.31. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.31 [21] E. Giannelli, S. Law, Sylow branching coefficients for symmetric groups, J. Lond. Math. Soc 103 (2020) 697–728. https://doi.org/10.1112/jlms.12389. https://doi.org/10.1112/jlms.12389 [22] S. Gribling, L. Sinjorgo, R. Sotirov: Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs, preprint arXiv:2504.11120. https://doi.org/10.48550/arXiv.2504.11120. https://doi.org/10.48550/arXiv.2504.11120 arXiv:2504.11120 [23] M. X. Goemans, D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42 (1995) 1115–1145. https://doi.org/10.1145/227683.227684. https://doi.org/10.1145/227683.227684 [24] D. Grinberg: Rook sums in the symmetric group algebra, preprint arXiv:2507.22386. https://doi.org/10.48550/arXiv.2507.22386. https://doi.org/10.48550/arXiv.2507.22386 arXiv:2507.22386 [25] D. Gross, S. Nezami, M. Walter, Schur-Weyl duality for the Clifford group with applications: property testing, a robust Hudson theorem, and de Finetti representations, Commun. Math. Phys. 385 (2021) 1325–1393. https://doi.org/10.1007/s00220-021-04118-7. https://doi.org/10.1007/s00220-021-04118-7 [26] A. W. Harrow, A. Montanaro, Extremal eigenvalues of local Hamiltonians, Quantum 1 (2017) 6. https://doi.org/10.22331/q-2017-04-25-6. https://doi.org/10.22331/q-2017-04-25-6 [27] M. B. Hastings, R. O’Donnell, Optimizing strongly interacting fermionic Hamiltonians, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (2022) 776–789. https://doi.org/10.1145/3519935.3519960. https://doi.org/10.1145/3519935.3519960 [28] D. Henrion, M. Korda, J.-B. Lasserre: The moment-SOS hierarchy: Lectures in probability, statistics, computational geometry, control and nonlinear PDEs, Optimization and Its Applications 4, World Scientific, 2020. https://doi.org/10.1142/q0252. https://doi.org/10.1142/q0252 [29] J. W. Helton, S. A. McCullough, A Positivstellensatz for non-commutative polynomials, Trans. Amer. Math. Soc. 356 (2004) 3721–3737. https://doi.org/10.1090/S0002-9947-04-03433-6. https://doi.org/10.1090/S0002-9947-04-03433-6 [30] R. A. Horn, C. R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985. https://doi.org/10.1017/CBO9780511810817. https://doi.org/10.1017/CBO9780511810817 [31] F. Huber, K. Thompson, O. Parekh, S. Gharibian, Second order cone relaxations for quantum Max Cut, preprint arXiv:2411.04120. https://doi.org/10.48550/arXiv.2411.04120. https://doi.org/10.48550/arXiv.2411.04120 arXiv:2411.04120 [32] V. Ivanov, G. Olshanski, Kerov’s central limit theorem for the Plancherel measure on Young diagrams, Symmetric Functions 2001: Surveys of Developments and Perspectives, NATO Science Series 74, Springer, Dordrecht, 2002. https://doi.org/10.1007/978-94-010-0524-1_3. https://doi.org/10.1007/978-94-010-0524-1_3 [33] D. Jakab, Adrian Solymos, Z. Zimborás: Extendibility of Werner states, preprint arXiv:2208.13743. https://doi.org/10.48550/arXiv.2208.13743. https://doi.org/10.48550/arXiv.2208.13743 arXiv:2208.13743 [34] N. Kawashima, Y. Tanabe, Ground States of the ${\rm SU}(N)$ Heisenberg Model, Phys. Rev. Lett. 98 (2007) 057202. https://doi.org/10.1103/PhysRevLett.98.057202. https://doi.org/10.1103/PhysRevLett.98.057202 [35] J. Kempe, A. Yu. Kitaev, O. Regev, The complexity of the local hamiltonian problem, SIAM J. Comput. 35 (2006) 1070–1097. https://doi.org/10.1137/S0097539704445226. https://doi.org/10.1137/S0097539704445226 [36] S. Khot, On the power of unique 2-prover 1-round games, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (2002) 767–775. https://doi.org/10.1145/509907.510017. https://doi.org/10.1145/509907.510017 [37] M. Khovanov, A. D. Lauda, M. Mackaay, M. Stošić, Extended graphical calculus for categorified quantum $\mathfrak{sl}(2)$, Mem. Amer. Math. Soc. 1029, 87p., 2012. https://doi.org/10.1090/S0065-9266-2012-00665-4. https://doi.org/10.1090/S0065-9266-2012-00665-4 [38] R. King, An Improved Approximation Algorithm for Quantum Max-Cut on Triangle-Free Graphs, Quantum 7 (2023), 1180. https://doi.org/10.22331/q-2023-11-09-1180. https://doi.org/10.22331/q-2023-11-09-1180 [39] A. Yu. Kitaev, A. H. Shen, M. N. Vyalyi, Classical and quantum computation, Graduate studies in mathematics 47, American Mathematical Society, Providence, RI, 2002. https://doi.org/10.1090/gsm/047. https://doi.org/10.1090/gsm/047 [40] Z. Landau, U. Vazirani, T. Vidick, A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians, Nat. Phys. 11 (2015) 566–569. https://doi.org/10.1038/nphys3345. https://doi.org/10.1038/nphys3345 [41] M. Lassalle, An explicit formula for the characters of the symmetric group, Math. Ann. 340 (2008) 383–405. https://doi.org/10.1007/s00208-007-0156-5. https://doi.org/10.1007/s00208-007-0156-5 [42] J.-B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim. 11 (2001) 796–817. https://doi.org/10.1137/S1052623400366802. https://doi.org/10.1137/S1052623400366802 [43] M. Laurent: Sums of squares, moment matrices and optimization over polynomials, in Emerging applications of algebraic geometry 157–270, IMA Vol. Math. Appl. 149, Springer, New York, 2009. https://doi.org/10.1007/978-0-387-09686-5_7. https://doi.org/10.1007/978-0-387-09686-5_7 [44] E. Lee, Optimizing quantum circuit parameters via SDP, 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Leibniz International Proceedings in Informatics 248, 48:1-48:16, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.ISAAC.2022.48. https://doi.org/10.4230/LIPIcs.ISAAC.2022.48 [45] F. Levkovich-Maslyuk, The Bethe Ansatz, J. Phys. A: Math. Theor. 49 (2016) 323004. https://doi.org/10.1088/1751-8113/49/32/323004. https://doi.org/10.1088/1751-8113/49/32/323004 [46] E. Lieb, D. Mattis, Ordering energy levels of interacting spin systems, J. Math. Phys. 3 (1962) 749–751. https://doi.org/10.1063/1.1724276. https://doi.org/10.1063/1.1724276 [47] B.D. McKay, A. Piperno, Practical Graph Isomorphism, II, J. Symbolic Comput. 60 (2014) 94–112. https://doi.org/10.1016/j.jsc.2013.09.003. https://doi.org/10.1016/j.jsc.2013.09.003 [48] F. Mora, Groebner bases for noncommutative polynomial rings, Algebraic algorithms and error correcting codes (Grenoble, 1985), 353–362, Lecture Notes in Comput. Sci. 229, Springer, Berlin, 1986. https://doi.org/10.1007/3-540-16776-5_740. https://doi.org/10.1007/3-540-16776-5_740 [49] A. Morales, I. Pak, G. Panova, Hook formulas for skew shapes I. q-analogues and bijections, J. Combin. Theory Ser. A 154 (2018), 350–405. https://doi.org/10.1016/j.jcta.2017.09.002. https://doi.org/10.1016/j.jcta.2017.09.002 [50] H. Naruse, Schubert calculus and hook formula, 73rd Sém. Lothar. Combin., Strobl, Austria, 2014. Talk slides available at https://www.mat.univie.ac.at/ slc/wpapers/s73vortrag/naruse.pdf. https://www.mat.univie.ac.at/~slc/wpapers/s73vortrag/naruse.pdf [51] M. Navascués, S. Pironio, A. Acín, A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations, New J. Phys. 10 (2008) 073013. https://doi.org/10.1088/1367-2630/10/7/073013. https://doi.org/10.1088/1367-2630/10/7/073013 [52] J. Nie, Moment and polynomial optimization, Society for Industrial and Applied Mathematics (SIAM), 2023. https://doi.org/10.1137/1.9781611977608. https://doi.org/10.1137/1.9781611977608 [53] M. A. Nielsen, I. L. Chuang, Quantum computation and quantum information, Cambridge University Press, Cambridge, 2000. https://doi.org/10.1017/CBO9780511976667. https://doi.org/10.1017/CBO9780511976667 [54] O. Parekh, K. Thompson, Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Leibniz International Proceedings in Informatics 198, 102:1–102:20, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.ICALP.2021.102. https://doi.org/10.4230/LIPIcs.ICALP.2021.102 [55] O. Parekh, K. Thompson, An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians with Positive Terms, preprint arXiv:2206.08342. https://doi.org/10.48550/arXiv.2206.08342. https://doi.org/10.48550/arXiv.2206.08342 arXiv:2206.08342 [56] S. Piddock, A. Montanaro, The complexity of antiferromagnetic interactions and 2D lattices, Quantum Inf. Comput. 17 (2017) 636–672. https://doi.org/10.26421/QIC17.7-8-6. https://doi.org/10.26421/QIC17.7-8-6 [57] S. Piddock, A. Montanaro, Universal qudit Hamiltonians, Commun. Math. Phys. 382 (2021) 721–771. https://doi.org/10.1007/s00220-021-03940-3. https://doi.org/10.1007/s00220-021-03940-3 [58] S. Pironio, M. Navascués, A. Acín, Convergent relaxations of polynomial optimization problems with noncommuting variables, SIAM J. Optim. 20 (2010) 2157–2180. https://doi.org/10.1137/090760155. https://doi.org/10.1137/090760155 [59] C. Procesi, Lie groups. An approach through invariants and representations, Universitext, Springer, New York, 2007. https://doi.org/10.1007/978-0-387-28929-8. https://doi.org/10.1007/978-0-387-28929-8 [60] C. Procesi, A note on the Formanek Weingarten function, Note Mat. 41 (2021) 69–109. https://doi.org/10.1285/i15900932v41n1p69. https://doi.org/10.1285/i15900932v41n1p69 [61] P. Raghavendra, Optimal algorithms and inapproximability results for every CSP?, Proceedings of the fortieth annual ACM symposium on Theory of computing (2008) 245–254. https://doi.org/10.1145/1374376.1374414. https://doi.org/10.1145/1374376.1374414 [62] P. Raghavendra, Approximating NP-hard problems efficient algorithms and their limits, University of Washington, 2009, PhD thesis. https://dl.acm.org/doi/10.5555/1751149. https://dl.acm.org/doi/10.5555/1751149 [63] B. E. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, Graduate Texts in Mathematics 203, Springer, 2001. https://doi.org/10.1007/978-1-4757-6804-6. https://doi.org/10.1007/978-1-4757-6804-6 [64] R.P. Stanley, Enumerative combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999. https://doi.org/10.1017/CBO9780511609589. https://doi.org/10.1017/CBO9780511609589 [65] J. Takahashi, C. Rayudu, C. Zhou, R. King, K. Thompson, O. Parekh, An SU(2)-symmetric semidefinite programming hierarchy for Quantum Max Cut, preprint arXiv:2307.15688 https://doi.org/10.48550/arXiv.2307.15688. https://doi.org/10.48550/arXiv.2307.15688 arXiv:2307.15688 [66] A. M. Vershik, S. V. Kerov, Asymptotic theory of the characters of a symmetric group, Funktsional. Anal. i Prilozhen. 15 (1981) 15–27. https://doi.org/10.1007/BF01106153. https://doi.org/10.1007/BF01106153 [67] Y. Wang, Z. Hu, B. C. Sanders, S. Kais, Qudits and High-Dimensional Quantum Computing, Front. Phys. 8 (2020) 589504. https://doi.org/10.3389/fphy.2020.589504. https://doi.org/10.3389/fphy.2020.589504Cited byCould not fetch Crossref cited-by data during last attempt 2026-09-03 08:48:16: Could not fetch cited-by data for 10.22331/q-2026-09-03-2203 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-09-03 08:48:16: Cannot retrieve data from ADS due to rate limitations.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. AbstractQuantum Max Cut (QMC) problem for systems of qubits is an example of a 2-local Hamiltonian problem, and a prominent paradigm in computational complexity theory. This paper investigates the algebraic structure of a higher-dimensional analog of the QMC problem for systems of qudits.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

Discussion

0 professional contributions

Be the first to add a constructive contribution.

Quantum Max d-Cut via qudit swap operators

Tags

Source Information