Quantum 2025 – wissenschaftliches Programm
Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe
MON: Monday Contributed Sessions
MON 9: Quantum Entanglement
MON 9.6: Vortrag
Montag, 8. September 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