From Factoring to Phase Estimation

The publication of Shor's quantum algorithm for efficiently factoring numbers [4,5] was the key event that stimulated many theoretical and experimental investigations of quantum computation. One of the reasons why this algorithm is so important is that the security of widely used public key cryptographic protocols relies on the conjectured difficulty of factoring large numbers. An elementary overview of these protocols and the quantum algorithm for breaking them is in [15]. Here, we outline the relationship between factoring and the powerful technique of phase estimation. This relationship helps in understanding many of the existing quantum algorithms and was first explained in [16], motivated by Kitaev's version [17] of the factoring algorithm.

The factoring problem requires writing a whole number $N$ as a product of primes. (Primes are whole numbers greater than $1$ that are divisible without remainder only by $1$ and themselves.) Shor's algorithm solves this problem by reducing it to instances of the order-finding problem, which will be defined below. The reduction is based on basic number theory and involves efficient classical computation. At the core of Shor's algorithm is a quantum algorithm that solves the order-finding problem efficiently. In this case, an algorithm is considered efficient if it uses resources bounded by a polynomial in the number of digits of $N$. For more information on the requisite number theory, see any textbook on number theory [18,19].

We begin by showing that factoring reduces to order finding. The first observation is that to factor a whole number it is sufficient to solve the factor-finding problem, whose statement is: Given a whole number $N$ find a proper factor of $N$, if one exists. A ``factor'' of $N$ is a whole number $f$ that satisfies $N=fg$ for some whole number $g$. The factor $f$ is ``proper'' if $f\not=1$ and $f\not= N$. For example, if $N=15$, then $3$ and $5$ are its proper factors. For some numbers it is easy to find a proper factor. For example, you can tell that $N$ is even from the least significant digit (in decimal or binary), in which case $2$ is a proper factor (unless $N=2$, a prime). But many numbers are not so easy. As an example, you can try to find a proper factor of $N=149573$ by hand¹. You can complete the factorization of a whole number by recursively applying an algorithm for the factor-finding problem to all the proper factors found.

Before we continue the reduction of factoring to order finding, we briefly explain modular arithmetic, which both simplifies the discussion and is necessary to avoid computing with numbers that have exponential numbers of digits. We say that $a$ and $b$ are ``equal modulo $N$'', written as $a=b\;\mathrm{mod}\;N$, if $a-b$ is divisible by $N$ (without remainder). For example, $3=18\;\mathrm{mod}\;15 = 33\;\mathrm{mod}\;15$. Equality modulo $N$ is well-behaved with respect to addition and multiplication. That is, if $a=b\;\mathrm{mod}\;N$ and $c=d\;\mathrm{mod}\;N$, then $a+c=b+d\;\mathrm{mod}\;N$ and $ac=bd\;\mathrm{mod}\;N$. For factoring $N$, we will be looking for whole numbers $a$ that are divisible by a proper factor of $N$. If $a$ has this property, then so does any $b$ with $b=a\;\mathrm{mod}\;N$. We therefore perform all arithmetic ``modulo $N$''. One way to think about this is that we only use whole numbers $a$ that satisfy $0\leq a\leq N-1$. We can implement an arithmetic operation modulo $N$ by first applying the operation in the usual way and then computing the remainder after division by $N$. For example, to obtain $ab\;\mathrm{mod}\;N$, we first compute $ab$. The unique $c$ such that $0\leq c\leq N-1$ and $c=ab\;\mathrm{mod}\;N$ is the remainder after division of $ab$ by $N$. Thus $c$ is the result of multiplying $a$ by $b$ modulo $N$. Consistent with this procedure, we can think of the expression $a\;\mathrm{mod}\;N$ as referring to the remainder of $a$ after division by $N$.

