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

The hidden subgroup problem is to recover a subgroup $K\le G$, usually by giving generators of a group, from an oracle machine providing $f:G\to Y$ with the promiseThus $f$ is constant on each left coset and distinguishes different left cosets. The input includes an effective representation of elements of the group and access to the group operations; the desired efficiency is measured against the number of bits describing an element, rather than necessarily against $|G|$.

Write the finite abelian group additively. Its group shift operator isThese unitary operators form the regular representation and commute. The representation-theoretic facts we use are that every irreducible representation of a finite abelian group is one-dimensional, there are $|G|$ such characters of a representation, and their character orthogonality gives an orthonormal basis of functions on $G$. Each linear character here is a group homomorphism $\chi :G\to U(1)$, with $|\chi (g)|=1$.

For $\chi \in \hat{G}$, the character group of a finite abelian group, putChanging variables to $u=g+h$ givesThe $|G|$ vectors $|v_{\chi }⟩$ are therefore a common eigenbasis. Using $\chi (g)$ instead of its complex conjugate in their definition reverses every eigenphase; this is merely the quantum Fourier transform sign convention.

Measure the coset state in the common eigenbasis $\{|v_{\chi }⟩\}$ of the group shift operators. Its overlap isThe character-sum cancellation lemma makes this sum $|K|$ when $\chi$ is trivial on $K$, and zero otherwise. Hence, with $K^{\perp }$ the annihilator of a subgroup of a finite abelian group,Since $|K^{\perp }|=|G|/|K|$, this is the uniform distribution on a finite set $K^{\perp }$. The factor $\chi (g_0)$ has modulus one, so the distribution is independent of $g_0$. This is abelian hidden-subgroup Fourier sampling.

The distinct values in one period imply that $r$ is the least positive period, $r\mid N$, and $|Y|=r$. Write $x=j+tr$, where $0\le j<r$ and $0\le t<N/r$. Use the positive-exponent quantum Fourier transform convention already used in the concept article. The amplitude of first-register value $y$ isBy the root-of-unity filter, the inner sum vanishes unless $y=mN/r$. DefineThe distinct $f(j)$ give an orthonormal basis of the second register, and the transformed state isReindexing $j+l$ modulo $r$ showsConsequently measurement in this common eigenbasis returns each $m$ with probability $1/r$; the corresponding eigenvalue of $U_1$ is a uniformly sampled $r$th root of unity. A single measured phase $-m/r$ reveals the denominator $r/\gcd (m,r)$, which need not be $r$. Repeated samples permit exact period recovery from a Fourier sample, for example by taking the least common multiple of their reduced denominators. The simultaneous eigenspaces and their probabilities depend on $r$, not on the particular labels $f(j)$.

Let $\Pi$ be the orthogonal projection onto the good linear subspace $\mathcal{G}$, and let $|\psi ⟩$ be a prepared unit vector with $p=⟨\psi |\Pi |\psi ⟩$. For $0<p<1$, defineThe amplitude amplification theorem states that, if the reflection operators about the initial state and the good subspace can be implemented, the iterationsatisfiesTo prove it, the two reflections preserve the linear span of $|g⟩,|b⟩$. In this ordered orthonormal basis, direct multiplication givesMultiplying this rotation matrix by $(\sin \alpha ,\cos \alpha {)}^T$ replaces $\alpha$ by $\alpha +2\theta$, proving the formula by mathematical induction.

For known $0<p\le 1/2$, choose $j$ to be a nearest nonnegative integer to $\pi /(4\theta )-1/2$. Then $|(2j+1)\theta -\pi /2|\le \theta$, so measurement finds the good subspace with probability at least $1-p$, using $O(p^{-1/2})$ iterations. For $p>1/2$, measurement of the initial state already has constant success probability. If $p=1$ success is certain; if $p=0$ these reflections cannot create any good component. If $|\psi ⟩=A|0⟩$, the initial-state reflection is $A(2|0⟩⟨0|-I)A^{†}$, implemented using quantum state preparation and its inverse quantum circuit.

The map $x\mapsto -x(\mathrm{mod}K)$ is a bijection and an involution, so its permutation matrix satisfiesIn particular $S^{†}S=I$, which proves that $S$ is a unitary operator. Equivalently, it permutes the computational basis and therefore preserves every inner product.

