Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Quantum Computing
#9: Extra Quantum Algorithms

송기원

2022
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Outline

1 Introduction

2 Grover’s Algorithm

3 Quantum Fourier Transform

4 Quantum Phase Estimation

5 Modular Exponents

6 Shor’s Algorithm
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Caution

This lecture is an extra lecture; just an additional lecture to

look some of the famous algorithms.
This lecture needs additional knowledge of qubits;
must read the appendix of lecture 03 and lecture 07
This lecture is not kind enough to introduce all the maths
inside the algorithm, you must follow up with your own proofs!
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Abbreviation of qubits (1/2)

Like using 101 to represent 5, we make another abbreviation:

Abbreviation of qubits
For integer N = A0 A1 A2 A3 · · · An (2) , |N⟩n := |A0 A1 A2 A3 · · · An ⟩.

Example
Note that the subscript represents the number of digits.
|5⟩3 = |101⟩ = |1⟩ ⊗ |0⟩ ⊗ |1⟩
|1⟩8 = |00000001⟩ = |0⟩ ⊗ |0⟩ ⊗ |0⟩ ⊗ |0⟩ ⊗ |0⟩ ⊗ |0⟩ ⊗ |0⟩ ⊗ |1⟩
|0⟩⊗n = |0⟩n
2 −1 n N−1
1 X 1 X
H ⊗n |0⟩n = √ n |x⟩n = √ |x⟩n where N = 2n
2 x=0 N x=0

We often exclude n in |·⟩n when it is implied, so be careful!

Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Abbreviation of qubits (2/2)

We have another name to call |→⟩ and |←⟩.

Abbreviation of qubits
1 1 1 1
|+⟩ = H |0⟩ = √ |0⟩ + √ |1⟩, |−⟩ = H |1⟩ = √ |0⟩ − √ |1⟩
2 2 2 2

Example
1 1
√ |+⟩ + √ |−⟩ = |0⟩
2 2
QFT2 |11⟩ = (− |−⟩) ⊗ (− |+⟩) = |−+⟩
▶ QFT explained later
H ⊗n |0⟩n = |+⟩⊗n = |+⟩ ⊗ |+⟩ ⊗ · · · ⊗ |+⟩
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Outline

1 Introduction

2 Grover’s Algorithm

3 Quantum Fourier Transform

4 Quantum Phase Estimation

5 Modular Exponents

6 Shor’s Algorithm
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Grover’s problem

Now we are finding the solution of f among all possible bits.

Lets say f (α) = 1 and f (x) = 0 for all x ̸= α.
▶ We are finding α now, treating as the root.

Grover’s problem
For given f : { 0, 1 }m → { 0, 1 }, find unique α such that f (α) = 1.

This is actually practical, we need to find roots!

We need to check m times with classical computing.
√
▶ Grover’s algorithm gives O( m) query complexity.
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Phase oracle

As the output is just 0 or 1, we can distinguish the output by

phase oracle. (It can run with boolean oracle too)

Definition(Phase oracle)
A phase oracle Pf of f : { 0, 1 }m → { 0, 1 } maps |x⟩ where x is
m-qubits , to (−1)f (x) |x⟩.

So by superposing all possible inputs, the phase oracle makes

phase change only to the root.
But changing the phase does not change the probability
▶ How to amplify the difference?
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Amplitude amplifier

We amplify the amplitudes by flipping over/under the average.

▶ Inversion about the mean: x 7→ 2µ − x where µ is average
N−1
1 X
We can do it with As = 2 |s⟩ ⟨s| − I where s = √ |x⟩
N x=0
h ih i
▶ Understand |s⟩ ⟨s| as a product of matrix |s⟩ ⟨s| .

Proof of |s⟩ ⟨s| |ψ⟩ is an average vector

N−1 N−1 N−1
X X X cx
If |ψ⟩ = cx |x⟩ where cx2 = 1, then µ = and:
N
x=0 x=0 x=0
N−1 N−1 N−1
c cx
√x |s⟩ =
X X X
|s⟩ ⟨s| |ψ⟩ = ⟨s|ψ⟩ |s⟩ = |x⟩ = µ |x⟩
N N
x=0 x=0 x=0
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Grover iteration

