Preliminaries Shor’s Algorithm Example

Basic Quantum Algorithms

Fred Ezerman

Senior Research Fellow

School of Physical and Mathematical Sciences
Nanyang Technological University, Singapore.

Institut Teknologi Bandung

1 November 2017
Preliminaries Shor’s Algorithm Example

Preliminaries

Shor’s Algorithm

Example
Preliminaries Shor’s Algorithm Example

A Big Picture

Upside-down turns in Science (1905 – 1953)

• Physics (twice!): general relativity and quantum mechanics.
• Formal logic (perhaps even philosophy): Godel’s
undecidability.
• Economics: Keynes.
• Birth of Computer Science: Turing, Church, von Neuman.
• Statistics as a scientific discipline: Fisher, Neyman, Pearson.
• Probability theory: Kolmogorov.
• Birth of Information Theory: Shannon circa 1948.
• DNA double-helix structure: Crick and Watson.
In this lecture series, we see how QM, Comp. Sci, Inf. Theory, and
Molecular Bio. interact and what some of the implications are.
Preliminaries Shor’s Algorithm Example

5th Solvay Conference

Brussels, 1927
Preliminaries Shor’s Algorithm Example

Shannon and Turing

• Early 1943 for two months in Washington DC.

• Shannon was at Bell-Labs. Turing was visiting to share British
GCHQ’s method of breaking the German cipher.
• They met daily at the cafeteria, discussing computing, crypto,
AI, and conceptualized a chess program.
Preliminaries Shor’s Algorithm Example

Information is Physical

• At the intersection of Information Theory, Computing, and

Physics.
• Highly interdiscplinary.
• Mathematicians and Computer Scientists must think in terms
of the physical realizations.
• In physics, the debate (often philosophical) over the nature
and interpretations of QM started to give way to how to
harness the power of QM for information processing.
• QM is about information and probabilities and observables,
and how they relate to each other.
• Using Information Theory, physicists can test whether QM is
complete.
Preliminaries Shor’s Algorithm Example

Bits and Qubits

• Qubits are physical objects.
• Here, most of the times, we treat them as mathematical
objects using Dirac notations.
• But why? It gives us freedom of abstraction without
depending too much on the specifics of the physical systems.
Preliminaries Shor’s Algorithm Example

More on Qubits

• A qubit lives in C2 and has a state.

• Two possible states are |0i and |1i, like 0 and 1 for a bit.
• Here where it differs: a qubit can be in a superposition of |0i
and |1i, e.g., |ψi , α |0i + β |1i with |α|2 + |β|2 = 1 for
α, β ∈ C.
1 1
• Example: Consider |ψi = √ |0i + √ |1i.
2 2
• In fact, one can express a qubit in orthonormal bases other
than {|0i , |1i} (Think linear algebraically).
Preliminaries Shor’s Algorithm Example

Bloch Sphere
√
• Let i = −1. The state |ψi in example can be written as
 
iγ θ iϕ θ
|ψi = e cos |0i + e sin |1i with θ, γ, ϕ ∈ R.
2 2
• The term e iγ can be ignored since it has no observable effect.
• The numbers θ and ϕ define a point on a three dimensional
sphere called Bloch sphere.
Preliminaries Shor’s Algorithm Example

Multiple Qubits

• An n qubit system has 2n computational basis states forming

the set {|vi : v ∈ Fn2 }.
X n
X
• A typical state is |ψi , αi |vi i with |αi |2 = 1.
vi ∈Fn2 i=1
• Example: A two qubit system has CBS |00i , |01i , |10i , |11i.
A state is a (normalized) linear combination of elements in
CBS.
• Notations often confuse beginners, e.g., hψ| |ϕi denote inner
product of two states, i.e., a scalar; while |ψi hϕ| denote the
(matrix) outer product, and

|001i = |0i ⊗ |0i ⊗ |1i = |13 i .

Preliminaries Shor’s Algorithm Example

Gates and Operators

• We express changes occurring to a state in the language of

quantum computation, i.e., as unitary matrices or operators
that represent gates, circuits, etc.
• This is what one sees in books or papers written by quantum
computer scientists.
• Here are some basic wire symbols.
Preliminaries Shor’s Algorithm Example

More Gates and Operators

Here is a list of common operators
Preliminaries Shor’s Algorithm Example

