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

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

For a positive Hermitian matrix,The HHL algorithm phase-estimates $A$, performs a controlled rotation with amplitude proportional to $1/{\lambda }_i$, uncomputes the estimate, and postselects the rotation ancilla. Resolving the smallest eigenvalue requires phase-estimation precision $O({\lambda }_{\min })$ and evolution time $\Omega (1/{\lambda }_{\min })$. Since ${\lambda }_{\max }\le 1$, this contributes a dependence at least linear in $\kappa$.

The controlled rotation must use a scale $C\le {\lambda }_{\min }$. In the worst input direction its success probability is of orderso obtaining constant success by amplitude amplification costs another $O(\kappa )$ factor. Thus a runtime polynomial in $\log N$ requiresAn exponentially ill-conditioned matrix would require exponentially fine phase resolution or exponentially many amplification steps.