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.

The Quantum Fourier Transform Circuit

The quantum Fourier transform \(QFT\) was defined to map an arbitrary  computational basis state \(\left|j\right>\in\mathcal{H}^{2^n}\) to the state
\[\left|\psi\right>=QFT\left|j\right>=\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{k=0}^{2^n-1}e^{\frac{i2\pi jk}{2^n}}\left|k\right>.\]
In this section, it will be shown that this state \(\left|\psi\right>\) can be expressed as the tensor product of \(n\) qubits \(\left|\psi_i\right>\) so that
\[\left|\psi\right>=\left|\psi_1\right>\otimes\left|\psi_2\right>\otimes\dots\otimes\left|\psi_n\right>.\]
Such a construction will provide insight on how an explicit circuit can be constructed that implements the \(QFT\).

Before beginning, recall the equivalent means of representing the computational basis states of \(\bigotimes_{i=1}^{n}\mathcal{H}^2\) in the binary representation as \(\left|b_1b_2\dots b_n\right>\), for \(b_i\in\{0,1\}\), and  the decimal representation as \(\left|j\right>\), for an integer \(j\in{0,1,\dots,2^n-1}\), given by the map
\[\displaystyle\sum\limits_{i=1}^{n}b_i2^{n-i}=b_12^{n-1}+b_{2}2^{n-2}+...+b_{n-1}2+b_n=j.\]
 For some fraction \(\omega\in[0,1)\subset\mathbb{R}\), a binary representation can be defined for this decimal as \(\omega=0.x_1x_2\dots x_n\) for some \(n\) as the map
\[\omega=\displaystyle\sum\limits_{i=1}^{n}x_i2^{-i}=x_12^{-1}+x_22^{-2}+\dots+x_n2^{-n}.\] Instead the decimal \(\omega\) may be given by bitstrings that begin labelled with a higher index such as \(\omega=x_lx_{l+1}\dots x_n\) for some \(l>1\). In this case
\[\omega=\displaystyle\sum\limits_{i=l}^{n}x_i2^{-i+l-1}=x_l2^{-1}+x_{l+2}2^{-2}+...+x_n2^{-n+l-1}.\]
If \(\omega\) is a rational number, then its decimal representation is of finite length and the number of binary digits \(n\) of \(\omega=0.x_1x_2\dots x_n\) is determined by the number of bits needed to completely specify \(\omega\). Such a \(\omega\) always corresponds to the fraction \(\omega=x/2^n\) for some integer \(x\in\{0,1,2,\dots, 2^{n}-1\}\). On the other hand, if \(\omega\) is an irrational number then the binary representation \(\omega=0.x_1x_2x_3\dots \) will contain infinitely many bits \(x_i\) in the expansion. However, irrational numbers \(\omega= 0.x_1x_2x_3\dots \) can be approximated by a rational number \(\tilde{\omega}=0.x_1x_2\dots x_k\) for some \(k\), meaning the \(x_i\) of \(\tilde{\omega}\) coincide with the \(x_i\) of \(\omega\) up to the first \(k\) bits. In this context, \(\tilde{\omega}\) is called a rational approximation of \(\omega\) to \(k\) bits of accuracy.

Let \(k\) be some integer and consider the product of \(2^k\) with \(\omega=0.x_1x_2\dots x_n\)
\[2^k\omega=2^k\displaystyle\sum\limits_{i=1}^{n}x_i2^{-i}=x_12^{k-1}+x_{2}2^{k-2}+...+x_n2^{k-n}.\]
Suppose now that \(k\) is some positive integer such that \(1\leq k<n\). Then this summation can be regarded as two different sums, one over non-negative powers of \(2\) and the other over negative powers of \(2\):
\[\begin{array}{r l}
2^k\omega=2^k\displaystyle\sum\limits_{i=1}^{n}x_i2^{-i}= &
\displaystyle\sum\limits_{i=1}^{k}x_i2^{k-i}+\displaystyle\sum\limits_{i=k+1}^{n}x_i2^{k-i} \\
= & \left(x_12^{k-1}+x_{2}2^{k-2}+...+x_k2^{0}\right)+\left(x_{k+1}2^{-1}+x_{k+2}2^{-2}+...+x_n2^{-n}\right) \\
\equiv & x_1x_2\dots x_{k} + 0.x_{k+1}x_{k+2}\dots x_{n} \\
= & x_1x_2\dots x_{k}.x_{k+1}x_{k+2}\dots x_{n}.
\end{array}\]
Here, \(x_1x_2\dots x_{k}\) can be thought of as the integer part of the number \(2^k\omega\), and \(0.x_{k+1}x_{k+2}\dots x_{n}\) can be thought of as the fractional part of \(2^k\omega\).

