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

The hidden subgroup problem for a group $G$ is specified by an oracle $f:G\to S$ that hides an unknown subgroup $H\le G$: it is constant on each left coset of $H$ and takes distinct values on distinct cosets. The task is to determine $H$, usually by finding a generating set for it.

A shift-invariant basis is a common eigenbasis of all cyclic shift operators $U(\gamma )$. For the displayed Fourier states, orthonormality follows from the root-of-unity filter:There are $N$ vectors in this orthonormal set in the $N$-dimensional Hilbert space, so they form a basis. Reindexing the finite sum givesThus every $|{\xi }_{\alpha }⟩$ is simultaneously an eigenvector of every shift, with eigenvalue ${\omega }^{\alpha \gamma }$ for $U(\gamma )$.

For each fixed $\alpha$, right multiplication by $x^{-\alpha }$ is a bijection of $G$, whose inverse is right multiplication by $x^{\alpha }$. Therefore $D_x$ permutes the displayed orthonormal basis of the tensor-product space. It is consequently a unitary operator, with

Write $x=g^{\eta }$. Applying $D_x$ and then changing the summation variable from $k$ to $\ell =k-\alpha \eta$ givesHence this state is an eigenvector of $D_x$ with eigenvalue $\boxed{{\omega }^{\alpha \beta \eta }}$.

Using the conventionpart (ii) applies the extra phase ${\omega }^{j\beta \eta }$ to term $j$. The resulting first register is the quantum Fourier transform of $|\alpha +\beta \eta \mathrm{mod}N⟩$. Applying its inverse therefore produces

Choose $\alpha =0$ and prepare $|{\chi }_1⟩$. The circuit from part (iii) returnsso a quantum measurement in the computational basis of the first register reveals the discrete logarithm $\eta$ exactly. More generally, any $\beta$ that is invertible modulo $N$ returns $\beta \eta \mathrm{mod}N$, from which $\eta$ follows by multiplication by the modular inverse of $\beta$.

Let ${\Pi }_{\mathcal{G}}$ be the orthogonal projection onto the good linear subspace and writewhere the two displayed states are normalized projections into $\mathcal{G}$ and ${\mathcal{G}}^{\perp }$. Define the reflectionsThe amplitude amplification iterate $Q=R_{\psi }{R}_G$ preserves the good-bad plane, and its $k$th iterate satisfiesThus repeated reflections rotate amplitude toward the good subspace, reaching constant success probability after $O(1/\sin \theta )$ iterations.

In the ordered orthonormal basisof $\mathcal{S}$, the Pauli Z gate acts asIt fixes the line $|g{⟩}^{\perp }\cap \mathcal{S}$ and negates $|g⟩$, so it is the reflection in a hyperplane orthogonal to the good state.

Set $|\Psi ⟩=U|0^m⟩$. Unitary conjugation givesThe operator negates $|\Psi ⟩$ and fixes every vector in $\mathcal{S}$ orthogonal to it. It is therefore the reflection in a hyperplane whose normal is $|\Psi ⟩$.

Put $\sqrt{p}=\sin \theta$ and $\sqrt{1-p}=\cos \theta$, where $0<\theta <\pi /2$. In the ordered basis $(|b⟩,|g⟩)$, the product of the two reflections isThe leading minus sign is a physically irrelevant global phase. The remaining rotation matrix rotates the good-bad plane through $2\theta$, whereEquivalently, one iterate changes the initial angle $\theta$ to $3\theta$.

Attach a quantum ancilla prepared with amplitudeon $|1⟩$; this is possible because $p>1/4$. Mark a state as good only when both the original success qubit and this ancilla equal one. The enlarged state's good probability is $p{c}^2=1/4$, so its good amplitude is $1/2=\sin (\pi /6)$. One amplitude amplification iteration rotates the angle from $\pi /6$ to $3\pi /6=\pi /2$. It therefore prepares $|{\psi }_1⟩$ exactly, after which the flag and ancillary qubits may be discarded. This is an instance of exact amplitude amplification.

The spectral norm of an operator $O$ is the induced operator normEvery Pauli X gate $X_i$ is unitary, so $\Vert X_i\Vert =1$. The triangle inequality for the norm therefore givesIn fact equality holds, as the product of $+1$ eigenvectors of the $X_i$ has eigenvalue $n$ under $J_X$.

