Max-Cut Hamiltonian
A diagonal Hamiltonian whose eigenvalue on each bitstring equals the value of the corresponding cut.
Symbols
| $H_C$ | Cost Hamiltonian |
|---|---|
| $w_{ij}$ | Weight of edge (i,j) |
| $Z_i$ | Pauli Z on node i |
| $C(z)$ | Cut value |
$E$ is the set of edges, $w_{ij}$ is the edge weight, $Z_i$ is Pauli $Z$ on qubit (node) $i$, and $C(z)$ is the cut value of string $z$. The term $(I-Z_iZ_j)/2$ equals 1 if the two bits differ and 0 if they are equal. It applies to weighted and unweighted Max-Cut ($w=1$). The lab uses this same formula in QAOA.
Example
The triangle with weights 1 and the string 001 ($q_0=1$): edge $0\!-\!1$ is cut (1), $1\!-\!2$ is not cut (0), and $0\!-\!2$ is cut (1), so $C=2=C_{\max}$ (verified). The string 000 gives 0.
Test your understanding
The quiz needs JavaScript.
Related topics
References
- Edward Farhi; Jeffrey Goldstone; Sam Gutmann (2014). A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 doi:10.48550/arXiv.1411.4028
- Andrew Lucas (2014). Ising formulations of many NP problems. Frontiers in Physics 2:5 doi:10.3389/fphy.2014.00005
