An Improved Approximation Algorithm for Quantum Max-Cut on Triangle-Free Graphs

Robbie King

doi:10.22331/q-2023-11-09-1180

An Improved Approximation Algorithm for Quantum Max-Cut on Triangle-Free Graphs

Department of Computing and Mathematical Sciences, Caltech

Published:	2023-11-09, volume 7, page 1180
Eprint:	arXiv:2209.02589v3
Doi:	https://doi.org/10.22331/q-2023-11-09-1180
Citation:	Quantum 7, 1180 (2023).

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

Abstract

We give an approximation algorithm for Quantum Max-Cut which works by rounding an SDP relaxation to an entangled quantum state. The SDP is used to choose the parameters of a variational quantum circuit. The entangled state is then represented as the quantum circuit applied to a product state. It achieves an approximation ratio of 0.582 on triangle-free graphs. The previous best algorithms of Anshu, Gosset, Morenz, and Parekh, Thompson achieved approximation ratios of 0.531 and 0.533 respectively. In addition, we study the EPR Hamiltonian, which we argue is a natural intermediate problem which isolates some key quantum features of local Hamiltonian problems. For the EPR Hamiltonian, we give an approximation algorithm with approximation ratio $1 / \sqrt{2}$ on all graphs.

Featured image: Local neighborhood of edge in triangle-free graph.

Popular summary

How can we round an SDP relaxation to an entangled quantum state? And how should we optimize a variational circuit ansatz? In this work, we solve these two problems by combining them: Use the SDP solution to choose the parameters of the variational circuit.

► BibTeX data

@article{King2023improved,
  doi = {10.22331/q-2023-11-09-1180},
  url = {https://doi.org/10.22331/q-2023-11-09-1180},
  title = {An {I}mproved {A}pproximation {A}lgorithm for {Q}uantum {M}ax-{C}ut on {T}riangle-{F}ree {G}raphs},
  author = {King, Robbie},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {7},
  pages = {1180},
  month = nov,
  year = {2023}
}

► 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, 2020. https://doi.org/10.4230/LIPIcs.TQC.2020.7.
https://doi.org/10.4230/LIPIcs.TQC.2020.7

[2] Anurag Anshu, David Gosset, Karen Morenz, and Mehdi Soleimanifar. Improved approximation algorithms for bounded-degree local hamiltonians. Physical Review Letters, 127(25):250502, 2021. https://doi.org/10.1103/PhysRevLett.127.250502.
https://doi.org/10.1103/PhysRevLett.127.250502

[3] Jop Briët, Fernando Mário de Oliveira Filho, and Frank Vallentin. Grothendieck inequalities for semidefinite programs with rank constraint. Theory OF Computing, 10(4):77–105, 2014. https://doi.org/10.4086/toc.2014.v010a004.
https://doi.org/10.4086/toc.2014.v010a004

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

[5] Fernando GSL Brandao and Aram W Harrow. Product-state approximations to quantum states. Communications in Mathematical Physics, 342:47–80, 2016. https://doi.org/10.1007/s00220-016-2575-1.
https://doi.org/10.1007/s00220-016-2575-1

[6] Toby Cubitt and Ashley Montanaro. Complexity classification of local hamiltonian problems. SIAM Journal on Computing, 45(2):268–316, 2016. https://doi.org/10.1137/140998287.
https://doi.org/10.1137/140998287

[7] Uriel Feige and Gideon Schechtman. On the optimality of the random hyperplane rounding technique for max cut. Random Structures & Algorithms, 20(3):403–440, 2002. https://doi.org/10.1002/rsa.10036.
https://doi.org/10.1002/rsa.10036

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

[9] Sevag Gharibian and Ojas Parekh. Almost optimal classical approximation algorithms for a quantum generalization of max-cut. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.31.
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.31

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

[11] Johan Håstad. Some optimal inapproximability results. Journal of the ACM (JACM), 48(4):798–859, 2001. https://doi.org/10.1145/502090.502098.
https://doi.org/10.1145/502090.502098

[12] 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. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1319–1384. SIAM, 2023. https://doi.org/10.1137/1.9781611977554.ch48.
https://doi.org/10.1137/1.9781611977554.ch48

[13] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for max-cut and other 2-variable csps? SIAM Journal on Computing, 37(1):319–357, 2007. https://doi.org/10.1137/S0097539705447372.
https://doi.org/10.1137/S0097539705447372

[14] Eunou Lee. Optimizing quantum circuit parameters via sdp. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). 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

[15] Stephen Piddock and Ashley Montanaro. The complexity of antiferromagnetic interactions and 2d lattices. Quantum Information & Computation, 17(7-8):636–672, 2017. https://dl.acm.org/doi/abs/10.5555/3179553.3179559.
https://dl.acm.org/doi/abs/10.5555/3179553.3179559

[16] 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). 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

