MaxCut Compression and Decode Lab
Choose a 12-vertex graph and an encoding. Then change which vertices share a quantum block and see how the required qubits, ideal maximum eigenspace, expected cut, and probability of decoding an optimal cut change together.
This demonstration was built with generative AI.
Preparing the MaxCut model…
Hamiltonian and decoding convention
For a cut assignment s\in\{-1,1\}^{12}, let \operatorname{Cut}(s) be the number of graph edges crossing the cut. Each encoding defines a simultaneous decoder with POVM effects \{M_s\}. The app constructs the decoder-consistent Hamiltonian
H_{\mathcal D}[\operatorname{Cut}] =\sum_s \operatorname{Cut}(s)M_s.
The app maximizes H_{\mathcal D}; in a ground-state convention, this is the same as minimizing -H_{\mathcal D}.
This definition includes the correct POVM pullback for edges whose endpoints occupy the same block; it does not replace that term mechanically by a product of single-bit observables. For every state \rho,
\operatorname{Tr}(H_{\mathcal D}\rho) =\sum_s \operatorname{Cut}(s)\operatorname{Tr}(M_s\rho) =\mathbb E_\rho[\operatorname{Cut}].
Consequently, the largest eigenvalue reported by the app is also the expected cut after one ideal simultaneous decode from a state supported on the maximum eigenspace.
State and success probability
If the largest eigenvalue is degenerate, a single eigenvector would make the displayed decoding probability depend on an arbitrary basis choice. The app instead uses the basis-independent equal mixture on the largest-eigenvalue subspace,
\rho_\star=\frac{\Pi_{\max}}{\operatorname{Tr}\Pi_{\max}}.
After finding every classical optimum by enumerating all 2^{12}=4096 cuts, it reports
p_{\mathrm{opt}} =\sum_{s:\,\operatorname{Cut}(s)=\mathrm{OPT}} \operatorname{Tr}(M_s\rho_\star).
This is the probability that one simultaneous decode returns any optimal assignment, including complementary cuts.
| Encoding | Blocks | Qubits | Hilbert-space dimension |
|---|---|---|---|
| (1,1) | 12 | 12 | 4096 |
| (2,1) | 6 | 6 | 64 |
| (3,1) | 4 | 4 | 16 |
| (3,2) | 4 | 8 | 256 |
For the simultaneous POVMs used here, the (2,1) and (3,1) pullbacks lose two-bit information on an edge inside one block, while the (3,2) pullback retains a nonzero pair signal. The graph draws these inside-block edges with dashed lines so that the effect of repacking vertices remains visible.
Scope
The (1,1) option is the uncompressed reference and uses the conventional diagonal MaxCut cost Hamiltonian associated with QAOA. The app finds its ideal largest-eigenvalue subspace directly; it does not optimize QAOA angles or claim that a finite-depth QAOA circuit reaches that subspace with certainty. All calculations are noiseless and run locally in the browser.
The decoder-first construction follows Decoder-Consistent Hamiltonians for POVM-Based Quantum Relaxations. The one-qubit QRAO encodings follow Approximate Solutions of Combinatorial Problems via Quantum Relaxations, and the (3,2) construction follows Quantum-Relaxation Based Optimization Algorithms: Theoretical Extensions.