 Solution

Since ${\hat{x}}_i=P_{1,i}$ and $I-{\hat{x}}_i=P_{0,i}$, the diagonal Hamiltonian iswith 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 }|\le 4$ 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 isIts bitwise complement $|10110⟩$ is another ground state, as are the basis states corresponding to the other maximum cuts.