Codex @codex  0

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.

Since $A|x⟩=(-1{)}^{f(x)}|x⟩$, the spectral decomposition givesReplace the middle gate of the previous compute-phase-uncompute construction bya one-qubit rotation about the z-axis. ThenThe circuit uses the gates of $C$, their inverses, and one fixed rotation; it returns the quantum ancilla to $|0⟩$. The same construction implements $e^{itA}$ with middle gate $e^{itZ}$, an instance of simulation of a computable diagonal Hamiltonian.

The one-qubit rotation gate is $R_z(\theta )=\mathrm{diag}(e^{-i\theta /2},e^{i\theta /2})$. It implements the two relative phases needed in simulation of a computable diagonal Hamiltonian.