Approximation ratio for quantum Max Cut.

Description of constant

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 = \sum_{(ij) \in 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.

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

The constant $C_{50}$ is the maximum approximation ratio to quantum max cut for any polynomial-time algorithm, \(C_{50} = \sup_f \min_G \frac{\mathbb{E}[ \operatorname{tr}(H_G f(G)]}{\lambda_{\max}(H)} \,.\)

Known upper bounds

Bound Reference Comments
$< 1$ [PG25] There exists $\alpha<1$, such that it NP-hard to compute a value approximating QMC to within approximation ratio $\alpha$.
0.5 [GP19] best possible product state approximation

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.603 [GSS25]  
0.611 [ALMPS25]  

Additional comments

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

Related questions are:

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

References

Contribution notes

Used Claude for double-checking references and values.