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

For coprime integers $\alpha ,N$, the multiplicative order is the smallest positive exponentIt exists because multiplication by $\alpha$ is an element of the finite group of units modulo an integer. For the example, the successive residues areNone of the first three is one, so the order is four.

The factor extraction from an even modular order uses the factorization ${\alpha }^r-1=({\alpha }^{r/2}-1)({\alpha }^{r/2}+1)$. If the multiplicative order $r$ is even, put $z={\alpha }^{r/2}\mathrm{mod}N$. Minimality of the multiplicative order excludes $z=1$; we also require $z\ne -1(\mathrm{mod}N)$. Thus $z^2\equiv 1(\mathrm{mod}N)$ is a nontrivial square root of one. Neither $z-1$ nor $z+1$ is divisible by all of $N$. If either were coprime to $N$, its inverse modulo $N$, applied to $(z-1)(z+1)\equiv 0$, would make the other divisible by $N$, a contradiction. Hence the greatest common divisorsare proper nontrivial factors. For odd $N$, $(z-1)$ and $(z+1)$ have no common prime divisor of $N$, so these two divisors are complementary. If the initial $\alpha$ is not coprime to $N$, a proper $\gcd (\alpha ,N)$ already supplies a factor without quantum order finding.

For $N=15$ and $\alpha =7$, $r=4$ and $z=7^2\mathrm{mod}15=4$, which is neither $1$ nor $14$. The factors areThe necessary conditions for this order-based reduction are a unit $\alpha \mathrm{mod}N$, even true multiplicative order, and ${\alpha }^{r/2}\not\equiv -1(\mathrm{mod}N)$.

Let $L=\lceil {\log }_{2}N\rceil$. In the Shor algorithm, first use classical arithmetic to deal with even $N$ and perfect powers, and to reject prime inputs. Perfect-power recognition and primality testing have polynomial-time classical algorithms. Factoring a perfect power $b^k$, with $b,k>1$, already gives a nontrivial factor $b$. We may therefore consider an odd composite $N$ with at least two distinct prime factors.

Choose $\alpha$ uniformly from $1<\alpha <N$ and compute its greatest common divisor with $N$ using the Euclidean algorithm. A proper nontrivial divisor ends the computation. Otherwise $\alpha$ is a unit, and the remaining task is quantum order finding. SetPrepare a uniform quantum superposition in a $t$-qubit register and use quantum modular exponentiation in a second register to obtainRepeated squaring and reversible modular multiplication implement this step with polynomially many quantum gates in $L$. Apply the inverse quantum Fourier transform to the first register and perform a quantum measurement in the computational basis, obtaining $j$. Measuring the second register first, and Fourier-transforming the resulting periodic coset, gives the same distribution of $j$.

Here is a quantitative quantum Fourier sampling bound for order finding. If $r={\mathrm{ord}}_N(\alpha )$, multiplication by $\alpha$ cycles its $r$ orbit states. The Fourier eigenstates of that cycle have eigenvalues $e^{2\pi is/r}$, and the initial state $|1⟩$ has squared overlap $1/r$ with each, for $0\le s<r$. ThereforeConditioned on a particular eigenphase $s/r$, its nearest integer outcome $j_s$ obeys $|j_s/Q-s/r|\le 1/(2Q)$ and has probability at least $4/{\pi }^2$. Indeed the absolute amplitude is $|\sin (\pi Q\delta )/(Q\sin (\pi \delta ))|$, where $\delta =s/r-j_s/Q$. For $|Q\delta |\le 1/2$, the numerator is at least $2Q|\delta |$ and the denominator at most $\pi Q|\delta |$; the limiting value at $\delta =0$ is one.

If $\gcd (s,r)=1$, the fraction $s/r$ is reduced, and $r<N$ givesUse continued-fraction recovery in quantum order finding. The relevant approximation theorem says that reduced fractions satisfying $|a/b-p/q|<1/(2q^2)$ are continued fraction convergents of $a/b$. For an input rational of $O(L)$ digits, their $O(L)$ candidates can be enumerated classically in $O(L^3)$ time, and their denominators are at most the reduced input denominator. This is the supplied continued-fraction result; discard candidate denominators exceeding $N$. A zero measurement is treated as a failed order-finding sample.

