An Improved Approximation Algorithm for Quantum Max-Cut

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.

References in corpus (8)

• Approximation algorithms for quantum many-body problems
• Grothendieck inequalities for semidefinite programs with rank constraint
• Approximation algorithms for QMA-complete problems
• Improved approximation algorithms for bounded-degree local Hamiltonians
• Beyond product state approximations for a quantum analogue of Max Cut
• An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians with Positive Terms
• Application of the Level-$2$ Quantum Lasserre Hierarchy in Quantum Approximation Algorithms
• Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems

Cited by in corpus (6)

• Lower Bounding Ground-State Energies of Local Hamiltonians Through the Renormalization Group
• Entropy Constraints for Ground Energy Optimization
• Linear programming with unitary-equivariant constraints
• Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators
• Monogamy of highly symmetric states
• Expanding the reach of quantum optimization with fermionic embeddings