The second observation in the reduction of factoring to order finding is that it is sufficient to find a whole number $r$ with the property that $r^2-1$ is a multiple of $N$ but $r-1$ and $r+1$ are not. Using the language of modular arithmetic, the property is expressed as $r^2=1\;\mathrm{mod}\;N$ but $r\not=1\;\mathrm{mod}\;N$ and $r\not= -1\;\mathrm{mod}\;N$. Because $1\;\mathrm{mod}\; N$ and $-1\;\mathrm{mod}\;N$ are the obvious square roots of $1\;\mathrm{mod}\;N$, we say that $r$ is a ``non-trivial square root of unity'' (modulo $N$). For such an $r$, one can write $r^2-1=(r-1)(r+1)=mN$ for some whole number $m$. This implies that every prime factor $p$ of $N$ divides either $(r-1)$ or $(r+1)$ so that either $(r-1)$ or $(r+1)$ is or shares a factor with $N$. Suppose that $r-1$ is or shares such a factor. Because $r-1$ is not a multiple of $N$, the greatest common divisor of $r-1$ and $N$ is a proper factor of $N$. Since there exists an efficient classical algorithm (the ``Euclidean algorithm'') for finding the greatest common divisor, we can easily find the desired proper factor.

The examples of $N=15$ and $N=21$ serve to illustrate the key features of the algorithm. For $N=15$, possible choices for $r$ are $r=4$ ($4^2-1=1*15$) and $r=11$ ( $11^2-1 = 120 = 8*15$). For the first choice, the proper factors emerge immediately: $4-1=3,4+1=5$. For the second, it is necessary to determine the greatest common divisors. Let $\textrm{gcd}(x,y)$ stand for the greatest common divisor of $x$ and $y$. The proper factors are $\textrm{gcd}(11-1,15)=\textrm{gcd}(10,15)=5$ and $\textrm{gcd}(11+1,15)=\textrm{gcd}(12,15)=3$. For $N=21$, one can take $r=8$, as $8^2-1=63=3*21$. In this case, $8-1=7$ is a proper factor and $\textrm{gcd}(8+1,21)=3$ is another.

For $N$ even or a power of a prime it is not always possible to find a non-trivial square root of unity. Because both of these cases can be handled efficiently by known classical algorithms, we can exclude them. In every other case, such numbers $r$ exist. One way to find such an $r$ is to start from any whole number $q$ with $1<q<N$. If $\textrm{gcd}(q,N)=1$, then according to a basic result in number theory there is a smallest whole number $k>1$ such that $q^k-1=0\;\mathrm{mod}\; N$. The number $k$ is called the ``order'' of $q$ modulo $N$. If $k$ is even, say $k=2\,l$, then $(q^l)^2=1\;\mathrm{mod}\;N$, so $q^l$ is a (possibly trivial) square root of unity. For the example of $N=15$, we can try $q=2$. The order of $2$ modulo $15$ is $4$, which gives $r=2^2=4$, the first of the two choices in the previous paragraph. For $N=21$, again with $q=2$, the order is $6$: $2^6-1=63=3*21$. Thus, $r=2^3=8$. We can also try $q=11$, in which case with foresight it turns out that $11^6-1$ is divisible by $21$. A possible problem appears, namely, the powers $q^k$ that we want to compute are extremely large. But modular arithmetic can be used to avoid this problem. For example, to find the order of $11$ modulo $21$ by a direct search, we can perform the following computation:

$$\begin{array}[b]{rcrcrcrcrcrcrcrcr} 11^2 &=& 121 &=& 5*21+16... ...=& &&11*2 \;\mathrm{mod}\;21&=& 1\;\mathrm{mod}\;21 \end{array}$$ (52)

In general such a direct search for the order of $q$ modulo $N$ is very inefficient, but as we will see, there is an efficient quantum algorithm that can determine the order.

A factor-finding algorithm based on the above observations is the following:

The efficiency of this algorithm depends on the probability that a randomly chosen $q$ at step 3 results in finding a factor. By using an analysis of the group of numbers $q$ that satisfy $\textrm{gcd}(q,N)=1$, it can be shown that this probability is sufficiently large.

The main problem that remains to be solved is that of finding the order of $q\;\mathrm{mod}\;N$. A direct search for the order of $q\;\mathrm{mod}\;N$ involves computing the sequence

