= Solution
All four promised functions have $a=1$. Use <quadratic Boolean phase cancellation>: apply a <Controlled-Z gate> to remove the phase $(-1)^{xy}$, then apply the <Walsh-Hadamard transform>. With the rightmost gate acting first, choose
$$
\boxed{U=(H\otimes H)C_Z.}
$$
Because $C_Z^2=I$ and the <Controlled-Z gate> commutes with the <Pauli Z gates>,
$$
(U\otimes I)|\psi_{1bcd}\rangle=(-1)^d|bc\rangle\otimes|-\rangle.
$$
The <quantum measurement in the computational basis> consequently produces
$$
\begin{array}{c|cccc}
\text{oracle}&f_{1000}&f_{1011}&f_{1101}&f_{1111}\\\hline
\text{outcome}&00&01&10&11
\end{array}
$$
Each answer occurs with <probability> one for its promised <Boolean quantum oracle>.
Back to article page
