Shor's Algorithm: Order Finding, Fourier Transforms and Continued Fractions

Problem 1 warmup

order of an element Chinese remainder theorem reduction of factoring to order-finding

Let $n$ be odd, composite and not a prime power, and let $x$ be an integer with $\gcd(x,n)=1$ . Write $r=\operatorname{ord}_n(x)$ for the least positive integer with $x^r\equiv 1 \pmod n$ . Say that $x$ succeeds if $r$ is even and $\gcd(x^{r/2}-1,\,n)$ is a divisor of $n$ other than $1$ and $n$ ; otherwise $x$ fails.

Throughout, $n=91=7\cdot 13$ .

(a) Compute $\operatorname{ord}_{91}(3)$ , $\operatorname{ord}_{91}(9)$ and $\operatorname{ord}_{91}(90)$ . For each of the three, say whether it succeeds, and if it does, exhibit the factor of $91$ obtained.

Hint 1 of 2
$3^6=729=8\cdot 91+1$ .

Hint 2 of 2
Two of the three fail, and they fail for different reasons.
(b) Prove that $x$ fails if and only if $r$ is odd or $x^{r/2}\equiv -1\pmod n$ . (Both directions; you will need that $n$ is odd for one of them.)

Hint 1 of 2
Factor $x^r-1=(x^{r/2}-1)(x^{r/2}+1)$ and ask what $\gcd(x^{r/2}-1,n)\in\{1,n\}$ would force.

Hint 2 of 2
For the converse, if $n\mid x^{r/2}+1$ , what can a common divisor of $n$ and $x^{r/2}-1$ divide?
(c) Determine exactly how many of the $72$ units $x$ modulo $91$ fail. (Your answer should be a specific integer; you may use that $(\mathbb{Z}/p)^{\times}$ is cyclic for $p$ prime.)

Hint 1 of 3
Use the Chinese remainder theorem to write $x\leftrightarrow(u,v)\in(\mathbb{Z}/7)^\times\times(\mathbb{Z}/13)^\times$ , and let $r_1,r_2$ be the orders of $u,v$ . How is $r$ built from $r_1,r_2$ ?

Hint 2 of 3
Let $e_i$ be the exponent of $2$ in $r_i$ . Show that $x$ fails exactly when $e_1=e_2$ : if $e_1<e_2$ show $x^{r/2}\equiv 1 \pmod 7$ while $x^{r/2}\equiv-1\pmod{13}$ .

Hint 3 of 3
In a cyclic group of order $12$ , count the elements whose order has $2$ -adic valuation $0,1,2$ respectively. Then take the appropriate inner product of the two count vectors.

Hint 1 of 1

Nothing here is quantum: this is the classical wrapper that turns a period into a factor.

Solution

(a) $3^6=729=8\cdot 91+1$ , and $3^1,3^2,3^3=27,3^4=81,3^5=61$ are all $\ne 1$ , so $\operatorname{ord}_{91}(3)=6$ . It is even, $3^3=27\not\equiv -1\equiv 90$ , and $\gcd(27-1,91)=\gcd(26,91)=13$ . So $x=3$ succeeds and yields the factor $13$ (and $91/13=7$ ).

$9=3^2$ has $9^3=729\equiv 1$ , and $9,81\ne 1$ , so $\operatorname{ord}_{91}(9)=3$ , which is odd: $x=9$ fails.

$90\equiv -1$ has order $2$ , and $90^{1}\equiv -1 \pmod{91}$ , so $\gcd(90-1,91)=\gcd(89,91)=1$ : $x=90$ fails.

(b) Suppose $r$ is even and $x^{r/2}\not\equiv -1$ . Put $y=x^{r/2}$ , so $n\mid (y-1)(y+1)$ and let $g=\gcd(y-1,n)$ . If $g=n$ then $x^{r/2}\equiv 1$ , contradicting the minimality of $r$ . If $g=1$ then $n\mid y+1$ (since $n$ divides $(y-1)(y+1)$ and is coprime to $y-1$ ), i.e. $x^{r/2}\equiv -1$ , contradiction. So $1<g<n$ and $x$ succeeds.

Conversely, if $r$ is odd then $r/2$ does not exist and $x$ fails by definition; and if $x^{r/2}\equiv -1$ , then any common divisor $t$ of $n$ and $y-1$ also divides $y+1$ (because $n\mid y+1$ ), hence divides $(y+1)-(y-1)=2$ ; as $n$ is odd, $t=1$ , so $\gcd(y-1,n)=1$ and $x$ fails.

(c) By CRT, choosing a unit $x$ mod $91$ is the same as choosing $u\in(\mathbb{Z}/7)^\times\cong\mathbb{Z}_6$ and $v\in(\mathbb{Z}/13)^\times\cong\mathbb{Z}_{12}$ independently. If $r_1,r_2$ are their orders then $r=\operatorname{lcm}(r_1,r_2)$ . Write $e_i=v_2(r_i)$ , so $v_2(r)=\max(e_1,e_2)$ .

If $e_1=e_2=e$ . If $e=0$ then $r$ is odd and $x$ fails. If $e\ge 1$ , then $v_2(r/2)=e-1<e=v_2(r_i)$ , so $r_i\nmid r/2$ while $r_i\mid r$ ; hence $x^{r/2}$ has order exactly $2$ modulo each prime, and in a cyclic group the unique element of order $2$ is $-1$ . So $x^{r/2}\equiv-1$ mod $7$ and mod $13$ , hence mod $91$ : $x$ fails.

