= Solution
Since $A|x\rangle=(-1)^{f(x)}|x\rangle$, the <spectral decomposition> gives
$$
e^{iA}|x\rangle=e^{i(-1)^{f(x)}}|x\rangle.
$$
Replace the middle gate of the previous <compute-phase-uncompute construction> by
$$
e^{iZ}=\operatorname{diag}(e^i,e^{-i})=R_z(-2),
$$
a one-qubit <rotation about the z-axis>. Then
$$
\boxed{C^\dagger(I\otimes e^{iZ})C\,|x,0\rangle
=e^{i(-1)^{f(x)}}|x,0\rangle.}
$$
The circuit uses the gates of $C$, their inverses, and one fixed rotation; it returns the <quantum ancilla> to $|0\rangle$. The same construction implements $e^{itA}$ with middle gate $e^{itZ}$, an instance of <simulation of a computable diagonal Hamiltonian>.
Back to article page