For each remaining even candidate denominator $q$, compute $z={\alpha }^{q/2}\mathrm{mod}N$ by repeated squaring, and try $\gcd (z-1,N)$ and $\gcd (z+1,N)$. Return only a divisor $d$ with $1<d<N$; otherwise repeat the quantum sample or choose another $\alpha$. This candidate-denominator gcd post-processing cannot return an incorrect factor, since its output is checked directly. When the recovered denominator is the true even multiplicative order and the square root of one is nontrivial, part (i) guarantees success. Checking ${\alpha }^q\equiv 1(\mathrm{mod}N)$ before trying the gcds is also a valid, more restrictive convention; the single-run distinction matters in part (iii).

Two further standard quantitative facts explain why repetitions remain efficient. First, for a uniformly chosen unit modulo an odd integer with at least two distinct prime divisors, the probability of a useful unit in Shor factorization is at least $1/2$: its true multiplicative order is even and ${\alpha }^{r/2}\not\equiv -1(\mathrm{mod}N)$. To see the source of this bound, the Chinese remainder theorem for unit groups makes the prime-power components independent. Each odd-prime-power unit group is cyclic. If its 2-primary order is $2^v$, the probability of the largest possible value of $v$ is $1/2$, and the probability of any specified smaller value is at most $1/2$. Failure requires all components to have the same $v$: either all zero, making $r$ odd, or all the same positive value, making the halfway power $-1$ in every component. Conditioning on one component, the chance another component matches it is at most $1/2$, so total failure is at most $1/2$.

Second, the fraction of phase numerators coprime to $r$ is $\phi (r)/r$, where $\phi$ is the Euler totient function. The elementary totient-ratio lower bound suffices: if the distinct prime divisors are $p_1<\cdots <p_k$, then $p_j\ge j+1$ and $k\le {\log }_{2}r$. The totient product formula therefore givesThus for a good $\alpha$, the probability of sampling a coprime phase numerator with the required accuracy is at least $(4/{\pi }^2)\phi (r)/r$. This is inverse-polynomial in the input length, so polynomially many repetitions achieve any fixed success probability. The quantum Fourier transform uses $O(t^2)$ elementary rotations and Hadamard gates in the ideal gate description, and the other quantum and classical stages are polynomial in $L$.

The reduction is therefore polynomial in the bit length:A small denominator need not itself be the true multiplicative order; verification of the final factor is essential, and no guarantee is claimed for every individual sample.

Here the true multiplicative order is four, and it divides every power-of-two Fourier-register size $Q\ge 4$, including the $Q=256$ choice from part (ii). A second-register measurement produces one of the four periodic cosetsIts quantum Fourier transform has nonzero amplitudes only at $j=0,Q/4,Q/2,3Q/4$, and each has squared modulus $1/4$. The inverse transform only changes phases or permutes these four labels. Hence the measured ratios $0,1/4,1/2,3/4$ are equally likely.

For $1/4$ or $3/4$, continued-fraction recovery in quantum order finding returns denominator four. Part (i) then gives factors three and five. For $1/2$, the reduced denominator is two. Although two is not a period, the candidate-denominator gcd post-processing in part (ii) still gives a factor:The zero outcome produces no useful even candidate and the run fails. For the factor-extraction procedure specified above, three of the four outcomes succeed:There is an important convention behind this answer. A version that rejects a candidate unless $7^q\equiv 1(\mathrm{mod}15)$ before attempting any gcd rejects $q=2$, since $7^2\equiv 4$. Under that validated-period convention only the two odd-numerator phases succeed, givingThus the probability of recovering the true multiplicative order is $1/2$, whereas the probability of finding a factor with direct gcd post-processing is $3/4$. The printed question does not specify this classical post-processing detail; stating it avoids identifying these two different events.