More . . .
And some more.
Preliminaries Shor’s Algorithm Example

More . . .

And some less common ones.

Preliminaries Shor’s Algorithm Example

References for Studies

• Michael Nielsen and Isaac Chuang, Quantum Computation

and Quantum Information 10th Anniversary Edition, 2011,
Cambridge Univ. Press. First 3 chapters.
• Lecture notes available online: John Preskill, Jan Woutrous,
Mark Wilde.
• Survey materials.
Preliminaries Shor’s Algorithm Example

Basic References

• Technical paper: Polynomial-Time Algorithms for Prime

Factorization and Discrete Logarithms on a Quantum
Computer, SIAM J. Comput., vol. 26, no. 5, pp. 1484–1509,
Oct. 1997.
• Chuang and Nielsen, Chapter 5.
Preliminaries Shor’s Algorithm Example

Recall RSA
Basis of many commercial public key cryptosystems and protocols.
Preliminaries Shor’s Algorithm Example

Classical Ingredients; Complexity on Input n-String

• Euclidean Algorithm to find greatest common divisor (GCD).

• Test of Primality.
• Deterministic like Agrawal Kayal Saxena (AKS) Algorithm
O(n6 ). PRIMES is in P. Annals of Mathematics, 160 (2).
• Probabilistic like Miller-Rabin Test O(n4 ).
• Prime Power Test, e.g., Bernstein 1997 O(n).
Detecting perfect powers in essentially linear time.
Math. of Computation of AMS vol. 67, 1998.
• Continued fraction expansion to approximate a rational
number by an integer fraction. Most textbooks in Number
Theory discuss this.
Preliminaries Shor’s Algorithm Example

Discrete Fourier Transform

The Discrete Fourier Transform (DFT) transforms a set

{x0 , . . . , xN−1 } with xj ∈ C into a set of complex numbers
y0 , . . . , yN−1 defined by
N−1
1 X 2πi jk
yk = √ e N xj . (1)
N j=0

DFT is very useful in many branches of science: the transformed

version of the problem is often (much) easier to solve than the
original problem.
Preliminaries Shor’s Algorithm Example

Quantum DFT

• Define a (unitary) transformation U on n qubits by its action

on computational basis states |ji for j ∈ J0, 2n − 1K given by
2n −1
1 X 2πi jkn
|ji 7→ √ e 2 |ki.
2n k=0
• Writing out its action on superpositions,
n −1
2X 2n −1
" 2n −1
# 2Xn −1
1 X 1 X 2πi jkn
xj |ji 7→ √ √ e 2 xj |ki = yk |ki
j=0
2n k=0 2n k=0 k=0
(2)
corresponds to a vector notation for (1) for N = 2n .
• Classically, DFT takes n2n steps for 2n numbers.
• On a quantum computer, only log2 (2n ) = n2 steps.
Exponential saving!
Preliminaries Shor’s Algorithm Example

Quantum DFT

• Define a (unitary) transformation U on n qubits by its action

on computational basis states |ji for j ∈ J0, 2n − 1K given by
2n −1
1 X 2πi jkn
|ji 7→ √ e 2 |ki.
2n k=0
• Writing out its action on superpositions,
n −1
2X 2n −1
" 2n −1
# 2Xn −1
1 X 1 X 2πi jkn
xj |ji 7→ √ √ e 2 xj |ki = yk |ki
j=0
2n k=0 2n k=0 k=0
(2)
corresponds to a vector notation for (1) for N = 2n .
• Classically, DFT takes n2n steps for 2n numbers.
• On a quantum computer, only log2 (2n ) = n2 steps.
Exponential saving!
Preliminaries Shor’s Algorithm Example

Quantum DFT

• Define a (unitary) transformation U on n qubits by its action

on computational basis states |ji for j ∈ J0, 2n − 1K given by
2n −1
1 X 2πi jkn
|ji 7→ √ e 2 |ki.
2n k=0
• Writing out its action on superpositions,
n −1
2X 2n −1
" 2n −1
# 2Xn −1
1 X 1 X 2πi jkn
xj |ji 7→ √ √ e 2 xj |ki = yk |ki
j=0
2n k=0 2n k=0 k=0
(2)
corresponds to a vector notation for (1) for N = 2n .
• Classically, DFT takes n2n steps for 2n numbers.
• On a quantum computer, only log2 (2n ) = n2 steps.
Exponential saving!
Preliminaries Shor’s Algorithm Example