$$1\rightarrow q \rightarrow q^2\;\mathrm{mod}\;N \rightarrow\... ...^{k-1}\;\mathrm{mod}\;N \rightarrow 1=q^{k}\;\mathrm{mod}\;N.$$ (53)

This sequence can be conveniently visualized as a cycle whose length is the order of $q\;\mathrm{mod}\;N$ (Fig. 4).

FIG. 4: Multiplicative cycles of $q\;\mathrm{mod}\;N$. Each number on a cycle is obtained from the previous one by multiplication by $q\;\mathrm{mod}\;N$.

To introduce the quantum algorithm, we first associate the logical quantum states $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{0}\mbox{$\rangle\hspace*{-... ...-3pt}\vert$}{N-1}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ with the numbers $0,1,\ldots,N-1$. The map $f$ which takes each number on the cycle to the next number along the cycle is given by $f(x)=qx\;\mathrm{mod}\;N$. For $q$ satisfying $\textrm{gcd}(q,N)=1$, the map $f$ permutes not only the numbers on the cycle, but all the numbers modulo $N$. As a result, the linear operator $\hat f$ defined by $\hat f\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{x}\mbox{$\rangle\hsp... ...;\mathrm{mod}\;N}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ is unitary. The quantum algorithm deduces the length of the cycle for $q$ by making measurements to determine properties of the action of $\hat f$ on superpositions of the states $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{q^s\;\mathrm{mod}\;N}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$. To illustrate the basic ideas, we work out the example of $N=15$ and $q=8$. The action of $\hat f$ on the states $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{1}\mbox{$\rangle\hspace*{-... ...*{-3pt}\vert$}{2}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ in the cycle of $8\;\mathrm{mod}\;15$ is completely determined by the eigenstates and eigenvalues of $\hat f$. For cyclicly acting permutations, a basis of eigenstates is given by the ``Fourier'' basis for the space spanned by the states in a cycle. For the cycle of interest, the Fourier basis consists of the states

$$\begin{array}{rcr@{}c@{}r@{}c@{}r@{}c@{}r} \mbox{$\vert\hs... ...pace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}\Big) \end{array}$$ (54)

The phases of the $l$'th state of the cycle occurring in the sum for $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi_m}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ can be written as $i^{lm}$. It follows that $\hat f\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi_m}\mbox{$\rangl... ...t}\vert$}{\psi_m}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$, that is, the eigenvalue of $\hat f$ for $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi_m}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ is $i^m$. Note that in the complex numbers, the powers of $i$ are all the fourth roots of unity. In general, the Fourier basis for the cycle $\ldots\rightarrow\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{q^l\;\mat... ...\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}\rightarrow\ldots$ consists of the states $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi_m}\mbox{$\rangle\hspa... ...;\mathrm{mod}\;N}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$, where $\omega=e^{i2\pi/k}$ is a primitive $k$'th root of unity. (The complex number $x$ is a primitive $k$'th root of unity if $k$ is the smallest whole number $k>0$ such that $x^k=1$. For example, both $-1$ and $i$ are fourth roots of unity, but only $i$ is primitive.)

It is, of course, possible to express the logical state $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{1}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ using the Fourier basis:

$$\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{1}\mbox... ...$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}\Big).$$ (55)

The key step of the quantum algorithm for order finding consists of a measurement to estimate a random eigenvalue of $\hat f$ whose associated eigenstate occurs in the expression for $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{1}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ in terms of the Fourier basis. If the eigenvalue found is a primitive $k$'th root of unity, we infer that the cycle length is divisible by $k$ and check (using a classical algorithm) whether this is the order of $q$. In the example, the random eigenvalues are $1$ (the only primitive first root of unity), $i$ and $-i$ (primitive fourth roots of unity) and $-1$ (the primitive second root of unity). The order is found if the random eigenvalue is a primitive fourth root of unity, which happens with probability $1/2$ in this case.

