REVIEW 2 cited by
Second order cone relaxations for quantum Max Cut
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
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.
Forward citations
Cited by 2 Pith papers
-
Sharp Bounds on Ground State Energy of the SYK Model
For super-constant k = o(√n), the expected operator norm of the k-SYK Hamiltonian equals (1−o(1))√(2n)/k, via a twisted-boson operator whose moments match SYK trace moments exactly.
-
On the Approximability of Boolean Max-$k$-CSP
A new Gaussian comparison inequality yields a randomized k/2^k approximation for Boolean Max-k-CSP for every fixed k>=10, the first algorithm to reach the asymptotic optimum constant.
Discussion (0). Continue with ORCID to comment.