Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators

Adam Bene Watts1, Anirban Chowdhury1, Aidan Epperly2, J. William Helton2, and Igor Klep3,4

1University of Waterloo
2University of California San Diego
3Faculty of Mathematics and Physics, University of Ljubljana
4Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


The Quantum Max Cut (QMC) problem has emerged as a test-problem for designing approximation algorithms for local Hamiltonian problems. In this paper we attack this problem using the algebraic structure of QMC, in particular the relationship between the quantum max cut Hamiltonian and the representation theory of the symmetric group.

The first major contribution of this paper is an extension of non-commutative Sum of Squares (ncSoS) optimization techniques to give a new hierarchy of relaxations to Quantum Max Cut. The hierarchy we present is based on optimizations over polynomials in the qubit swap operators. This is in contrast to the "standard" quantum Lasserre Hierarchy, which is based on polynomials expressed in terms of the Pauli matrices. To prove correctness of this hierarchy, we exploit a finite presentation of the algebra generated by the qubit swap operators. This presentation allows for the use of computer algebraic techniques to manipulate and simplify polynomials written in terms of the swap operators, and may be of independent interest. Surprisingly, we find that level-2 of this new hierarchy is numerically exact (up to tolerance $10^{-7}$) on all QMC instances with uniform edge weights on graphs with at most 8 vertices.

The second major contribution of this paper is a polynomial-time algorithm that computes (in exact arithmetic) the maximum eigenvalue of the QMC Hamiltonian for certain graphs, including graphs that can be "decomposed" as a signed combination of cliques. A special case of the latter are complete bipartite graphs with uniform edge-weights, for which exact solutions are known from the work of Lieb and Mattis [33]. Our methods, which use representation theory of the symmetric group, can be seen as a generalization of the Lieb-Mattis result.

► BibTeX data

► References

[1] Anurag Anshu, David Gosset, and Karen Morenz. Beyond Product State Approximations for a Quantum Analogue of Max Cut. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography TQC 2020, volume 158 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1–7:15, Riga, Latvia, 2020. Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing. OCLC: 1194977622. URL: https:/​/​​opus/​volltexte/​2020/​12066, doi:10.4230/​LIPIcs.TQC.2020.7.

[2] Jacob C Bridgeman and Christopher T Chubb. Hand-waving and interpretive dance: an introductory course on tensor networks. Journal of Physics A: Mathematical and Theoretical, 50(22):223001, may 2017. URL: https:/​/​​10.1088/​1751-8121/​aa6dc3, doi:10.1088/​1751-8121/​aa6dc3.

[3] Wieb Bosma, John Cannon, and Catherine Playoust. The Magma algebra system. I. The user language. J. Symbolic Comput., 24(3-4):235–265, 1997. Computational algebra and number theory (London, 1993). URL: http:/​/​​10.1006/​jsco.1996.0125, doi:10.1006/​jsco.1996.0125.

[4] Magali Bardet, Jean-Charles Faugère, and Bruno Salvy. On the complexity of the $F_5$ Gröbner basis algorithm. J. Symb. Comput., 70:49–70, 2015. doi:10.1016/​j.jsc.2014.09.025.

[5] Sergey Bravyi, David Gosset, Robert König, and Kristan Temme. Approximation algorithms for quantum many-body problems. Journal of Mathematical Physics, 60(3):032203, March 2019. URL: http:/​/​​doi/​10.1063/​1.5085428, doi:10.1063/​1.5085428.

[6] Fernando G.S.L. Brandao and Aram W. Harrow. Product-state approximations to quantum ground states. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC '13, page 871–880, New York, NY, USA, 2013. Association for Computing Machinery. doi:10.1145/​2488608.2488719.

[7] Sabine Burgdorf, Igor Klep, and Janez Povh. Optimization of polynomials in non-commuting variables. SpringerBriefs in Mathematics. Springer, [Cham], 2016. doi:10.1007/​978-3-319-33338-0.

[8] Calum Buchanan, Christopher Purcell, and Puck Rombach. Subgraph complementation and minimum rank. Electron. J. Combin., 29(1):Paper No. 1.38, 20, 2022. doi:10.37236/​10383.

[9] Boaz Barak, Prasad Raghavendra, and David Steurer. Rounding semidefinite programming hierarchies via global correlation. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science—FOCS 2011, pages 472–481. IEEE Computer Soc., Los Alamitos, CA, 2011. doi:10.1109/​FOCS.2011.95.

[10] David A. Cox, John Little, and Donal O'Shea. Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra. Undergraduate Texts in Mathematics. Springer, Cham, fourth edition, 2015. doi:10.1007/​978-3-319-16721-3.