The operators $X_i$ act on different qubits and therefore commute, soSince $X=HZH$,The scalar $e^{-it}$ is a global phase. Thus each factor uses two Hadamard gates and one phase gate, and applying the factors in parallel or sequentially gives an exact quantum circuit of $\boxed{3n}$ elementary gates.

Each summand of $J_X$ acts on one qubit, while each summand $Z_i{Z}_j$ of $J_Z$ acts on two. Therefore $J=J_X+J_Z$ is a 2-local Hamiltonian. We haveSplit $t$ into $r$ steps of length $\delta =t/r$ and use the second-order product formulaFor one step, $\Lambda =O(\delta n^2)$ in the stated estimate, so the spectral-norm error is $O({\delta }^3{n}^6)$. The error bound for a product of unitary operators makes the total errorIt is therefore enough to choosewith $r$ also large enough that the small-step estimate applies.

All $Z_i{Z}_j$ terms commute. A factor $e^{-i\delta Z_i{Z}_j}$ uses a constant-size circuit of two controlled-NOT gates and one phase gate, up to a global phase, so one product-formula step costs $O(n^2)$ gates. The complete Hamiltonian simulation consequently has size

First construct a controlled unitary gate from the uncontrolled oracle. Keep the supplied $|v_0⟩$ in a reference register. Controlled on an extra qubit, swap the data and reference registers, query $U$ on the register that contains $|v_0⟩$ in one branch, and swap back. Because $U|v_0⟩=|v_0⟩$, that branch is unchanged, while the other branch acquires $U$ on the data. Reversing the control convention with Pauli X gates gives controlled-$U$. The reference state is returned unchanged, and each use costs one query to $U$ and $O(n)$ controlled-SWAP gates.

Expand $|b⟩={\sum }_j{b}_j|v_j⟩$ in an eigenbasis of $U$. Exact quantum phase estimation with an $m$-qubit phase register producesApply the available phase gates, controlled by the corresponding bits of $c_j$, to multiply branch $j$ byThen reverse phase estimation. Although no $U^{†}$ oracle was supplied, every eigenvalue obeys ${\lambda }_j^{2^m}=1$, so $U^{-q}=U^{2^m-q}$. The inverse controlled powers can therefore be implemented with forward calls to $U$. Since $2^m=\mathrm{poly}(n)$, phase estimation and its inverse use only $\mathrm{poly}(n)$ queries. The phase register returns to $|0^m⟩$, while the data register isAs a direct check, the same spectral promise implies $U^{†}=U^{2^m-1}$.

The HHL algorithm requires coherent, efficient and repeatable preparation of the normalized state $|b⟩$, normally through a known preparation circuit and its inverse; possession of a single unknown physical specimen does not supply that access. The component of $b$ on any discarded or unresolved small-eigenvalue subspace must also be negligible. Here $U$ is a unitary operator, so it is invertible and all its singular values equal one, giving condition number $\kappa =1$.

Standard HHL is stated for a Hermitian matrix with an efficient sparse-access or block encoding oracle. A non-Hermitian $U$ can be embedded in the Hermitian block matrixpart (a) supplies efficient access to $U^{†}$. With inverse-polynomial target precision, $m=O(\log n)$ phase bits, and an efficient preparation oracle for $|b⟩$, the runtime is $\mathrm{poly}(n)$. The output is the normalized quantum state proportional to the solution $x$, rather than a classical list of all its amplitudes.

Implement the assumed efficient classical algorithm for $x\mapsto {\theta }_x$ as a reversible circuit. On input $|x⟩|0^s⟩$, it computes an $O(m)$-bit binary expansion of the angle in a work register using $\mathrm{poly}(m)$ Toffoli gates and elementary reversible gates. Write the computed angle as a sum of binary-weighted angles. For each angle bit, apply the corresponding controlled single-qubit $R_y$ rotation to the target. These rotations have the same axis, so their angles add and produceFinally apply uncomputation to erase the work register. Each Toffoli gate and controlled rotation has a constant-size decomposition into one- and two-qubit gates when arbitrary one-qubit rotations are available. Ignoring the stipulated precision costs, the resulting circuit has size $\mathrm{poly}(m)$ and returns every quantum ancilla to zero.