Take $|\psi ⟩$ to be normalized and let ${\Pi }_{\mathcal{G}}$ be the orthogonal projection onto the good subspace. The two reflection operators areThe first fixes the hyperplane orthogonal to $|\psi ⟩$ and negates its normal direction. The second fixes ${\mathcal{G}}^{\perp }$ and negates $\mathcal{G}$. Both are Hermitian operators and unitary operators, since their defining projectors square to themselves. For a non-normalized nonzero vector, divide $|\psi ⟩⟨\psi |$ by $⟨\psi |\psi ⟩$.

Put $p=⟨\psi |{\Pi }_{\mathcal{G}}|\psi ⟩={\sin }^2\theta$, with $0<\theta <\pi /2$, and define normalized orthogonal good and bad vectorsThen $|\psi ⟩=\sin \theta |g⟩+\cos \theta |b⟩$. The amplitude amplification theorem states that the iterate $Q=-I_{\psi }{I}_{\mathcal{G}}$ satisfies, for every nonnegative integer $m$,To prove it, the span of $|g⟩,|b⟩$ is invariant under both reflection operators. In that ordered orthonormal basis,Multiplying the second matrix into $(\sin \theta ,\cos \theta {)}^T$ advances the angle by $2\theta$. Induction proves the formula, and projecting onto $\mathcal{G}$ gives $p_m$. The minus sign in $Q$ is just a global phase choice, but it makes the displayed state formula exact.

If $p$ is known, choose $m$ nearest to $\pi /(4\theta )-1/2$, with $m\ge 0$. The final angle is within $\theta$ of $\pi /2$, so $p_m\ge {\cos }^2\theta =1-p$. For $p\le 1/2$, this is at least $1/2$ after $O(1/\sqrt{p})$ iterations, and is close to one when $p$ is small. For $p>1/2$, measuring the initial state already has success above $1/2$. Repeated independent attempts with a success test give any fixed desired success probability. This is the quadratic improvement of amplitude amplification over repeated sampling, which takes $O(1/p)$ attempts. At $p=0$ there is no good component to amplify, and at $p=1$ the initial state is already entirely good; these endpoint cases do not require the undefined normalized component vectors.

Prepare an ancillary qubit inIt can be prepared from $|0⟩$ by an $X$ operation followed by a Hadamard gate, independently of $g$. One call to the Boolean quantum oracle then gives quantum phase kickback:The data state receives a minus sign precisely on the basis vectors spanning $\mathcal{G}$, while the ancilla remains unchanged and unentangled. One oracle call realizes the reflection. By linearity it is the marked-state phase oraclewith one oracle call. The ancillary preparation and its optional inverse use only fixed operations, so no additional knowledge of $g$ is needed.

Follow the printed examples by counting positive squares, so zero is not marked. For $N\ge 2$, the marked output set isA one-to-one map from the finite set $[N]$ to itself is a permutation, so exactly $K$ inputs have outputs in $S$. In the uniform quantum superposition $|s⟩=N^{-1/2}{\sum }_x|x⟩$, the initial good probability is therefore $p=K/N$. For permutation-preimage quantum search, this known marked density under a permutation is $\Theta (N^{-1/2})$.

Define the efficiently computable predicate $h(y)$ to be one if and only if $y$ is a positive square. The assumed Boolean quantum oracle for $h$, acting on $y$ and a $|-⟩$ ancilla, implements its diagonal sign operation $D_h|y⟩=(-1{)}^{h(y)}|y⟩$. Compute the modular-addition quantum oracle into a zero output register, apply this sign operation, and uncompute:This implements $I_{\mathcal{G}}$ for $\mathcal{G}=\mathrm{span}\{|x⟩:f(x)\in S\}$, with the work registers clean. Only forward calls to $U_f$ were promised, but its inverse costs one such call: if $J|y⟩=|-y\mathrm{mod}N⟩$ on the second register, thenIndeed the output addition is changed into subtraction. Thus each marked reflection costs exactly two queries to $U_f$; all other operations used here are independent of the unknown $f$.

