The Factoring Problem: Sampling Estimates to an Integer Multiple of k/r

In this section, it will be shown that the problem of finding the order \(r\) satisfying \(x^r=1(mod\hspace{1mm} N)\) for some coprime integers \(x\) and \(N\), can be solved through classical means provided with random samples of integer multiples \(k/r\) of \(1/r\).  Furthermore, a quantum algorithm will be constructed based off of the eigenvalue estimation algorithm which can efficiently sample estimates of these random integer multiples of \(1/r\). The results obtained from these sub-routines can then be used to factor \(N\) via the reductions described in the previous section.

Let \(r\) be some positive integer and consider the set \(\{k/r\hspace{1mm}|\hspace{1mm}k\in\mathbb{Z}\}\) consisting of integer multiples of \(1/r\). Now let \(k_1/r\) and \(k_2/r\) be two random elements from this set, and suppose the integer \(r\) is unknown. Given the values of the \(k_i/r\) it may not be possible to determine the value of \(r\) because the fractions may or may not be simplified into lower terms leaving a certain ambiguity in determining \(r\). However, if two other fractions can be found of the form \(c_1/r_1\) and \(c_2/r_2\) such that \(gcm(c_1,r_1)=gcm(c_2,r_2)=1\) with \(c_1/r_1=k_1/r\) and \(c_2/r_2=k_2/r\), then it is possible to determine the value of \(r\). With these conditions, the fractions \(c_1/r_1\) and \(c_2/r_2\) are both simplified to lowest terms so \(r_1\) and \(r_2\) can be uniquely determined. This would in turn determine \(r\) since \(lcm(r_1,r_2)=r\), where \(lcm(r_1,r_2)\) denotes the least common multiple of \(r_1\) and \(r_2\).

 The classical continued fractions algorithm \cite{hardy} (although not discussed here for the sake of brevity), can be used to find fractions of the type \(c_1/r_1\) and \(c_2/r_2\) provided with some random multiples \(k_1/r\) and \(k_2/r\), and can do so efficiently with a time complexity in \(O(log^2r)\). Making use of this technique will be essential in the post-processing required to determine orders after the quantum part of the algorithm is applied.

The problem remains to have the ability to randomly sample integer multiples \(k/r\) of \(1/r\). Actually, as a consequence of the continued fractions algorithm it will suffice to obtain an estimate of \(k/r\) to a certain degree of precision in order to arrive at the fraction \(c_1/r_1\). This motivates the following problem.

Sampling Estimates to random integer multiples of 1/r

Input: Integers \(x\) and \(N\) such that \(gcd(x,N)=1\)

Problem: Output a number \(y\in\{0,1,\dots,2^{n}-1\}\) such that for each \(k\in\{0,1,\dots,r-1\}\), the probability \(p\) such that \(\left| \frac{y}{2^n}- \frac{k}{r}\right|\leq \frac{1}{2r^2}\) is \(p\geq\frac{c}{r}\) for some constant \(c>0\), where \(r\) denotes the unknown order of \(x\).

The distance constraint required in the problem statement ensures that the estimate meets a certain degree of precision in order to yield appropriate results. In addition, there is  a probability constrained present to make sure such a sampling is faithful in practice.

To aid in solving the sampling problem, define the operator given by
\[U_x: \left|s\right>\mapsto \left|sx (mod\hspace{1mm}N)\right>.\] 
with the assumption that \(x\) is coprime to \(N\) such a map always has a well-defined inverse so that \(U_x\) in indeed a unitary operator. The order \(r\) of \(x\) is reflected in the  action of the operator \(U_x\) since \(x^r=1(mod\hspace{1mm} N)\) and
\[U_x^r\left|s\right>=\left|sx^r (mod\hspace{1mm}N)\right>=\left|s\right>.\]
 This implies that the eigenvalues of \(\left|s\right>\) will actually be \(r^{th}\) roots of unity of the form \(e^{i2\pi k/r}\) for integers \(k\in\{0,1,\dots, r-1\}\).

 Now, consider the state
