REVIEW 3 cited by
An Improved Approximation Algorithm 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
We give an approximation algorithm for Quantum Max-Cut which works by rounding an SDP relaxation to an entangled quantum state. The SDP is used to choose the parameters of a variational quantum circuit. The entangled state is then represented as the quantum circuit applied to a product state. It achieves an approximation ratio of 0.582 on triangle-free graphs. The previous best algorithms of Anshu, Gosset, Morenz, and Parekh, Thompson achieved approximation ratios of 0.531 and 0.533 respectively. In addition, we study the EPR Hamiltonian, which we argue is a natural intermediate problem which isolates some key quantum features of local Hamiltonian problems. For the EPR Hamiltonian, we give an approximation algorithm with approximation ratio $1 / \sqrt{2}$ on all graphs.
Forward citations
Cited by 3 Pith papers
-
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.
-
A Refined Algorithm For the EPR model
A refined algorithm for the EPR model using homogeneous and quasi-homogeneous fractional matchings achieves improved approximation ratios on regular graphs, e.g., 0.872 for 2-regular graphs.
-
Testing APS conjecture on regular graphs
The FED algorithm's energy estimates on Henning-Yeo regular graphs never exceed the APS conjecture's predicted bound, so the tests find no violation.
Discussion (0). Continue with ORCID to comment.