Use the amplitude amplification theorem with $|\psi ⟩=|s⟩$, whose reflection is allowed by the assumptions. With $\theta =\arcsin \sqrt{K/N}$, choose $m$ nearest to $\pi /(4\theta )-1/2$. Here $p\le 1/2$ for every $N\ge 2$, so a trial succeeds with probability at least $1/2$. AlsoMeasure $x$ and use one additional $U_f$ query to evaluate and check $f(x)$. On failure, restart with fresh registers. Four independent trials have failure probability at most $2^{-4}$, so the required confidence and query bound areThis is an upper bound on quantum query complexity, not a claim that arbitrary reflections or every classical gate have constant cost. Including zero as a square would change $K$ to $K+1$ without changing the asymptotic bound. With the printed positive-square interpretation, $N=1$ has no valid output and no algorithm can satisfy the success requirement; the intended asymptotic task necessarily has $N\ge 2$.

Store a tensor-product element of the Pauli group asThe phases of the original single-qubit factors can all be accumulated into $i^s$. This binary phase representation of a Pauli string uses $2n+2$ bits. It retains phases, which must not be dropped when computing probabilities later.

For the conjugation convention $U^{†}PU$ in the question, direct multiplication of the two-by-two matrices givesandThese backward Pauli updates for Hadamard and phase gates use $S^{†}PS$, not $SP{S}^{†}$. On the affected line $j$, the updates areAll phases are reduced modulo four and the updates use the old bits.

For a Controlled-Z gate on lines $j,k$, its diagonal action givesFor the controlled-Z update in the binary phase representation, conjugation respects products, so these determine the rule for every Pauli operator on those lines. In the chosen ordered $XZ$ convention it isThe phase arises when a newly introduced $Z_k$ is moved past $X_k$. For instance $X_j{X}_k$ becomes $-X_j{Z}_j{X}_k{Z}_k$, so this sign matters.

The untouched factors are unchanged. Each Clifford operation therefore needs only a fixed number of local bit updates; reconstructing the requested full list takes $O(n)$ time. Put the final phase into the first factor, which is permitted because the single-qubit Pauli group includes all multiples by $\pm 1,\pm i$. The classical cost is polynomial, despite the exponentially large matrix of the operation on the full state space.

The computational-basis projectors on the first qubit areThe Pauli Z gate acts as $+1$ on the first subspace and $-1$ on the second, so $Z_1={\Pi }_0-{\Pi }_1$. By the Born rule, $p_b=⟨\psi |{\Pi }_b|\psi ⟩$. Therefore the expectation determines the output probabilities:The normalization supplies $p_0+p_1=1$; no product-state assumption is needed for this identity.

Write $|a⟩={⨂}_j|a_j⟩$. Instead of storing the output vector, use Heisenberg propagation of a Pauli observable through a Clifford circuit:Initialize the compact Pauli group representation at $Z_1$ and conjugate successively by $U_N,U_{N-1},\dots ,U_1$, in that order, using $P\mapsto U_j^{†}P{U}_j$. This giveswith $O(N+n)$ local-update work and $O(n)$ storage. The resulting Pauli operator is Hermitian, so we can express it as $P=\eta {⨂}_j{\sigma }_j$, where $\eta \in \{+1,-1\}$ and each ${\sigma }_j$ is $I,X,Y$ or $Z$. Any factors $XZ$ in the representation from part (i) are converted using $XZ=-iY$, with their phases absorbed into $\eta$.

The product state input now makes the expectation factorize:Each factor is a two-by-two matrix calculation. More explicitly, for $|a_j⟩={\alpha }_j|0⟩+{\beta }_j|1⟩$, the three nontrivial expectations are $2\mathrm{Re}({\overline{\alpha }}_j{\beta }_j)$, $2\mathrm{Im}({\overline{\alpha }}_j{\beta }_j)$, and $|{\alpha }_j{|}^2-|{\beta }_j{|}^2$ for $X,Y,Z$, respectively.

Thus this single-output process has a strong classical simulation in polynomial time, even when the individual input states are not stabilizer states. As usual, the given state identities must provide efficiently computable amplitudes. With finite-precision inputs, each factor can be evaluated to error $\delta /n$ and its approximation clipped to $[-1,1]$ to obtain the final expectation to error at most $\delta$, because all factors lie in $[-1,1]$. The required extra precision is only $O(\log (n/\delta ))$ bits. Exact evaluation applies when the input descriptions support exact arithmetic. This avoids silently assigning a finite exact-computation cost to arbitrary unspecified real numbers.