\[\left|u_k\right>=\displaystyle\frac{1}{\sqrt{r}}\displaystyle\sum\limits_{s=0}^{r-1}e^{-i2\pi \frac{k}{r} s}\left|x^s (mod\hspace{1mm}N)\right>.\]
Then observe that
\[\begin{array}{r l}
U_x\left|u_k\right>=&\displaystyle\frac{1}{\sqrt{r}}\displaystyle\sum\limits_{s=0}^{r-1}e^{-i2\pi \frac{k}{r} s}U_x\left|x^s (mod\hspace{1mm}N)\right> \\
=& \displaystyle\frac{1}{\sqrt{r}}\displaystyle\sum\limits_{s=0}^{r-1}e^{-i2\pi \frac{k}{r} s}\left|x^{s+1} (mod\hspace{1mm}N)\right> \\
=& \displaystyle\frac{e^{i2\pi \frac{k}{r}}}{\sqrt{r}}\displaystyle\sum\limits_{s=0}^{r-1}e^{-i2\pi \frac{k}{r} (s+1)}\left|x^{s+1} (mod\hspace{1mm}N)\right>\\
=&e^{i2\pi \frac{k}{r}}\left|u_k\right>,
\end{array}\]
where the last identity follows from \[e^{i2\pi \frac{k}{r}r}\left|x^r (mod\hspace{1mm}N)\right>=e^{i2\pi \frac{k}{r}0}\left|x^0 (mod\hspace{1mm}N)\right>=\left|1 (mod\hspace{1mm}N)\right>.\] Hence, the \(\left|u_k\right>\) is an eigenstate of \(U_x\) with eigenvalue \(e^{i2\pi \frac{k}{r}}\).

 If such a state \(\left|u_k\right>\) was provided, then the eigenvalue estimation algorithm can be implemented on the input state \(\left|0\right>\left|u_k\right>\) to yield the output \(\left|\tilde{k/r}\right>\left|u_k\right>\). Then upon measuring the first register an estimate \(\tilde{k/r}\) of some integer multiple of \(1/r\) could be determined.  The issue here is that, since \(r\) is originally unknown, the state \(\left|u_k\right>\) cannot be prepared directly because it is defined in terms of \(r\). Fortunately,  such a state does not need to be constructed directly in order to effectively sample estimate to an integer multiple of \(1/r\). For consider the following equally weighted superposition of all \(r\) states \(\left|u_k\right>\)
\[\begin{array}{r l}
\displaystyle\frac{1}{\sqrt{r}}\displaystyle\sum\limits_{k=0}^{r-1}\left|u_k\right>=& \displaystyle\frac{1}{\sqrt{r}}\displaystyle\sum\limits_{k=0}^{r-1}\displaystyle\frac{1}{\sqrt{r}}\displaystyle\sum\limits_{s=0}^{r-1}e^{-i2\pi \frac{k}{r} s}\left|x^s (mod\hspace{1mm}N)\right> \\
=& \displaystyle\frac{1}{r}\displaystyle\sum\limits_{s=0}^{r-1}\left(\displaystyle\sum\limits_{k=0}^{r-1}e^{-i2\pi \frac{k}{r} s}\right)\left|x^s (mod\hspace{1mm}N)\right>
\end{array}\]
The amplitude \(\alpha_1\) of the state \(\left|1\right>=\left|x^0 (mod\hspace{1mm}N)\right>\) in the above superposition. Notice this occurs when \(s=0\) since \(x^0=1\). So the amplitude is therefore
\[\alpha_1=\displaystyle\frac{1}{r}\displaystyle\sum\limits_{k=0}^{r-1}e^{-i2\pi \frac{k}{r} 0}=\displaystyle\frac{1}{r}\displaystyle\sum\limits_{k=0}^{r-1}1=1.\]
Since the superposition satisfies the normalization constraint, the amplitudes of all other states \(\alpha_s\) for \(s \neq 0\) must be zero. Hence,
\[\displaystyle\frac{1}{\sqrt{r}}\displaystyle\sum\limits_{k=0}^{r-1}\left|u_k\right>=\left|1\right>\]  and this superposition is really just the computational basis state \(\left|1\right>\) in disguise.
 
  If instead this superposition was input into the eigenvalue estimation algorithm, then some superposition of states corresponding to estimates of integer multiples of \(1/r\) will be output. This is ultimately a consequence of the linearity of the operator implementing the eigenvalue estimation algorithm.  More explicitly, the action of the eigenvalue algorithm when the target register is prepared in the superposition consisting of  equally weighted eigenstates, outputs an equally weighted superposition of estimates of integer multiples of \(1/r\):
\[\left|0\right>\left|1\right>=\displaystyle\frac{1}{\sqrt{r}}\displaystyle\sum\limits_{k=0}^{r-1}\left|0\right>\left|u_k\right> \mapsto \displaystyle\frac{1}{\sqrt{r}}\displaystyle\sum\limits_{k=0}^{r-1}\left|\tilde{k/r}\right>\left|u_k\right>.\]
By measuring the control register some state \(\left|\tilde{k/r}\right>\) corresponding to an integer \(x\) will be observed with equal probability such that \(x/2^n\) is an estimate of an integer multiple \(\frac{k}{r}\). Therefore, a uniformly random integer multiple of \(1/r\) can be sampled. A circuit depicting the algorithm uses to sample estimates of a random integer multiple of \(1/r\) is shown in the figure below. Having found such samples, allows the order \(r\) to be determined using the continued fractions algorithm. Then, this order \(r\) can be used to find a non-trivial factor of the integer \(N\) as described through the classical methods involved in the reduction of the problem.


