Pith. sign in

REVIEW 4 cited by

Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

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

arxiv 2504.15276 v1 pith:4DHCEOIO submitted 2025-04-21 quant-ph

Anuj Apte , Eunou Lee , Kunal Marwaha , Ojas Parekh , James Sud This is my paper · ORCID
classification quant-ph
keywords algorithmalgorithmsapproximationmaxcutpartiallyquantumstatesallows
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Sharp Hardness for MAX-3-CUT and Quantum MAX-CUT

    cs.CC 2026-07 conditional novelty 8.0 of 10

    Under UGC, MAX-3-CUT and product-state Quantum MAX-CUT are NP-hard to approximate beyond 0.8360 and 0.9563 times optimal, matching the best known algorithms.

  2. Sharp Bounds on Ground State Energy of the SYK Model

    quant-ph 2026-07 accept novelty 7.5 of 10

    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.

  3. A Refined Algorithm For the EPR model

    quant-ph 2025-06 conditional novelty 6.0 of 10

    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.

  4. Testing APS conjecture on regular graphs

    quant-ph 2025-07 conditional novelty 5.0 of 10

    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.

Pith tools