[11] Toby S. Cubitt, Ashley Montanaro, and Stephen Piddock. Universal quantum Hamiltonians. Proceedings of the National Academy of Sciences, 115(38):9497–9502, September 2018. URL: https:/​/​​doi/​full/​10.1073/​pnas.1804949115, doi:10.1073/​pnas.1804949115.

[12] J. Ignacio Cirac, David Pérez-García, Norbert Schuch, and Frank Verstraete. Matrix product states and projected entangled pair states: Concepts, symmetries, theorems. Rev. Mod. Phys., 93:045003, Dec 2021. URL: https:/​/​​10.1103/​RevModPhys.93.045003, doi:10.1103/​RevModPhys.93.045003.

[13] Etienne de Klerk. Aspects of semidefinite programming, volume 65 of Applied Optimization. Kluwer Academic Publishers, Dordrecht, 2002. Interior point algorithms and selected applications. doi:10.1007/​b105286.

[14] Andrew C. Doherty, Yeong-Cherng Liang, Ben Toner, and Stephanie Wehner. The quantum moment problem and bounds on entangled multi-prover games. In 2008 23rd Annual IEEE Conference on Computational Complexity, pages 199–210. IEEE, 2008. doi:10.1109/​CCC.2008.26.

[15] Pavel Etingof, Oleg Golberg, Sebastian Hensel, Tiankai Liu, Alex Schwendner, Dmitry Vaintrob, and Elena Yudovina. Introduction to representation theory, volume 59 of Student Mathematical Library. American Mathematical Society, Providence, RI, 2011. With historical interludes by Slava Gerovitch. doi:10.1090/​stml/​059.

[16] Renato M. Fonseca. Groupmath: A mathematica package for group theory calculations. 2020. arXiv:2011.01764 [hep-th]. arXiv:arXiv:2011.01764, doi:10.1016/​j.cpc.2021.108085.

[17] Sevag Gharibian and Julia Kempe. Approximation algorithms for QMA-complete problems. SIAM Journal on Computing, 41(4):1028–1050, 2012. doi:10.1137/​110842272.

[18] Sevag Gharibian and Ojas Parekh. Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut. volume 145 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1–31:17. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. Artwork Size: 17 pages Medium: application/​pdf Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/​Saarbruecken, Germany Version Number: 1.0. URL: http:/​/​​opus/​volltexte/​2019/​11246/​, doi:10.4230/​LIPICS.APPROX-RANDOM.2019.31.

[19] Edward L. Green. Multiplicative bases, Gröbner bases, and right Gröbner bases. Journal of Symbolic Computation, 29(4-5):601–623, 2000. doi:10.1006/​jsco.1999.0324.

[20] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6):1115–1145, November 1995. URL: https:/​/​​doi/​10.1145/​227683.227684, doi:10.1145/​227683.227684.

[21] Aram Wettroth Harrow. The church of the symmetric subspace, August 2013. arXiv:1308.6595 [quant-ph]. doi:10.48550/​arXiv.1308.6595.

[22] J. William Helton and Scott McCullough. A Positivstellensatz for noncommutative polynomials. Transactions of the American Mathematical Society, 356(9):3721– 3737, 2004. doi:10.1016/​j.aim.2012.04.028.

[23] Aram W. Harrow and Ashley Montanaro. Extremal eigenvalues of local Hamiltonians. Quantum, 1:6, April 2017. doi:10.22331/​q-2017-04-25-6.

[24] Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson, and John Wright. Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality, September 2022. arXiv:2111.01254 [quant-ph]. URL: http:/​/​​abs/​2111.01254, doi:10.48550/​arXiv.2111.01254.

[25] Matthew B. Hastings and Ryan O'Donnell. Optimizing strongly interacting fermionic Hamiltonians. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 776–789, New York, NY, USA, 2022. Association for Computing Machinery. doi:10.1145/​3519935.3519960.

[26] Gordon Douglas James. The representation theory of the symmetric groups, volume 682. Springer, 2006. doi:10.1007/​BFb0067708.

[27] Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 767–775, 2002. doi:10.1145/​509907.510017.

[28] Robbie King. An Improved Approximation Algorithm for Quantum Max-Cut on Triangle-Free Graphs. Quantum, 7:1180, November 2023. doi:10.22331/​q-2023-11-09-1180.

[29] Julia Kempe, Alexei Kitaev, and Oded Regev. The complexity of the local hamiltonian problem. SIAM Journal on Computing, 35(5):1070–1097, 2006. arXiv:https:/​/​​10.1137/​S0097539704445226, doi:10.1137/​S0097539704445226.

[30] Se-Jin Kim, Vern Paulsen, and Christopher Schafhauser. A synchronous game for binary constraint systems. Journal of Mathematical Physics, 59(3):032201, 2018. doi:10.1063/​1.4996867.

