Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 324 (Quantum Computation)

Let $H={\mathrm{Stab}}_F(x)$. The identity belongs to $H$ because $F(e,x)=x$. If $g,h\in H$, the group action law givesso $gh\in H$. Finally, if $g\in H$, thenso $g^{-1}\in H$. The subgroup criterion therefore proves that ${\mathrm{Stab}}_F(x)$ is the stabilizer subgroup of $x$.

Put $H={\mathrm{Stab}}_F(x)$. For $g,h\in G$,Thus $f_x$ is constant on every left coset of $H$ and takes different values on different cosets. Its oracle is therefore an oracle for the hidden subgroup problem, and the hidden subgroup is precisely the stabilizer subgroup $H$.

Since $\gcd (x,N)=1$, multiplication by $x$ modulo $N$ is a bijection of ${\mathbb{Z}}_N$, with inverse multiplication by the modular inverse $x^{-1}$. Hence $U_x$ permutes the standard orthonormal basis. It preserves all inner products and satisfiesso $U_x$ is a unitary operator.

The multiplicative order $r$ makes the states $|a^k\mathrm{mod}N⟩$, $0\le k<r$, distinct and cyclic under $U_a$. ThereforeThus each $|{\psi }_s⟩$ is an eigenvector withThese are the Fourier eigenvectors of the cyclic modular-multiplication orbit.

Summing the eigenvectors and reversing the finite sums givesThe root-of-unity filter makes the inner sum equal to $r$ for $k=0$ and zero otherwise. Since $a^0=1$,

Use $|1⟩$ as the target register for quantum phase estimation of $U_a$. By part (iii), it is the equal superposition $r^{-1/2}{\sum }_s|{\psi }_s⟩$ of eigenvectors with phases $s/r$. Controlled modular multiplications implement the required powers $U_a^{2^j}$ efficiently. The phase-estimation circuit produceswhere the first register contains an $m$-bit approximation with constant success probability. A quantum measurement in the computational basis therefore outputs an approximation to $s/r$, with $s$ uniformly distributed over $\{0,\dots ,r-1\}$.

For the HHL algorithm to have runtime polynomial in $\log N$, the Hermitian matrix $A$ must be invertible, have a condition number $\kappa$ bounded by $\mathrm{poly}(\log N)$, and be a sparse matrix with its nonzero entries efficiently accessible by an oracle. The normalized state $|b⟩$ must also be preparable in $\mathrm{poly}(\log N)$ time. With precision costs suppressed, these assumptions let HHL prepare, with high probability,

Normalization gives $p^2+q^2=1$. Write $p=\sin \theta$, $q=\cos \theta$ with $0<\theta <\pi /2$, and set $|u⟩=U|b⟩$. Define the two Householder reflectionsThe amplitude amplification iterate $G=R_u{R}_{\xi }$ preserves $\mathrm{span}\{|\xi ⟩,|\varphi ⟩\}$ and rotates that plane through $2\theta$. ConsequentlyIn particular, $O(1/p)$ iterations raise the success probability to a constant close to one.

Choose an integer $k$ large enough thatPrepare an ancillary qubit in $\sqrt{1-c^2}|0⟩+c|1⟩$ and declare only $|\xi ⟩|1⟩$ to be good. The initial good amplitude ofis $pc=\sin {\theta }^{\prime }$. Applying $k$ amplitude amplification iterations gives good amplitudeThe final state is therefore $|\xi ⟩|1⟩$ up to a global phase. Discarding the ancilla prepares $|\xi ⟩$ exactly; this is exact amplitude amplification.

Let $t=e^{iz}$ and $|u⟩=U|b⟩=p|\xi ⟩+q|\varphi ⟩$. The first factor in $G$ isSince $R(\xi ,z)|u⟩=pt|\xi ⟩+q|\varphi ⟩$, the coefficient of $|\varphi ⟩$ in $G|u⟩$ isIt vanishes whenor, using $p^2+q^2=1$,A unit-modulus solution $t=e^{iz}$ exists exactly when the right-hand side lies in $[-2,2]$. The upper bound is automatic, while the lower bound isThus exact preparation by one application of $G$ is possible precisely whenOne may choose $z$ so that $\cos z=(p^2-q^2)/(2p^2)$. Then $G|u⟩$ has no $|\varphi ⟩$ component and, by unitarity, equals $|\xi ⟩$ up to phase. This is a phase-matched amplitude amplification step.