(A circuit for the problem of sampling random integer multiples of \(1/r\). This circuit is analogous to the general circuit for the eigenvalue estimation problem shown here, except here the controlled \(-U_{x}^{x}\) operation is defined differently. In this circuit, the input in the target register is prepared to be in the state \(\left|1\right>\) instead of an eigenstate of \(U_x\). Consequently the output in the control register is a superposition of estimates \(\left|\tilde{k/r}\right>\) of integer multiples of \(1/r\).)


This circuit is nearly identical to the circuit presented for the general eigenvalue estimation algorithm. Here, the controlled\(-U_{x}^{x}\) gate is supposed to signify an analogous sequence of controlled \(-U_{x}^{2^s}\) operations, where \(s\) ranges from \(0\leq s \leq r-1\). Since the action of the \(U_x\) gate is defined to multiply a basis state by \(x(mod\hspace{1mm}N)\), a natural way to compute the \(c-U_x^{2^s}\) gate for some \(s\) would be to simply apply the \(c-U_x\) gate \(2^s\) times. This, however, would not be efficient as it requires an exponential number of operations to implement. Instead, observe that by applying a similarly defined gate \(c-U_{x^{2^s}}\) accomplishes an equivalent operation and only needs to be applied a single time. Moreover, calculating the value of \(x^{2^s}\) by repeatedly squaring \(x^2\) modulo \(N\) can be done classically with only \(s\)-many multiplications.

 To be more rigorous, it can be shown that the \(c-U_{x}^{x}\) operation can be computed with time in \(O((logN)^2loglogNlogloglogN)\).\cite{mosca} Recall that the \(QFT\) and \(QFT^{-1}\) can each be computed in time \(O((logN)^2)\). Therefore, the whole sampling problem can be implemented efficiently in this case with time \(O((logN)^2loglogNlogloglogN)\). When compared to the classical complexity of the same problem the best known bounds are in \(e^{O((logN)^{1/2}(loglogN)^{1/2})}\). Thus, the quantum algorithm can perform exponentially faster than the classical when trying to factor integers.

It is worth mentioning that the approach taken by Shor in his factoring algorithm \cite{shor} involved a slightly different analysis. However, when comparing his method to the one outlined here it can be seen that the main different results from analyzing the problem in a different basis.

The Factoring Problem: The Reduction of Factoring to Order-finding

For any positive integer \(N\), the fundamental theorem of arithmetic says that \(N\) can be expressed as a product of prime numbers alone. That is, there exist  distinct prime numbers \(p_i\) and positive integers \(q_i\) such that
\[N=p_1^{q_1}p_2^{q_2}\dots p_m^{q_m}.\]
 The factoring problem can thus be phrased as follows.

The Factoring Problem

Input: A positive integer \(N\).

Problem: Determine distinct prime numbers \(p_i\) and integers \(q_i\) such that  \[N=p_1^{q_1}p_2^{q_2}\dots p_m^{q_m}.\]

 The factoring problem becomes more or less difficult depending on the nature of the integer \(N\) to be factored. If \(N\) is even, then \(2\) will always be a factor of \(N\). Moreover, some power of \(2\)  may be a factor of \(N\), and each such power of \(2\) will also be a factor of \(N\). Therefore, assume \(N\) is odd so that \(2\) is not a factor of \(N\).  A slightly harder case is if \(N=p^q\) for some odd prime \(p\) and integer \(q\). However, even this scenario is easy to solve classically because it must always be the case that \(q\leq log_2(N)\). So by simply computing the first \(log_2(N)\) roots of \(N\), say \(N^{1/k}\) for some \(k\leq log_2(N)\), and then checking to see if \(N^{1/k}\) is a prime number determines a \(p\) such that \(p^k=N\). This test would need to be repeated at most \(log_2(N)\) times, and since the problem of determining whether some integer is prime is in \(\mathbf{P}\) the problem of finding a prime factor \(p\) such that \(p^q=N\) will have a time complexity corresponding to some polynomial in \(log_2(N)\).

 The remaining case to consider in factoring \(N\) is when \(N\) is an odd, non-prime power--that is, \(N\) has at least two distinct  odd prime factors. In this case the integer can be expressed as \(N=N_1N_2\) for two positive integers \(N_1\) and \(N_2\) both less than \(N\). Each \(N_i\) is a factor of \(N\), which can in turn be factored further if the \(N_i\) is not itself a prime integer. Hence, the problem of factoring \(N\)  in this case can be reduced the problem of splitting an odd, non-prime power \(N\).

Splitting an Odd, Non-prime Power

