← Back to papers
Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings
Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, James Sud·April 21, 2025·DOI: 10.4230/LIPIcs.ESA.2025.101
Computer SciencePhysics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
We introduce a $0.611$-approximation algorithm for Quantum MaxCut and a $\frac{1+\sqrt{5}}{4} \approx 0.809$-approximation algorithm for the EPR Hamiltonian of [arXiv:2209.02589]. A novel ingredient in both of these algorithms 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.