Single amplification does not do much work when N is large.

1 4 3 4
▶ Other vectors: √ − √ , the solution vector: √ − √
N N N N N N
We iterate this r (N) times where r is selected according to
the desired accuracy.
√
▶ To make it near 1, r (N) must be at least O( N)
▶ Why???
We can think Grover iteration as a rotation of phase vectors,
represented in a special way.
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Geometrical interpretation of Grover iteration (1/3)

Using the orthonormal basis, we can make another

orthonormal set with two vectors |a⟩ and |b⟩, where
1 X
|a⟩ = √ |x⟩ |b⟩ = |α⟩
N − 1 x̸=α
√
N −1 1
We start from |s⟩ = √ |a⟩ + √ |b⟩ and the goal is |b⟩.
N N

Grover iteration in the hyperplane

Initial state: |ψ⟩ = cos 2θ |a⟩ + sin 2θ |b⟩ where sin 2θ = √1N
After phase change: Pf |ψ⟩ = cos 2θ |a⟩ − sin 2θ |b⟩
After amplification: As Pf |ψ⟩ = cos( 2θ + θ) |a⟩ + sin( 2θ + θ) |b⟩

The phase vector always exists on the plane that |a⟩ and |b⟩ spans.
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Geometrical interpretation of Grover iteration (2/3)

Grover iteration in the hyperplane

Initial state: |ψ⟩ = cos 2θ |a⟩ + sin 2θ |b⟩ where sin 2θ = √1N
After phase change: Pf |ψ⟩ = cos 2θ |a⟩ − sin 2θ |b⟩
After amplification: As Pf |ψ⟩ = cos( 2θ + θ) |a⟩ + sin( 2θ + θ) |b⟩
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Geometrical interpretation of Grover iteration (3/3)

θ 1
Starting from θ/2 as the angle of |s⟩ where sin =√
2 N
Making rotation of θ, we need to get it close to |b⟩
If r rotation is made, the probability amplitude of |b⟩ is
  !
1 1
sin r+ θ where θ = 2 sin−1 √
2 N
√
π N
Thus to make this near 1, r (N) ≈ which gives this
√ 4
O( N) query complexity. (When N is large)
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Grover’s Algorithm

repeat r (N) times

|0⟩⊗n H⊗n Pf H⊗n A|0⟩ H⊗n

A|0⟩ is just 2 |0⟩ ⟨0| − I , where |0⟩ = |0⟩n

▶ How to implement it?
To apply A|s⟩ , we turn the qubit itself with Hadamard gate,
and then apply A|0⟩ , then return back with Hadamard gate.
▶ Note that |0⟩ is same with |s⟩ under basis generated with H⊗n

How to implement A|0⟩

Note that |0⟩n is a one-hot vector with first entry 1.
A|0⟩ is a matrix with 1 on the top left, and −1 for rest of diagonals.
This is multiplying −1 to phase ̸= |0⟩n , which is −X ⊗n (MCZ )X ⊗n
where MCZ is a multi-controlled Z gate targeting |11 · · · 1⟩.
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Grover’s algorithm with multiple solutions

Let f (x) = 1 if and only if x ∈ S, where |S| = M ≥ 1.

Then redefine |a⟩ and |b⟩ as:
1 X 1 X
|a⟩ = √ |x⟩ |b⟩ = √ |x⟩
N − M x̸∈S M x∈S
√ √
N −M M
Similarly, we start from |s⟩ = √ |a⟩ + √ |b⟩.
√ √ N N
▶ Thus sin(θ/2) = M/ N
r
π N
Again, r (N) ≈ to get the probability near 1:
4 M
  ! √
2 1 −1 M
sin r+ θ where θ = 2 sin √
2 N
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Time complexity of Grover’s algorithm

 
So the number of iteration is r = O (N/M)1/2
▶ How much time complexity for one iteration?
2n Hadamard gates and 2n X gates, one MCZ gate: O(n)
▶ As N = 2n , O(n) = O(log N)
Phase oracle Pf : O(???)
▶ So it hardly depends on the time complexity of the oracle.
 