Input: An odd positive integer \(N\) such that \(N\) is not a power of some prime.

Problem: Determine positive integer factors \(N_1\) and \(N_2\) less than N such that \(N=N_1N_2\).


 For any factorization of \(N\) as \(N=N_1N_2\), it must be the case that both \(N_i\) are such that \(N_i\leq \sqrt{N}\). Therefore, the problem of completely factoring an integer \(N\) can be reduced to splitting some odd, non-prime integer \(N\) at most \(log_2(N)\) times. This reduction can be done classically and deterministically placing the complexity of such a reduction in the class \(\mathbf{P}\).
 
  Finally, suppose we are in the scenario where \(N\) is an odd, non-prime power. Denote by \(gcd(x,y)\) the greatest common divisor of two integers \(x\) and \(y\), and call two numbers coprime if and only if \(gcd(x,y)=1\). Let \(N\)  be some integer to be factored, and \(x\) be an integer such that \(0<x<N\). If \(N\) and \(x\) are not coprime, then \(gcd(x,N)>1\) will be a nontrivial factor of \(N\). Moreover, \(gcd(x,N)\) can be computed efficiently through classical means such as the extended Euclidean algorithm in time \(O(log_2(N))\).\cite{knuth}

 Instead, suppose that some integer \(0<x<N\) is chosen such that \(x\) and \(N\) are coprime. Then since \(gcd(x, N)=1\), a non-trivial factor cannot be found by simply evaluating \(gcd(x,N)\). Then for \(x\) coprime to \(N\), consider the following sequence of numbers
\[1=x^0 (mod\hspace{2mm}N),\hspace{2mm} x^1 (mod\hspace{2mm}N),\hspace{2mm} x^2 (mod\hspace{2mm}N), ...\]
This sequence will necessarily begin to repeat itself after finitely many terms. That is, the function
 \[f_{x,N} : \{0,1,2,...\} \rightarrow \{0,1,2,...\},\] sending \[a\mapsto x^a (mod\hspace{2mm}N),\]
has a period \(r\), which is the smallest positive integer \(r\) that satisfies \(f_{x,N}(a+r)=f_{x,N}(a)\) for all \(a\). Such an \(r\) also satisfies \(x^r=1 (mod\hspace{2mm}N)\), and will be called the order of \(x\).

Suppose that the period \(r\) of the function \(f_{x,N}(a)=x^a (mod\hspace{2mm}N)\) is given. In addition, suppose that \(r\) is an even number. The it follows that
\[x^r =1 (mod\hspace{2mm}N) \Longleftrightarrow (x^{ \frac{r}{2}})^2 = 1 (mod\hspace{2mm}N) \Longleftrightarrow (x^{ \frac{r}{2}})^2-1 = 0 (mod\hspace{2mm}N)  \Longleftrightarrow\]
\[ (x^{\frac{r}{2}} +1)(x^{ \frac{r}{2}}-1)= 0 (mod\hspace{2mm}N)  \Longleftrightarrow (x^{ \frac{r}{2}} +1)(x^{ \frac{r}{2}}-1) = kN\] for some \(k\).

Since \(x>1\), this implies both \(x^{ \frac{r}{2}} +1>1\) and \(x^{ \frac{r}{2}}-1>1\), so that \(k>0\). Therefore, \(x^{ \frac{r}{2}} +1\) and \(x^{ \frac{r}{2}}-1\) must share a factor with \(N\). Now suppose that \((x^{ \frac{r}{2}} +1)\) and \((x^{ \frac{r}{2}}-1)\) are not multiples of \(N\). Then the common factor shared with \(N\) must be less than \(N\). Calculating \(gcd(x^{ \frac{r}{2}} +1, N)\) and \(gcd(x^{ \frac{r}{2}}-1, N)\) would then yield two nontrivial factors of \(N\). It has been shown that if we know \(x\) and \(r\) meeting the criterion above, then we could effectively determine nontrivial factors of \(N\). Therefore, the problem of splitting an odd, non-prime integer \(N\) can be reduced to the problem of finding the order \(r\) of a random element \(x\) \(mod\hspace{2mm}N\).

The Order Finding Problem

Input: Integers \(x\) and \(N\) such that \(gcd(x,N)=1\)

Problem: Find the order \(r\) of \(x\) \(mod\hspace{2mm}N\), where \(x^r=1 (mod\hspace{2mm}N)\).