The quantum algorithm for obtaining an eigenvalue is called the ``phase estimation'' algorithm. It exploits a more general version of the phase kick back we encountered in the solution of the parity problem. The phase kick back transfers the eigenvalue of an eigenstate of $\hat f$ to a Fourier basis on a number of additional qubits called ``helper'' or ``ancilla'' qubits. Which Fourier state results is then determined by a subroutine called the ``measured quantum Fourier transform''. We introduce these elements in the next paragraphs. Their combination for solving the general order-finding problem is shown in Fig. 10.

Fig. 5 shows how to kick back the eigenvalue of an eigenstate of $\hat f$ using a network implementing the controlled-$\hat f$ operation.

FIG. 5: Phase estimation with one qubit. The input is a product state on one ancilla qubit and on a second quantum system as shown. The state $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi_m}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ on the second system is an eigenstate of $\hat f$. For the example under discussion (see Eq. 54), the eigenvalue is $i^m$. A controlled-$\hat f$ operation is applied to the input, that is, $\hat f$ is applied to the second system conditional on $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\mathfrak{1}}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ for the ancilla qubit. In the bra-ket notation, the total operation can be written as $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\mathfrak{0}}\mbox{$\rangl... ...angle$}{\mathfrak{1}}\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}\hat f$ (system labels have been omitted). Since $\hat f$ changes only the phase of its input, the second system is unchanged, but the phase modifies the ancilla qubit's superposition as shown.

The network in Fig. 5 can be used with input $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{1}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ on the second system. From Eq. 55 and the superposition principle, it follows that the output correlates the different phase kickback states with the four eigenvectors $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi_m}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$. That is, the network implements the following transformation:

$${1\over 2\sqrt{2}}\left(\mbox{$\vert\hspace*{-3pt}\vert\hspa... ...*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$} \end{array} \right)$$ (56)

The hope is that a measurement of the first qubit can distinguish between the four possible phases that can be kicked back. However, because the four states are not mutually orthogonal, they are not unambiguously distinguishable by a measurement. To solve this problem, we use a second qubit and a controlled-$\hat f^2$ as shown in Fig. 6.

