Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 61 / 2

Assume $|\xi ⟩$ is normalized and the Hilbert space has dimension $d$. The rank-one orthogonal projection $P=|\xi ⟩⟨\xi |$ satisfies $P^{†}=P$ and $P^2=P$.

For $d>1$, $P$ has eigenvalue zero on the orthogonal complement of $|\xi ⟩$, so it cannot be a unitary operator. The complementary orthogonal projection $I-P$ kills $|\xi ⟩$ and is not unitary in any positive dimension. In contrast, the Householder reflectionis Hermitian and obeys $R^{†}R=R^2=I-4P+4P^2=I$. Its eigenvalues are $-1$ along $|\xi ⟩$ and $+1$ on the orthogonal complement.

Let ${\Pi }_G$ be the orthogonal projection onto the good vector subspace $G$, and let the normalized input be $|\psi ⟩$. Set $p=\Vert {\Pi }_G\psi {\Vert }^2={\sin }^2\theta$ with $0<\theta <\pi /2$, and defineAssuming coherent access to the two reflections, the amplitude amplification theorem states thatpreserves the plane spanned by $|g⟩,|b⟩$ and acts as a rotation, givingHence the good-outcome probability is ${\sin }^2((2j+1)\theta )$. When $p$ is known, choose the nearest nonnegative integer to $\pi /(4\theta )-1/2$. The resulting angle is within $\theta$ of $\pi /2$, so the good probability is at least ${\cos }^2\theta =1-p$. For small $p$ this is close to one and requires $O(1/\sqrt{p})$ iterations. Exact success occurs when $(2j+1)\theta =\pi /2$. Known $p$ also allows exact amplitude amplification by ancilla qubit dilution or selective phase adjustment when ordinary integer iterations would overshoot.

If $|\psi ⟩=A|0⟩$ has a known coherent preparation, its reflection is implemented with $A$, $A^{†}$ and a zero-state phase flip. A coherent membership test supplies the reflection about $G$. Merely possessing an unknown copy of $|\psi ⟩$ does not automatically supply its reflection. For $p=1$ the state is already good; for $p=0$ this two-reflection construction cannot generate a good component. These cases delimit the theorem's algorithmic assumptions.

Prepare the two data qubits in $|s⟩=\frac{1}{2}{\sum }_{x\in B_2}|x⟩$ and a phase ancilla qubit in $|-⟩$. A single Boolean quantum oracle query flips only the marked amplitude. Its success fraction is $p=1/4$, so $\theta =\pi /6$ in amplitude amplification. The fixed diffusion reflection $D=2|s⟩⟨s|-I$ gives $\sin (3\theta )=1$ after one iteration.

Directly, after the query the marked amplitude is $-1/2$ and the other three are $1/2$. Their mean is $1/4$. The diffusion reflection replaces each amplitude $c_x$ by $2(1/4)-c_x$, yielding one at the marked input and zero elsewhere. ThusHere $U_f$ is understood with its target ancilla qubit, and $D$ acts only on the data. It is independent of $f$: $D=H^{\otimes 2}(2|00⟩⟨00|-I)H^{\otimes 2}$, with the central diagonal gate implementable using two Pauli Z gates and one Controlled-Z gate. Measuring the data in the computational basis therefore finds the unique marked string with certainty after one oracle query.

Write $Q=2^n$, $t=(p-1)(q-1)$ and $a=t/Q$. The easy starting state is uniform over all $n$-bit labels, so its good fraction is $a$, not $t/N$. For distinct primes one has $a\ge 1/4$. If both primes are odd, $t/N\ge (1-1/3)(1-1/5)=8/15$ and $N/Q\ge 1/2$, giving $a\ge 4/15$. If one prime is two, the other is an odd prime $q$; since $2q$ has $n$ bits, $q>2^{n-2}$, and $t=q-1\ge 2^{n-2}=Q/4$.

The uniform coprime state for a semiprime can now be prepared by one exact Grover rotation. SetPrepareUse the good subspace spanned by $|k⟩|1⟩$ with $1\le k<N$ and $\gcd (k,N)=1$. Its squared overlap with $|\Psi ⟩$ is exactly $a\lambda =1/4$. The Euclidean algorithm supplies a reversible computation of the membership predicate, including the range check; condition a sign flip on membership and the extra qubit being one, then uncompute the workspace. This implements $S_G=I-2{\Pi }_G$.

The starting-state reflection $D_{\Psi }=2|\Psi ⟩⟨\Psi |-I$ uses the inverse of its known preparation and a reflection on the all-zero state. Applying $D_{\Psi }{S}_G$ once invokes exact amplitude amplification at $\theta =\pi /6$, and givesThe extra qubit factors off, and the arithmetic workspace is returned to zero. Although the stated range includes $N$, that label is not coprime to itself, so the predicate $k<N$ is equivalent and avoids admitting labels outside the intended range.

The supplied $p,q$ determine $t$ in polynomial time; no factoring procedure is needed. Binary arithmetic, range comparison, the reversible greatest common divisor, the two starting-state reflections and the controlled sign flip all have polynomial-size circuits. Thus the construction takes polynomial time in $n$ in the ideal model allowing the specified one-qubit state preparation. Exactness uses the rotation with known amplitudes $\sqrt{\lambda },\sqrt{1-\lambda }$; with a fixed finite approximate gate library one obtains arbitrary accuracy with precision overhead, rather than an automatic promise of exact state preparation. In the ideal model the preparation succeeds with certainty, without rejection sampling. If desired, the extra $|1⟩$ can be reset by a Pauli X gate.