Editing Shor's algorithm (section)

==== Quantum phase estimation ====
[[File:Shor's algorithm.svg|frame|Quantum subroutine in Shor's algorithm]]
In general the [[quantum phase estimation algorithm]], for any unitary <math>U</math> and eigenstate <math>|\psi\rangle</math> such that <math>U|\psi\rangle=e^{2\pi i\theta} |\psi\rangle</math>, sends input states <math>|0\rangle|\psi\rangle</math> to output states close to <math>|\phi\rangle|\psi\rangle</math>, where <math>\phi</math> is a superposition of integers close to <math>2^{2n} \theta</math>. In other words, it sends each eigenstate <math>|\psi_j\rangle</math> of <math>U</math> to a state containing information close to the associated eigenvalue. For the purposes of quantum order-finding, we employ this strategy using the unitary defined by the action
<math display="block">
 U|k\rangle = \begin{cases}
  |ak \pmod N\rangle & 0 \le k < N, \\
  |k\rangle & N \le k < 2^n.
\end{cases}</math>
The action of <math>U</math> on states <math>|k\rangle</math> with <math> N \leq k < 2^n </math> is not crucial to the functioning of the algorithm, but needs to be included to ensure that the overall transformation is a well-defined quantum gate. Implementing the circuit for quantum phase estimation with <math>U</math> requires being able to efficiently implement the gates <math> U^{2^j} </math>. This can be accomplished via [[modular exponentiation]], which is the slowest part of the algorithm.

The gate thus defined satisfies <math>U^r = I</math>, which immediately implies that its eigenvalues are the <math>r</math>-th [[Root of unity|roots of unity]] <math>\omega_r^k = e^{2\pi ik/r}</math>. Furthermore, each eigenvalue <math>\omega_r^j</math> has an eigenvector of the form <math display="inline">|\psi_j\rangle=r^{-1/2}\sum_{k=0}^{r-1}\omega_r^{-kj}|a^k\rangle </math>, and these eigenvectors are such that
<math display="block">\begin{align}
 \frac{1}{\sqrt{r}} \sum_{j = 0}^{r - 1} |\psi_j\rangle &= \frac{1}{r} \sum_{j = 0}^{r - 1} \sum_{k = 0}^{r - 1} \omega_r^{jk}|a^k\rangle \\
 &= |1\rangle + \frac{1}{r} \sum_{k = 1}^{r - 1} \left(\sum_{j = 0}^{r - 1} \omega_r^{jk} \right) |a^k\rangle =|1\rangle,
\end{align}</math>
where the last identity follows from the [[geometric series]] formula, which implies <math display="inline">\sum_{j = 0}^{r - 1} \omega_r^{jk} = 0</math>.

Using [[Quantum phase estimation algorithm|quantum phase estimation]] on an input state <math>|0\rangle^{\otimes 2 n}|\psi_j\rangle</math> would then return the integer <math>2^{2n} j/r</math> with high probability. More precisely, the quantum phase estimation circuit sends <math>|0\rangle^{\otimes 2 n}|\psi_j\rangle</math> to <math>|\phi_j\rangle|\psi_j\rangle</math> such that the resulting probability distribution <math>p_k \equiv|\langle k|\phi_j\rangle|^2</math> is peaked around <math>k=2^{2n} j/r</math>, with <math>p_{2^{2n}j/r} \ge 4/\pi^2 \approx 0.4053</math>. This probability can be made arbitrarily close to 1 using extra qubits.

Applying the above reasoning to the input <math>|0\rangle^{\otimes 2 n}|1\rangle</math>, quantum phase estimation thus results in the evolution
<math display="block">
 |0\rangle^{\otimes 2 n}|1\rangle =
  \frac{1}{\sqrt{r}} \sum_{j = 0}^{r - 1} |0\rangle^{\otimes 2 n} |\psi_j\rangle \to
  \frac{1}{\sqrt{r}} \sum_{j = 0}^{r - 1} |\phi_j\rangle|\psi_j\rangle.
</math>
Measuring the first register, we now have a balanced probability <math>1/r</math> to find each <math>|\phi_j\rangle</math>, each one giving an integer approximation to <math>2^{2 n} j/r</math>, which can be divided by <math>2^{2n}</math> to get a decimal approximation for <math>j/r</math>.