[Quantum Information] Shor's Algorithm

  Shor's Algorithm

Notes from RWTH Aachen University course 
“Quantum Information” Summer semester 2020
professor: Müller, Markus

Shor’s Algorithm

• factor a number

Fourier Transform

• classical Fourier transform

  • input: \(x_0,x_1...,x_{n-1}\)
  • output: \(y_0,y_1...,y_{n-1}\)
  • Definition:
    \[y_k=\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_j e^{2\pi i j\cdot k/N}=\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1} \omega_N^{jk}x_j\]

• cost?

  • naive: \(O(N^2)\) for \(N\)-vector
  • more efficient: Fast Fourier Transform (FFT): \(O(n\log n)\)

• Quantum Fourier transform (QFT)

  • acts on orthonormal basis \(|0\rangle,|1\rangle,...,|N-1\rangle\)
    \[|y_k\rangle=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{2\pi i j\cdot k/N}|k\rangle\]
    
    
    
    
    
    
    
    
  • If start at a basis state, no entanglement will be created (results in a product state)
  • Resources of \(n\)-qubit QFT gate:
    • \(O(n)\) hadamard gates
    • \(O(n^2)\) single qubit rotation gates (2 CNOT each)
    • at most \(n/2\) swap gate: \(O(n)\) (3 CNOT each)

  \(O(n^2)\) Quantum Algorithm

  • classical FFT: \(O(n2^n)\)
    • QFT provdes an exponential speed up

QFT is not an algorithm to speed up classical transformation
Problem: No way known to access the amplitude in quantum computer.
No way known to prepare efficiently original state to be transformed.
an ingredient of other quantum algorithm

Phase Estimation

• make use of QFT
• Setting:
  • \(U\): unitary
  • eigenvector \(|u\rangle\) with eigenvalues \(e^{2\pi i\varphi}\), where \(\varphi\) is unknown
• Goal: to estimate \(\varphi, \varphi\in[0,1]\)
• Assumption:
  • can prepare \(|u\rangle\)
  • can perform controlled-\(U^{2^j}\)
• Algorithm:

1. 1-st register prepare \(t\) qubits \(|0\rangle\), where \(t\) depends on

   • precision
   • success probability

   2-nd register begin in \(|u\rangle\), contains as many qubits as needed to store \(|u\rangle\)
   \[|0\rangle|u\rangle\]

2. Hadamard gates to 1-st register
   \[|0\rangle|u\rangle\xrightarrow[]{H}\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)|u\rangle\]

3. Controlled-\(U^{2^j}\) on 2-nd register
   \[\begin{aligned}\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)|u\rangle\xrightarrow[]{c-U^{2^j}}&\frac{1}{\sqrt{2}}|0\rangle|u\rangle+\frac{1}{\sqrt{2}}U^{2^j}|1\rangle|u\rangle\\ =&\frac{1}{\sqrt{2}}|0\rangle|u\rangle+\frac{1}{\sqrt{2}}e^{2\pi i 2^j\varphi}|1\rangle|u\rangle\\ =& \frac{1}{\sqrt{2}}(|0\rangle+e^{2\pi i 2^j\varphi}|1\rangle)|u\rangle \end{aligned}\]

   • \(t\)-qubit
     \[\frac{1}{\sqrt{2^t}}\sum_{k=0}^{2^t-1}e^{2\pi i\varphi k}|k\rangle\]
   • suppose \(\varphi=0.\varphi_1...\varphi_t\)
     \[\frac{1}{\sqrt{2^t}}(|0\rangle+e^{2\pi i\cdot 0.\varphi_t}|1\rangle)(|0\rangle+e^{2\pi i\cdot 0.\varphi_t\varphi_{t-1}}|1\rangle)...(|0\rangle+e^{2\pi i\cdot 0.\varphi_t...\varphi_1}|1\rangle)\]
     The Fourier transform of \(|\varphi\rangle=|\varphi_1\rangle|\varphi_2\rangle...|\varphi_t\rangle\)

4. apply inverse QFT to the 1-st register
   \[\frac{1}{\sqrt{2^t}}\sum_{k=0}^{2^t-1}e^{2\pi i\varphi k}|k\rangle|u\rangle\xrightarrow[]{FT^\dagger}|e\rangle|u\rangle\]

5. measure the qubits of first register in computational basis
   
   

   
   
   

• Discuss:
  • To achieve accuracy \(2^{-n}\) with probability \((1-\varepsilon)\)
    \[t=n+\lceil\log(2+\frac{1}{2\varepsilon})\rceil\]
  • What if we cannot prepare the eigenstates \(|u\rangle\)?
    \[|\psi\rangle=\sum_u C_u|u\rangle\]
    After the estimation, we get
    \[\sum_u C_u |\tilde{\varphi_u}\rangle|u\rangle\]
    where \(\tilde{\varphi_u}\) is a good approximation to the eigenvalue \(\varphi_u\)
    with probability \(|C_u|^2\) we get \(\tilde{\varphi_u}\)
    If we do it many times, we can avoid the requirement of preparing \(|u\rangle\)

Order Finding

• output \(r\) where \(x^r=1\text{ mod }N\)

• is a hard problem in classical computer (no polynomial time algorithm)

• in quantum computer, it is the phase estimation algorithm applied to the unitary
  \[U|y\rangle=|xy\ (\text{ mod }N)\rangle\]
  \(y\) is an \(b\)-qubit state