Once the probabilities are known, a classical randomized computation can reproduce this measured bit. The argument concerns the specified one-qubit output; it does not assert that every joint measurement distribution for arbitrary product inputs can be simulated by this same single-observable calculation.

Use GHZ preparation with Hadamard and controlled-Z gates for $n\ge 2$. Apply a Hadamard gate to the first qubit, then a controlled-NOT gate from that qubit to each of the other $n-1$ qubits. Every controlled-NOT can be written in the allowed gate set asIndeed conjugating the target $Z$ by $H$ makes the controlled phase into a controlled $X$. The rightmost gate acts first. Consequently the Clifford circuit uses $1+3(n-1)$ allowed gates and givesFor every chosen qubit $j$, tracing out the other qubits yields ${\rho }_j=\frac{1}{2}(|0⟩⟨0|+|1⟩⟨1|)=I/2$. Equivalently, across that qubit versus the rest, the displayed state is a Schmidt decomposition with two nonzero coefficients $1/\sqrt{2}$. It is therefore entangled across every such bipartition.

Entanglement does not prevent the polynomial single-output simulation from part (iii). The simulation follows the measured observable rather than claiming that the intermediate states remain product states. When $n=1$, there is no remaining subsystem and the requested entanglement is impossible; the construction and claim require $n\ge 2$.

The spectral norm is the induced Euclidean operator norm:It is the largest singular value. From the definition, multiplying on either side by a unitary operator leaves the norm unchanged: right multiplication permutes the unit sphere of possible inputs, and left multiplication preserves output lengths. In particular every unitary operator has norm one.

For unitary product telescoping, replace the factors one at a time. With empty products interpreted as the identity,All cross terms cancel. By the triangle inequality and unitary invariance of the spectral norm,This bound is independent of the dimension and does not assume that any of the factors commute.

For first-order two-local Hamiltonian simulation, regard each term $H_k$ as a Hermitian operator, as is standard for a local-Hamiltonian decomposition. The Lie-Trotter product formula for bounded operators statesin operator norm; the reversed factor ordering is just as valid as the displayed one. Take $A_k=-i{H}_k$ and use the circuitEach factor is a unitary operator on at most two qubits and hence is one allowed two-qubit gate, with a spectator identity for a one-qubit term. The factors in the rightmost part of each written product act first. Merely quoting the limit would not establish the requested rate, so we give a quantitative error bound.

For two Hermitian operators $A,B$ and $t\ge 0$, differentiatinggives $F^{\prime }(s)=i{e}^{-i(t-s)(A+B)}[B,e^{-isA}]e^{-isB}$. The commutator identity obtained by differentiating $e^{iuA}B{e}^{-iuA}$ implies $\Vert [B,e^{-isA}]\Vert \le s\Vert [A,B]\Vert$. Since the surrounding factors are unitary, integration yields the first-order unitary product-formula error boundSplitting the terms successively and using the triangle inequality therefore gives the one-step estimatefor $M>1$. Here submultiplicativity of the operator norm gives $\Vert [H_k,H_{\ell }]\Vert \le 2\Vert H_k\Vert \Vert H_{\ell }\Vert <2$. The ordering chosen for the products changes the sign of local commutators, not this norm bound. Applying part (i) to the $r$ steps givesChoose $r=\max (1,\lceil M(M-1)/(2ϵ)\rceil )$. For $M>1$ the error is strictly below $ϵ$; $M=1$ is exact already with $r=1$. The quantum circuit contains $Mr$ two-qubit gates. A sufficient gate count isThus the worst-case polynomial degree in this first-order bound is six. Terms with disjoint supports commute and may improve the count in particular decompositions, but the stated assumptions alone suffice for this bound, without a further sparsity or bounded-degree condition. The requested gate model allows arbitrary two-qubit unitaries, so no additional compilation error is incurred here.