Main Quantum Algorithms:

Shor and Grover

Ronald de Wolf

Main Quantum Algorithms: Shor and Grover – p. 1/23

 Overview
Recap of previous lecture:
Quantum algorithm: circuit of elementary gates
(such as Hadamard)
This transforms starting state to final state
Measurement of final state yields (classical) output
Algorithm is efficient it it uses few elementary gates
Examples: Deutsch-Jozsa and Simon algorithms

Today’s lecture:
1. Shor’s quantum algorithm for factoring
2. Grover’s quantum algorithm for search
3. Other algorithms

Main Quantum Algorithms: Shor and Grover – p. 2/23

 Factoring
Given N = p · q , compute the prime factors p and q
Fundamental mathematical problem since Antiquity
Fundamental computational problem on log N bits
α
Best known classical algorithms use time 2(log N ) ,
where α = 1/2 or 1/3
Its assumed computational hardness is basis of
public-key cryptography (RSA)
A quantum computer can break this,
using Shor’s efficient quantum factoring algorithm!

Main Quantum Algorithms: Shor and Grover – p. 3/23

 Overview of Shor’s algorithm
Classical reduction: choose random x ∈ {2, . . . , N − 1}.
It suffices to find period r of f (a) = xa mod N
Shor’s quantum algorithm for period-finding uses the
quantum Fourier transform

|0i
.. QFT QFT ..
. . measure
|0i
Of
|0i
.. ..
. . measure
|0i

Overall complexity: roughly (log N )2 elementary gates

Main Quantum Algorithms: Shor and Grover – p. 4/23

 Reduction to period-finding
Pick a random integer x ∈ {2, . . . , N − 1}, gcd(x, N )=1
The sequence x0 , x1 , x2 , x3 , . . . mod N cycles:
has an unknown period r (min r > 0 s.t. xr ≡ 1 mod N )
For at least 1/4 of the x’s:
r is even and xr/2 ± 1 6≡ 0 mod N
Then:
xr = (xr/2 )2 ≡ 1 mod N ⇐⇒
(xr/2 + 1)(xr/2 − 1) ≡ 0 mod N ⇐⇒
(xr/2 + 1)(xr/2 − 1) = kN for some k
xr/2 ± 1 shares a factor with N
This factor of N can be extracted using gcd-algorithm

Main Quantum Algorithms: Shor and Grover – p. 5/23

 Quantum Fourier transform
q−1
1 X 2πijk
Fourier basis (dimension q ): |χj i = √ e q |ki
q
k=0
Quantum Fourier Transform: |ji 7→ |χj i
If q = 2ℓ , then can do this with O(ℓ2 ) gates. |χj0 j1 j2 i =
√1 (|0i + e2πi0.j2 |1i)(|0i + e2πi0.j1 j2 |1i)(|0i + e2πi0.j0 j1 j2 |1i)
8

For Shor: choose q power of 2 in (N 2 , 2N 2 ]

Main Quantum Algorithms: Shor and Grover – p. 6/23
 Easy case: r|q
1. Apply QFT to 1st register of |0 . . . 0i|0 . . . 0i:
q−1
1 X
√ |ai|0i
q
a=0

2. Compute xa mod N (repeated squaring)

q−1
1 X
√ |ai|xa mod N i
q
a=0

3. Observing 2nd register gives |xs mod N i (random s < r)

1st register collapses to superposition of

|si, |r + si, |2r + si, . . . , |q − r + si

Main Quantum Algorithms: Shor and Grover – p. 7/23

 Easy case: r|q (continued)
q/r−1
X
Recall: 1st register is in superposition |jr + si
j=0

4. Apply QFT once more:

 
q/r−1 q−1 q−1 q/r−1  j
X X 2πi (jr+s)b
X 2πi sb
X 2πi rb
e q |bi = e q  e q  |bi
j=0 b=0 b=0 j=0
| {z }
geometric sum

2πi rb rb
Sum 6= 0 iff e = 1 iff
q is an integer
q
q
Only the b that are multiples of have non-zero amplitude!
r
Main Quantum Algorithms: Shor and Grover – p. 8/23
 Easy case: r|q (continued)
q
5. Observe 1st register: random multiple b = c , c ∈ [0, r):
r
b c
=
q r

b and q are known; c and r are unknown

c and r are coprime with probability Ω(1/ log log r)

b
Then: we know r by writing in lowest terms
q

Since we can find r, we can factor!

Main Quantum Algorithms: Shor and Grover – p. 9/23

 Hard case: r 6 |q
b c
We do not have = anymore
q r
 
b c 1
Still, we probably observe a b such that  −  ≤
 
q r 2q
There is at most one fraction with denominator < N in
1 1
an interval of length < 2
q N
c
This fraction must be
r
c b
Can compute from by continued fraction expansion
r q
Again, if c and r are coprime, then we know r

Main Quantum Algorithms: Shor and Grover – p. 10/23

Summary for Shor’s algorithm
Reduce factoring to finding the period r of modular
exponentiation function f (a) = xa mod N
Use quantum Fourier transform to find a multiple of q/r
Repeat a few times to find r
Overall complexity:
QFT takes O(log q)2 ≈ O(log N )2 elementary gates
Modular exponentiation: ≈ (log N )2 log log N gates;
classical computation by repeated squaring
(use Schönhage-Strassen for fast multiplication)
Everything repeated O(log log N ) times
Classical postprocessing takes O(log N )2 gates
Roughly (log N )2 elementary gates in total

Main Quantum Algorithms: Shor and Grover – p. 11/23

 Part 2:

Grover’s algorithm

