Lennart Sinjorgo

We introduce a 0.611-approximation algorithm for Quantum MaxCut (QMC) and a 0.8395-approximation algorithm for the EPR Hamiltonian. A novel ingredient in the QMC approximation is to partially entangle pairs of qubits associated to edges in a matching, while preserving the direction of their single-qubit Bloch vectors. This allows us to interpolate between product states and matching-based states with a tunable parameter. For the EPR Hamiltonian, our improvement comes from a new nonlinear monogamy-of-entanglement bound on star graphs and a refined parameterization of a shallow quantum circuit from previous works. We also prove limitations showing that current methods cannot achieve substantially better approximation ratios, indicating that further progress will require fundamentally new techniques.