So the time complexity is O (N/M)1/2 (log N + f (N))
▶ where f (N) is the time complexity of simulating Pf .
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Outline

1 Introduction

2 Grover’s Algorithm

3 Quantum Fourier Transform

4 Quantum Phase Estimation

5 Modular Exponents

6 Shor’s Algorithm
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Concept

Note that the second entry of a qubit is complex.

We want to encode qubits to the complex plane!
As the complex plane is useful for rotation, let’s use e iθ .
▶ e iθ = cos θ + i sin θ
▶ So the base coordinates are based on |+⟩ and |−⟩
Rotating the qubit based on the values input: Think |x⟩n as x
▶ Like |0⟩2 rotate 0◦ , |1⟩2 rotates 90◦ , · · · , |3⟩2 rotates 270◦
But we need to have n bits as outputs too, so we differ the
amount of rotation.
▶ 1st qubit: |x⟩n rotates 2πx/2n = 2πx/N
▶ 2st qubit: |x⟩n rotates half; 2πx/2n−1 = 4πx/N
▶ ···
▶ n-th qubit: |x⟩n rotates 180◦ = Nπx/N
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Different Basis

Let |x̃⟩n be the qubits that |x⟩n maps to.

" # " # " # " #

1 1 1 1 1 1 1 1
|9̃⟩4 = √ ⊗√ ⊗√ ⊗√
2 e 9/8πi 2 e 9/4πi 2 e 9/2πi 2 e 9πi
QFT maps the same, but in reversed order.
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Quantum Fourier Transform

Definition(QFT)
N−1
1 X 2πixy /N
QFT of n is a matrix that maps QFTn |x⟩n = √ e |y ⟩n
N y =0

QFTn |x⟩n = |xn xn−1 · · · x1 ⟩ where |x̃⟩n = |x1 · · · xn−1 xn ⟩

N−1 1 n
1 X 2πixy /N 1 X 2πix P ykk
√ e |y ⟩n = √ e 2 |y1 y2 · · · yn ⟩
N y =0 N y =0n
 
1 1 1 n
1 X X X Y yk
2πix k
=√ ···  e 2 |yk ⟩
N y1 =0 y2 =0 yn =0 k=1
n
1 Y k

=√ |0⟩ + e 2πix/2 |1⟩
N k=1
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Rotation matrix

How to implement QFT with gates we can actually use?

We are going to rotate the second element
" #
of "the #qubits:
1 1 1 1
▶ Rotating θ about the z-axis: √ 7→ √
2 1 2 e iθ

Definition(Rθ )
" #
1 0
Rθ = is a matrix that rotates the second element by θ.
0 e iθ

We can implement this by physically rotating the spin.

Hadamard gate and other rotation matrices

If the subscript is a natural number: Rk := Rπ/2k
H = Rπ = R1 but we usually just use H
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Controlled rotation matrix

π
The first output qubit rotates if k-th qubit is 1
2k−1
▶ We need controlled Rk−1 , which is controlled by k, targeting 1.
Thus we define the controlled rotation matrix CRθ :

Definition(Controlled rotation matrix)

 
1 0 0 0
 
0 1 0 0 
CRθ =   rotates the second, controlled by the first.
 0 0 1 0 

0 0 0 e iθ

So first qubit gets H for rotating π for itself, CR2 with the
second qubit, CR3 with the third, · · · , CRn for the last.
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

QFT circuit

|x1 ⟩ H R2 R3 ··· Rn

|x2 ⟩ H R2 ··· RRn−1

n

|x3 ⟩

|xn−1 ⟩ H R2

|xn ⟩ H

with at most n/2 swaps at last, and we abbreviate it to

|x1 ⟩
|x2 ⟩
|x3 ⟩
QFTn
|xn−1 ⟩
|xn ⟩
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Inverse QFT and quantum Fourier basis

Every QFT matrices are unitary, so QFT † = QFT −1 .

We can define QFT −1 similarly:

Definition(QFT−1 )
N−1
1 X −2πixy /N
QFT−1 is a matrix that maps QFT † |x⟩n = √ e |y ⟩n .
N y =0

