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

Write the local Hamiltonian as $H={\sum }_{j=1}^m{h}_j$. Since its terms commute, their matrix exponentials factor exactly:Each factor acts on at most two qubits and can be compiled over a fixed universal quantum gate set to operator norm error at most $\epsilon /m$. The telescoping bound for products of operators then bounds the total error by the sum of the factor errors, at most $\epsilon$. Because $m$ is polynomial in $n$ and the Solovay--Kitaev theorem gives gate count polynomial in $\log (m/\epsilon )$ for each fixed-dimensional factor, this is an efficient commuting local Hamiltonian simulation. Finally, the eigenvalue equation $H|\Psi ⟩=\lambda |\Psi ⟩$ impliesso $|\Psi ⟩$ remains an eigenstate and its eigenvalue is $e^{-i\lambda t}$.

Apply exact quantum phase estimation to $U(t)$ with the supplied eigenstate $|\Psi ⟩$. Sincethe promise that the phase has an $N$-bit representation makes an $N$-qubit control register recover $\varphi$ exactly. Multiplying by $-2\pi$ modulo $2\pi$ gives $\lambda t\mathrm{mod}2\pi$. Equivalently, phase estimation may be run on $U(t{)}^{†}$, whose eigenphase is $\lambda t/(2\pi )$ modulo one.

Let $A=X\otimes X\otimes I$ and $B=Z\otimes I\otimes Z$. The two Pauli operators anticommute because their local factors anticommute at exactly one qubit. Since $A^2=B^2=I$, the mixed terms cancel andThis is a scalar, or $0$-local, Hamiltonian, so the smallest value is $\boxed{k=0}$.

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.