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

The hidden subgroup problem supplies an oracle $f:G\to X$ promised to satisfyfor an unknown subgroup $H\le G$; the task is to determine $H$.

For a function $f:{\mathbb{Z}}_K\to \mathbb{Z}$ with least period $r$ dividing $K$, use the additive group $G={\mathbb{Z}}_K$ and hidden subgroupIts cosets are the residue classes modulo $r$. Periodicity makes $f$ constant on each coset, while injectivity within a period makes values on distinct cosets different. Determining $H$, or its least positive generator $r$, is exactly quantum period finding.

The matrix-element orthogonality theorem for irreducible unitary representations statesand ${\sum }_{\alpha }{d}_{\alpha }^2=|G|$. Consequently the normalized vectorsform an orthonormal basis. The non-abelian quantum Fourier transform is the unitary basis changeup to the harmless choice of transform direction and complex-conjugation convention.

Put $x=g_{0}g$ in the definition of $U(g_0)|\alpha ij⟩$ and useOne obtainsThus every $d_{\alpha }^2$-dimensional subspace ${\mathcal{H}}_{\alpha }$ is invariant; the left regular representation acts as $M_{\alpha }(g_0)$ on the first matrix index and as the identity on the second.

Let $P_{\alpha }$ project onto ${\mathcal{H}}_{\alpha }$. Since the subspace is invariant under every $U(g)$, $P_{\alpha }$ commutes with those unitaries. Also $|gH⟩=U(g)|H⟩$. Thereforewhich is independent of the coset representative $g$ and depends only on $H$.

No. In particular, conjugate subgroups $H^{\prime }=xH{x}^{-1}$ produce the same weak irrep-label distribution. Under an irrep, the subgroup averageis related by unitary similarity, so its squared Hilbert-Schmidt norm, and hence every ${\Pi }_H(\alpha )$, is unchanged. Weak Fourier sampling can therefore fail to identify even distinct subgroups of a non-abelian group.

Use $m$ control qubits and exact quantum phase estimation. A controlled $U^{2^j}$ on the unknown eigenstate can be synthesized from the available uncontrolled operation and the known eigenstate $|{\xi }_0⟩$: conditionally swap $|\xi ⟩$ into an auxiliary register initialized to $|{\xi }_0⟩$, apply $U^{2^j}$ to that register, and swap back. The auxiliary state is restored, while the control-one branch acquires $e^{2\pi i{2}^j\varphi }$.

After Hadamard gates and these controlled powers, the control register isThe inverse quantum Fourier transform maps this state exactly to $|c⟩$, so measurement determines $c$ with certainty. There are $m$ controlled swaps of $O(n)$ qubits, each promised power costs $\mathrm{poly}(n,j)$, and the inverse transform uses $O(m^2)$ elementary gates. The total cost is therefore $\mathrm{poly}(n,m)$.

Expand $|b⟩={\sum }_i{b}_i|{\lambda }_i⟩$ in the nondegenerate eigenbasis of $A$. Apply quantum phase estimation to $U_{+}=e^{2\pi iA}$, using $U_{-}$ when inverse powers are needed, to coherently attach the eigenvalue:On an ancillary qubit perform the eigenvalue-controlled rotationUncompute the value register and measure the ancilla. Conditional on outcome one, the system is proportional toand normalization gives the desired $|\psi ⟩$.

The success probability isSince every ${\lambda }_i>0$,a positive lower bound independent of $|b⟩$. The promised precision assumptions permit the eigenvalue-controlled arithmetic and rotation.

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.

The process is classically strongly efficiently simulatable if a deterministic classical algorithm can compute the probability of any specified $K$-bit output string to requested additive precision $2^{-m}$ in time polynomial in $n$, the circuit description, and $m$. This is strong classical simulation of a quantum circuit, and is stronger than merely sampling its output.

For the first output qubit,A Clifford circuit maps the Pauli observable $Z_1$ under conjugation to a tensor-product Pauli operator $\pm P_1\otimes \cdots \otimes P_n$, found by propagating it backward through the circuit in polynomial time. Since the input is a product state,Each factor is efficiently computable, so both one-bit output probabilities are strongly simulatable. This is Heisenberg propagation of a Pauli observable through a Clifford circuit.

Take any bounded-error polynomial-size quantum circuit for a language in $\mathrm{BQP}$ and express it using $H,CX,S,T$. Replace each $T$ gate by the supplied $T$-gadget. Before measurements and conditional corrections, the resulting circuit uses only Clifford gates and has a product input consisting of the original input and one magic state $|A⟩$ per gadget.

Consider the branch in which all $t=\mathrm{poly}(n)$ gadget measurements return zero. No conditional $S$ corrections are then needed, so the ancilla measurements may be deferred to the end. This branch has known probability $2^{-t}$, and conditioned on it the remaining output is exactly that of the original universal circuit.

The assumed simulator applies with $K=t+1$: ask it for the joint probabilitiesUsing polynomially many bits of requested precision, computeThe usual bounded-error gap separates yes instances from no instances, so this conditional probability decides the language deterministically in polynomial time. Hence $\mathrm{BQP}\subseteq \mathrm{P}$. The reverse inclusion is immediate because a quantum computer can implement classical deterministic computation, and therefore