If $e_1\ne e_2$ , say $e_1<e_2$ . Then $v_2(r/2)=e_2-1\ge e_1$ and the odd part of $r$ is divisible by the odd part of $r_1$ , so $r_1\mid r/2$ and $x^{r/2}\equiv 1 \pmod 7$ ; while as above $x^{r/2}\equiv -1 \pmod{13}$ . Thus $x^{r/2}\not\equiv\pm1 \pmod{91}$ and $r$ is even, so $x$ succeeds by (b).

So failures are exactly the pairs with $e_1=e_2$ . In $\mathbb{Z}_6$ the number of elements of order $d$ is $\varphi(d)$ : orders $1,2,3,6$ occur $1,1,2,2$ times, so $e_1=0$ for $1+2=3$ elements and $e_1=1$ for $1+2=3$ elements. In $\mathbb{Z}_{12}$ : orders $1,2,3,4,6,12$ occur $1,1,2,2,2,4$ times, so $e_2=0$ for $3$ elements, $e_2=1$ for $1+2=3$ , $e_2=2$ for $2+4=6$ .

Hence the number of failures is $3\cdot3+3\cdot3+0\cdot 6=18$ .

So exactly $18$ of the $72$ units fail: a random $x$ succeeds with probability $3/4$ , comfortably better than the general guarantee $1-2^{1-k}=1/2$ for $k=2$ prime factors. (Check: $x=3$ has $(e_1,e_2)=(1,0)$ , success; $x=9$ has $(0,0)$ and $x=90$ has $(1,1)$ , failures — matching (a).)

Problem 2 standard

quantum Fourier transform character orthogonality circuit construction periodic states

Fix $q=2^{\ell}$ and let $\omega=e^{2\pi i/q}$ . The quantum Fourier transform on $q$ points is the linear map $F$ on $\mathbb{C}^q$ (with basis $|0\rangle,\dots,|q-1\rangle$ ) defined by $F|a\rangle=\frac{1}{\sqrt q}\sum_{c=0}^{q-1}\omega^{ac}\,|c\rangle .$ We write $a=\sum_{j=0}^{\ell-1}a_j2^{j}$ for the binary expansion, and identify $|a\rangle$ with $|a_{\ell-1}\rangle\otimes\cdots\otimes|a_0\rangle$ .

(a) Show that $F$ is unitary.

Hint 1 of 2
Compute $\langle c'|F^{\dagger}F|c\rangle$ and reduce to evaluating $\sum_{a=0}^{q-1}\omega^{a(c-c')}$ .

Hint 2 of 2
Sum a geometric series; the ratio is $1$ exactly when $q\mid c-c'$ .
(b) Prove the identity $F|a\rangle=\bigotimes_{m=1}^{\ell}\frac{|0\rangle+e^{2\pi i a/2^{m}}|1\rangle}{\sqrt2},$ where the $m$ -th tensor factor carries the output bit $c_{\ell-m}$ . Deduce that $F$ (up to reversing the order of the output bits) can be implemented by $\ell$ one-qubit gates and $\ell(\ell-1)/2$ two-qubit gates, and say exactly which gates.

Hint 1 of 3
Write $c=\sum_k c_k2^k$ and split $\omega^{ac}=\prod_k e^{2\pi i a c_k/2^{\ell-k}}$ ; then the sum over all $c$ factorises.

Hint 2 of 3
Note that $e^{2\pi i a/2^{m}}$ depends only on $a \bmod 2^{m}$ , i.e. only on the bits $a_0,\dots,a_{m-1}$ .

Hint 3 of 3
The factor $e^{2\pi i a_{m-1}2^{m-1}/2^{m}}=(-1)^{a_{m-1}}$ is produced by a Hadamard gate on qubit $m-1$ ; each remaining factor $e^{2\pi i a_j 2^{j}/2^{m}}$ with $j<m-1$ is a phase $e^{2\pi i/2^{m-j}}$ applied conditionally on $a_j=1$ .
(c) Take $\ell=4$ , so $q=16$ , and let $|\chi\rangle=\tfrac12\big(|3\rangle+|7\rangle+|11\rangle+|15\rangle\big)$ . Compute $F|\chi\rangle$ and the resulting probability distribution of the measured value $c$ . Then do the general case: if $r\mid q$ , $0\le k<r$ , and $|\chi_{r,k}\rangle=\sqrt{r/q}\sum_{b=0}^{q/r-1}|br+k\rangle$ , determine the distribution of $c$ after applying $F$ and measuring. What does the offset $k$ do?

Hint 1 of 2
Pull the phase $\omega^{kc}$ out of the sum; what remains is a geometric series in $b$ with ratio $\omega^{rc}$ .

Hint 2 of 2
The series vanishes unless $rc\equiv 0 \pmod q$ , i.e. unless $c$ is a multiple of $q/r$ .

Hint 1 of 1

Every computation on this sheet reduces to summing a geometric series of roots of unity; it is worth getting the bookkeeping of $\omega^{ac}$ into your fingers now.

Solution

