= Solution
For one input <bit>, a <Boolean function> is specified by the pair $(f(0),f(1))$, and $k=f(0)+f(1)$ counts its <satisfying assignments>. In the ordered <computational basis> $(|0\rangle,|1\rangle)$, the supplied <phase oracle> convention gives
$$
U_f|x\rangle=(-1)^{f(x)\oplus1}|x\rangle,\qquad
U_f=\operatorname{diag}\bigl(2f(0)-1,2f(1)-1\bigr).
$$
Here $\oplus$ is <exclusive or>: \b[the oracle changes the sign of the inputs with $f(x)=0$]. With $I$ the <identity matrix> and $Z$ the <Pauli Z gate>, all four cases are
$$
\begin{array}{c|c|c|c}
f(x)&(f(0),f(1))&k&U_f\\\hline
0&(0,0)&0&\begin{pmatrix}-1&0\\0&-1\end{pmatrix}=-I\\[3pt]
x&(0,1)&1&\begin{pmatrix}-1&0\\0&1\end{pmatrix}=-Z\\[3pt]
1-x&(1,0)&1&\begin{pmatrix}1&0\\0&-1\end{pmatrix}=Z\\[3pt]
1&(1,1)&2&\begin{pmatrix}1&0\\0&1\end{pmatrix}=I
\end{array}
$$
The two middle cases are <balanced Boolean functions>; the others are <constant functions>. The specified zero-state sign change and the <Hadamard gate> are
$$
\boxed{U_0=\begin{pmatrix}-1&0\\0&1\end{pmatrix}=-Z,\qquad
H=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}.}
$$
Use the top <qubit> as the first <tensor product> factor. Write the <controlled unitary gate> as $C(V)=|0\rangle\langle0|\otimes I+|1\rangle\langle1|\otimes V$. Reading the bracketed <quantum circuit> from left to right, its four operations are $C(U_f)$, $C(H)$, $C(U_0)$, $C(H)$. Thus the target operation in its control-one branch is
$$
G=H U_0 H U_f,
\qquad C(G)=C(H)C(U_0)C(H)C(U_f),
$$
where the rightmost <matrix> acts first. The control-zero branch is the <identity operator>. The <Hadamard conjugation of a controlled gate> identity gives
$$
\boxed{C(H)C(U_0)C(H)=(I\otimes H)C(U_0)(I\otimes H).}
$$
Indeed, on control zero the replacement applies $H I H=I$ to the target, while on control one both sides apply $H U_0 H$. By <linearity>, the identity holds on every <quantum superposition> and therefore in every repetition of the bracket. This replaces the two internal controlled <Hadamard gates> as a pair.
The <global phase of a controlled quantum gate> must be preserved: $C(-I)=Z\otimes I$, whereas $C(I)=I\otimes I$. Consequently the minus signs in $U_0=-Z$ and the special <phase oracles> $U_f=-I,-Z$ cannot be discarded as an unobservable <global phase> of the complete <quantum circuit>.
Back to article page
