Relaxations And Exact Solutions To Quantum Max Cut Via The Algebraic Structure Of Swap Operators

Republished By Plato

Followers: 0

Adam Bene Watts¹, Anirban Chowdhury¹, Aidan Epperly², J. William Helton², and Igor Klep^3,4

¹University of Waterloo
²University of California San Diego
³Faculty of Mathematics and Physics, University of Ljubljana
⁴Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

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

Abstract

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.

Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Featured image: Sample Clique-Tree Decomposition of a 10 vertex Quantum Max Cut Graph.

► BibTeX data

@article{Watts2024relaxationsexact, doi = {10.22331/q-2024-05-22-1352}, url = {https://doi.org/10.22331/q-2024-05-22-1352}, title = {Relaxations and {E}xact {S}olutions to {Q}uantum {M}ax {C}ut via the {A}lgebraic {S}tructure of {S}wap {O}perators}, author = {Watts, Adam Bene and Chowdhury, Anirban and Epperly, Aidan and Helton, J. William and Klep, Igor}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, pages = {1352}, month = may, year = {2024} }

► 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://drops.dagstuhl.de/opus/volltexte/2020/12066, doi:10.4230/LIPIcs.TQC.2020.7.
https://doi.org/10.4230/LIPIcs.TQC.2020.7
https://drops.dagstuhl.de/opus/volltexte/2020/12066

[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://dx.doi.org/10.1088/1751-8121/aa6dc3, doi:10.1088/1751-8121/aa6dc3.
https://doi.org/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://dx.doi.org/10.1006/jsco.1996.0125, doi:10.1006/jsco.1996.0125.
https://doi.org/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.
https://doi.org/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://aip.scitation.org/doi/10.1063/1.5085428, doi:10.1063/1.5085428.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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://pnas.org/doi/full/10.1073/pnas.1804949115, doi:10.1073/pnas.1804949115.
https://doi.org/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://doi.org/10.1103/RevModPhys.93.045003, doi:10.1103/RevModPhys.93.045003.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1016/j.cpc.2021.108085
arXiv:arXiv:2011.01764

[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.
https://doi.org/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://drops.dagstuhl.de/opus/volltexte/2019/11246/, doi:10.4230/LIPICS.APPROX-RANDOM.2019.31.
https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.31
http://drops.dagstuhl.de/opus/volltexte/2019/11246/

[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.
https://doi.org/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://dl.acm.org/doi/10.1145/227683.227684, doi:10.1145/227683.227684.
https://doi.org/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.
https://doi.org/10.48550/arXiv.1308.6595
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.
https://doi.org/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.
https://doi.org/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://arxiv.org/abs/2111.01254, doi:10.48550/arXiv.2111.01254.
https://doi.org/10.48550/arXiv.2111.01254
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.
https://doi.org/10.1145/3519935.3519960

[26] Gordon Douglas James. The representation theory of the symmetric groups, volume 682. Springer, 2006. doi:10.1007/BFb0067708.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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://doi.org/10.1137/S0097539704445226, doi:10.1137/S0097539704445226.
https://doi.org/10.1137/S0097539704445226
arXiv:https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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://doi.org/10.1007/3-540-16776-5_740, doi:10.1007/3-540-16776-5_740.
https://doi.org/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://iopscience.iop.org/article/10.1088/1367-2630/10/7/073013, doi:10.1088/1367-2630/10/7/073013.
https://doi.org/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://doi.org/10.1103/PhysRevB.74.094411, doi:10.1103/PhysRevB.74.094411.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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://drops.dagstuhl.de/opus/volltexte/2021/14171, doi:10.4230/LIPIcs.ICALP.2021.102.
https://doi.org/10.4230/LIPIcs.ICALP.2021.102
https://drops.dagstuhl.de/opus/volltexte/2021/14171

[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://arxiv.org/abs/2206.08342, doi:10.48550/arXiv.2206.08342.
https://doi.org/10.48550/arXiv.2206.08342
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.
https://doi.org/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.
https://doi.org/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] Sevag Gharibian, “The 7 faces of quantum NP”, arXiv:2310.18010, (2023).

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

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

The above citations are from SAO/NASA ADS (last updated successfully 2024-05-26 00:54:55). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref’s cited-by service no data on citing works was found (last attempt 2024-05-26 00:54:54).

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.

SEO Powered Content & PR Distribution. Get Amplified Today.
PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
Source: https://quantum-journal.org/papers/q-2024-05-22-1352/

Time Stamp: May 22, 2024

Time Stamp: Mar 9, 2023

Republished By Plato

Fermion-qudit quantum processors for simulating lattice gauge theories with matter

Low depth algorithms for quantum amplitude estimation

Quantum Liouvillian exceptional and diabolical points for bosonic fields with quadratic Hamiltonians: The Heisenberg-Langevin equation approach

Real-Time Krylov Theory for Quantum Computing Algorithms

TensorKrowch: Smooth integration of tensor networks in machine learning

Tight Cramér-Rao type bounds for multiparameter quantum metrology through conic programming

Constant gap between conventional strategies and those based on C*-dynamics for self-embezzlement

Neural Network Approach to the Simulation of Entangled States with One Bit of Communication

Driven-dissipative topological phases in parametric resonator arrays

Call for editors 2024

About Us

Vertical Search & Ai

Platform

Stay Connected

Account