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

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$.