Note that every vector in quantum Fourier basis contains

equal amount of vectors of classical basis.

Quantum Fourier basis

n−1
" # n−1
1 Y 1 Y
2πix/2k

QFT |x⟩n = fx = √ k = |0⟩ + e |1⟩
N k=0 e 2πix/2 k=0
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Outline

1 Introduction

2 Grover’s Algorithm

3 Quantum Fourier Transform

4 Quantum Phase Estimation

5 Modular Exponents

6 Shor’s Algorithm
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Eigenvalue

Definition(Eigenvalue)
An eigenvalue λ of a matrix M is a value such that there exists
some nonzero vector x such that Mx = λx.

We can say that there is n complex eigenvalues to any n × n

matrix M, as Mx = λx ⇐⇒ (M − λI )x = 0.
▶ This means det(M − λI ) = 0, and it can be rewritten with
n-th degree polynomial.

Eigenvalue of a unitary matrix

Any eigenvalue a + bi of a unitary matrix satisfies a2 + b 2 = 1.

Proof
For eigenvalue λ of a unitary matrix U with its eigenvector x,
x† x = x† I x = x† U † Ux = (Ux)† Ux = λλx† x so λλ = 1 as x† x ̸= 0.
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Eigenvector

Definition(Eigenvector)
For an eigenvalue λ of a matrix M, any nonzero vector x such that
Mx = λx is an eigenvector of λ.

We can have different eigenvectors for the same eigenvalue.

▶ For example, I has two eigenvectors for eigenvalue 1.

Definition(Orthogonality)
Eigenvectors of different eigenvalues of U are orthogonal.

Proof
For eigenvalue λx for x and λy for y of matrix U where λx ̸= λy ,
x† y = x† I y = (λx x)† (λy y) = λx λy x† y so λx λy = 1 or x† y = 0.
But λx λy = 1 ⇐⇒ λx λx λy = λx ⇐⇒ λy = λx so x† y = 0.
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Simple quantum phase estimation (1/2)

As the eigenvalue has its argument 1, we can say λ = e iθ .

But multiplying e iθ does not change the probability.
▶ See the global phase on the appendix of lecture 07.
Then how can we find θ from given U and its eigenvector |ψ⟩?
Quantum phase estimation
Given unitary U and its eigenvector |ψ⟩, find θ s.t. U |ψ⟩ = e iθ |ψ⟩.

Answer: Repeating the circuit below several times.

|0⟩ H H

|ψ⟩ U
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Simple quantum phase estimation (2/2)

|0⟩ H H

|ψ⟩ U

1
Initial state: |0⟩ |ψ⟩, after Hadamard gate: √ (|0⟩ + |1⟩) ⊗ |ψ⟩
2
1 e iθ
After controlled U: √ |0⟩ |ψ⟩ + √ |1⟩ |ψ⟩
2 2
1 
After Hadamard gate: (1 + e ) |0⟩ + (1 − e iθ ) |1⟩ |ψ⟩
iθ
2
2 2
1 − e iθ 1 + e iθ
Chance p of measuring 1: , while 0:
2 2
▶ Find θ = ± cos−1 (1 − 2p) by finding probability p by testing.
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Quantum phase estimation (1/4)

We increase the accuracy by using more qubits to measure.

|0⟩ H ···
.. ..
. .
QFTn†
|0⟩ H ···

|0⟩ H ···

m
|ψ⟩ U2
0
U2
1
··· U2
n−1

Note that the controlled units applied in reversed order as

QFT itself is reversed in the first place.
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Quantum phase estimation (2/4)

|0⟩ H ···
.. ..
. QFTn† .
|0⟩ H ···
|0⟩ H ···

m 0 1 n−1
|ψ⟩ U2 U2 ··· U2

1
Initial state: |0⟩⊗n |ψ⟩, after H gate: √ n (|0⟩ + |1⟩)⊗n |ψ⟩
2
2 k i2 kθ k
As U |ψ⟩ = e |ψ⟩, k-th qubit: (|0⟩ + e i2 θ |1⟩) |ψ⟩
n−1
1 X k
Before inverse QFT: √ n (|0⟩ + e i2 θ |1⟩) |ψ⟩
2 k=0
▶ So we can say |ψ⟩ is left unchanged.
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Quantum phase estimation (3/4)