This representation will be useful in the analysis to come, because of the consequences this has when considering the number \(e^{i2\pi(2^k\omega)}\) with \(\omega=0.x_1x_2\dots x_n\in[0,1)\) and \(k\geq 1\). Since \(e^{i2\pi z}=1\) for any integer \(z\), it follows that
\[\begin{array}{r l}
e^{i2\pi(2^k\omega)}=&e^{i2\pi( x_1x_2\dots x_{k}.x_{k+1}x_{k+2}\dots x_{n})} \\
&=e^{i2\pi(x_1x_2\dots x_{k}) }e^{i2\pi(0.x_{k+1}x_{k+2}\dots x_{n})} \\
&=e^{i2\pi z}e^{i2\pi(0.x_{k+1}x_{k+2}\dots x_{n})} \\
&=e^{i2\pi(0.x_{k+1}x_{k+2}\dots x_{n})},
\end{array}\]where \(z=x_1x_2\dots x_{k}\) is just some integer.

With these results in mind, the following identity will be proved which expresses the action of the \(QFT\) on a basis state \(\left|j\right>\in\mathcal{H}^{2^n}\) as the tensor product state of \(n\) qubits, where \(\left|j\right>=\left|j_1j_2\dots j_n\right>\) when represented in the binary representation. That is, if \(\left|\psi\right>=QFT\left|j\right>\), it will be shown that \(\left|\psi\right>=\left|\psi_1\right>\otimes\left|\psi_2\right>\otimes\dots\otimes\left|\psi_n\right>\) for some states \(\left|\psi_i\right>\in\mathcal{H}^2\).
In this tensor decomposition the state of each qubit is in some superposition and has a relative phase factor in terms of the bit string \(j_1j_2\dots j_n\). Showing this will ultimately be an  algebraic exercise in translating between the decimal and binary representation of basis states. Proceed as follows:
\[\begin{array}{r l}
\left|\psi\right>=QFT\left|j\right>=&\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{k=0}^{2^n-1}e^{\frac{i2\pi jk}{2^n}}\left|k\right> \\
=& \displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{k_1=0}^{1}\cdots \displaystyle\sum\limits_{k_n=0}^{1}e^{i2\pi j(\sum_{l=1}^nk_l2^{-l})}\left|k_1k_2\dots k_n\right> \\
=& \displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{k_1=0}^{1}\cdots \displaystyle\sum\limits_{k_n=0}^{1}\displaystyle\bigotimes\limits_{l=1}^{n}e^{i2\pi j k_l2^{-l}}\left|k_l\right> \\
=& \displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\bigotimes\limits_{l=1}^{n}\left[\displaystyle\sum\limits_{k_l=0}^{1}e^{i2\pi j k_l2^{-l}}\left|k_l\right>\right] \\
=& \displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\bigotimes\limits_{l=1}^{n}\left[\left|0\right>+e^{i2\pi j 2^{-l}}\left|k_l\right>\right] \\
=& \left( \displaystyle\frac{\left|0\right>+e^{i2\pi j2^{-1}}\left|1\right>}{\sqrt{2}}\right)\otimes\left( \displaystyle\frac{\left|0\right>+e^{i2\pi j2^{-2}}\left|1\right>}{\sqrt{2}}\right)\otimes\dots\otimes\left( \displaystyle\frac{\left|0\right>+e^{i2\pi j2^{-n}}\left|1\right>}{\sqrt{2}}\right) \\
=& \left( \displaystyle\frac{\left|0\right>+e^{i2\pi0.j_n}\left|1\right>}{\sqrt{2}}\right)\otimes\left( \displaystyle\frac{\left|0\right>+e^{i2\pi0.j_{n-1}j_n}\left|1\right>}{\sqrt{2}}\right)\otimes\dots\otimes\left( \displaystyle\frac{\left|0\right>+e^{i2\pi0.j_1j_2\dots j_n}\left|1\right>}{\sqrt{2}}\right).
\end{array}\]