• construct
  \[|u_s\rangle=\frac{1}{\sqrt{r}}\sum_{k=0}^r\text{exp}(-\frac{2\pi i s k}{r})|x^k\text{ mod }N\rangle\]
  For integer \(s\), \(|u_s\rangle\) are eigenstates of \(U\).
  \[U|u_s\rangle=\text{exp}(\frac{2\pi i s}{r})|u_s\rangle\]
  so \(\text{exp}(\frac{2\pi i s}{r})\) is the eigenvalue of \(|u_s\rangle\)
  This allows us to estimate \(\frac{s}{r}=\varphi\)
  \(\Rightarrow\) with the addition work to access order \(r\)

  • Problem: not allowed to use \(r\), we cannot prepare \(|u_s\rangle\)
  • \(\Rightarrow\)
    \[\frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}|u_s\rangle=|x^0(\text{ mod }N)\rangle=|1\rangle\]
    \(|1\rangle\) is trivial to prepare

• Algorithm:

1. prepare 1-st register with \(t\) qubits \(|0\rangle\)
   prepare 2-nd regester with \(|1\rangle\)
2. run phase estimation
3. measuring the first registers
   • for each \(s\) in the range of \(1\) to \(r\), this will lead to an estimation of the phase \(\varphi=s/r\)
   • accuracy: \(2L+1\) bits
   • probability \((1-\varepsilon)/r\)
     • “\(/r\)” because don’t know which \(|u_s\rangle\) \[\frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}|u_s\rangle\]
       entangled with the second register when measuring.

• moduler exponentiation
  • speed up exponentiation \(|z\rangle|x^z\rangle\)
  • use the third temporary registers
  • reversible computing
  • \(O(L)\) spanning operations
    \(O(L^2)\) standard multiplication for each operation
    \(\Rightarrow\) total \(O(L^3)\) operations
• How to get \(r\) from the output \(\varphi\)

4. run continued function algorithm (on a classical computer)
   • Continued Fraction Algorithm
     • a rational number \(s/r\) such that
       \[\left|\frac{s}{r}-\varphi\right|\leq\frac{1}{2r^2}\]
       then \(s/r\) is a convergence of the continued fraction for \(\varphi\), and can be calculated in \(O(L^3)\) steps
     • idea: express the number as
       \[[a_0,a_1,...,a_M]=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{...+\frac{1}{a_M}}}}\]
     • check \([a_0],[a_0,a_1],...[a_0,...a_M]\) which satisfies \(s/r\)
     • the algorithm provides efficiently \(s'/r'\)

• complexity
  • Hadamard gates: \(O(L)\)
  • Inverse FT: \(O(L^2)\)
  • Modular exponentiation: \(O(L^3)\)
  • classical continued fraction algorithm: \(O(L^3)\)
  • If order finding fails, one has to repeat only for a constant number to obtain \(r\) with high probability: \(O(1)\)
    \(\Rightarrow\) overall cost: \(O(L^3)\)

  can be reduced to almost \(O(L^2)\) by square-and-multiply

Shor’s Algorithm

• Factoring \(N\) to two prime numbers
• reduce factoring to order finding
• If we have
  \[y^2=1\text{ mod }N\\ (y-1)(y+1)=0\text{ mod }N=k\cdot N\]
  If \(y\neq \pm1\text{ mod }N\), then
  \[\text{gcd}(y+1,N)\\\text{gcd}(y-1,N)\]
  must each be a proper divisor of \(N\), i.e. prime factors.
• How can we find a non-trivial square root \(y\)?
  
  
  

1. choose a random \(1< x\leq N-1\)
2. run the order finding algorithm to find \(r\), \(x^r=1\text{ mod }N\)
   • If \(r\) is even:
     \[\begin{aligned} x^r&=1\text{ mod }N\\ (x^{r/2}+1)(x^{r/2}-1)&=0\text{ mod }N=k\cdot N \end{aligned}\]
     then \(y=x^{r/2}\) is a square root of \(1\)
     and if \(x^{r/2}\neq \pm 1\), then compute gcd

   success probability to find a “good” \(x\)?
   “good”: order \(r\) is even and \(x^{r/2}\neq1\)
   Theorem: If \(N\) is divisible by \(l\) distinct odd primes, then at least \[1-\frac{1}{2^{l-1}}\] elements are “good”.
   \(l=2\Rightarrow 1/2\) probability to have “good” \(x\)
   \(O(1)\) trials

   • If \(r\) is not even:

• Complexity:
• \(O(1)\) for order finding
• overall: \(O(L^3)\)
• classical factoring: \(\text{exp}(O(L^{1/3}))\)
• exponential speedup

RSA Algorithm

1. pick random two primes \(p,q\), and \(n=p\cdot q\)
2. pick random public key by \(e\in\phi(n)\), where \(\phi(n)=(p-1)(q-1)\)
3. choose private key \(d\) such that \(e\cdot d=1\text{ mod }\phi(n)\)
4. public key: \((n,e)\)
   private key: \((n,d)\)

• Encryption:
  \(E(m) = m^e\text{ mod }n\)
• Decryption:
  \(D(c)=c^d\text{ mod }n=m^{e\cdot d}\text{ mod }n=m^{1\text{ mod }\phi(n)}\text{ mod }n= m \text{ mod }n\)

Shor’s Algorithm allows us to factor efficiently on a quantum computer
RSA public key scheme is broken, as soon as sufficiently large quantum computer exists.

Readings

Nielsen and Chuang

    5.1 The quantum Fourier transform

    5.2 Phase estimation

    5.3 Applications: order-finding and factoring

Shor's Algorithm