An Improved Approximation Algorithm For Quantum Max-Cut On Triangle-Free Graphs

Republished By Plato

Followers: 0

Department of Computing and Mathematical Sciences, Caltech

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.

[embedded content]

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}<br /> }

► 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] Nicolas PD Sawaya, Daniel Marti-Dafcik, Yang Ho, Daniel P Tabor, David Bernal, 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).

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

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

[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”, arXiv:2307.15661, (2023).

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

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

The above citations are from SAO/NASA ADS (last updated successfully 2023-11-09 11:49:09). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2023-11-09 11:49:08: Could not fetch cited-by data for 10.22331/q-2023-11-09-1180 from Crossref. This is normal if the DOI was registered recently.

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-2023-11-09-1180/

Time Stamp: November 9, 2023

Time Stamp: Jul 11, 2023

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

Republished By Plato

Abstract

Popular summary

► BibTeX data

► References

Cited by

More from Quantum Journal

Random access codes via quantum contextual redundancy

Certifying the quantum Fisher information from a given set of mean values: a semidefinite programming approach

Dissipation as a resource for Quantum Reservoir Computing

Measurement-induced multipartite-entanglement regimes in collective spin systems

Seasonal submission slumber

Loss-tolerant architecture for quantum computing with quantum emitters

Contextuality in entanglement-assisted one-shot classical communication

Persistent Tensors and Multiqudit Entanglement Transformation

On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks

Quantum key distribution rates from semidefinite programming

Quantum game theory and the complexity of approximating quantum Nash equilibria

Quantum correlations on the no-signaling boundary: self-testing and more

About Us

Vertical Search & Ai

Platform

Stay Connected

Account