Skip to main content
Chemistry LibreTexts

8.84: Shor's Quantum Algorithm - A Summary

  • Page ID
    149124
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    This tutorial presents a toy calculation dealing with quantum factorization using Shor's algorithm. Before beginning that task, traditional classical factorization is reviewed with the example of finding the prime factors of 15. As shown below the key is to find the period of ax modulo 15, where a is chosen randomly.

    \[ \begin{matrix} a = 4 & N = 15 & & f(x) = mod \left( a^x,~N \right) & Q = 8 & x = 0 .. Q - 1\end{matrix} \nonumber \]

    \[ \begin{matrix} x = \begin{array}{|c|} \hline \\ 0 \\ \hline \\ 1 \\ \hline \\ 2 \\ \hline \\ 3 \\ \hline \\ 4 \\ \hline \\ 5 \\ \hline \\ 6 \\ \hline \\ 7 \\ \hline \end{array} & f(x) = \begin{array}{|c|} \hline \\ 1 \\ \hline \\ 4 \\ \hline \\ 1 \\ \hline \\ 4 \\ \hline \\ 1 \\ \hline \\ 4 \\ \hline \\ 1 \\ \hline \\ 4 \\ \hline \end{array} \end{matrix} \nonumber \]

    Seeing that the period of f(x) is two, the next step is to use the Euclidian algorithm by calculating the greatest common denominator of two functions involving the period and a, and the number to be factored, N.

    \[ \begin{matrix} \text{period = 2} & \text{ged} \left( a^{ \frac{ \text{period}}{2}} - 1,~N \right) = 3 & \text{ged} \left( a^{ \frac{ \text{period}}{2}} + 1,~N \right) = 5 \end{matrix} \nonumber \]

    We proceed by ignoring the fact that we already know that the period of f(x) is 2 and demonstrate how it is determined using a quantum (discrete) Fourier transform. After the registers are loaded with x and f(x) using a quantum computer, they exist in the following superposition.

    \[ \frac{1}{ \sqrt{Q}} \sum_{x=0}^{Q-1} |x \rangle |f(x) \rangle = \frac{1}{2} \left[ |0 \rangle |1 \rangle + |1 \rangle |4 \rangle + |2 \rangle |1 \rangle + |3 \rangle |4 \rangle + \cdots \right] \nonumber \]

    The next step is to find the period of f(x) by performing a quantum Fourier transform (QFT) on the input register |x>.

    \[ \begin{matrix} Q = 4 & m = 0 .. Q-1& n = 0 .. Q-1 & QFT_{m,~n} = \frac{1}{ \sqrt{Q}} \text{exp} \left( \frac{2 \pi m n}{Q} \right) & QFT = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{pmatrix} \end{matrix} \nonumber \]

    \[ \begin{matrix} x=0 & QFT \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0.5 \\ 0.5 \\ 0.5 \\ 0.5 \end{pmatrix} & x=1 & QFT \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0.5 \\ 0.5i \\ -0.5 \\ -0.5i \end{pmatrix} & x = 2 & QFT \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0.5 \\ -0.5 \\ 0.5 \\ -0.5 \end{pmatrix} & x = 3 & QFT \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 0.5 \\ -0.5i \\ -0.5 \\ 0.5i \end{pmatrix} \end{matrix} \nonumber \]

    The operation of the QFT on the x-register is expressed algebraically in the middle term below. Quantum interference in this term yields the result on the right which shows a period of 2 on the x-register.

    \[ \begin{matrix} ~ & \frac{1}{4} \left[ |0 \rangle + |1 \rangle + |2 \rangle + |3 \rangle \right] |1 \rangle \\ ~ & + \\ ~ & \frac{1}{4} \left[ |0 \rangle + i |1 \rangle -|2 \rangle - i|3 \rangle \right] |4 \rangle \\ ~ & + \\ QFT (x) \frac{1}{2} \left[ |0 \rangle |1 \rangle + |1 \rangle |4 \rangle + |2 \rangle |1 \rangle + |3 \rangle |4 \rangle \right] = & + & = \frac{1}{2} \left[ |0 \rangle \left( |1 \rangle + |4 \rangle \right) + |2 \rangle \left( |1 \rangle - |4 \rangle \right) \right] \\ ~ & \frac{1}{4} \left[ |0 \rangle - |1 \rangle + |2 \rangle - |3 \rangle \right] |1 \rangle \\ ~ & + \\ ~ & \frac{1}{4} \left[ |0 \rangle - i |1 \rangle - |2 \rangle + i|3 \rangle \right] |4 \rangle \end{matrix} \nonumber \]

    Figure 5 in "Quantum Computation," by David P. DiVincenzo, Science 270, 258 (1995) provides a graphical illustration of the steps of Shor's factorization algorithm.

    Screen Shot 2019-04-25 at 12.09.23 PM.png


    This page titled 8.84: Shor's Quantum Algorithm - A Summary is shared under a CC BY 4.0 license and was authored, remixed, and/or curated by Frank Rioux via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.