Submit progress

on Approximation ratio for quantum Max Cut ($C_{50}$)

The statement

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_G)} \,.

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.