REVIEW 3 cited by
Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs
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 study polynomial-time approximation algorithms for the Quantum Max-Cut (QMC) problem. Given an edge-weighted graph $G$ on n vertices, the QMC problem is to determine the largest eigenvalue of a particular $2^n \times 2^n$ matrix that corresponds to $G$. We provide a sharpened analysis of the currently best-known QMC approximation algorithm for general graphs. This algorithm achieves an approximation ratio of $0.599$, which our analysis improves to $0.603$. Additionally, we propose two new approximation algorithms for the QMC problem on triangle-free and bipartite graphs, that achieve approximation ratios of $0.61383$ and $0.8162$, respectively. These are the best-known approximation ratios for their respective graph classes.
Forward citations
Cited by 3 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.
-
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). Sign in to comment.