OpenFrontiers
Join
← Back to the index
OP-12062OpenQuantum information

Approximation ratio for quantum Max Cut (C50C_{50})

Approximation ratio for quantum Max Cut: determine C50C_{50} or improve its bounds; the repository records 0.614 (lower) and <1<1 (0.5 for product states) (upper).

MSC 81P68 · Quantum computationMSC 68W25 · Approximation algorithms

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

Quantum Max Cut is the quantum analog of Max Cut. Given a graph G=(E,V)G = (E,V), it asks for the maximum eigenvalue of HG=∑(ij)∈E(I−XiXj−YiYj−ZiZj)H_G = \sum_{(ij) \in E} (I - X_iX_j - Y_iY_j - Z_i Z_j), where Xi,Yi,ZiX_i, Y_i, Z_i are the Pauli matrices acting on the i'th tensor factor and trivially on all other coordinates.

Let ff be a polynomial-time approximation algorithm which for graph G returns an n-qubit quantum state f(G)=ϱf(G) = \varrho. Then ff has approximation ratio α\alpha, if E[tr⁡(Hϱ)]≥α⋅λmax⁡(G)\mathbb{E}[ \operatorname{tr}(H \varrho)] \geq \alpha \cdot \lambda_{\max}(G) holds for all graphs GG.

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

C50=sup⁡fmin⁡GE[tr⁡(HGf(G))]λmax⁡(HG) .C_{50} = \sup_f \min_G \frac{\mathbb{E}[ \operatorname{tr}(H_G f(G))]}{\lambda_{\max}(H_G)} \,.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

The 1/21/2 figure from [GP19] is the optimal product-state approximation ratio (cf. the 0.4980.498 product-state lower bound in the table above), not a general upper bound on the entangled constant C50C_{50}.

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 (from the repository page)

  • [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

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 0.614; best known upper bound <1<1 (0.5 for product states). Values marked with an asterisk have minimal verification.

Known upper bounds

Bound Reference Comments
<1< 1 [P25] There exists α<1\alpha<1, such that it is NP-hard to compute a value approximating QMC to within approximation ratio α\alpha.

Known lower bounds

Bound Reference Comments
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]
References
  1. [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Approximation ratio for quantum Max Cut ($C_{50}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.