|0⟩ H ···
.. ..
. QFTn† .
|0⟩ H ···
|0⟩ H ···

m 0 1 n−1
|ψ⟩ U2 U2 ··· U2

2 −1 n
1 X ikθ
Rewriting the qubits above: √ n e |k⟩n
2 k=0
N−1 N−1
1 X ikθ X −2πikx/N
Applying QFT inverse: n e e |x⟩n
2
k=0 x=0
N−1 N−1
1 XX 2πik
Let θ = 2πω then e− N
(x−Nω)
|x⟩n
N
k=0 x=0
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Quantum phase estimation (4/4)

|0⟩ H ···
.. ..
. QFTn† .
|0⟩ H ···
|0⟩ H ···

m 0 1 n−1
|ψ⟩ U2 U2 ··· U2
N−1 N−1
1 X X − 2πik (x−Nω)
We have |ϕ⟩ = e N |x⟩n
N
k=0 x=0
1 1
Let Nθ = Nω = A + Nδ where A ∈ Z and |Nδ| ≤ .
2π 2
N−1 N−1
1 X X − 2πik (x−A)+2πiδk
Then |ϕ⟩ = e N |x⟩n
N
k=0 x=0
2
N−1
2 1 X −2πiδk
So Pr (A) = ⟨A|ϕ⟩ = e
N
k=0
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Accuracy of QPE

2
N−1
2 1 X −2πiδk
Pr (A) = ⟨A|ϕ⟩ = e
N
k=0
4
If δ = 0 then Pr (A) = 1 and otherwise Pr (A) ≥ ≈ 0.405
π
2
1 1 − e 2πiNδ
Pr (A) = 2
N 1 − e 2πδ
2 2
1 2 sin(πNδ) 1 2Nδ 4
= ≥ =
N 2 2 sin(πδ) N 2 πδ π
1
as |δ| ≤ implies | sin(πδ)| ≤ |πδ| and | sin(πNδ)| ≥ |2Nδ|.
2N
A can be found quickly, as Pr (A) ≥ 4/π.
Thus θ′ = A/N can be found, less than 1/2N error from θ.
▶ As θ′ − θ = δ
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Outline

1 Introduction

2 Grover’s Algorithm

3 Quantum Fourier Transform

4 Quantum Phase Estimation

5 Modular Exponents

6 Shor’s Algorithm
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Modular arithmetics

Definition(Modulo operation)
For integers a and nonzero integer n, a mod n is defined as a
nonnegative integer b < n such that a = kn + b for some k ∈ Z.

This is well defined as such b is unique for each a.

Then we can partition all numbers to n categories, based on
the value of mod n, defining 1 ≡ n + 1, · · ·
▶ Let the n representatives 0, 1, · · · , n, i.e., i ≡ kn + i.

Definition(Ring of integers modulo n)

Zn ≜ { 0, 1, 2, · · · , n }, a +n b ≜ a + b mod n, a ·n b ≜ ab mod n

Can we find the minimum r > 0 such that ar ≡ 1?

▶ covered in the next section
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Greatest common divisor and primality

Definition(Divisibility)
For a, b ∈ Z, if there exists some k ∈ Z such that a = kb, we say
that b can divide a, or b | a.

Definition(Greatest common divisor)

For a, b ∈ Z, the maximum value of g ∈ N such that g | a and
g | b is called a greatest common divisor; g = gcd(a, b).

Definition(Primality)
p is prime when there is no d such that |d| =
̸ p, |d| =
̸ 1, and d | p.

For N ∈ N, if there exists k ∈ N such that gcd(k, N) = d

where 1 < d < N, then N must not be prime.
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Hardness of FACTOR

Definition(FACTOR)
FACTOR is a problem that receives N as an input, and outputs the
prime factorization of N.

Neither Pness nor NP-hardness of FACTOR has been proven.

