Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 324 / 3 / b

The vertices $v_2,v_3,v_5$ form a triangle in a graph, so every cut of a graph leaves at least one of their three edges uncut. Hence the cut size is at most four. TakeThe crossing edges are $(1,5),(2,3),(3,5),(4,5)$, so $C=4$. The upper bound is attained and this is a maximum cut.

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.