Applying the two modular-addition quantum oracles consecutively adds $h(x)+r(x)=0(\mathrm{mod}M)$ to the answer register. ThusLet $S_M|y⟩=|-y(\mathrm{mod}M)⟩$. Applying $I\otimes S_M$, then $U_h$, then $I\otimes S_M$ givesThereforeusing one query and two unitary operators independent of $h$. This is modular-oracle inversion by negation.

Let the known phase gate on the answer register bewhere the comparison uses ordinary integers, not modular arithmetic. A reversible circuit computes the predicate, applies a Pauli Z gate to its flag, then performs uncomputation.

The compute-phase-uncompute construction now givesUse modular-oracle inversion by negation to realize the last operation with one further $U_f$ query. Exactly two oracle queries implement $I_g$, returning the answer register and comparison workspace to their initial states.

An injective self-map of the finite set ${\mathbb{Z}}_N$ is a bijection. For sufficiently large $N$, exactlyoutputs satisfy the integer comparison, so there are exactly $m$ good inputs. Prepare the uniform superposition state $|\psi ⟩=N^{-1/2}{\sum }_x|x⟩$, whose good probability isUse the phase oracle from the previous part and the reflection $2|\psi ⟩⟨\psi |-I$. The amplitude amplification theorem requires $O(p^{-1/2})$ iterations; each uses two $U_f$ queries, while the state preparation and its reflection are independent of $f$. With the nearest-integer iteration count from that theorem, the failure probability is at most $p$, tending to zero. Therefore the success probability eventually exceeds $0.9$, withThis is a bound on quantum query complexity; implementation costs of the known gates are not counted as oracle queries.

The spectral norm is the operator norm induced by the Euclidean norm:The Pauli operators $X_1$ and $Z_2$ act on different qubits, and each is a unitary operator. Their product is therefore unitary and preserves the norm of every vector. Hence

For finite-dimensional matrices $A_1,\dots ,A_m$, the Lie-Trotter product formula stateswhere convergence is in operator norm. In particular, for Hermitian matrices $H_j$, set $A_j=-i{H}_j$ to obtain a product of unitary operators approximating $e^{-it{\sum }_j{H}_j}$.

The printed sum contains $Z_n$ although the stated labels end at $n-1$. We use the natural periodic convention $Z_n=Z_0$, with $n\ge 3$. If an open chain was intended, omitting the final term gives the same asymptotic bound.

Set $H_j=X_{j-1}{Z}_j$, with indices modulo $n$, and implement the product-formula Hamiltonian simulationEach factor acts on two qubits, so it is a two-qubit unitary operator. More explicitly, if $a=j-1$, $b=j$, and $C_{a\to b}$ is a controlled-NOT gate,where ${\mathsf{H}}_a$ is a Hadamard gate. This gives a constant number of one-qubit and two-qubit gates per factor; one-qubit gates can also be viewed as two-qubit gates tensored with the identity.

The spectral norm obeys the triangle inequality, submultiplicativity of the operator norm, and invariance under multiplication by unitary operators. In particular, the telescoping bound for products of operators gives $\Vert V^k-W^k\Vert \le k\Vert V-W\Vert$ for unitary $V,W$. The first-order unitary product-formula error bound consequently yieldsOnly neighboring terms can have a nonzero commutator, because all other supports are disjoint. There are $n$ neighboring unordered pairs, and $\Vert [H_j,H_l]\Vert \le 2\Vert H_j\Vert \Vert H_l\Vert =2$. Thus $\Vert U-\tilde{U}\Vert \le n/k$. Choosing $k>n/\epsilon$ givesThe coarser bound that counts all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs also proves the often-used $O(n^3/\epsilon )$ construction. Locality improves that cubic estimate to the quadratic bound above; neither assertion is a lower bound on the best possible circuit.

Use a clean quantum ancilla and apply the quantum circuit $C$, then the Pauli Z gate on the ancilla, then the inverse quantum circuit $C^{†}$:This compute-phase-uncompute construction implements $A\otimes I$ on every input with the ancilla initially $|0⟩$, and by linearity on any superposition of those inputs. The action on ancilla-$|1⟩$ inputs need not coincide with $A\otimes I$; the question only requires the clean-ancilla subspace.

