Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 324 / 3 / a

Let $P_G$ project onto the good subspace and writeThe amplitude amplification theorem says that alternating the reflection $I-2P_G$ with the reflection $2|\psi ⟩⟨\psi |-I$ rotates this two-dimensional plane by $2\theta$. After $j$ amplification iterations the good probability is

Reversibly test whether the measured integer $x$ is a nontrivial divisor of $N$, and phase-flip exactly those computational basis states. This implements the good-subspace reflection in classical and quantum polynomial time. The reflection in $C_N|0^n⟩$ iswhich is polynomial size by the stated assumption.

Here ${\sin }^2\theta ={\sin }^2(\pi /10)$, so $\theta =\pi /10$. Two amplification iterations giveThe final measurement therefore returns a nontrivial factor with certainty whenever $N$ is composite. Only two uses each of $C_N,C_N^{†}$ up to a constant factor and polynomial-size verification circuits are required, so the complete algorithm is polynomial in $n$.