= Solution
Applying the two <modular-addition quantum oracles> consecutively adds $h(x)+r(x)=0\pmod M$ to the answer register. Thus
$$
\boxed{U_r=U_h^{-1}.}
$$
Let $S_M|y\rangle=|-y\pmod M\rangle$. Applying $I\otimes S_M$, then $U_h$, then $I\otimes S_M$ gives
$$
|x,y\rangle\longmapsto|x,-y\rangle
\longmapsto|x,-y+h(x)\rangle
\longmapsto|x,y-h(x)\rangle.
$$
Therefore
$$
\boxed{U_h^{-1}=(I\otimes S_M)U_h(I\otimes S_M),}
$$
using one query and two <unitary operators> independent of $h$. This is <modular-oracle inversion by negation>.
Back to article page