Since $A|x⟩=(-1{)}^{f(x)}|x⟩$, the spectral decomposition givesReplace the middle gate of the previous compute-phase-uncompute construction bya one-qubit rotation about the z-axis. ThenThe circuit uses the gates of $C$, their inverses, and one fixed rotation; it returns the quantum ancilla to $|0⟩$. The same construction implements $e^{itA}$ with middle gate $e^{itZ}$, an instance of simulation of a computable diagonal Hamiltonian.

The usual sufficient input promises for the HHL algorithm are efficient quantum state preparation of the nonzero vector $b$, efficient access to a sparse matrix $A$ with at most $\mathrm{poly}(n)$ nonzero entries per row, and a condition number $\kappa ={\lambda }_{\max }/{\lambda }_{\min }=\mathrm{poly}(n)$ after an efficiently known normalization. Both the positions and values of the nonzero matrix elements must be computable coherently in polynomial time. More generally, efficient Hamiltonian simulation can replace the sparsity promise. We assume $A$ is invertible; if zero eigenvalues occur, one must instead restrict $b$ to their orthogonal complement and specify the desired inverse on that support.

With $a={\lambda }_{\max }$ and a known bound $\kappa$, choose $c=a/\kappa \le {\lambda }_{\min }$. The HHL controlled reciprocal rotation then succeeds with probabilityThis is the required inverse-polynomial lower bound. In the usual approximate algorithm, inverse-polynomial requested error also gives polynomial runtime under these input promises. The original HHL paper states the dependence on sparsity, conditioning, and accuracy.

There is a qualification for a literally exact version. Representability of the eigenvalues in $n$ bits does not itself make exact quantum phase estimation efficient: using $e^{2\pi iA}$ requires controlled powers corresponding to evolution times as large as $2\pi 2^{n-1}$. Under the paper's idealization we may describe their exact action, but polynomial runtime for that exact circuit additionally requires efficient implementations of those controlled powers, or equivalent efficient exact spectral access. Assuming an operation executes exactly does not bound its cost. This distinction is recorded in cost of exact phase estimation on a dyadic spectrum.

Write the normalized input as $|b⟩={\sum }_j{\beta }_j|u_j⟩$, where $A|u_j⟩={\lambda }_j|u_j⟩$ and ${\lambda }_j>0$. Use a data register, an $n$-qubit eigenvalue register, and a flag quantum ancilla. Begin with $|b⟩|0^n⟩|0⟩$.

Apply exact quantum phase estimation to $e^{2\pi iA}$. Its controlled evolutions and inverse quantum Fourier transform produceApply the HHL controlled reciprocal rotation, with $0<c\le {\lambda }_{\min }$:The function of ${\ell }_j$ is computed by quantum arithmetic; the rotation is a quantum variable rotation. On a zero eigenvalue label with no input amplitude, define any unitary action, for example no rotation.

Run the inverse phase-estimation circuit. Because each amplitude multiplier depends only on ${\lambda }_j$, the eigenvalue register is reset to $|0^n⟩$ on both flag branches. Measuring the flag and conditioning on outcome one leavesThe successful unnormalized branch is $c{A}^{-1}|b⟩$, giving the probability in the preceding part. The operations independent of $A,b$ are the Hadamard gates preparing the phase register, the inverse quantum Fourier transform, the reversible reciprocal/angle arithmetic, the controlled fixed-angle rotations, and the final flag measurement. Uncomputation removes all arithmetic workspace; the $A$-dependent controlled evolutions and the $b$-dependent state-preparation circuit supply the input-specific operations.

Use a reversible circuit $T$ to compute an $L=O(n)$-bit representation of the angle into a workspace register, with all additional work bits retained:Write that representation as ${\theta }_x={\sum }_{l=1}^L{b}_l(x){\alpha }_l$, with known binary place values ${\alpha }_l$ (including the fixed scale and any integer bit). On the target, apply a controlled unitary gate $R_y(2{\alpha }_l)$ controlled by each angle bit $b_l$. Rotations about the same axis add their angles, so their product isFinally apply $T^{†}$ to perform uncomputation. The workspace returns to zero while the control register and rotated target remain unchanged; the construction works coherently on every superposition of $x$.

A polynomial time classical calculation has a polynomial-size reversible circuit with Toffoli gates, and each Toffoli gate has a constant-size decomposition into one-qubit and two-qubit gates. The $L$ controlled rotations are themselves two-qubit gates. Thus the total quantum circuit size is $\mathrm{poly}(n)$. This is the binary-angle implementation of a quantum variable rotation; the stipulated angle precision is understood.