RSA cryptosystem relies on the hardness of FACTOR.
The most effective classical algorithm for number over 10100
is known to be GFNS, or general number field sieve with time
1/3 2/3
complexity O(e (1.9223+o(1))(ln N) (ln ln N) ), sub-exponential.
▶ One can think it is just O(n log2 n), but note that we need to
consider the input size with the bit size of the number.
Shor’s algorithm challenges GFNS with query complexity
O((log N)2 log log N)
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Outline

1 Introduction

2 Grover’s Algorithm

3 Quantum Fourier Transform

4 Quantum Phase Estimation

5 Modular Exponents

6 Shor’s Algorithm
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Classical part of Shor’s algorithm: Guideline

Assume the input number is N.

Pick any integer 1 < a < N.
Calculate K = gcd(a, N) and if K ̸= 1, we are done.
▶ K | N and 1 < K < N, thus N is not a prime.
If K = 1, find minimum r ∈ N such that ar ≡ 1(mod N)
▶ This part can be done with the quantum algorithm in BQP.
If r is odd, try another a.
If r is even but ar /2 ≡ −1(mod N), try another a.
Then both or one of gcd(ar /2 + 1, N) and gcd(ar /2 − 1, N) is
a nontrivial factor of N, thus N is not a prime.
▶ Why??
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Classical part of Shor’s algorithm: Proof

Find some b such that b 2 ≡ 1(mod N), b ̸≡ ±1(mod N).

▶ b = ar /2 on the previous slide.
Let d = gcd(b − 1, N). Trivially d ̸= N as b ̸≡ 1(mod N).
If d = 1, it contradicts that b ̸≡ −1(mod N) as
N | (b + 1)(b − 1) and gcd(b − 1, N) = 1.
Therefore 1 < d < N, proving that N is not prime.
Vice versa, case of d ′ = gcd(b + 1, N) can be proven similarly.
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Hardness of finding the period of a function

Now we need to find minimum r such that ar ≡ 1(mod N).

f (x) ≜ ax mod N. Then we need to find the period of f .
However, finding the period of f is not easy; need infinitely
many samples to ensure the period.
2
0
−2
0 0.5 1 1.5 2 2.5 3
2
0
−2
0 5 10 15 20 25 30
Both graphs represent sin(5πx) + sin(4.9πx).
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Shor’s algorithm

But we have QPE: quantum phase estimation!

▶ A good way to find the eigenvalue of a function.
Let’s say r is the period of f , or ar ≡ 1(mod N).
Define U as an oracle of x 7→ ax mod N
▶ That is, U |x⟩n = |ax mod N⟩n
Then U |ai mod N⟩ = |ai+1 mod N⟩n for i = 1, 2, · · · , r .
r
1 X −2πisk/r k
|us ⟩ ≜ √ e |a mod N⟩ then U |us ⟩ = e 2πis/r |us ⟩
r
k=1
▶ Prove yourself! This proves that |us ⟩ is an eigenvector of U.
Note that the uniform superposition of |us ⟩ sums up to |1⟩n .
▶ Thus θ of QPE from |1⟩n gives sr for some s with equal chance.
▶ Classically find p/q ≈ s/r with q < N, then q will be a divisor
of r . Test for every kq whether it is a period.
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

The circuit of Shor’s algorithm

|0⟩ H ···
.. ..
. .
QFTn†
|0⟩ H ···

|0⟩ H ···

n
0 1 n−1
|1⟩n Ua2 Ua2 ··· Ua2

k
In QPE, Ua2 must be a repeated multiplication of Ua .
However, it takes too much time, so we can make use of
k k
Ua2 = Ua2k by calculating a2 classically.
Introduction Grover’s Algorithm Quantum Fourier Transform Quantum Phase Estimation Modular Exponents Shor’s Algorithm

Summary

For given N:
Pick any integer 1 < a < N.
Calculate K = gcd(a, N) and if K ̸= 1, K is a nontrivial
factor of N.
If K = 1, find minimum r ∈ N such that ar ≡ 1(mod N)
▶ New QPE is made for each a.
If r is odd, try another a.
If r is even but ar /2 ≡ −1(mod N), try another a.
Then both gcd(ar /2 + 1, N) and gcd(ar /2 − 1, N) are a
nontrivial factor of N.
Boolean and Phase Oracle Rotation effect of Grover iteration Additional Information of QFT Probability Theories for QPE