This decomposition of \(\left|\psi\right>= \bigotimes_{i=1}^n\left|\psi_i\right>\) into the tensor product of the states \(\left|\psi_i\right>\) is useful because it shows that if its possible to construct a unitary operators \(U_i\) on the state space such that \(U_i\left|j_1j_2\dots j_n\right>=\left|j_1\right>\dots\left|j_{i-1}\right>\left|\psi_i\right>\left|j_{i+1}\right>\dots\left|j_n\right>\) for each \(i\in\{1,2,\dots n\}\), then the composition \(U_nU_{n-1}\dots U_1\) must be the unitary operator that performs the quantum Fourier transform \(QFT\):
\[QFT\left|j_1j_2\dots j_n\right>=U_{n}U_{n-1}\dots U_1\left|j_1j_2\dots j_n\right>.\]
If a circuit can be explicitly constructed that implements each \(U_i\) in terms  of elementary gates, then the composition of these circuits can be used to construct a circuit for the quantum Fourier transform.

In order to construct a circuit for each \(U_i\) define the single qubit gate \(R_k\) parameterized by an integer \(k\) and  defined by mapping the basis states as \(R_k\left|0\right>=\left|0\right>\) and \(R_k\left|1\right>=e^{i2\pi/2^k}\left|1\right>\). The matrix for \(R_k\) in the computational basis is given as
\[R_k=\begin{pmatrix}1 & 0  \\ 0 & e^{i2\pi/2^k}  \end{pmatrix},\]
 and it can be seen as adding a relative phase factor to a qubit  in some superposition
\[R_k\frac{1}{\sqrt{2}}\left(\left|0\right>+\left|1\right>\right)=\frac{1}{\sqrt{2}}(\left|0\right>+e^{i2\pi/2^k}\left|1\right>).\]
Also, define a two qubit controlled\(-R_k\) gate \(c_r-R_k\) acting in an ambient \(n\) qubit register, where the index \(r\) signifies that the \(r^{th}\) qubit in the register is to serve as the control qubit. The \(c_r-R_k\) gate applies the \(R_k\) gate to some qubit only if the qubit in the \(r^{th}\) register is in the state \(\left|1\right>\) and leaves the qubit unchanged if the control is in the state \(\left|0\right>\).

