= Solution
Since $\hat x_i=P_{1,i}$ and $I-\hat x_i=P_{0,i}$, the <diagonal Hamiltonian> is
$$
H=-\sum_{(i,j)\in E}\left(P_{1,i}P_{0,j}+P_{0,i}P_{1,j}\right),
$$
with the identity on every unlisted qubit. Each <computational-basis state> is an <eigenstate>, and its eigenvalue is minus the cost of the corresponding cut. Part i supplies cost four, while the assumed bound $|\lambda_{\min}|\leq4$ rules out a lower energy. Thus the <ground-state energy> is $-4$. For the assignment $(x_1,x_2,x_3,x_4,x_5)=(0,1,0,0,1)$, one <ground state> is
$$
\boxed{|\psi\rangle=|01001\rangle}.
$$
Its bitwise complement $|10110\rangle$ is another ground state, as are the basis states corresponding to the other maximum cuts.
Back to article page