Main Quantum Algorithms: Shor and Grover – p. 12/23

 The search problem
We want to search for some good item in
an unordered N -element search space
Model this as function f : {0, 1}n → {0, 1} (N = 2n )
f (x) = 1 if x is a solution
We can query f :
Of : |xi|0i 7→ |xi|f (x)i
or
Of : |xi 7→ (−1)f (x) |xi
Goal: find a solution
Classically this takes O(N ) steps (queries to f )
√
Grover’s algorithm does it in N steps

Main Quantum Algorithms: Shor and Grover – p. 13/23

 Grover’s algorithm
Define Grover iteration G = H ⊗n RH ⊗n Of ,
where R negates |xi for all x 6= 0n
Apply G k times on uniform starting state


|0i H ... 

 


 

n |0i H G G ... G measure

 


 

|0i H ...
| {z }
k
Rough idea: each iteration moves √1N amplitude
√
towards solutions ⇒k ≈ N iterations should suffice

Main Quantum Algorithms: Shor and Grover – p. 14/23

 Example
N = 4, f (00) = f (10) = f (11) = 0, f (01) = 1, 1 iteration
Starting state: |00i
1
After H ⊗2 : 2 (|00i + |01i + |10i + |11i)
The 4 parts of one Grover iterate G:
After Of : 21 (|00i−|01i + |10i + |11i)
1
After H ⊗2 : 2 (|00i + |01i − |10i + |11i)
1
After R: 2 (|00i − |01i + |10i − |11i)
After H ⊗2 : |01i, this is the index of the solution!
We found the solution in a space of size 4, with 1 query!

Main Quantum Algorithms: Shor and Grover – p. 15/23

 Analysis
Suppose y is the only solution, so f (x) = 1 iff x = y
Define “good” and “bad” states:
1 X
|Gi = |yi |Bi = √ |xi
N − 1 x6=y

All intermediate states are in span{|Gi, |Bi}

Initial uniform state is sin(θ)|Gi + cos(θ)|Bi
√
for θ = arcsin(1/ N )
Grover iteration is a rotation over angle 2θ:
after k iterations the state is

sin((2k + 1)θ)|Gi + cos((2k + 1)θ)|Bi

Main Quantum Algorithms: Shor and Grover – p. 16/23

How many iterations do we need?
Success probability after k iterations:
2
√ √
sin ((2k + 1)θ), with θ = arcsin(1/ N ) ≈ 1/ N
π 1
If k = − , then success probability is sin2 (π/2) = 1
4θ 2

Example: N = 4 ⇒ k = 1
Choose k nearest integer (small error)
π√
Query complexity is k ≈ N
4
√
Gate complexity is O( N log N )

Main Quantum Algorithms: Shor and Grover – p. 17/23

 Executive summary
Quantum computers can search
√
any
N -element space in about N iterations

√ √
That’s N queries, and N log N elementary gates

r
N
If there are t solutions, then iterations suffice
t

The algorithm has a small error probability,

but can be modified to error 0 if we know t

Main Quantum Algorithms: Shor and Grover – p. 18/23

Application: Speed up NP problems
Given a propositional formula f (x1 , . . . , xn )
Computable in time poly(n)

Question: is f satisfiable?

This is a typical NP-complete problem

Search space of N = 2n possibilities
Classically: exhaustive search is the best we know.
This takes about N steps
Quantumly:
√
Grover finds a satisfying assignment in
N · poly(n) steps

Main Quantum Algorithms: Shor and Grover – p. 19/23

Other applications & generalizations
√
Minimize f : [N ] → R in N steps
Find collision in r-to-1 f in (N/r)1/3 steps
Approximate counting
Amplitude amplification
Find shortest path between 2 vertices
in N -vertex graphs in N 3/2 steps
Minimum spanning tree, other graph problems, . . .
Faster sorting if we have limited space

Main Quantum Algorithms: Shor and Grover – p. 20/23

 Lower bound (BBBV 93)
Fix a T -query quantum search algorithm
|φty i = state before t-th query, on f where only f (y) = 1
αyt = amplitude on query y in |φt∅ i (constant-0 f )
Compare constant-0 f with all other f
Easy: k φt+1
∅
− φ t+1 k≤k φt − φt k +2|αt |, so
y ∅ y y
T
1 X
≤k φT∅ +1 − φTy +1 k≤ 2 |αyt |
2
t=1
T T
N X X X X
Sum over all y : ≤ 2 |αyt | = 2 |αyt |
2
y∈{0,1}n t=1 t=1 y∈{0,1}n
T √ √
C.S. X s X √ N
≤ 2 N t 2
|αy | ≤ 2T N ⇒ ≤T
4
t=1 y∈{0,1} n

Main Quantum Algorithms: Shor and Grover – p. 21/23

 Other quantum algorithms
Generalizations of Shor’s algorithm
Discrete logarithm (Shor), elliptic curves
Hidden subgroup problem (Kitaev)
Pell’s equation (Hallgren)

Quantum random walks

Element distinctness (Ambainis)
Verifying AB = C for matrices (Buhrman & Špalek)
Computing formulas (Farhi et al)

Main Quantum Algorithms: Shor and Grover – p. 22/23

Summary: quantum algorithms
Shor’s algorithm (1994) factors an n-bit integer in
roughly n2 elementary quantum gates. This is
exponential speed-up over best known classical algo
breaks a lot of public-key cryptography

Grover’s algorithm
√
(1996) searches a size-N search
space in ∼ N time
quadratic speed-up over classical
widely applicable

Many other quantum algorithms discovered since then

Next lecture: quantum communication

Main Quantum Algorithms: Shor and Grover – p. 23/23