With $\omega =e^{2\pi i/Q}$, the quantum Fourier transform over the additive group ${\mathbb{Z}}_Q$ is

Apply Hadamard gates to $|0^m⟩$ to prepareReversibly compute the efficiently decidable predicate $[x<Q]$ into an ancillary qubit and measure it. The success probability is $Q/2^m>1/2$, and conditioned on success the first register is exactlyRestart after a failed measurement. After $L=\lceil {\log }_2(1/\delta )\rceil$ attempts, the probability that all attempts fail is below $\delta$, so the state is prepared with probability at least $1-\delta$ using a number of gates polynomial in $m$ and $\log (1/\delta )$.

Write $b={\sum }_{j=0}^{m-1}{2}^j{b}_j$. Applying the phase gateto qubit $b_j$ contributes $\exp (2\pi i{2}^j{b}_j/Q)$. The product of these $m$ gates is thereforeSimilarly, for $a={\sum }_j{a}_j{2}^j$ and $b={\sum }_k{b}_k{2}^k$, apply a controlled phase gatebetween every pair $(a_j,b_k)$. The accumulated phase isThe $m^2$ controlled phase gates implement

Prepare $|\xi ⟩=Q^{-1/2}{\sum }_b|b⟩$ in the second register by part (ii), while preserving the first register $|a⟩$. Applying the diagonal unitary $V$ from part (iii) givesThe preparation can be made coherent using amplitude amplification in place of postselection when this map is needed as a subroutine.

The shift $S|x⟩=|x-1\mathrm{mod}Q⟩$ acts on a Fourier state asThus ${\mathrm{QFT}}_Q|a⟩$ is an eigenvector of $S$ with eigenphase $a/Q$. Apply the unitary part of exact quantum phase estimation for $S$ to a zeroed control register and this Fourier state. It writes the eigenphase label coherently:

Start with $(|a⟩+|b⟩)/\sqrt{2}$ and a zeroed second register. Apply the coherent construction from part (a)(iv) to obtainNow run the inverse of the phase-estimation map from part (b) on the two registers. It erases the first label in both branches:Discarding the zeroed register leaves the required quantum Fourier transform of the superposition. The coherent use of a computed label followed by its inverse is an uncomputation.

The process admits a strong classical simulation of a quantum circuit if a classical algorithm, given its circuit and input descriptions, computes either output probability to the requested polynomial precision in time polynomial in the input size and precision parameter. This asks for the probabilities themselves, rather than only efficient samples from their distribution.

Suppose output qubit $j$ is measured. Its probability of outcome zero isBecause $C$ is a Clifford operation, the Pauli group is preserved under conjugation. Propagating $Z_j$ backward through the $N=\mathrm{poly}(n)$ gates therefore produces, including its sign, a tensor-product PauliThe input is a product state, so the expectation factors:Each one-qubit factor follows directly from the classical description of $|{\alpha }_k⟩$, and conjugating a Pauli through each Clifford gate takes constant classical work. Hence $p_0$, and $p_1=1-p_0$, are computable in polynomial time. This is Heisenberg propagation of a Pauli observable through a Clifford circuit.

Write $|\psi ⟩=\alpha |0⟩+\beta |1⟩$ and $t=e^{i\theta }$. Before measurement, the three controlled-NOT gates map a computational-basis component $|x,y,0⟩$ toThe measured bit is therefore $b=y\oplus x$. For $b=0$, the unnormalized state of the first qubit isFor $b=1$, it isEach branch has probability $1/2$; after normalization and removal of the irrelevant global phase $t$, the two outputs arewith equal probability. This is probabilistic phase-gate injection.