In this reduction it was required that \(r\) be an even number so that \(r/2\) is also an integer. Since \(x\) such that \(0<x<N\) is initially chosen at random, it is possible to choose a \(x\) where \(r\) is not even or that at least one of \((x^{ \frac{r}{2}} +1)\) and \((x^{ \frac{r}{2}}-1)\) is a multiple of \(N\). Such an \(x\) would not yield a factor using the method described above. In this case, to successfully factor \(N\) by reducing the problem to order finding, another \(x\) would have to be chosen that does meet the necessary criterion. However, it can be shown that with probability greater than \(1/2\), an \(x\) can be chosen such that \(r\) is even and \((x^{ \frac{r}{2}} +1)\) and \((x^{ \frac{r}{2}}-1)\) are not multiples of \(N\). This reduction of factoring to order finding has a probabilistic classical algorithm placing the problem corresponding to this reduction in the complexity class \(\mathbf{BPP}\).\cite{mosca}

The previous arguments only showed that an integer \(N\) can be factored if the order \(r\) of some integer \(x\) coprime to \(N\) is given, but did not offer any means of actually finding such an \(r\). If an algorithm exists for finding these orders, and if it can accomplish the task efficiently, then an efficient algorithm for the factoring problem would follow through the series of reductions since each reduction cold be done efficiently as well. Its important to note that all these previous reductions are classical, and either deterministic or probabilistic. That is, no quantum algorithm has been used thus far in attempting to solve the factoring problem.  The next section will explicitly show how to find orders using an efficient quantum algorithm making use of the eigenvalue estimation algorithm, which will in turn solve the factoring problem efficiently.

The Factoring Problem

Given some positive integer \(N\) consider the problem of determining  its factors. Factors of \(N\) are just the integers that evenly divide \(N\). For a number that is not too large this calculation seems reasonable. The factoring problem can naturally be phrased as a decision problem, in which case the question is: `Does \(N\) have any nontrivial factors  less than some other integer \(p\)?'. As a decision problem, this problem can always be decided in the sense that there always exists a way in principle to answer this question with a `yes' or `no' answer. For instance, some algorithm can simply perform an exhaustive test to check whether or not each integer less than \(N\) divides \(N\) evenly. Suppose now that the number N is some large 500 digit number, or even larger still! Unless this algorithm was able to make some lucky guesses at what the factors may be, this task would take an algorithm like this an impractical amount of time to accomplish. Without prior knowledge to any properties the number N may have, factoring a large N using a computer takes a long time since the computer has to test many potential factors to actually find them.

  On the other hand, the task of simply multiplying two numbers together is a task that computers can efficiently solve. The difference in these two computational tasks, which is the ease in multiplying and the difficulty in factoring, forms the basis of a widely used cryptographic scheme known as  the RSA protocol.\cite{rivest} The RSA protocol is used mainly for purposes of digital security such as banking and other internet transactions. However, for this security, the implementors of RSA are relying on the assumption that no one has an algorithm or  computer fast enough to successfully factor N. For all practical purposes this assumption is reasonable since no classical algorithm is known which enables  efficient factoring. The current best being the number field sieve.\cite{lenstra}

In 1994, Peter Shor \cite{shor} constructed an algorithm to be implemented on a quantum computer that can factor a large integer exponentially faster than the best classical algorithms. This is interesting because Shor's algorithm provides evidence that quantum computers may have greater capabilities than traditional classical computers. One of these being the ability for quantum computers to render the RSA protocol obsolete. The running time of the algorithm is bounded by a polynomial in \(n\), where \(n\approx log(N)\) is the number of qubits used, thus placing the problem of factoring in the complexity class \(\mathbf{BQP}\). Although this problem is in \(\mathbf{NP}\) since its easy to verify that a factor is indeed a factor, it is not known if it is also in \(\mathbf{BPP}\) or even \(\mathbf{P}\). In other words, Shor's quantum algorithm is exponentially faster than any classical algorithm that is known at present.

 The essence of Shor's algorithm lies in the fact that the problem of factoring an integer can be reduced to the problem of finding the period of a certain function, which is a problem that can be  efficiently solved on a quantum computer by making use of the eigenvalue estimation algorithm as it will be shown. This reduction can be done classically, meaning that there already exists known efficient and classical algorithmic means for factoring an integer provided with the period of a certain function. To understand why these reductions work requires some number theoretic results. The rest of this section will be invested on explaining the details of this reduction and how a quantum algorithm enables an efficient solution.

Eigenvalue Estimation

This section will combine the technique deployed in the phase kick-back algorithms, and the method of phase estimation to solve a problem of a similar nature. Here, the objective will be to determine the eigenvalue of the form \(e^{i2\pi\omega}\) of a eigenvector \(\left|\phi\right>\) associated to a particular unitary operator \(U\). In the eigenvalue estimation problem, the details of the unitary operator \(U\) and eigenvector \(\left|\phi\right>\) are unknown and not of main concern. It is assumed that such a state is already provided as well as the means to operate on the state with a circuit that implements \(U\).

Eigenvalue Estimation Problem

