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

Let $\Pi$ be the orthogonal projection onto the good linear subspace $\mathcal{G}$, and let $|\psi ⟩$ be a prepared unit vector with $p=⟨\psi |\Pi |\psi ⟩$. For $0<p<1$, defineThe amplitude amplification theorem states that, if the reflection operators about the initial state and the good subspace can be implemented, the iterationsatisfiesTo prove it, the two reflections preserve the linear span of $|g⟩,|b⟩$. In this ordered orthonormal basis, direct multiplication givesMultiplying this rotation matrix by $(\sin \alpha ,\cos \alpha {)}^T$ replaces $\alpha$ by $\alpha +2\theta$, proving the formula by mathematical induction.

For known $0<p\le 1/2$, choose $j$ to be a nearest nonnegative integer to $\pi /(4\theta )-1/2$. Then $|(2j+1)\theta -\pi /2|\le \theta$, so measurement finds the good subspace with probability at least $1-p$, using $O(p^{-1/2})$ iterations. For $p>1/2$, measurement of the initial state already has constant success probability. If $p=1$ success is certain; if $p=0$ these reflections cannot create any good component. If $|\psi ⟩=A|0⟩$, the initial-state reflection is $A(2|0⟩⟨0|-I)A^{†}$, implemented using quantum state preparation and its inverse quantum circuit.

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.