2024/11/06 by Felix Huber, Huber, Felix, Kevin Thompson +5 · 2 citations
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum and electron transport phenomena
paper · pdf · doi:10.48550/arxiv.2411.04120
openalex publication_date 2024/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Quantum Max Cut (QMC), also known as the quantum anti-ferromagnetic Heisenberg model, is a QMA-complete problem relevant to quantum many-body physics and computer science. Semidefinite programming relaxations have been fruitful in designing theoretical approximation algorithms for QMC, but are computationally expensive for systems beyond tens of qubits. We give a second order cone relaxation for QMC, which optimizes over the set of mutually consistent three-qubit reduced density matrices. In combination with Pauli level-1 of the quantum Lasserre hierarchy, the relaxation achieves an approximation ratio of 0.526 to the ground state energy. Our relaxation is solvable on systems with hundreds of qubits and paves the way to computationally efficient lower and upper bounds on the ground state energy of large-scale quantum spin systems.