[17] Ojas Parekh and Kevin Thompson. Beating random assignment for approximating quantum 2-local hamiltonian problems. In 29th Annual European Symposium on Algorithms (ESA 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.ESA.2021.74.
https://doi.org/10.4230/LIPIcs.ESA.2021.74

[18] Ojas Parekh and Kevin Thompson. An optimal product-state approximation for 2-local quantum hamiltonians with positive terms. arXiv preprint arXiv:2206.08342, 2022. https://doi.org/10.48550/arXiv.2206.08342.
https://doi.org/10.48550/arXiv.2206.08342
arXiv:2206.08342

Cited by

[1] Jihyeok Kim, Deok-Kyu Jang, and Whan-Hyuk Choi, "Quantum Circuits for Amplitude Reweighting", IEEE Access 14, 47259 (2026).

[2] Hamza Fawzi, Omar Fawzi, and Samuel O. Scalet, "Entropy constraints for ground energy optimization", Journal of Mathematical Physics 65 3, 032201 (2024).

[3] Brandon Barton, Jacob Sagal, Sean Feeney, George Grattan, Pratik Patnaik, Vadim Oganesyan, Lincoln D Carr, and Eliot Kapit, "Iterative quantum optimization of spin glass problems with rapidly oscillating transverse fields", Quantum Science and Technology 10 4, 045063 (2025).

[4] Ilya Kull, Norbert Schuch, Ben Dive, and Miguel Navascués, "Lower Bounds on Ground-State Energies of Local Hamiltonians through the Renormalization Group", Physical Review X 14 2, 021008 (2024).

[5] Vorapong Suppakitpaisarn and Jin-Kao Hao, Lecture Notes in Computer Science 14753, 219 (2024) ISBN:978-3-031-62911-2.

[6] Zackary Jorquera, Alexandra Kolla, Steven Kordonowy, Juspreet Singh Sandhu, and Stuart Wayland, "Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians", Quantum 10, 2088 (2026).

[7] Adam Bene Watts, Anirban Chowdhury, Aidan Epperly, J. William Helton, and Igor Klep, "Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators", Quantum 8, 1352 (2024).

[8] Rene Allerstorfer, Matthias Christandl, Dmitry Grinko, Ion Nechita, Maris Ozols, Denis Rochette, and Philip Verduyn Lunel, "Monogamy of Highly Symmetric States", Communications in Mathematical Physics 407 1, 21 (2026).

[9] Andrew Zhao and Nicholas C. Rubin, "Expanding the reach of quantum optimization with fermionic embeddings", Quantum 8, 1451 (2024).

[10] Dmitry Grinko and Maris Ozols, "Linear Programming with Unitary-Equivariant Constraints", Communications in Mathematical Physics 405 12, 278 (2024).

[11] Steven Heilman, "Sphere valued noise stability and quantum MAX-CUT hardness", The Annals of Probability 53 4(2025).

[12] Nicolas PD Sawaya, Daniel Marti-Dafcik, Yang Ho, Daniel P. Tabor, David E. Bernal Neira, Alicia B. Magann, Shavindra Premaratne, Pradeep Dubey, Anne Matsuura, Nathan Bishop, Wibe A. de Jong, Simon Benjamin, Ojas Parekh, Norm Tubman, Katherine Klymko, and Daan Camps, "HamLib: A library of Hamiltonians for benchmarking quantum algorithms and hardware", Quantum 8, 1559 (2024).

[13] Jun Takahashi, Chaithanya Rayudu, Cunlu Zhou, Robbie King, Kevin Thompson, and Ojas Parekh, "An SU(2)-symmetric Semidefinite Programming Hierarchy for Quantum Max Cut", arXiv:2307.15688, (2023).

[14] Joao Basso, Chi-Fang Chen, and Alexander M. Dalzell, "Optimizing random local Hamiltonians by dissipation", arXiv:2411.02578, (2024).

[15] Vir B. Bulchandani and Stephen Piddock, "The classical limit of Quantum Max-Cut", arXiv:2401.12968, (2024).

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

[17] Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, and James Sud, "Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings", arXiv:2504.15276, (2025).

[18] Adrian Solymos, Dávid Jakab, and Zoltán Zimborás, "Extendibility of Brauer states", arXiv:2411.04597, (2024).

[19] Kunal Marwaha, Adrian She, and James Sud, "Performance of Variational Algorithms for Local Hamiltonian Problems on Random Regular Graphs", arXiv:2412.15147, (2024).

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

[21] Wenxuan Tao and Fen Zuo, "A Refined Algorithm For the EPR model", arXiv:2506.08547, (2025).

[22] Wenxuan Tao and Fen Zuo, "Testing APS conjecture on regular graphs", arXiv:2507.10050, (2025).

[23] Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, Lennart Sinjorgo, and James Sud, "A 0.8395-approximation algorithm for the EPR problem", arXiv:2512.09896, (2025).

[24] Sujit Rao, "Analysis of sum-of-squares relaxations for the quantum rotor model", arXiv:2311.09010, (2023).

[25] Steven Heilman, "Sphere Valued Noise Stability and Quantum MAX-CUT Hardness", arXiv:2306.03912, (2023).

[26] Jun Takahashi, Sam Slezak, and Elizabeth Crosson, "Rapidly mixing loop representation quantum Monte Carlo for Heisenberg models on star-like bipartite graphs", arXiv:2411.01452, (2024).

[27] SeungYeop Baik, Sicheol Sung, and Yo-Sub Han, "A Framework for Quantum Finite-State Languages with Density Mapping", arXiv:2407.02776, (2024).

[28] Vorapong Suppakitpaisarn and Jin-Kao Hao, "Utilizing Graph Sparsification for Pre-processing in Maxcut QUBO Solver", arXiv:2401.13004, (2024).

[29] Vincenzo Lipardi, David Mestel, and Georgios Stamoulis, "Product-State Approximation Algorithms for the Transverse Field Ising Model", arXiv:2601.13106, (2026).

[30] Ainesh Bakshi, Arpon Basu, Pravesh Kothari, and Anqi Li, "Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut", arXiv:2605.14994, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-08 01:08:36) and SAO/NASA ADS (last updated successfully 2026-08-08 01:08:37). The list may be incomplete as not all publishers provide suitable and complete citation data.

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.