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

Robbie King

Department of Computing and Mathematical Sciences, Caltech

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


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.

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

► 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:/​/​​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:/​/​​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:/​/​​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:/​/​​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:/​/​​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:/​/​​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:/​/​​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:/​/​​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:/​/​​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:/​/​​10.1145/​227683.227684.

[11] Johan Håstad. Some optimal inapproximability results. Journal of the ACM (JACM), 48(4):798–859, 2001. https:/​/​​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:/​/​​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:/​/​​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:/​/​​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:/​/​​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:/​/​​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:/​/​​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:/​/​​10.48550/​arXiv.2206.08342.

Cited by

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

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

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

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

[5] 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 D Parekh, Norm Tubman, Katherine Klymko, and Daan Camps, "HamLib: A library of Hamiltonians for benchmarking quantum algorithms and hardware", arXiv:2306.13126, (2023).

[6] Dmitry Grinko and Maris Ozols, "Linear programming with unitary-equivariant constraints", arXiv:2207.05713, (2022).

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

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

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

[10] Andrew Zhao and Nicholas C. Rubin, "Expanding the reach of quantum optimization with fermionic embeddings", arXiv:2301.01778, (2023).

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

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

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

The above citations are from Crossref's cited-by service (last updated successfully 2024-07-15 20:27:17) and SAO/NASA ADS (last updated successfully 2024-07-15 20:27:18). The list may be incomplete as not all publishers provide suitable and complete citation data.