Boolean oracle to phase oracle back

Let’s say we only have the boolean oracle Uf .

Uf will be a (n + 1) × (n + 1) matrix containing output qubit.
▶ So Uf (|x⟩ ⊗ |y ⟩) = |x⟩ ⊗ |y ⊕ f (x)⟩ for 1-qubit y
But if we input |x⟩ ⊗ |−⟩ to Uf then
 !
1 1
Uf (|x⟩ ⊗ |−⟩) = Uf |x⟩ ⊗ √ |0⟩ − √ |1⟩
2 2
1

= √ |x⟩ ⊗ |0 ⊕ f (x)⟩ − |1 ⊕ f (x)⟩
2
1
= √ |x⟩ ⊗ (−1)f (x) |0⟩ − |1⟩


2
= Pf |x⟩ ⊗ |−⟩

It maps |x⟩ ⊗ |−⟩ to Pf |x⟩ ⊗ |−⟩, maintaining independency.

Boolean and Phase Oracle Rotation effect of Grover iteration Additional Information of QFT Probability Theories for QPE

Reflection of gates back

Think about a matrix A|v ⟩ = 2 |v ⟩ ⟨v | − I , for a vector |v ⟩.

▶ Of course, |v ⟩ is a unit vector.
For ψ = p |v ⟩ + q |v ⊥ ⟩ where |v ⊥ ⟩ holds ⟨v |v ⊥ ⟩ = 0:
A|v ⟩ |ψ⟩ = pA|v ⟩ |v ⟩ + qA|v ⟩ |v ⊥ ⟩
= p(2 |v ⟩ ⟨v | |v ⟩ − I |v ⟩) + q(2 |v ⟩ ⟨v | |v ⊥ ⟩ − I |v ⊥ ⟩)
= p(2 |v ⟩ ⟨v |v ⟩ − |v ⟩) + q(2 |v ⟩ ⟨v |v ⊥ ⟩ − |v ⊥ ⟩)
= p(2 |v ⟩ − |v ⟩) + q(0 − |v ⊥ ⟩)
= p |v ⟩ − q |v ⊥ ⟩
Reflection matrix
A|v ⟩ = 2 |v ⟩ ⟨v | − I reflects the vector about the unit vector |v ⟩.

Thus As is a reflection about the vector |s⟩.

Boolean and Phase Oracle Rotation effect of Grover iteration Additional Information of QFT Probability Theories for QPE

Rotation effect of gates

We can say Pf = A|a⟩ = −A|b⟩ = I − 2 |b⟩ ⟨b|

▶ As Pf : p |a⟩ + q |b⟩ 7→ p |a⟩ − q |b⟩ and ⟨b|a⟩ = 0
Thus for every vector |ψ⟩ on the plane spanned by |a⟩ and |b⟩:

|b⟩ |b⟩
As Pf |ψ⟩
|ψ⟩ |ψ⟩

|s⟩ |s⟩
|a⟩ |a⟩

Pf |ψ⟩ Pf |ψ⟩

As Pf is a rotation of θ where θ/2 = angle between |s⟩ and |a⟩.

Boolean and Phase Oracle Rotation effect of Grover iteration Additional Information of QFT Probability Theories for QPE

Mathematical proof of inverse QFT back

P P
For A |x⟩ = f (x, y ) |y ⟩, we can say A = f (x, y ) |y ⟩ ⟨x|.
y x,y
▶ It is because the inputs are in the orthonormal basis.
Let F is the matrix representing QFT , then the claim is:
N−1 N−1
1 X 2πixy /N 1 X −2πix ′ y ′ /N ′
F =√ e |x⟩ ⟨y | F† = √ e |y ⟩ ⟨x ′ |
N x,y =0 N x ′ ,y ′ =0