Consider the first qubit \(\left|j_1\right>\) in the \(n\) qubit basis state \(\left|j\right>=\bigotimes_{i=1}^{n}\left|j_i\right>\). Then applying the Hadamard gate to \(\left|j_1\right>\) gives
\[H\left|j_1\right>=\frac{1}{\sqrt{2}}(\left|0\right>+e^{i2\pi 0.j_1}\left|1\right>),\]
since \(e^{i2\pi 0.j_1}=1\) if \(j_1=0\) and \(e^{i2\pi 0.j_1}=-1\) if \(j_1=1\). Now, if a \(c_2-R_2\) gate is applied to \(H\left|j_1\right>\) while using the state \(\left|j_2\right>\) of the qubit in the \(2^{nd}\) register as the control qubit, then
\[\begin{array}{r l}
c_2-R_kH\left|j_1\right>=&c_2-R_k\frac{1}{\sqrt{2}}(\left|0\right>+e^{i2\pi 0.j_1}\left|1\right>) \\
=&\frac{1}{\sqrt{2}}(\left|0\right>+e^{i2\pi /2^2}e^{i2\pi 0.j_1}\left|1\right>) \\
=&\frac{1}{\sqrt{2}}(\left|0\right>+e^{i2\pi (0.j_1+j_n2^{-2})}\left|1\right>) \\
=&\frac{1}{\sqrt{2}}\left(\left|0\right>+e^{i2\pi0.j_1j_2}\left|1\right>\right).
\end{array}\]
In a similar manner, if this time the gate \(c_3-R_3\) is applied to this state while using the \(3^{rd}\) qubit \(\left|j_3\right>\) in the register as the control what results is the state
\[c_3-R_3c_2-R_2H\left|j_1\right>=c_3-R_3\frac{1}{\sqrt{2}}\left(\left|0\right>+e^{i2\pi0.j_1j_2}\left|1\right>\right)=\frac{1}{\sqrt{2}}\left(\left|0\right>+e^{i2\pi0.j_1j_2j_3}\left|1\right>\right).\]
Then continuing in this way by applying \(c_r-R_r\) gates iteratively for \(2\leq r \leq n\) yields
\[c_n-R_nc_{n-1}-R_{n-1}\dots c_2-R_2H\left|j_1\right>=\frac{1}{\sqrt{2}}\left(\left|0\right>+e^{i2\pi0.j_1j_2\dots j_n}\left|1\right>\right)=\left|\psi_n\right>,\]
which is the state \(\left|\psi_n\right>\) of the \(n^{th}\) qubit in the register of the tensor decomposition of the \(QFT\) shown above.

A similar set of operations is applied to each qubit \(\left|j_i\right>\) in the \(n\) qubit register. For the first \(n-1\) qubits \(\left|j_i\right>\), with \(1\leq i<n\),  apply the gates
\[c_{n+1-i}-R_{n+1-i}c_{n-i}-R_{n-1}\dots c_2-R_2H\left|j_i\right>=\frac{1}{\sqrt{2}}\left(\left|0\right>+e^{i2\pi0.j_ij_{i+1}\dots j_n}\left|1\right>\right)=\left|\psi_{n+1-i}\right>.\]