Input: A quantum circuit implementing a unitary operator \(U\) with an eigenvector \(\left|\phi\right>\) and associated eigenvalue \(e^{i2\pi\omega}\).

Problem: Determine an estimate for the unknown parameter \(\omega\) which determines the eigenvalue.


 Since \(\left|\phi\right>\) is an eigenvector of \(U\) with eigenvalue \(e^{i2\pi\omega}\), then by definition \(U\left|\phi\right>=e^{i2\pi\omega}\left|\phi\right>\). Define a controlled\(-U\) operation, \(c-U\) where a single qubit is used as the control register.  Then if the target register is prepared in the state \(\left|\phi\right>\), the action of \(c-U\) is given by
\[\begin{array}{r l}
c-U\left|0\right>\left|\phi\right>=&\left|0\right>\left|\phi\right>, \\

c-U\left|1\right>\left|\phi\right>=&e^{i2\pi\omega}\left|1\right>\left|\phi\right>.
\end{array}.\]
Thus, the phase factor \(e^{i2\pi\omega}\) can be associating to the control qubit as in the phase kick-back algorithms. Now, denote the action of applying \(c-U\) \(m\) times as \(c-U^m\), and observe that \(c-U^m\) acts as follows
\[\begin{array}{r l}
c-U^m\left|0\right>\left|\phi\right>=&\left|0\right>\left|\phi\right>, \\

c-U^m\left|1\right>\left|\phi\right>=&e^{i2\pi\omega m}\left|1\right>\left|\phi\right>.
\end{array}.\]
This follows straight from the definition \(\left|\psi\right>\) being an eigenvector of \(U\) with eigenvalue \(e^{i2\pi\omega}\), and since a product of exponentials is equivalent to a single exponential whose argument is the sum of the arguments of the exponentials.

The ability to perform the action of \(c-U^m\) for various values of \(m\) is helpful in solving the eigenvalue estimation problem, because this will allow the value of \(\omega\) to be encoded into the relative phases of states. If the state
\[\left|\psi\right>=\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{j=0}^{2^n-1}e^{i2\pi \omega j}\left|j\right>,\]
can be prepared, then as done in the phase estimation algorithms the value of \(\omega\) can be estimated by applying the \(QFT^{-1}\) to the state \(\left|\psi\right>\). However, since the value of \(\omega\) is unknown this state cannot be prepared directly. Fortunately, the ability to perform \(c-U^m\) operations on the state \(\left|\phi\right>\), which is given, can be used to construct the state \(\left|\psi\right>\). Therefore, once this state \(\left|\psi\right>\) has been constructed and the phase estimation algorithm is performed by making use of \(QFT^{-1}\), information about \(\omega\) will be obtained enabling an estimate of the eigenvalue.

A circuit can be constructed using \(c-U^m\) gates that takes some basis state, say \(\left|\mathbf{0}\right>\in\mathcal{H}^{2^n}\), and produces the state
\[\begin{array}{r l}
\left|\psi\right>=&\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{j=0}^{2^n-1}e^{i2\pi \omega j}\left|j\right> \\
= &\left( \displaystyle\frac{\left|0\right>+e^{i2\pi \omega2^{n-1}}\left|1\right>}{\sqrt{2}}\right)\otimes\left( \displaystyle\frac{\left|0\right>+e^{i2\pi \omega2^{n-2}}\left|1\right>}{\sqrt{2}}\right)\otimes\dots\otimes\left( \displaystyle\frac{\left|0\right>+e^{i2\pi \omega2^{0}}\left|1\right>}{\sqrt{2}}\right) \\
=&\left|\psi_1\right>\otimes\left|\psi_2\right>\otimes\dots\otimes\left|\psi_n\right>.
\end{array}.\]
To accomplish this, first observe the action of \(c-U^m\) on a qubit in an equally weighted superposition in the control register, and the eigenstate \(\left|\phi\right>\) in the target register
\[c-U^m\left(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\right)\left|\phi\right>=\left(\displaystyle\frac{\left|0\right>+e^{i2\pi\omega m}\left|1\right>}{\sqrt{2}}\right)\left|\phi\right>.\]
Then by setting \(m=2^n-k\) for integers \(1\leq n\leq n\), it follows that
\[c-U^{2^{n-k}}\left(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\right)\left|\phi\right>=\left(\displaystyle\frac{\left|0\right>+e^{i2\pi\omega 2^{n-k}}\left|1\right>}{\sqrt{2}}\right)\left|\phi\right>=\left|\psi_k\right>,\]
which is the state of the \(k^{th}\) qubit in the register of the state \(\left|\psi\right>\).