Proof of F † F = I
1 X ′ y ′ )/N
F †F = e 2πi(xy −x |x⟩ ⟨x ′ | ⟨y |y ′ ⟩
N
x,y ,x ′ ,y ′
1 X 2πi(x−x ′ )y /N
= e |x⟩ ⟨x ′ |
N ′x,y ,x
1 X 2πi(x−x ′ )y /N X
= e |x⟩ ⟨x ′ | = |x⟩ ⟨x| = I
N ′ x
x,y ,x
Boolean and Phase Oracle Rotation effect of Grover iteration Additional Information of QFT Probability Theories for QPE

Quantum Fourier basis back

For orthonormal basis {x0 , x1 , · · · , xN−1 }, the probability of

measuring xi from qubits |y ⟩ is ⟨y |xi ⟩2
▶ Let |y ⟩ = p0 |x0 ⟩ + p1 |x1 ⟩ + · · · + pi |xi ⟩ + · · · + pN−1 |xN−1 ⟩
▶ Verify yourself
1
Thus xi can be measured from fj with ⟨fj |xi ⟩2 = probability.
N
Proof

⟨fj |xi ⟩2 = ⟨fj |xi ⟩ ⟨xi |fj ⟩

= ⟨xj |F † |xi ⟩ ⟨xi |F |xj ⟩
1 1
= √ e −2πixi xj /N ⟨xj |xj ⟩ ⟨xi |xi ⟩ · √ e 2πixi xj /N ⟨xi |xi ⟩ ⟨xj |xj ⟩
N N
1
=
N
Boolean and Phase Oracle Rotation effect of Grover iteration Additional Information of QFT Probability Theories for QPE

Simple QPE: Chernoff bound back

We can try several times and get average p ′ . How to get p?

We need to choose θ′ less than ε error from θ for any ε > 0.

Chernoff bound(above mean)

Let X1 , · · · , Xn be independent 0/1 random variables, and
X = X1 + · · · + Xn . Then for any µ ≥ E [X ] and for any δ > 0,
!µ
eδ
Pr [X > (1 + δ)µ] <
(1 + δ)1+δ

Chernoff bound(below mean)

Let X1 , · · · , Xn be independent 0/1 random variables, and
X = X1 + · · · + Xn . Then for any µ ≥ E [X ] and for any 0 < δ < 1,
2 µ/2
Pr [X > (1 − δ)µ] < e −δ
Boolean and Phase Oracle Rotation effect of Grover iteration Additional Information of QFT Probability Theories for QPE

Simple QPE: Arc cosine function

We can approximate |p ′ − p| < δp by the Chernoff bound.

But how about |θ′ − θ| = cos−1 (1 − 2p ′ ) − cos−1 (1 − 2p) ?

0
0 0.2 0.4 0.6 0.8 1

We need to bound |θ′ − θ| but it is hard when θ is near 0 or π.

Objective: Find M and c such that |θ′ − θ|c p ≤ M|p ′ − p|
▶ Then we can choose δ = εc /M (Let |θ′ − θ| < 1)
Boolean and Phase Oracle Rotation effect of Grover iteration Additional Information of QFT Probability Theories for QPE

Simple QPE: Finding the power of epsilon

The problem occurs when p → 1 or p → 0.

c
′ |θ′ − θ|c p cos−1 (1 − 2p ′ ) − cos−1 (1 − 2p)) p
f (p , p) := =
|p ′ − p| |p ′ − p|
′ ′
lim
′
f (p , 0) = 0 and we want lim′
f (p , 1) = M < ∞.
p →0 p →1
′ ′
▶ For p ∈ (0, 1), lim
′
f (p , p) = 0 assuming c > 1,
p →p
as cos−1 is differentiable on (0, 1).
If c = 2 then lim
′
f (p ′ , 1) = 4
p →1
Therefore |θ′ − θ|2 p ≤ 4|p ′ − p| for small enough |θ′ − θ|.
▶ This only considers cases when |θ′ − θ| < 1
▶ So |p ′ − p| < ε2 /4 =⇒ |θ′ − θ| < ε.
Bounding p will determine the query complexity.
▶ So we can say that it is not that practical; depending on p.