Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 58 / 4

For $n\ge 2$, the Pauli X gate and Pauli Z gate act on different qubits in $X_0{Z}_1$, so they commute. Their product is a Hermitian matrix and squares to the identity operator. Its eigenvalues have modulus one; equivalently it is a unitary operator. Therefore its spectral norm isThe $n\ge 2$ qualification is necessary because the qubit labelled one does not exist for $n=1$.

The printed upper summation limit introduces $Z_n$ although only qubits $0,\dots ,n-1$ were defined. Literally the final term is undefined. Use the natural open-chain repairThis preserves the stated $n$-qubit system and agrees with the supplied sum-of-squares hint. If a cyclic convention $Z_n=Z_0$ was intended instead, it must be stated; the same argument works for its $n$ terms when $n\ge 2$. For $n=1$, the repaired open chain is empty and the target is the identity.

Here is a product-formula Hamiltonian simulation using exactly the two supplied lemmas. Let $L=n-1$ and choose an integer $r\ge L$. Every $h_i$ is a norm-one Hermitian matrix. One time slice is the product of two-qubit gatesTo compare a partial product with $e^{i(h_1+\cdots +h_j)/r}$, first propagate the previous error through the next unitary gate, which preserves the spectral norm, and then use Lemma A with $A=-(h_1+\cdots +h_{j-1})/r$, $B=-h_j/r$. Both norms are at most $j/r\le 1$. Its new error is at most $c(j/r{)}^2$ for a universal constant $c$. For an explicit choice, $c=4$ follows from the unitary Taylor bounds $\Vert e^{iA}-I-iA\Vert \le \Vert A{\Vert }^2/2$ and $\Vert e^{iA}-I\Vert \le \Vert A\Vert$. Induction and the triangle inequality therefore giveLemma B, the unitary product telescoping bound, now compares the $r$ repeated slices with $(e^{i{H}_{\mathrm{open}}/r}{)}^r=e^{i{H}_{\mathrm{open}}}$:Take, for example, $r=\max (1,L,\lceil 2c{\sum }_{j=2}^L{j}^2/ϵ\rceil )$. If the sum is zero the product is already exact; otherwise its error is at most $ϵ/2<ϵ$. There are $Lr$ two-qubit gates. This explicit lemma-based construction has fourth-degree dependence on $n$ for fixed precision:This is a sufficient polynomial, not an optimality claim. The polynomial-degree statement treats $ϵ$ as fixed; the inverse-precision dependence is displayed separately. No first-order term error is accumulated without the required repeated-slice factor.

For a unitary operator $W$, $W{W}^{†}=I$. Thus for every nonnegative integer $j$,Insert this into the convergent matrix exponential series in the finite-dimensional qubit setting:Consequently unitary conjugation commutes with the exponential:For an unbounded self-adjoint Hamiltonian, the same identity follows from the spectral theorem for normal operators, with the domain transported by $W$; no unbounded power-series manipulation is needed.

Use one target ancilla qubit initially in $|0⟩$. Apply a CNOT gate from each data qubit $x_j$ to that same target, for $j=1,\dots ,n$. Each CNOT gate adds its control bit modulo two without changing the control. After all $n$ gates the target contains the parity bit $f(x)=x_1\oplus \cdots \oplus x_n$. Thus the required circuit is the $n$-gate parity fan-in:This is parity computation by CNOT gates. The circuit also satisfies $W|x⟩|y⟩=|x⟩|y\oplus f(x)⟩$ for either target value, and $W^{-1}=W$ because all these shared-target CNOT gates commute and individually square to the identity. The action on general superpositions follows by linearity.

The product of the data Pauli Z gates has computational-basis eigenvalueUse the parity circuit $W$ from part (ii), apply the target unitary gate $R=e^{itZ}=\mathrm{diag}(e^{it},e^{-it})$, and then uncompute the parity with $W^{†}$. For every basis input,This equals $e^{it{Z}^{\otimes n}}$ on the data, with the ancilla qubit returned to zero. The compute-phase-uncompute construction therefore gives an exact linear-size circuit:This is a Pauli-string phase by parity computation, an instance of simulation of a computable diagonal Hamiltonian. Part (i) also explains it by $W^{†}(I\otimes Z)W=Z^{\otimes n}\otimes Z$, whose exponential restricts correctly to the target-$|0⟩$ subspace. If no extra line is desired, accumulate parity into the last data qubit, apply $e^{itZ}$ there, and undo the $n-1$ CNOT gates, for $2n-1$ gates. Both constructions implement the global phase as well as the relative phases exactly.