FIG. 6: Phase estimation with two qubits. Using two qubits ensures distinguishability of the eigenvalues of $\hat f$ for the states $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi_m}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$. The states of the input qubits are used to represent the numbers from $0$ to $3$ in binary. The most significant bit (the ``two'''s digit in the binary representation) is carried by the top qubit. That is, we make the following identification: $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{0}\mbox{$\rangle\hspace*{-... ...k{0}\mathfrak{0}}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$, $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{1}\mbox{$\rangle\hspace*{-... ...k{0}\mathfrak{1}}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$, $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{2}\mbox{$\rangle\hspace*{-... ...k{1}\mathfrak{0}}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ and $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{3}\mbox{$\rangle\hspace*{-... ...k{1}\mathfrak{1}}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$. It follows that the network has the effect of applying $\hat f^m$ conditional on the input qubits' logical state being $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{m}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$.

The four possible states $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{u_m}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ that appear on the ancilla qubits in the network of Fig. 6 are the Fourier basis for the cycle $0\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 0$ and are therefore orthonormal. If we apply the network of Fig. 6 with $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{1}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ instead of $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi_m}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ at the lower input, the output correlates the four $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi_m}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ in the superposition with the $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{u_m}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$, which makes the information about the eigenvalues of $\hat f$ available in the Fourier basis of the two ancilla qubits. This approach has the advantage that the states are known, whereas in the Fourier basis for the cycle of $q\;\mathrm{mod}\;N$, the states depend on the numbers in the cycle, which are not known in advance (except in very simple cases, such as the example we are working with).

To learn one of the eigenvalues of $\hat f$, the last step is to make a ``measurement in the Fourier basis''. For one qubit representing the binary numbers $0$ and $1$, the Fourier basis is ${1\over \sqrt{2}}\left(\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{0}\... ...\vert$}{1}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}\right)$ and ${1\over \sqrt{2}}\left(\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{0}\... ...\vert$}{1}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}\right)$, which is constructed as discussed after Eq. 54, but using the square root of unity $\omega=-1$ instead of the fourth root $i$. To make a measurement that determines which of the two basis vectors is present, it suffices to apply the Hadamard transform $\mathbf{H}$ and make a standard measurement, just as we did twice in the network of Fig. 2. A more complicated network works with two qubits representing the binary numbers from $0$ to $3$. Such a network is shown in Fig. 7.

FIG. 7: The measured quantum Fourier transform [20] on two qubits representing the numbers $0,1,2,3$. If the input is one of the Fourier states $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{u_{a}}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$, where the binary digits of $a$ are determined by $a=2*a_1+a_0$, then the measurement outcomes are $a_0$ and $a_1$, as shown. The numbers under the network are checkpoints used for analyzing the network.

To see how the network extracts the bits in the index of $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{u_a}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$, we can follow the states as the network is executed. The input state at checkpoint 1 in Fig. 7 is given by

$$\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\phi_1}... ...e*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$} \end{array}\right).$$ (57)

In the last sum, the relevant numbers have been fully expanded in terms of their binary digits to give a flavor of the general principles underlying the measured Fourier transform. The next step of the network applies a Hadamard gate to the qubit carrying the most significant digit. To understand how it succeeds in extracting $a_0$, the least significant bit of $a$, let $b$ with binary digits $b_0$ and $b_1$ represent one of the logical states of the two qubits. As before, the most significant bit $b_1$ is represented by the top/first qubit that the first Hadamard gate is applied to. The phase of $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{b}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ in Eq. 57 is given by $i^{(b_1*2^1+b_0*2^0)(a_1*2^1+a_0*2^0)}$. Next, we determine how this phase depends on $b_1$:

$$i^{(b_1*2^1+b_0*2^0)(a_1*2^1+a_0*2^0)} = i^{b_1*2^1*(a_1*2^1+a_0*2^0)}\;i^{b_0*2^0*(a_1*2^1+a_0*2^0)}$$

$$= i^{b_1*a_1*2^2}i^{b_1*a_0*2^1}\;i^{b_0*2^0*(a_1*2^1+a_0*2^0)}$$

$$= (i^4)^{b_1*a_1}(i^2)^{b_1*a_0}\;i^{b_0*2^0*(a_1*2^1+a_0*2^0)}$$

$$= (-1)^{b_1*a_0}\;i^{b_0*2^0*(a_1*2^1+a_0*2^0)}.$$ (58)

It follows that if $a_0=0$, the phase does not depend on $b_1$, and if $a_0=1$, it changes sign with $b_1$. This sign change can be detected by performing the Hadamard transform and measuring, as can be seen explicitly by computing the state after the Hadamard transform at checkpoint 2:

$$\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\phi_2}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$} = {1\over\sqrt{2}}\left( i^{0*2^0*(a_1*2^1+a_0*2^0)}\mbox{$\vert\hs... ...hfrak{1}}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$} \right)$$

$$= \mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{a_0}\mbox{$\... ...frak{1}}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$} \right).$$ (59)

The phases still show a dependence on $a_0$ via the terms $i^{b_0*2^0*a_0*2^0} = i^{b_0a_0}$. The purpose of the phase shift gate conditioned on the measurement outcome is to remove that dependence. The result is the following state on the remaining qubit at checkpoint 3:

$$\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\phi_3}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$} = {1\over\sqrt{2}}\left( i^{0*2^0*a_1*2^1}\mbox{$\vert\hspace*{-3pt... ...hfrak{1}}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$} \right)$$

$$= {1\over\sqrt{2}}\left( \setlength{\strutdepthdim}{\depthof{$i^{0*... ...hfrak{1}}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$} \right)$$

$$= {1\over\sqrt{2}}\left( \setlength{\strutdepthdim}{\depthof{$i^{0*... ...hfrak{1}}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}\right).$$ (60)

The final Hadamard transform followed by a measurement therefore results in the bit $a_1$, as desired.

The elements that we used to determine the order of $8$ modulo $15$ can be combined and generalized to determine the order of any $q$ modulo $N$ with $\textrm{gcd}(q,N)=1$. The general network is shown in Fig. 10. Two features of the generalization are not apparent from the example. First, in order for the quantum network to be efficient, an efficient implementation of the controlled ${\hat f}^{2^l}$ operation is required. To obtain such an implementation, first note that to calculate $f^{2^l}(x)=q^{2^l}x\;\mathrm{mod}\;N$ it suffices to square $q$ repeatedly modulo $N$ using $\left(q^{2^m}\right)^2\;\mathrm{mod}\; N=q^{2^{m+1}}\;\mathrm{mod}\;N$ until we obtain $q^{2^l}\;\mathrm{mod}\;N$. The result is then multiplied by $x \;\mathrm{mod}\;N$. This computation is efficient. For any given $q$, it can be converted to an efficient network consisting of Toffoli and controlled-not gates acting on the binary representation of $x$. The conversion can be accomplished with standard techniques from the theory of reversible classical computation. The result is an efficient network for ${\hat f}^{2^l}$. Basic network theory can then be used to implement the controlled version of this operation [21].

The understand the second feature, note that we were lucky that the order of $8$ modulo $15$ was a power of $2$, which nicely matched the measured Fourier transform we constructed on two qubits. The measured Fourier transform on $m$ ancilla qubits can detect exactly only eigenvalues that are powers of the $2^{m}$'th root of unity $e^{i\pi/2^{m-1}}$. The phase kicked back by the controlled operations corresponds to a $k$'th root of unity. Given a Fourier state on the cycle of $q\;\mathrm{mod}\;N$, the resulting state on the ancilla qubits has phases that go as powers of a $k$'th root of unity. Fortunately, the ancilla's Fourier basis is such that the measured Fourier transform picks up primarily those basis states whose generating phase is close to the kick back phase. Thus we are likely to detect a nearby $\omega=e^{i\,l\pi/2^{m-1}}$. It is still necessary to infer (a divisor of) $k$ from knowledge of such an $\omega$. Since we know that the order $k$ is bounded by $N$, the number of possible phases kicked back that are near the measured $\omega$ is limited. To ensure that there is only one possible such phase, it is necessary to choose $m$ such that $2^m > N^2$. See also the caption of Fig. 10.

FIG. 8: Network for quantum order finding and phase estimation. The number $m$ of qubits used for the phase kick back has to be chosen such that $m>2*\log_2(k_u)$, where $k_u$ is a known upper bound on the order $k$ of $q\;\mathrm{mod}\;N$. Because $N>k$, one can set $m=2\lceil\log_2(N)\rceil$, where $\lceil x\rceil$ is the least whole number $s\geq x$. There is an eigenvalue $\lambda_l=e^{i\, 2l\pi/k}$ of one of the Fourier eigenvectors associated with the cycle of $q\;\mathrm{mod}\;N$ such that the number $a$ whose binary digits are the measurement outcomes satisfies $e^{i\pi a/2^{m-1}}\approx e^{i\,2\pi l/k}$. More precisely, with probability above $.405$, there exists $l$ such that $\vert a/2^{m}-l/k\vert\leq 1/2^{m+1}$ [16]. Since any two distinct rational numbers with denominator at most $k_u$ differ by at least $1/k_u^2 > 2/2^{m+1}$, the theory of rational approximations guarantees that we can uniquely determine the number $l/k$. There is an efficient classical algorithm based on continued fractions that computes $r$ and $s$ with $r/s=l/k$ and $s=k/\textrm{gcd}(l,k)$. The probability that $\textrm{gcd}(l,k)=1$ is at least $1/(\log_2(k)+1)$, in which case we learn that $s=k$, and this is the order of $q\;\mathrm{mod}\;N$. Note that the complexity of the network depends on the complexity of implementing the controlled ${\hat f}^{2^l}$ operations. Because these operations can be implemented efficiently, the network and hence the determination of the order of $q\;\mathrm{mod}\;N$ are efficient in the sense that on average, polynomial resources in $\log_2(N)$ suffice.