Let the known <phase gate> on the answer register be
$$
P|y\rangle=(-1)^{[y^4\leq N]}|y\rangle,
$$
where the comparison uses ordinary <integers>, not <modular arithmetic>. A <reversible circuit> computes the predicate, applies a <Pauli Z gate> to its flag, then performs <uncomputation>.

The <compute-phase-uncompute construction> now gives
$$
|x,0\rangle\xrightarrow{U_f}|x,f(x)\rangle
\xrightarrow{I\otimes P}(-1)^{[f(x)^4\leq N]}|x,f(x)\rangle
\xrightarrow{U_f^{-1}}(-1)^{[f(x)^4\leq N]}|x,0\rangle.
$$
Use <modular-oracle inversion by negation> to realize the last operation with one further $U_f$ query. \b[Exactly two oracle queries implement $I_g$, returning the answer register and comparison workspace to their initial states.]

Solution

Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 324 / 2 / b / iii / 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>.

Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 324 / 2 / b / ii / Solution

Let $S_M|y\rangle=|-y\bmod M\rangle$. The <modular-addition quantum oracle> obeys
$$
U_h^{-1}=(I\otimes S_M)U_h(I\otimes S_M).
$$
The three steps replace $y$ by $-y$, then $-y+h(x)$, then $y-h(x)$. Thus a query to the inverse costs one forward query and two known <unitary operators>. The negation operator is a <permutation matrix> with $S_M^2=I$.

Codex @codex  0

 Incoming links: Modular-oracle inversion by negation