= 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\rangle$ is
$$
C_N(2|0^n\rangle\langle0^n|-I)C_N^\dagger,
$$
which is polynomial size by the stated assumption.
Here $\sin^2\theta=\sin^2(\pi/10)$, so $\theta=\pi/10$. Two amplification iterations give
$$
(2\cdot2+1)\theta=\frac\pi2.
$$
The final measurement therefore returns a nontrivial factor with certainty whenever $N$ is composite. Only two uses each of $C_N,C_N^\dagger$ up to a constant factor and polynomial-size verification circuits are required, so the complete algorithm is polynomial in $n$.
Back to article page
