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

The map $x\mapsto -x(\mathrm{mod}K)$ is a bijection and an involution, so its permutation matrix satisfiesIn particular $S^{†}S=I$, which proves that $S$ is a unitary operator. Equivalently, it permutes the computational basis and therefore preserves every inner product.

Applying the two modular-addition quantum oracles consecutively adds $h(x)+r(x)=0(\mathrm{mod}M)$ to the answer register. ThusLet $S_M|y⟩=|-y(\mathrm{mod}M)⟩$. Applying $I\otimes S_M$, then $U_h$, then $I\otimes S_M$ givesThereforeusing one query and two unitary operators independent of $h$. This is modular-oracle inversion by negation.

Let the known phase gate on the answer register bewhere 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 givesUse modular-oracle inversion by negation to realize the last operation with one further $U_f$ query. Exactly two oracle queries implement $I_g$, returning the answer register and comparison workspace to their initial states.

An injective self-map of the finite set ${\mathbb{Z}}_N$ is a bijection. For sufficiently large $N$, exactlyoutputs satisfy the integer comparison, so there are exactly $m$ good inputs. Prepare the uniform superposition state $|\psi ⟩=N^{-1/2}{\sum }_x|x⟩$, whose good probability isUse the phase oracle from the previous part and the reflection $2|\psi ⟩⟨\psi |-I$. The amplitude amplification theorem requires $O(p^{-1/2})$ iterations; each uses two $U_f$ queries, while the state preparation and its reflection are independent of $f$. With the nearest-integer iteration count from that theorem, the failure probability is at most $p$, tending to zero. Therefore the success probability eventually exceeds $0.9$, withThis is a bound on quantum query complexity; implementation costs of the known gates are not counted as oracle queries.