[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