[31] Alexei Ju Kitaev, Aleksandr Ch Shen, and Michail N. Vyalyi. Classical and quantum computation. Number 47 in Graduate studies in mathematics. American Mathematical Society, Providence, RI, 2002. doi:10.1090/​gsm/​047.

[32] Eunou Lee. Optimizing quantum circuit parameters via SDP. In 33rd International Symposium on Algorithms and Computation, volume 248 of LIPIcs. Leibniz Int. Proc. Inform., pages Paper No. 48, 16. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2022. doi:10.4230/​lipics.isaac.2022.48.

[33] Elliott Lieb and Daniel Mattis. Ordering energy levels of interacting spin systems. Journal of Mathematical Physics, 3(4):749–751, jan 1962. doi:10.1063/​1.1724276.

[34] Fedor Levkovich-Maslyuk. The Bethe Ansatz. Journal of Physics A: Mathematical and Theoretical, 49(32):323004, 2016. doi:10.1088/​1751-8113/​49/​32/​323004.

[35] Zeph Landau, Umesh Vazirani, and Thomas Vidick. A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians. Nature Physics, 11(7):566–569, 2015. doi:10.1038/​nphys3345.

[36] Ferdinando Mora. Groebner bases for noncommutative polynomial rings. In Algebraic algorithms and error correcting codes (Grenoble, 1985), volume 229 of Lecture Notes in Comput. Sci., pages 353–362. Springer, Berlin, 1986. URL: https:/​/​​10.1007/​3-540-16776-5_740, doi:10.1007/​3-540-16776-5_740.

[37] Miguel Navascués, Stefano Pironio, and Antonio Acín. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New Journal of Physics, 10(7):073013, July 2008. URL: https:/​/​​article/​10.1088/​1367-2630/​10/​7/​073013, doi:10.1088/​1367-2630/​10/​7/​073013.

[38] Tobias J. Osborne. Statics and dynamics of quantum ${XY}$ and Heisenberg systems on graphs. Physical Review B, 74:094411, Sep 2006. URL: https:/​/​​10.1103/​PhysRevB.74.094411, doi:10.1103/​PhysRevB.74.094411.

[39] Maurice Pouzet, Hamza Si Kaddour, and Bhalchandra Thatte. On the boolean dimension of a graph and other related parameters. Discrete Mathematics & Theoretical Computer Science, 23(Special issues):2, #5, 2022. doi:10.46298/​dmtcs.7437.

[40] Stephen Piddock and Ashley Montanaro. The complexity of antiferromagnetic interactions and 2D lattices. Quantum Information & Computation, 17(7&8):636–672, 2017. doi:10.26421/​QIC17.7-8-6.

[41] Claudio Procesi. Lie groups. Universitext. Springer, New York, 2007. An approach through invariants and representations. doi:10.1007/​978-0-387-28929-8.

[42] Claudio Procesi. A note on the Formanek Weingarten function. Note Mat., 41(1):69–109, 2021. doi:10.1285/​i15900932v41n1p69.

[43] Ojas Parekh and Kevin Thompson. Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 102:1–102:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. URL: https:/​/​​opus/​volltexte/​2021/​14171, doi:10.4230/​LIPIcs.ICALP.2021.102.

[44] Ojas Parekh and Kevin Thompson. An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians with Positive Terms, June 2022. arXiv:2206.08342 [quant-ph]. URL: http:/​/​​abs/​2206.08342, doi:10.48550/​arXiv.2206.08342.

[45] Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 245–254, 2008. doi:10.1145/​1374376.1374414.

[46] Prasad Raghavendra. Approximating NP-hard problems efficient algorithms and their limits. University of Washington, 2009. PhD thesis.

[47] Richard P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. doi:10.1017/​CBO9780511609589.

[48] Jun Takahashi, Chaithanya Rayudu, Cunlu Zhou, Robbie King, Kevin Thompson, and Ojas Parekh. An SU(2)-symmetric semidefinite programming hierarchy for Quantum Max Cut. preprint.

[49] Xingqiang Xiu. Non-commutative Gröbner bases and applications. PhD thesis, 2012.

Cited by

[1] Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang, Proceedings of the 56th Annual ACM Symposium on Theory of Computing 1470 (2024) ISBN:9798400703836.

[2] Eunou Lee and Ojas Parekh, "An improved Quantum Max Cut approximation via matching", arXiv:2401.03616, (2024).

[3] Sevag Gharibian, "The 7 faces of quantum NP", arXiv:2310.18010, (2023).

[4] Charlie Carlson, Zackary Jorquera, Alexandra Kolla, Steven Kordonowy, and Stuart Wayland, "Approximation Algorithms for Quantum Max-$d$-Cut", arXiv:2309.10957, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-06-18 02:38:47) and SAO/NASA ADS (last updated successfully 2024-06-18 02:38:52). The list may be incomplete as not all publishers provide suitable and complete citation data.