Quantum 2025 – scientific programme

Parts | Days | Selection | Search | Updates | Downloads | Help

MON: Monday Contributed Sessions

MON 9: Quantum Entanglement

MON 9.6: Talk

Monday, September 8, 2025, 15:30–15:45, ZHG101

Improved bounds on Quantum Max-Cut via entanglement theory constraints — •Minh Duc Tran, Lucas Vieira, and Mariami Gachechiladze — Department of Computer Science, Technical University of Darmstadt, Darmstadt, 64289 Germany

The Quantum Max-Cut (QMC) problem is a paradigmatic example in the study of many-body physics and quantum Hamiltonian complexity. While variational methods present lower bounds on the energy of the most exciting state of the given Hamiltonian, semidefinite programming (SDP) hierarchies have been used to obtain upper bounds by solving a relaxed problem. The feasible points for the solutions, which in the relaxed problem may not represent valid quantum states, are then rounded back to a valid state to obtain the approximation ratio. There are two potential venues for improvements: first, speeding up convergence of the SDP by adding extra constraints, and second, improving the rounding schemes. In this work, we present an improved SDP relaxation of QMC for arbitrary graphs by applying polynomial constraints from entanglement theory, achieving tighter bounds on the true values compared to existing approximations. We further extend this framework to the rounding schemes by using the solutions of the SDPs to obtain better initial parameters for variational algorithms.

Keywords: Semidefinite programming; Quantum Max-Cut; Entanglement theory