For the last qubit \(\left|j_n\right>\) of the register only apply the Hadamard gate. Notice that these states also correspond accordingly to the states \(\left|\psi_{n+1-i}\right>\) of the \(QFT\) decomposition.
By letting \(U'_i\) denote the unitary operator consisting of these gates that act on the state \(\left|j_i\right>\) of the \(i^{th}\)  qubit in the \(n\) qubit register, it follows that
\[U'_n\cdots U'_2U'_1\left|j_1j_2\dots j_n\right>=\left|\psi_n\right>\otimes\left|\psi_{n-1}\right>\otimes\dots\otimes\left|\psi_1\right>.\]
This is almost exactly the state
 \[\left|\psi\right>=QFT\left|j_1j_2\dots j_n\right>=\left|\psi_1\right>\otimes\left|\psi_{2}\right>\otimes\dots\otimes\left|\psi_n\right>,\]
except that order of the qubits in the registers is merely reversed when compared to \(U'_n\cdots U'_2U'_1\left|j_1j_2\dots j_n\right>\).



(Part of the circuit used to implement the quantum Fourier transform QFT. Not shown in the circuit is the seqiences of \(SWAP\) gates used to reverse the order of the \(\left|\psi_i\right>\). This circuit begins with an \(n\) qubit register is some computational basis state \(\left|j_1j_2\dots j_n\right>\) and then applies the sequence of gates given by \(U'_i\) to each \(\left|j_i\right>\) consisting of a Hadamard gate followed by controlled\(-R_k\) gates that use the states \(\left|j_k\right>\), for \(j>i\) in the register as control qubits.)

 At this point, one might be satisfied as accepting the state produced by \(U'_n\cdots U'_2U'_1\left|j_1j_2\dots j_n\right>\)  as being close enough to actually implementing the \(QFT\). After all, simply relabeling the qubits in the registers seems to be a logical triviality. However, there does exist a unitary operator that effectively interchanges the states of two qubits in different registers given by the \(SWAP\) gate presented in the section on quantum gates.

  By appropriately interchanging the states of the qubits in the register of the state \(\left|\psi_n\right>\otimes\left|\psi_{n-1}\right>\otimes\dots\otimes\left|\psi_1\right>\), this state can be transformed into the state \(\left|\psi_1\right>\otimes\left|\psi_{2}\right>\otimes\dots\otimes\left|\psi_n\right>\). Only \( \frac{n}{2}\) \(SWAP\) operations performed on the appropriate registers are needed to reverse the order of the qubits. By performing this reversal of states after the operation \(U'_n\cdots U'_2U'_1\left|j_1j_2\dots j_n\right>\) is applied, the basis state \(\left|j_1j_2\dots j_n\right>\) is finally transformed into the state given by \(\left|\psi\right>=QFT\left|j_1j_2\dots j_n\right>\). The circuit produced by appending the appropriate \(SWAP\) gates to the end of the circuit shown in the figure below implements the actual \(QFT\), and can itself be represented by a quantum gate that signifies this circuit as shown.

 

(The gate representing the quantum Fourier transform \(QFT\). The \(QFT\) takes as input the state \(\left|j\right>\) and transforms it to the state \(\left|\psi\right>=\left|\psi_1\right>\otimes\left|\psi_2\right>\otimes\dots\otimes\left|\psi_n\right>\). This gate is equivalent to the circuit shown in the previous figure with the necessary \(SWAP\) gates appended to the end of the circuit.)

  A more careful analysis of the implementing the quantum Fourier transform is  worthwhile in order to determine its computational complexity. In terms of elementary gates, it can be seen that \(n+1-i\) gates are needed to perform the operation \(U'_i\). Then since each \(U_i\) must be performed, for \(1\leq 1\leq n\), the total number of gates to implement \(U'_n\cdots U'_2U'_1\left|j_1j_2\dots j_n\right>\) is
\[n+(n-1)\dots+1=\displaystyle\sum\limits_{i=1}^{n}i= \frac{n(n+1)}{2}.\]Therefore the  circuit size or time complexity of implementing \(U'_n\cdots U'_2U'_1\left|j_1j_2\dots j_n\right>\) is in \(O(n^2)\). In addition, the \( \frac{n}{2}\) \(SWAP\) operations must be accounted for in order to determine the true circuit size of implementing the \(QFT\). Recall, that \(3\) controlled\(-NOT\) gates were able to simulate the effect of the \(SWAP\) gate. Then the total number of elementary gates needed to perform the \( \frac{n}{2}\) swap operations is just \( \frac{3n}{2}\), which is in \(O(n)\) but still bounded above by \(O(n^2)\). Hence, the total number of gates needed to perform the quantum Fourier transform \(QFT\) is \(O(n^2)\).
 
 It is important to keep in mind that the \(QFT\) was defined in general on the state space \(\mathcal{H}^{N}\) for an arbitrary positive integer \(N\). The construction shown above is for the case when \(N=2^n\) for some \(n\). Although, this case will be the most relevant for quantum computing, the QFT can be defined for general \(N\).\cite{coppersmith} Moreover, the family of circuits constructed for varying \(N\) is also uniformly polynomial, which is a necessary property when considering the computational complexity of algorithms that make use of the \(QFT\).
   
The quantum Fourier transform will prove to be a useful and essential tool in the quantum algorithms to follow. The \(QFT\) allows special superpositions of states to be constructed and novel ways to encode information in the states involved and their relative phases, which can then be exploited to accomplish interesting tasks. An important property of the \(QFT\) is that it can be efficiently implemented in polynomial time, whereas \(\omega(n2^n)\) operations are needed to implement the classical discrete Fourier transform on \(2^n\) complex numbers.\cite{winograd}
 
   Hence, the quantum algorithm is exponentially faster than its classical counterpart. Therefore, if the \(QFT\) is used in some algorithm it can be done so efficiently.