(a) $\langle c'|F^{\dagger}F|c\rangle$ : the $a$ -th coordinate of $F^\dagger$ applied to basis vectors gives $\sum_{a=0}^{q-1}\overline{\left(\tfrac{1}{\sqrt q}\omega^{ac'}\right)}\tfrac{1}{\sqrt q}\omega^{ac}=\frac1q\sum_{a=0}^{q-1}\omega^{a(c-c')}.$ If $c=c'$ every term is $1$ and the sum is $q$ , giving $1$ . Otherwise $\omega^{c-c'}\ne1$ (as $0<|c-c'|<q$ ) and the geometric series equals $\frac{\omega^{q(c-c')}-1}{\omega^{c-c'}-1}=0$ . Hence the columns of $F$ are orthonormal and $F$ is unitary.

(b) Write $c=\sum_{k=0}^{\ell-1}c_k2^{k}$ . Then $\omega^{ac}=e^{2\pi i a c/2^{\ell}}=\prod_{k=0}^{\ell-1}e^{2\pi i a c_k 2^{k}/2^{\ell}}=\prod_{k=0}^{\ell-1}\left(e^{2\pi i a/2^{\ell-k}}\right)^{c_k}.$ Summing over all $c$ means summing independently over $c_{\ell-1},\dots,c_0\in\{0,1\}$ , so $F|a\rangle=\frac{1}{\sqrt q}\sum_{c_{\ell-1},\dots,c_0}\prod_k\left(e^{2\pi i a/2^{\ell-k}}\right)^{c_k}|c_{\ell-1}\cdots c_0\rangle=\bigotimes_{k=\ell-1}^{0}\frac{|0\rangle+e^{2\pi i a/2^{\ell-k}}|1\rangle}{\sqrt2},$ which is the claim with $m=\ell-k$ .

The output is unentangled: the qubit carrying $c_{\ell-m}$ ends in the state $(|0\rangle+e^{2\pi i a/2^{m}}|1\rangle)/\sqrt2$ . Since $e^{2\pi i a/2^m}=e^{2\pi i (a\bmod 2^m)/2^m}=\prod_{j=0}^{m-1}e^{2\pi i a_j/2^{m-j}}$ , this phase is built from the input bits $a_0,\dots,a_{m-1}$ only. The term $j=m-1$ contributes $e^{i\pi a_{m-1}}=(-1)^{a_{m-1}}$ , which is exactly what a Hadamard $H=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}$ applied to qubit $a_{m-1}$ produces; the terms $j<m-1$ contribute a phase $e^{2\pi i/2^{m-j}}$ applied precisely when $a_j=a_{m-1}=1$ , i.e. a two-qubit controlled phase gate $\mathrm{diag}(1,1,1,e^{i\pi/2^{m-j-1}})$ on qubits $j$ and $m-1$ . Doing this for each $m=1,\dots,\ell$ (in decreasing order of the target qubit, so that a qubit is used as a control only after it has been Hadamarded) costs $\ell$ Hadamards and $\sum_{m=1}^{\ell}(m-1)=\ell(\ell-1)/2$ controlled phases: $O(\ell^2)$ gates. The bit carrying $c_{\ell-m}$ sits in position $m-1$ , so the output bits come out reversed; reversing them is a classical relabelling (or $\lfloor \ell/2\rfloor$ swaps).

(c) For $|\chi\rangle$ (so $r=4$ , $k=3$ , $q=16$ ) the amplitude of $|c\rangle$ is $\frac12\cdot\frac14\sum_{b=0}^{3}e^{2\pi i(4b+3)c/16}=\frac18e^{2\pi i\cdot 3c/16}\sum_{b=0}^{3}e^{2\pi i bc/4}.$ The last sum is $4$ if $4\mid c$ and $0$ otherwise. So $F|\chi\rangle=\frac12\sum_{j=0}^{3}e^{2\pi i\cdot 3(4j)/16}|4j\rangle=\frac12\big(|0\rangle+i^{3}|4\rangle+i^{6}|8\rangle+i^{9}|12\rangle\big)$ , and the measured $c$ is uniform on $\{0,4,8,12\}$ , i.e. on the multiples of $q/r=4$ . (Check: four outcomes of probability $1/4$ .)

In general the amplitude of $|c\rangle$ in $F|\chi_{r,k}\rangle$ is $\frac{\sqrt r}{q}\,\omega^{kc}\sum_{b=0}^{q/r-1}\omega^{brc},$ and $\sum_{b}\omega^{brc}$ equals $q/r$ if $rc\equiv0\pmod q$ , i.e. if $(q/r)\mid c$ , and vanishes otherwise. Hence the amplitude has modulus $1/\sqrt r$ on each of the $r$ multiples $c=j\,q/r$ and $0$ elsewhere: $c$ is uniform on the multiples of $q/r$ . The offset $k$ only multiplies the amplitudes by the phase $\omega^{kc}$ and is invisible in the measurement statistics. This is the whole idea of the algorithm in its ideal case: the measured $c$ satisfies $c/q=j/r$ exactly, and it carries no information about which coset the second register collapsed to.

Problem 3 challenging

period finding Dirichlet kernel geometric sums measurement statistics

Let $n\ge 11$ be odd and composite, let $x$ be coprime to $n$ with multiplicative order $r<n$ , and let $q=2^{\ell}$ be chosen with $n^{2}\le q<2n^{2}$ . Set $\omega=e^{2\pi i/q}$ . The machine is prepared in $|\Psi\rangle=\frac{1}{\sqrt q}\sum_{a=0}^{q-1}|a\rangle\,|x^{a}\bmod n\rangle .$ For $z\in\mathbb{Z}$ write $\{z\}_q$ for the representative of $z$ modulo $q$ lying in $(-q/2,\,q/2]$ .

The second register is measured, then the Fourier transform $F:|a\rangle\mapsto q^{-1/2}\sum_{c}\omega^{ac}|c\rangle$ is applied to the first register, which is then measured, giving $c\in\{0,\dots,q-1\}$ .

(a) Show that measuring the second register returns $x^{k}$ for some $k$ with $0\le k<r$ , and that conditional on this outcome the first register is the uniform superposition over $A_k=\{a: 0\le a<q,\ a\equiv k \ (\mathrm{mod}\ r)\}$ . Writing $m=|A_k|$ and $\delta=\{rc\}_q$ , show that $\Pr[c\mid k]=\frac{1}{qm}\left|\sum_{b=0}^{m-1}\omega^{br c}\right|^{2}=\frac{1}{qm}\cdot\frac{\sin^{2}(\pi m\delta/q)}{\sin^{2}(\pi\delta/q)}\qquad(\delta\neq0),$ and $\Pr[c\mid k]=m/q$ when $\delta=0$ .

Hint 1 of 3
$x^a$ depends on $a$ only through $a \bmod r$ , so the basis states of the second register occurring in $|\Psi\rangle$ are $|x^0\rangle,\dots,|x^{r-1}\rangle$ , and they are distinct.

Hint 2 of 3
Substitute $a=br+k$ ; the factor $\omega^{kc}$ has modulus $1$ and can be discarded, and $\omega^{brc}$ depends on $rc$ only mod $q$ .

Hint 3 of 3
$|e^{i\theta}-1|=2|\sin(\theta/2)|$ .
(b) Call $c$ good if $|\{rc\}_q|\le r/2$ . Prove that every good $c$ satisfies $\Pr[c\mid k]\ge \frac{1}{4r}$ , for every $k$ .

Hint 1 of 3
Bound the denominator by $|\sin(\pi\delta/q)|\le\pi|\delta|/q$ , and bound $m$ from below by $q/r-1$ ; note $r/q<1/n\le 1/11$ .

Hint 2 of 3
Put $\varphi=m|\delta|/q$ . You would like $\sin(\pi\varphi)\ge2\varphi$ , but check the range of $\varphi$ first: $m$ can exceed $q/r$ by $1$ , so $\varphi$ can be slightly larger than $1/2$ .

Hint 3 of 3
$\sin(\pi\varphi)/\varphi$ is decreasing on $(0,1)$ , so it suffices to evaluate it at the largest possible $\varphi$ , namely $\tfrac12(1+\tfrac1n)\le\tfrac{6}{11}$ .
(c) Show that there are at least $r$ good values of $c$ , one for each $d\in\{0,1,\dots,r-1\}$ , and that a good $c$ with associated $d$ satisfies $\left|\frac{c}{q}-\frac{d}{r}\right|\le\frac{1}{2q}.$ Deduce that with probability at least $1/4$ the measured $c$ satisfies this inequality for some integer $d$ with $0\le d<r$ .

Hint 1 of 2
Given $d$ , take $c_d$ to be the nearest integer to $dq/r$ , and check that $\{rc_d\}_q=rc_d-dq$ .

Hint 2 of 2
Distinct $d$ give distinct $c_d$ because $q/r>n>1$ .

Hint 1 of 2

Everything is one geometric series; the work is in bounding it honestly rather than replacing it by an integral.

Hint 2 of 2

The two hypotheses $q\ge n^{2}$ and $r<n$ are used in different places: one controls the error in $m\approx q/r$ , the other will be needed in Question 4.

Solution

(a) Since $x^{a}$ depends only on $a\bmod r$ and $x^{0},\dots,x^{r-1}$ are distinct residues, we may group the sum: $|\Psi\rangle=\frac1{\sqrt q}\sum_{k=0}^{r-1}\Big(\sum_{a\in A_k}|a\rangle\Big)|x^{k}\rangle .$ Measuring the second register therefore returns $x^{k}$ with probability $|A_k|/q=m/q$ and projects the first register onto $m^{-1/2}\sum_{a\in A_k}|a\rangle$ , the uniform superposition over $A_k=\{k,k+r,\dots\}$ .

Applying $F$ , the amplitude of $|c\rangle$ is $\frac{1}{\sqrt{mq}}\sum_{b=0}^{m-1}\omega^{(br+k)c}$ . The factor $\omega^{kc}$ has modulus $1$ , so $\Pr[c\mid k]=\frac{1}{qm}\Big|\sum_{b=0}^{m-1}\omega^{brc}\Big|^{2}.$ Since $\omega^{rc}=\omega^{\delta}$ with $\delta=\{rc\}_q$ , the sum is $m$ if $\delta=0$ ; otherwise it is the geometric series $\frac{e^{2\pi i m\delta/q}-1}{e^{2\pi i\delta/q}-1},\qquad\text{of modulus }\ \frac{|\sin(\pi m\delta/q)|}{|\sin(\pi\delta/q)|},$ using $|e^{i\theta}-1|=2|\sin(\theta/2)|$ . This gives the stated formulas.

(b) First, $m=\#\{b\ge0: br+k<q\}=\lceil (q-k)/r\rceil$ , so $\frac{q}{r}-1\le\frac{q-k}{r}\le m\le\frac{q}{r}+1 .$ Also $r<n$ and $q\ge n^{2}$ give $r/q<1/n\le1/11$ .

If $\delta=0$ : $\Pr[c\mid k]=m/q\ge \frac1r\big(1-\frac rq\big)\ge\frac{10}{11r}>\frac1{4r}$ .

If $0<|\delta|\le r/2$ , set $\varphi=m|\delta|/q$ . Then $\varphi\le\Big(\frac qr+1\Big)\frac{r}{2q}=\frac12\Big(1+\frac rq\Big)\le\frac12\Big(1+\frac1{11}\Big)=\frac{6}{11}.$ Using $|\sin(\pi\delta/q)|\le\pi|\delta|/q=\pi\varphi/m$ , $\Big|\sum_{b}\omega^{brc}\Big|\ \ge\ \frac{|\sin(\pi\varphi)|}{\pi\varphi/m}=\frac{m}{\pi}\cdot\frac{\sin(\pi\varphi)}{\varphi}.$ The function $\varphi\mapsto\sin(\pi\varphi)/\varphi$ is decreasing on $(0,1)$ (its numerator's derivative test: $\frac{d}{d\varphi}\big[\sin\pi\varphi/\varphi\big]=g(\varphi)/\varphi^{2}$ with $g(\varphi)=\pi\varphi\cos\pi\varphi-\sin\pi\varphi$ , $g(0)=0$ , $g'(\varphi)=-\pi^{2}\varphi\sin\pi\varphi\le0$ ). Hence $\frac{\sin(\pi\varphi)}{\varphi}\ \ge\ \frac{\sin(6\pi/11)}{6/11}=\frac{11}{6}\sin\frac{5\pi}{11}=1.814\ldots,$ so $\big|\sum_b\omega^{brc}\big|\ge 0.577\,m$ and $\Pr[c\mid k]\ \ge\ \frac{(0.577)^{2}m^{2}}{qm}=0.333\,\frac mq\ \ge\ 0.333\cdot\frac1r\Big(1-\frac1{11}\Big)=\frac{0.303}{r}>\frac{1}{4r}.$ (The true asymptotic constant is $4/\pi^{2}=0.405\ldots$ ; we have thrown away a little to keep the estimate uniform in $k$ .)

(c) Fix $d\in\{0,\dots,r-1\}$ and let $c_d$ be the nearest integer to $dq/r$ , so $|c_d-dq/r|\le1/2$ , i.e. $|rc_d-dq|\le r/2$ . Since $r<n<q/2$ , the integer $rc_d-dq$ lies in $(-q/2,q/2]$ and is congruent to $rc_d$ mod $q$ , so $\{rc_d\}_q=rc_d-dq$ and $|\{rc_d\}_q|\le r/2$ : each $c_d$ is good. Distinct $d,d'$ give distinct $c_d$ , since $|dq/r-d'q/r|\ge q/r>n>1$ while each $c$ is within $1/2$ of its $dq/r$ . Also $0\le c_d\le q-q/r+1/2<q$ , so all $r$ values are legitimate outcomes.

Dividing $|rc_d-dq|\le r/2$ by $rq$ gives $|c_d/q-d/r|\le1/(2q)$ .

By (b) each of these $r$ outcomes has conditional probability at least $1/(4r)$ , whatever $k$ was observed; hence conditional on any $k$ , and therefore also unconditionally, $\Pr\big[\exists d:\ |c/q-d/r|\le 1/(2q)\big]\ \ge\ r\cdot\frac1{4r}=\frac14 .$

Problem 4 standard

continued fractions rational approximation Euler totient classical post-processing

Suppose a run of the algorithm of Question 3 has produced an integer $c$ with $0\le c<q$ such that $\left|\frac{c}{q}-\frac{d}{r}\right|\le\frac{1}{2q}\qquad\text{for some integer } d,\ 0\le d<r,$ where $r<n$ is the unknown order of $x$ modulo $n$ and $q$ is a power of $2$ with $n^{2}\le q<2n^{2}$ . The only data available to the classical post-processing are $c$ , $q$ , $n$ and $x$ .

You may use Legendre's theorem: if $\alpha\in\mathbb{R}$ and $\gcd(d',r')=1$ , $r'\ge1$ , satisfy $|\alpha-d'/r'|<1/(2r'^{2})$ , then $d'/r'$ is one of the convergents of the continued fraction expansion of $\alpha$ .

(a) Show that there is at most one rational number with denominator less than $n$ satisfying the displayed inequality, and that it is a convergent of the continued fraction expansion of $c/q$ . Point out exactly where each of the two hypotheses $q\ge n^{2}$ and $r<n$ is used.

Hint 1 of 2
If $d/r\ne d'/r'$ then $|d/r-d'/r'|\ge 1/(rr')$ ; compare with what the triangle inequality allows.

Hint 2 of 2
For Legendre's theorem you need $1/(2q)<1/(2r^2)$ after reducing $d/r$ to lowest terms — and reducing only decreases the denominator.
(b) Take $n=33$ , $x=5$ (whose order you should not assume known), $q=2048$ and suppose the machine returns $c=1229$ . Carry out the post-processing: compute the continued fraction expansion of $c/q$ , list its convergents, extract the candidate order, test it, and repair it if it is wrong. Finish the job: produce a nontrivial factor of $33$ .

Hint 1 of 3
$2048=1\cdot1229+819$ ; keep going with the Euclidean algorithm and read off the partial quotients.

Hint 2 of 3
The convergent you want is the last one whose denominator is $<33$ . Test the candidate $r'$ by computing $5^{r'}\bmod 33$ .

Hint 3 of 3
If $\gcd(d,r)>1$ the convergent gives you a proper divisor of $r$ , not $r$ : try $2r',3r',\dots$
(c) Combining with Question 3, show that a single run yields the exact order $r$ with probability at least $\varphi(r)/(4r)$ , where $\varphi$ is Euler's totient. Assuming the classical estimate $\varphi(r)/r>\delta/\log\log r$ for an absolute constant $\delta>0$ and $r\ge3$ , deduce that $O(\log\log n)$ runs suffice to find $r$ with probability bounded away from $0$ .

Hint 1 of 2
Which of the $r$ good values of $c$ from Question 3(c) let you read off $r$ itself rather than a proper divisor?

Hint 2 of 2
The number of $d\in\{0,\dots,r-1\}$ with $\gcd(d,r)=1$ is $\varphi(r)$ ; each contributes a distinct good $c$ .

Hint 1 of 1

The continued fraction step is entirely classical: the quantum computer's only job was to hand you one integer $c$ .

Solution

(a) Uniqueness. Suppose $d/r$ and $d'/r'$ both satisfy the inequality with $1\le r,r'<n$ . If they are unequal then $\frac{1}{rr'}\le\left|\frac dr-\frac{d'}{r'}\right|\le\left|\frac dr-\frac cq\right|+\left|\frac cq-\frac{d'}{r'}\right|\le\frac1q,$ so $rr'\ge q\ge n^{2}$ , contradicting $r,r'\le n-1$ . (Here $r<n$ and $q\ge n^{2}$ are both used.)

Recoverability. Write $d/r=d'/r'$ in lowest terms, so $r'\le r<n$ and $r'^{2}<n^{2}\le q$ . Then $\left|\frac cq-\frac{d'}{r'}\right|\le\frac1{2q}<\frac{1}{2r'^{2}},$ so by Legendre's theorem $d'/r'$ is a convergent of $c/q$ . The convergents of $c/q$ have strictly increasing denominators and are computed by the Euclidean algorithm in $O(\log q)$ steps, so we can list all of them with denominator $<n$ and, by uniqueness, the correct one is the last such convergent. This is exactly why $q$ was chosen with $q\ge n^{2}$ : it makes the window $1/(2q)$ narrow enough both to pin down $d/r$ uniquely and to trigger Legendre's theorem.

(b) Euclid on $1229/2048$ : $2048=1\cdot1229+819,\quad1229=1\cdot819+410,\quad819=1\cdot410+409,\quad410=1\cdot409+1,\quad409=409\cdot1,$ so $c/q=[0;1,1,1,1,409]$ . The convergents are $\frac01,\ \frac11,\ \frac12,\ \frac23,\ \frac35,\ \frac{1229}{2048}.$ The last one with denominator $<33$ is $3/5$ . So the candidate order is $r'=5$ . Test it: $5^{5}=3125=94\cdot33+23$ , so $5^{5}\equiv23\not\equiv1\pmod{33}$ — the candidate is wrong, because the true $d$ shares a factor with $r$ . Try small multiples: $5^{10}\equiv23^{2}=529=16\cdot33+1\equiv1\pmod{33}$ , and no proper divisor of $10$ works ( $5^{2}=25$ , $5^{5}=23$ ), so $r=10$ . (Indeed $c/q=0.60009\ldots$ and $d/r=6/10=0.6$ , with $|c/q-6/10|=1/10240\le1/4096=1/(2q)$ .)

Finally $r=10$ is even and $5^{5}\equiv23\not\equiv-1\equiv32\pmod{33}$ , so by Question 1(b) $\gcd(5^{5}-1,33)=\gcd(22,33)=11$ is a nontrivial factor: $33=3\cdot11$ .

(c) By Question 3(c) the good $c$ 's are in bijection with $d\in\{0,\dots,r-1\}$ , and by (a) the post-processing recovers $d/r$ in lowest terms, i.e. $d/\gcd(d,r)$ over $r/\gcd(d,r)$ . The denominator is $r$ itself exactly when $\gcd(d,r)=1$ , which happens for $\varphi(r)$ values of $d$ . Each such $c$ has probability at least $1/(4r)$ by Question 3(b) (uniformly in the second-register outcome, hence also unconditionally), so $\Pr[\text{run returns }r]\ \ge\ \varphi(r)\cdot\frac1{4r}=\frac{\varphi(r)}{4r}.$ With $\varphi(r)/r>\delta/\log\log r$ this is at least $\delta/(4\log\log n)$ , so after $t=\lceil 4\delta^{-1}\log\log n\rceil$ independent runs the probability of never seeing $r$ is at most $(1-\delta/(4\log\log n))^{t}\le e^{-1}$ . Hence $O(\log\log n)$ runs suffice. (In practice one does much better: testing the small multiples $2r',3r',\dots$ of each candidate, as in (b), converts most of the failures into successes and reduces the expected number of runs to $O(1)$ .)

Problem 5 challenging

eigenvalue/phase estimation viewpoint reversible computation and garbage entanglement and interference algorithm assembly

Keep the notation of Question 3: $n$ odd composite, $x$ coprime to $n$ of order $r$ , $q=2^{\ell}$ with $n^{2}\le q<2n^{2}$ , $\omega=e^{2\pi i/q}$ , and $|\Psi\rangle=\frac{1}{\sqrt q}\sum_{a=0}^{q-1}|a\rangle\,|x^{a}\bmod n\rangle .$ Let $U$ be the linear map on the $r$ -dimensional space spanned by $\{|x^{k}\bmod n\rangle: 0\le k<r\}$ determined by $U|y\rangle=|xy\bmod n\rangle$ .

(a) A careless implementation of modular exponentiation leaves its scratch bits behind, so that instead of $|\Psi\rangle$ the machine holds $|\Psi'\rangle=\frac1{\sqrt q}\sum_{a=0}^{q-1}|a\rangle\,|x^{a}\bmod n\rangle\,|g(a)\rangle,$ where $g$ is injective on $\{0,\dots,q-1\}$ . Show that applying $F$ to the first register and measuring it gives a value $c$ that is exactly uniform on $\{0,\dots,q-1\}$ . What does this say about the necessity of uncomputing scratch registers?

Hint 1 of 2
Write $|\Psi'\rangle=q^{-1/2}\sum_a|a\rangle|\phi_a\rangle$ and note what injectivity of $g$ says about $\langle\phi_a|\phi_{a'}\rangle$ .

Hint 2 of 2
The probability of $c$ is the squared norm of a vector $q^{-1}\sum_a\omega^{ac}|\phi_a\rangle$ ; orthonormal summands make cross terms vanish.
(b) For $0\le s<r$ put $|u_{s}\rangle=r^{-1/2}\sum_{k=0}^{r-1}e^{-2\pi isk/r}|x^{k}\bmod n\rangle$ . Show that $U|u_s\rangle=e^{2\pi is/r}|u_s\rangle$ , that $\{|u_s\rangle\}_{s=0}^{r-1}$ is orthonormal, and that $r^{-1/2}\sum_{s}|u_{s}\rangle=|1\rangle$ .

Hint 1 of 2
$U$ permutes the basis cyclically with period $r$ .

Hint 2 of 2
For the last identity, sum the geometric series over $s$ for each fixed $k$ .
(c) Show that $|\Psi\rangle=\frac{1}{\sqrt r}\sum_{s=0}^{r-1}|\psi_{s}\rangle\otimes|u_{s}\rangle,\qquad |\psi_{s}\rangle=\frac1{\sqrt q}\sum_{a=0}^{q-1}e^{2\pi isa/r}|a\rangle,$ and deduce that the distribution of the measured $c$ is $\Pr[c]=\frac1r\sum_{s}\big|\langle c|F|\psi_{s}\rangle\big|^{2}$ , which is the same whether or not the second register is measured (and the same as the average over $k$ of the conditional distributions of Question 3). Identify, for each $s$ , the value of $d$ near which $c/q$ concentrates.

Hint 1 of 3
Invert the definition in (b): express $|x^{k}\rangle$ in terms of the $|u_s\rangle$ , then swap the order of summation.

Hint 2 of 3
Two orthonormal decompositions of the same vector give the same reduced statistics for the first register — compute $\Pr[c]$ directly as a squared norm, without conditioning on anything.

Hint 3 of 3
$\langle c|F|\psi_s\rangle=q^{-1}\sum_a e^{2\pi ia(s/r+c/q)}$ , which is large when $s/r+c/q$ is close to an integer.
(d) Assemble the whole algorithm for factoring an odd composite $n$ that is not a prime power, using Questions 1, 3 and 4. State the expected number of quantum runs, and say for each step whether it is executed on the quantum computer or on the classical one.

Hint 1 of 2
The quantum computer is used only to turn one integer $x$ into one integer $c$ ; everything else — choosing $x$ , gcds, continued fractions, testing candidate orders — is classical.

Hint 2 of 2
Multiply the probability that a random $x$ is a useful witness (Question 1) by the probability that a run returns $r$ (Question 4(c)).

Hint 1 of 1

Parts (a) and (c) are both computations of the same kind: the statistics of the first register depend on the second only through the inner products of the states it is correlated with.

Solution

(a) Write $|\phi_a\rangle=|x^{a}\bmod n\rangle|g(a)\rangle$ . Since $g$ is injective, $\langle\phi_a|\phi_{a'}\rangle=\delta_{aa'}$ : the second and third registers record $a$ exactly. After applying $F$ to the first register, $(F\otimes I)|\Psi'\rangle=\sum_{c}|c\rangle\otimes\Big(\frac1q\sum_{a}\omega^{ac}|\phi_a\rangle\Big),$ so $\Pr[c]=\Big\|\frac1q\sum_a\omega^{ac}|\phi_a\rangle\Big\|^{2}=\frac1{q^{2}}\sum_{a,a'}\omega^{(a-a')c}\langle\phi_{a'}|\phi_a\rangle=\frac1{q^{2}}\sum_{a}1=\frac1q .$ The distribution is uniform: no information about $r$ whatsoever. Interference is what produces the peaks, and interference between $a$ and $a'=a+r$ requires the rest of the machine to be in the same state for both. Hence the modular exponentiation must be made reversible and its scratch bits uncomputed (Bennett's trick: compute, copy the answer, run the computation backwards), leaving the second register depending on $a$ only through $a\bmod r$ .

(b) $U|u_s\rangle=r^{-1/2}\sum_k e^{-2\pi isk/r}|x^{k+1}\rangle=r^{-1/2}\sum_{k'}e^{-2\pi is(k'-1)/r}|x^{k'}\rangle=e^{2\pi is/r}|u_s\rangle$ (indices mod $r$ , using $x^{r}\equiv1$ ). Orthonormality: $\langle u_{s'}|u_s\rangle=r^{-1}\sum_k e^{2\pi i(s'-s)k/r}=\delta_{ss'}$ by the geometric sum. Finally $\frac1{\sqrt r}\sum_{s}|u_s\rangle=\frac1r\sum_{k}\Big(\sum_{s}e^{-2\pi isk/r}\Big)|x^{k}\rangle=|x^{0}\rangle=|1\rangle,$ since the inner sum is $r$ for $k=0$ and $0$ otherwise. (So the easily-prepared state $|1\rangle$ is the uniform superposition of all $r$ eigenvectors — the reason we never need to prepare a single $|u_s\rangle$ , which would require knowing $r$ .)

(c) Inverting (b), $|x^{k}\rangle=r^{-1/2}\sum_{s}e^{2\pi isk/r}|u_s\rangle$ . Since $x^{a}=x^{a\bmod r}$ , $|\Psi\rangle=\frac1{\sqrt{qr}}\sum_{a}\sum_{s}e^{2\pi isa/r}|a\rangle|u_s\rangle=\frac1{\sqrt r}\sum_{s}|\psi_s\rangle\otimes|u_s\rangle .$ Because the $|u_s\rangle$ are orthonormal, applying $F$ to the first register and measuring gives $\Pr[c]=\Big\|\frac1{\sqrt r}\sum_s\langle c|F|\psi_s\rangle|u_s\rangle\Big\|^{2}=\frac1r\sum_{s}\big|\langle c|F|\psi_s\rangle\big|^{2}.$ No measurement of the second register was used in this computation. The identical computation with the computational basis $\{|x^{k}\rangle\}$ in place of $\{|u_s\rangle\}$ gives $\Pr[c]=\sum_k\frac{m_k}{q}\Pr[c\mid k]$ , the average of the conditional distributions of Question 3. So the second register may be measured, or not, or measured later: the marginal law of $c$ is the same. (Structurally: the reduced state of the first register is unchanged by a measurement of a disjoint register.)

For each $s$ , $\langle c|F|\psi_s\rangle=q^{-1}\sum_{a}e^{2\pi ia(s/r+c/q)}$ , whose modulus is large precisely when $s/r+c/q$ is near an integer, i.e. when $c/q\approx (r-s)/r$ . Thus the algorithm is phase estimation applied to $U$ on a uniformly random eigenvector $|u_s\rangle$ , and the $d$ of Questions 3–4 is $d\equiv-s\pmod r$ ; note $\gcd(d,r)=\gcd(s,r)$ , so the $\varphi(r)/r$ fraction of Question 4(c) is the chance that the random eigenvector has a primitive phase.

(d) To factor $n$ (odd, composite, not a prime power):

(classical) pick $x\in\{2,\dots,n-1\}$ at random; compute $\gcd(x,n)$ — if it exceeds $1$ we are done by luck; compute $q=2^{\ell}$ with $n^{2}\le q<2n^{2}$ .
(quantum) prepare $q^{-1/2}\sum_a|a\rangle|0\rangle$ by one Hadamard per qubit; compute $|a\rangle|x^{a}\bmod n\rangle$ by reversible modular exponentiation with all scratch uncomputed (Part (a)); apply $F$ to the first register (Question 2(b), $O(\ell^{2})$ gates); measure, obtaining $c$ .
(classical) expand $c/q$ in continued fractions, take the last convergent $d'/r'$ with denominator $<n$ , and test $r',2r',3r',\dots$ as candidate orders by modular exponentiation; if none satisfies $x^{R}\equiv1$ , go back to step 2.
(classical) with $r$ in hand: if $r$ is odd or $x^{r/2}\equiv-1\pmod n$ , go back to step 1 with a fresh $x$ ; otherwise output $\gcd(x^{r/2}-1,n)$ , which is a nontrivial factor by Question 1(b).

Probabilities: a random $x$ is useful with probability at least $1-2^{1-k}\ge1/2$ ( $k\ge2$ distinct odd primes dividing $n$ ; Question 1), and each quantum run returns $r$ with probability at least $\varphi(r)/(4r)=\Omega(1/\log\log n)$ (Question 4(c)). So the expected number of quantum runs is $O(\log\log n)$ — and $O(1)$ in practice with the multiple-testing refinement. Only step 2 is quantum; it consists of $O(\ell)$ modular multiplications on $\ell$ -bit numbers plus an $O(\ell^{2})$ -gate Fourier transform, and it emits a single classical integer $c$ .