Notes on factoring

• To factor a number M, we choose a number y < M with gcd(y,M) = 1. We then find r, the order of y in the multiplicative group$\pmod{M}$. If r is even, then (y^r/2+1)(y^r/2-1)= $(y^r-1)\equiv 0\pmod M$. Then gcd(y^r-1,M) is a non-trivial factor of M except when r is odd or $y^{r/2}\equiv -1\pmod M$. This procedure produces a non-trivial factor of M with probability at least 1 - 1/2^k-1, where k is the number of distinct odd prime factors of M. If we don't get a factor, we can choose a new y and repeat the process. By repeating the process, we can make our likelihood of success as close to one as we like. Note that if M is even, finding a factor is easy; if M is a power of a prime, there are other fast classical methods of factoring which we can use on M before we start this process.

• We want to find the period of the function $f(a) = y^a\pmod{M}$. We do that by measuring to find a state whose amplitude has the same period as f.

  We measure the qubits of the state obtained from encoding f(a). A random value u is obtained. We don't actually use the value u; only the effect the measurement has on our set of superpositions is of interest. This measurement projects the state space onto the subspace compatible with the measured value, so the state after measurement is
  

  $$C\sum_{a}g(a)\vert{a,u}\rangle,$$
  
  
  for some scale factor C where
  
  $$g(a) = \left\{ \begin{array}{ll} 1 & \mbox{if $f(a)=u$} \\ 0 & \mbox{otherwise} \end{array} \right.$$
  
  
  Note that the a's that actually appear in the sum, those with $g(a)\ne 0$, differ from each other by multiples of the period, and thus g(a) is the function we are looking for. If we could just measure two successive a's in the sum, we would have the period. Unfortunately the quantum world permits only one measurement.

• Shor's method uses a quantum version of the Fourier transform to find the period of the function $y^a\pmod M$. We apply the quantum Fourier transform to the state obtained by the measurement.
  
  $$\sum_{a}g(a)\vert{a}\rangle \overset{QFT}\longmapsto \sum_{c}G(c)\vert{c}\rangle$$
  
  
  Standard Fourier analysis tells us that when the period r of g(a) is a power of two, the result of the quantum Fourier transform is
  
  $$C'\sum_{j}\rho_j\vert{j\frac{2^n}{ r}}\rangle$$
  
  
  where $\vert\rho_j\vert=1$. When the period r does not divide 2ⁿ, the transform approximates the exact case so most of the amplitude is attached to integers close to multiples of $\frac{2^n}{r}$.

• In order for Shor's factoring algorithm to be a polynomial algorithm, the quantum Fourier transform must be efficiently computable. Shor developed a quantum Fourier transform construction with base 2ⁿ using only $\frac{n(n+1)}{2}$ gates. The construction makes use of two types of gates. One is a gate to perform the Hadamard transformation H. We will denote by H_j the Hadamard transformation applied to the jth bit. The other type of gate performs transformations of the form
  
  $$S_{j,k} = \left(\begin{array}{cccc}1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&e^{i\theta_{k-j}}\end{array}\right)$$
  
  
  where $\theta_{k-j}={\pi}/{2^{k-j}}$, which acts on the kth element, depending on the value of the jth element. Think of this as acting on the basis $\{\vert{00}\rangle,\vert{01}\rangle,\vert{10}\rangle,\vert{11}\rangle\}$ ...

  The quantum Fourier transform is given by
  

  $$H_0S_{0,1}\dots S_{0,n-1}H_1\dots$$
  
  
  
  
  H_n-3S_n-3,n-2S_n-3,n-1H_n-2S_n-2,n-1H_n-1.
  
  
  This actually produces the reverse of the Fourier transform, so it typically will be followed by a bit reversal transformation.
• There is a second piece of Shor's algorithm which must be accomplished in polynomial time. We need to extract (using the QFT) the period of the function $a \mapsto (y^a)\pmod M$. We must transform as:
  
  $$\frac{1}{\sqrt{2^n}}\sum_{a=0}^{2^n-1}\vert{a}\rangle \mapsto \frac{1}{\sqrt{2^n}}\sum_{a=0}^{2^n-1}\vert{a,y^a(mod M)}\rangle$$
  
  

  We want to develop a transformation which computes the function $f_{y,M}(a)=y^a \pmod M$. First, we write y^a as $y^a=y^{2^0a_0}\cdot y^{2^1 a_1} \cdot \ldots y^{2^{m-1} a_{m-1}}$, where m is the number of digits in the binary expansion of M. Then, modular exponentiation can be computed by initializing the result register to $\vert{1}\rangle$, and successively effecting m multiplications by $y^{2^i}\pmod M$, depending on the value of the qubit $\vert{a_i}\rangle$. If a_i=1, we want the operation
  

  $$\vert{y^{2^0a_0+\ldots 2^{i-1}a_{i-1}},0}\rangle \mapsto$$
  
  
  
  
  $$\vert{y^{2^0a_0+\ldots 2^{i-1}a_{i-1}},y^{2^0a_0+\ldots 2^{i-1}a_{i-1}}\cdot y^{2^i}}\rangle$$
  
  
  to be performed; otherwise, when a_i=0 we just require
  
  $$\vert{y^{2^0a_0+\ldots 2^{i-1}a_{i-1}},0}\rangle \mapsto$$
  
  
  
  
  $$\vert{y^{2^0a_0+\ldots 2^{i-1}a_{i-1}},y^{2^0a_0+\ldots 2^{i-1}a_{i-1}}}\rangle.$$
  
  
  Note that in both cases the result can be written as $\vert{y^{2^0a_0+\ldots 2^{i-1}a_{i-1}},y^{2^0a_0+\ldots 2^ia_i}}\rangle$.

• To extract the period, we measure the state in the standard basis for quantum computation, and call the result v. In the case where the period happens to be a power of 2 so that the quantum Fourier transform gives exactly multiples of the scaled frequency, the period is easy to extract. In this case, $v=j\frac{2^n}{r}$ for some j. Most of the time j and r will be relatively prime, in which case reducing the fraction $\frac{v}{2^n}$to its lowest terms will yield a fraction whose denominator qis the period r. The fact that in general the quantum Fourier transform only gives approximately multiples of the scaled frequency complicates the extraction of the period from the measurement. When the period is not a power of 2, a good guess for the period can be obtained using the continued fraction expansion of $\frac{v}{2^n}$.
• Various things could have gone wrong so that this process does not yield a factor of M:

  1.

  The value v was not close enough to a multiple of $\frac{2^n}{r}$.

  2.

  The period r and the multiplier j could have had a common factor so that the denominator q was actually a factor of the period, rather than the period itself.

  3.

  We find M as M's factor.

  4.

  The period of $f(a) = y^a\pmod{M}$ is odd.

  A few repetitions of this algorithm yields a factor of M with high probability.