Therefore, first take a control register in the basis state \(\left|\mathbf{0}\right>\in\mathcal{H}^{2^n}\) and apply the Hadamard gate to each qubit putting putting the register in an equally weighted superposition
\[H^{\otimes n}\left|\mathbf{0}\right>=\displaystyle\bigotimes\limits_{k=1}^{n}\left(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\right).\] Then by applying a \(c-U^{2^{n-k}}\) multiple times, for \(1\leq k\leq n\), each time controlled by the \(k^{th}\) qubit in the control register the state \(\left|\psi\right>\) is produced:
\[\displaystyle\bigotimes\limits_{k=1}^{n}\left[\left(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\right)\left|\phi\right>\right]=\displaystyle\bigotimes\limits_{k=1}^{n}\left|\psi_k\right>\left|\phi\right>=\left|\psi\right>.\]


(The circuit on the left implements the series of \(c-U^{2^{n-k}}\) gates controlled by the \(n\) qubits in the control register, where each is in the superposition \( \frac{1}{\sqrt{2}}\left(\left|0\right>+\left|1\right>\right)\) and the target register in the eigenstate \(\left|\phi\right>\), producing the state \(\left|\psi\right>\) as output in the control register. The controlled gate labelled by \(U^x\) in the circuit shown below is the shorthand symbol that represents the circuit above.)




Before giving a complete construction of a circuit that solves the eigenvalue estimation problem, consider the circuit shown that represents just the sequence of \(c-U^m\) gates acting on the states described above. As a notational convenience, this entire circuit will be represented in shorthand by the controlled\(-U^x\) gate also shown above. Then the output \(\left|\psi\right>\) provided in the control register after the controlled\(-U^x\) is applied to \(H^{\otimes n}\left|\mathbf{0}\right>\left|\phi\right>\) can be used as the input to the phase estimation algorithm. This is done by applying \(QFT^{-1}\) to the control register, which produces some state \(\left|x\right>\) such that \(x/2^m=\tilde{\omega}\) is an estimate of the phase parameter  \(\omega\) in the state \(\left|\psi\right>\). This estimate can then be used to determine an estimate \(e^{i2\pi\tilde{\omega}}\) of the eigenvalue. The circuit solving the eigenvalue estimation problem is shown in the figure below. Notice that the first gate is given by a \(QFT\) acting on the control register, since this gate's action is equivalent to the action of \(H^{\otimes n}\) on a control register where every qubit is in the state \(\left|0\right>\). By doing this, a certain symmetry in the circuit and algorithm is highlighted that is similar to many of the previously introduced algorithms. In this case, it is seen that the \(QFT\) plays an analogous role of the Hadamard gate \(H^{\otimes n}\) in its use to encode and decode information after some controlled gate is applied.

(A circuit for the eigenvalue estimation algorithm. The \(n\) qubit control register begins in the state \(\left|\mathbf{0}\right>\) and the target register in the eigenstate \(\left|\phi\right>\). First, the \(QFT\) is applied to the control register, followed by the controlled\(-U^x\) gate, and then the \(QFT^{-1}\) is applied to the control register. This produces some basis state \(\left|x\right>\) in the control register, which can then be used to estimate the eigenvalue through the phase parameter \(    \tilde{\omega}=x/2^n\).)

Since the \(QFT\) and \(QFT^{-1}\) can be implemented efficiently on a quantum computer, then provided with an eigenstate \(\left|\phi\right>\) and an efficient means to implement the controlled\(-U^x\), the eigenvalue estimation algorithm can solve the problem of estimating an eigenvalue efficiently.  The eigenvalue estimation problem is of a very general nature. After all, every unitary operator  acting on qubits has at least two eigenvalue/eigenvector pairs. Although this problem may still seem  of a somewhat contrived variety, the next section will reveal a remarkable application of the eigenvalue estimation algorithm to the problem of factoring integers efficiently.

Phase Estimation

The utility of the quantum Fourier transform \(QFT\) may not be immediately obvious. In this section, it will be shown that the \(QFT\) can be applied to some state containing unknown relative phase factors in order to determine information about the phase.  Let \(\omega=x/2^n\) for some positive integer \(x<2^n\) so that \(\omega=0.x_1x_2\dots x_n\), and suppose some state of the form
\[\left|\psi\right>=\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{j=0}^{2^n-1}e^{i2\pi \omega j}\left|j\right>=\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{j=0}^{2^n-1}e^{\frac{i2\pi xj}{2^n}}\left|j\right>\]
  is provided. Since the action of the \(QFT\) on the basis state \(\left|x\right>=\left|x_1x_2\dots x_n\right>\in\mathcal{H}^{2^n}\) is
  \[QFT\left|x\right>=\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{j=0}^{2^n-1}e^{\frac{i2\pi xj}{2^n}}\left|j\right>=\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{j=0}^{2^n-1}e^{i2\pi \omega j}\left|j\right>=\left|\psi\right>,\]
  then the inverse \(QFT^{-1}\) will map the state \(\left|\psi\right>\) to the basis state \(\left|x\right>\):
