Skip to content
Cairn Commons
X Sign in
Level B · Reproducible Quantum information P-constant-50a-approximation-ratio-for-quantum-max-cut

Approximation ratio for quantum Max Cut

Quantum Max Cut is the quantum analog of Max Cut. Given a graph G = (E,V), it asks for the maximum eigenvalue of H_G = Σ_(ij) ∈ E (I - X_iX_j - Y_iY_j - Z_i Z_j), where X_i, Y_i, Z_i are the Pauli matrices acting on the i'th tensor factor and trivially on all other coordinates.

From the catalogue. Imported from Terence Tao and contributors (optimizationproblems repository) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim.

Start working on it Submit a claim Follow
Cite 
@misc{cairn-constant-50a-approximation-ratio-for-quantum-max-cut,
  title        = {Approximation ratio for quantum Max Cut},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/constant-50a-approximation-ratio-for-quantum-max-cut}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-09-29}
}

Also: CITATION.cff · Atom feed of results

Claims
0
Verified
0
Disputed
0
Refuted
0
On the literature board
0

Current state

No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.

The problem

Description of constant

Quantum Max Cut is the quantum analog of Max Cut. Given a graph , it asks for the maximum eigenvalue of , where are the Pauli matrices acting on the i'th tensor factor and trivially on all other coordinates.

Let be a polynomial-time approximation algorithm which for graph G returns an n-qubit quantum state . Then has approximation ratio , if holds for all graphs .

The constant is the maximum approximation ratio to quantum max cut for any polynomial-time algorithm,

Known upper bounds

BoundReferenceComments
[P25]There exists , such that it is NP-hard to compute a value approximating QMC to within approximation ratio .

Known lower bounds

BoundReferenceComments
0.498[GP19]product state approximation
0.526[HTPG24]Pauli Level-1 + second order cone
0.531[AGM20]
0.533[PT21]
0.562[L22]
0.595[LP24]
0.599[JKKSW24]
0.603[GSS25]
0.611[ALMPS25]
0.614[BBKL26]Proves monogamy conjecture from [ALMPS25]

Additional comments

The figure from [GP19] is the optimal product-state approximation ratio (cf. the product-state lower bound in the table above), not a general upper bound on the entangled constant .

Improved ratios can be obtained on triangle-free and bipartite graphs [K22].

Related questions are:

  • approximation ratio for the EPR Hamiltonian, see e.g. [JN25]
  • bounds on the quantum surplus: see e.g. [H25].

See also an overview on techniques used for quantum Max Cut and related problems by Marwaha and Sud, webpage.

References

  • [AGM20] A. Anshu, D. Gosset, K. Morenz, Beyond product state approximations for a quantum analogue of Max Cut, In proceedings of 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), arXiv:2003.14394
  • [ALMPS25] A. Apte, A. Lee, K. Marwaha, O. Parekh, J. Sud. Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings, arXiv:2504.15276
  • [BBKL26] Ainesh Bakshi, Arpon Basu, Pravesh Kothari, Anqi Li, Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut arXiv:2605.14994
  • [GP19] S. Gharibian and O. Parekh. Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut.

In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), volume 145 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1–31:17, 2019, arXiv:1909.08846

  • [GSS25] S. Gribling, L. Sinjorgo, R. Sotirov. Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs, arXiv:2504.11120
  • [H25] F. Huber, A Lovász theta lower bound on Quantum Max Cut, arXiv:2512.20326.
  • [HTPG24] F. Huber, K. Thompson, O. Parekh, S. Gharibian. Second order cone relaxations for quantum Max Cut, arXiv:2411.04120
  • [JN25], N. Ju, A. Nagda, Improved approximation algorithms for the EPR Hamiltonian, arXiv:2504.10712
  • [JKKSW24], Z. Jorquera, A. Kolla, S. Kordonowy, S. S. Sandhu, and S. Wayland. Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians. Nov. 2024. arXiv:2410.15544
  • [K22] R. King, An Improved Approximation Algorithm for Quantum Max-Cut, Quantum 7, 1180 (2023), arXiv:2209.02589
  • [L22] E. Lee. Optimizing Quantum Circuit Parameters via SDP. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ISAAC.2022.48, arXiv:2209.00789
  • [LP24] E. Lee, O. Parekh. An improved Quantum Max Cut approximation via maximum matching, In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 105:1-105:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024) https://doi.org/10.4230/LIPIcs.ICALP.2024.105, arXiv:2401.03616
  • [P25] S. Piddock, Quantum Max-Cut is NP-hard to approximate, arXiv:2510.07995v1
  • [PT21] O. Parekh, K. Thompson, Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms, Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), 2021, arXiv:2105.05698

What counts as progress

  • A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
  • A formal proof (Lean) of a known bound, or a precise error in a claimed one.
  • New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.