Circuit to Implement QFT

Preliminaries Shor’s Algorithm Example

Reduction of Factoring to Period Finding

Source: Gary Miller, Riemann’s Hypothesis and tests for primality.
J. of Computer and System Sciences 13 (3), 1976.
• On input a number N ∈ N represented as an n-string, outputs
a nontrivial factor of N.
• Runtime O(n3 ). Succeed with high probability.
• If 2 | N, outputs 2.
• Use Bernstein Alg. to test if N = ab , i.e., a prime power. If
yes, returns a.
• Randomly choose x from J1, N − 1K. If gcd(x, N) > 1, return
gcd(x, N).
• Find the order r of x modulo N, i.e., find the smallest r such
that x r ≡ 1 (mod N).
• If r is even and x r /2 6≡ −1 (mod N), compute
r1 := gcd(x r /2 − 1, N) and r2 := gcd(x r /2 + 1, N). Return if
either one is a nontrivial factor of N.
• Else, the algorithm fails.
Preliminaries Shor’s Algorithm Example

Shor’s Algorithm Steps

Input: a number N, output: factorization of N = p · q, with high

probability.
1. Determine if N is even, a prime, or a prime power. If yes,
reduce the problem and repeat.
2. Pick a random integer x < N and compute gcd(x, N). If 6= 1,
we have obtained a factor.
3. The Quantum Algorithm part: period finding through QFT.
Measurement gives a variable c satisfying qc ≈ dr where d ∈ N.
4. Determine d, r via Continued Fraction Expansion Alg. This
can be done if gcd(d, r ) = 1.
5. If r is odd, go back to (2). If x r /2 ≡ −1 (mod N), go back to
(2). Otherwise, the factors p, q = gcd(x r /2 ± 1, N).
Preliminaries Shor’s Algorithm Example

Period Finding Algorithm

• Let q = 2` . Given a periodic function

f : J0, q − 1K 7→ J0, q − 1K, the periodicity conditions are
f (a) = f (a + r ) with r 6= 0 and f (a) 6= f (a + s)∀s < r .
• Initialize a quantum state |Φi = |0i⊗2` .
• Apply Hadamard gates on the first ` qubits and the identity
 ⊗`
1
operator I to the others, yielding √ (|0i + |1i) ⊗ |0i⊗` .
2
• Apply the unitary operator that implement the function
f = x a (mod N), getting
q−1
1 X
√ |ai |f (a)i
q
a=0
Preliminaries Shor’s Algorithm Example

Period Finding Alg. (cont.)

• If one performs a measurement on |f (a)i, the

post-measurement
r state of the first ` qubits is
r X
|Φiz = |ai.
q
a=0:f (a)=z

• Since f is periodic, let a0 , min a|f (a) = z and rewrite

q/r −1
X
|Φiz = |a0 + t · r i, assuming r | q.
t=0
Preliminaries Shor’s Algorithm Example

The QFT Part

Preliminaries Shor’s Algorithm Example

Computing the Probability

• The overall probability of measuring a c 0 of the form kq

r is then

X  2 1
hc 0 | |Φ̃i = r · = 1.

0
r
c =kq/r

kq
• The output is a natural number that has the form with
r
k ∈ N.
Preliminaries Shor’s Algorithm Example

Factoring 21

• Choose a random integer x ∈ J2, N − 1K. If it is not coprime

with 21, say x = 6, then gcd(6, 21) = 3 =⇒ 21/3 = 7.
Output and exit.
• If coprime with 21, say x = 11, then continue.
• Determine q = 2` such that 212 = 441 ≤ q < 2(21)2 . Here
q = 29 .
• The initial state has two registers of length ` = 9, i.e.,
|Φinit. i = |0ir1 |0ir2 = |0i⊗18 .
Preliminaries Shor’s Algorithm Example

First Register
Preliminaries Shor’s Algorithm Example

Second Register
Preliminaries Shor’s Algorithm Example

Apply QFT on Register One

Preliminaries Shor’s Algorithm Example

Measurement
Preliminaries Shor’s Algorithm Example

The Period
Preliminaries Shor’s Algorithm Example

Tying Loose Ends

Preliminaries Shor’s Algorithm Example

Final Check