\[QFT^{-1}\left|\psi\right>=QFT\left(\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{j=0}^{2^n-1}e^{i2\pi \omega j}\left|j\right>\right) =\left|x\right>.\]
 If the value of \(\omega=x/2^n\) in the relative phases of \(\left|\psi\right>\) was unknown, then by simply applying the \(QFT\) to \(\left|\psi\right>\) and measuring yields the state \(\left|x\right>\), which can then be used to determine \(\omega\). This consequence motivates the phase estimation problem.

 Phase Estimation Problem

Input: A state \(\left|\psi\right>=\displaystyle \frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{j=0}^{2^n-1}e^{i2\pi \omega j}\left|j\right>\in\mathcal{H}^{2^n}\), where the phase parameter \(\omega \in [0,1)\in\mathbb{R}\) is unknown.

Problem:  Determine an estimate for the unknown  phase parameter \(\omega\).


The reason why an estimate the phase parameter \(\omega\) is desired in the phase estimation problem is because \(\omega\) may not be a rational number. In the case where \(\omega\) is an irrational number, the binary expansion \(\omega=x_1x_2x_3\dots\) is infinite. To determine \(\omega\) exactly would then require infinitely many bits of information. On the other hand, if \(\omega\) is a rational number then the binary expansion \(\omega=x_1x_2\dots x_n\) will eventually terminate after \(n\) digits. Even in this case the number of digits \(n\) in the expansion can be an arbitrary large number. Therefore, an estimate \(\tilde{\omega}=x_1x_2\dots x_k\) of \(\omega\) might still be necessary. In the phase estimation problem, how close an estimate \(\tilde{\omega}\) is to the parameter \(\omega\) is determined by the number of qubits used to express the state \(\left|\psi\right>\). The more qubits used, the closer the estimate will be to \(\omega\).

As previously shown, if \(\omega=x/2^n\) for some integer \(x<2^n\), then the inverse quantum Fourier transform \(QFT^{-1}\) can be used to determine \(x\) exactly. To solve the phase estimation problem for general \(\omega\),  some number of qubits \(n\) is chosen in advance that will determine the degree of accuracy in the estimate. Then when \(QFT^{-1}\) acting on \(n\) qubits is applied to the provided state \(\left|\psi \right>\), a state \(\left|x\right>\) is produced such that \(x/2^n=\tilde{\omega}\)  yields an estimate of \(\omega\). Therefore, the circuit that implements \(QFT^{-1}\) can be used to solve the phase estimation problem, which is shown in the figure below. Recall that the inverse of the circuit implementing some unitary operator like \(QFT\) is simply the same circuit with the order of the gates reversed, and  each gate is replaced with its inverse operation.



(The circuit for the phase estimation algorithm. This circuit is the \(QFT^{-1}\) circuit, which takes as input some state state \(\left|\psi\right>\) with a phase factor \(\omega\), and transforms it to the basis state \(\left|x\right>\in\mathcal{H}^{2^n}\) such that \(x/2^n=\tilde{\omega}\) is an estimate for the phase \(\omega\) up to \(n\) bits of accuracy. The \(QFT^{-1}\) circuit is equivalent to the circuit  that results from reversing the order of the gates in the \(QFT\) circuit, shown here, and replacing each gate with its inverse.)\label{fig:qftinverse}
\end{figure}

Since it, was already argued that the \(QFT\) can be implemented efficiently with a number of gates in \(O(n^2)\), and the \(QFT^{-1}\) requires the exact same number of gates, it follows that the size or time complexity of implementing the \(QFT^{-1}\) is also in \(O(n^2)\). Thus, the phase estimation algorithm just described is a quantum algorithm that solves the phase estimation problem in polynomial time, placing the problem into the complexity class \(\mathbf{BQP}\). Moreover, it can be justified further that the phase estimation algorithm will output \(x\) corresponding to the state \(\left|x\right>\) such that \(x/2^n=\tilde{\omega}\) is the closest estimate to \(\omega\) with a probability greater than \(4/\pi^2\).\cite{mosca} This estimate is optimal for a given number \(n\) of qubits used. That is \(\tilde{\omega}=x/2^n\) will be the closest multiple of \(1/2^n\) to \(\omega\).

 The phase estimation algorithm is an example of a problem that a quantum computer can solve more efficiently than any known classical algorithm. Recall, that it takes \(O(n2^n)\) steps to implement the classical discrete Fourier transform. Therefore any classical algorithm that were to solve the phase estimation problem using the Fourier transform would take exponentially longer. The quantum phase estimation algorithm  can be said to provide  a superpolynomial speed-up when compared to the classical context.