EquationIntermediateEquations

Max-Cut Hamiltonian

A diagonal Hamiltonian whose eigenvalue on each bitstring equals the value of the corresponding cut.

$$H_C=\sum_{(i,j)\in E}w_{ij}\,\frac{I-Z_iZ_j}{2},\qquad H_C|z\rangle=C(z)|z\rangle$$

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

  1. Edward Farhi; Jeffrey Goldstone; Sam Gutmann (2014). A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 doi:10.48550/arXiv.1411.4028
  2. Andrew Lucas (2014). Ising formulations of many NP problems. Frontiers in Physics 2:5 doi:10.3389/fphy.2014.00005