= Solution
Let $X|x\rangle=|x+1\rangle$ on the input register and let $N|y\rangle=|-y\rangle$ on the target register. Both are fixed <unitary operators> independent of $f$. Conjugating the query by the input shift gives
$$
\boxed{U_{f_1}=(X^{-1}\otimes I)U_f(X\otimes I),}
$$
because the intermediate query is made at $x+1$. Conjugating by target negation gives
$$
\boxed{U_{f_2}=(I\otimes N)U_f(I\otimes N),}
$$
since $y\mapsto-y\mapsto-y+f(x)\mapsto y-f(x)$. Each construction uses $U_f$ exactly once.
Back to article page
