MULT20015 Elements of Quantum Computing Lecture 13
Subject outline
Lecture topics (by week)
1 – Introduction to quantum computing and maths basics 2 – Single qubit representations and logic operations
3 – Two qubit states and logic gates
4 – Multi-qubit states and quantum arithmetic
5 – Basic quantum algorithms
6 – Period finding, cryptography and quantum factoring
7 – Shor’s algorithm, post-quantum crypto, quantum key distribution 8 – Quantum search algorithms
9 – Grover search applications, optimisation problems
10 – Solving optimisation problems on quantum computers
11 – Applications in quantum machine learning
12 – Real quantum computer devices
Assignment schedule:
#1: Hand out in Week 2
#2: Hand out in Week 8
MULT20015 Elements of Quantum Computing Lecture 13
Lecture 13
Shor’s factoring algorithm
MULT20015 Elements of Quantum Computing Lecture 13
Recap of the last two lectures
MULT20015 Elements of Quantum Computing Lecture 13
Last week recap: Factoring and period finding
If we can find the period of
f(k) = ak mod N
efficiently, we can factor N efficiently.
If we can find this period efficiently, and we can then use classical techniques to factor semi-prime numbers into their prime factors.
MULT20015 Elements of Quantum Computing Lecture 13
Quantum Phase Estimation as a function
Uf
t register
Output register
|i
U |ti| i = |tiexp(i2⇡✓t)| i
Quantum computers find periods of periodic functions efficiently!
MULT20015 Elements of Quantum Computing Lecture 13
Period of which Function?
So what if we use a quantum computer to find the period of modular exponentiation,
This is Shor’s algorithm!
f(k) = ak mod N
MULT20015 Elements of Quantum Computing Lecture 13
13.1 Shor’s algorithm
MULT20015 Elements of Quantum Computing Lecture 13
Shor’s algorithm
Two registers*:
2n qubits n=L qubits
Uf
(1) Equal superposition
(2) Calculate function:
f(x) = ax mod N
* L = number of bits in N
Shor, Proc 35th Ann Symp of Comp Sci, 26, (1995)
(3) QFT
(4) Measure result
This is an application of the quantum phase estimation circuit which you saw last lecture.
MULT20015 Elements of Quantum Computing Lecture 13
Shor’s algorithm explained
After the Hadamard gates, the top register is in the equal superposition:
NX 1 x=0
1 | i=pn
2N
|xi|1i
MULT20015 Elements of Quantum Computing Lecture 13
Recap: Implementing irreversible functions
Step 2 is to calculate the modular exponentiation function. As we have seen in previous lectures, we can implement functions:
Input
Repeated at output
|xi |0i
Uf
|xi |f (x)i
(2) Calculate function: f(x) = ax mod N
Next slide shows how to efficiently perform this function on a quantum computer. It might look complicated, but is simply evaluating this modular exponentiation function.
MULT20015 Elements of Quantum Computing Lecture 13
Recap: Factoring and period finding
We want to factor N=15. Take a number a=2 (say) relatively-prime to N (ie. no prime factors in common) and find the order r of a. That is the least r>0, such that ar = 1 mod 15:
20=1 mod15 21=2 mod15 22=4 mod15 23=8 mod15 24=1 mod15
After which the pattern repeats.
Formally, we say: the order of 2 mod 15 is 4. Or, if we defined a function:
f(k) = ak mod N We would say that the period of f is r, since f(k+r) = f(k).
MULT20015 Elements of Quantum Computing Lecture 13
Recap: Example of finding factors from a period
In our case, we have a=2, N=15 and r=4. Happily r=4 is even. We can
rearrange:
ar=1 modN ar 1=0 modN
(ar/2+1)(ar/2 1)=0 modN ar/2 1=24/2 1=3
ar/2 +1=24/2 +1=5 3 ⇥ 5 = 15
In our case,
and
MULT20015 Elements of Quantum Computing Lecture 13
Recap: Divisors of N
In our case 3 and 5 divide N=15 exactly, but we’re not guaranteed that always, only that:
ie. that
(ar/2+1)(ar/2 1)=0 modN (ar/2 + 1)(ar/2 1) = kN
As long as neither factor is a multiple of N, then both will have non-trivial factors with N. To find these factors, we find the greatest common divisors (for which the Euclidean algorithm is efficient):
gcd(ar/2 +1,N)
gcd(ar/2 1,N) These give a non-trivial factor of N.
If r is odd or if the factors found are trivial, we repeat the algorithm with a different choice of a.
MULT20015 Elements of Quantum Computing Lecture 13
Modular exponentiation
2L qubits L qubits
Most Significant Bit
Least Significant Bit
Unitary which performs multiplication by a1, a2, a4 … mod N
For example if the top register contained x = 1012, and a=2, and N=15 then we would:
Top register in superposition, so bottom register is correlated (entangled) with the top register
• Start with 1
• Multiply by a1=21=2 giving 2 mod 15
• Not multiply by a2=22=4
• Multiply by a4=24=16 giving 32 or 2 mod 15
MULT20015 Elements of Quantum Computing Lecture 13
Example of modular exponentiation
|xi |ax mod Ni
After modular exponentiation: X
| i =
x
| i=(|0i+|4i+|8i+|12i)⌦|1i +(|1i+|5i+|9i+|13i)⌦|2i +(|2i+|6i+|10i+|14i)⌦|4i +(|3i+|7i+|11i+|15i)⌦|8i
Note: States are unnormalized! (for simplicity)
e.g. For a=2, N=15:
|xi|ax
mod Ni
MULT20015 Elements of Quantum Computing Lecture 13
Shor’s algorithm explained
|xi |ax mod Ni
If, at this point the bottom register is measured to be 2 (at random), we may collapse to the state:
| i=(|1i+|5i+|9i+|13i)⌦|2i
MULT20015 Elements of Quantum Computing Lecture 13
The quantum Fourier transform
13.2 QFT for Shor’s algorithm
MULT20015 Elements of Quantum Computing Lecture 13
Introduction to Fourier transform
Time domain
If we have a periodic function, and want to know:
What is the period/frequency of this function?
This can be achieved using the Fourier Transform
Frequency Domain
There is an efficient version of the Fourier Transform for quantum computers, which acts on states in superposition. This is known as the Quantum Fourier Transform.
Fourier Transform
MULT20015 Elements of Quantum Computing Lecture 13
The quantum Fourier transform
Imagine we measure the bottom register, and plot the amplitudes in the top register:
| i=(|1i+|5i+|9i+|13i)⌦|2i
This function is periodic, with a period of r.
MULT20015 Elements of Quantum Computing Lecture 13
Taking the QFT
|xi |ax mod Ni
MULT20015 Elements of Quantum Computing Lecture 13
Inverse QFT for N=15, a=2
To find the period, we will take the Quantum Fourier Transform to reveal r (and so also, if r is even, factors of N).
The result of taking a Fourier transform is a “spectrum” peaked around (for integer, k):
k2n r
n (2L) is number of qubits in the top register r is the period being determined
MULT20015 Elements of Quantum Computing Lecture 13
When r doesn’t divide evenly
What happens when r doesn’t divide evenly into the top register? Then we still get a very peaked distribution around the same values:
Peaked around:
k2n r
Here is an example for r=3 and 2n=256.
MULT20015 Elements of Quantum Computing Lecture 13
13.3 Measurement and post-processing
MULT20015 Elements of Quantum Computing Lecture 13
Measurement
|xi |ax mod Ni
Measurement will randomly give one of these values, close to:
m = k 2n r
k=m r 2n
We need a rational approximation of m/2n to find r.
or
MULT20015 Elements of Quantum Computing Lecture 13
Example for a=2, N=15
In our example:
k = m r 2n
We might randomly measure m=4
m=4 2n 16
= 14
and in this case:
Note: This step might only reveal a factor of r, and so might have to be repeated…
Since this is equal to k/r, We have correctly found
r=4
MULT20015 Elements of Quantum Computing Lecture 13
Continued Fractions
The result of taking a Fourier transform is a spectrum peaked around (for integer, k):
k2n r
Unless r divides 2n exactly, we will only get an approximation to k2n/r when measured.
Most of the time 2n and r will be relatively prime. The problem then is find good approximations to the measured value m/2n = k/r. The “correct” approximation yields the period, r, as the denominator.
A good method for making rational approximations is to use the continued fractions method.
a0+ 1 a1+ 11
a2+… 1 an
MULT20015 Elements of Quantum Computing Lecture 13
Continued Fraction of Pi
As an example, let’s try to make a rational approximation to pi. Our first approximation is
approximation:
(a0 = 3)
The remaining decimal part is 0.14159265… = 1/7.0625… This gives a second
⇡⇡3
⇡ ⇡ 3 + 17
(a1 = 7) The remaining decimal part 0.0625 = 1/15.9966… This gives a third
approximation:
⇡ ⇡ 3 + 1 (a2 = 15) 7+1
And so on. This method can be used to find good rational approximations to v/2n and find r.
15
MULT20015 Elements of Quantum Computing Lecture 13
Example: Factoring the number
ar/2 1=24/2 1=3 ar/2 +1=24/2 +1=5
Not really necessary here, but in general you’d have to evaluate:
gcd(3, 15) = 3 gcd(5, 15) = 5
And so we’ve found two non-trivial factors of 15:
3 ⇥ 5 = 15
MULT20015 Elements of Quantum Computing Lecture 13
13.4 Shor’s algorithm summary
MULT20015 Elements of Quantum Computing Lecture 13
Shor’s algorithm method
1. Randomly pick integer 0 < a < N (and check a coprime to N)
2. Use quantum circuit to calculate: ax mod N, QFT x.
3. Measure to obtain and approximation to m = k 2n/r
4. Use continued fractions of m/22n to obtain even r
5. Use Euclidean algorithm to find gcd of N with (ar/2+1) and (ar/2-1)
6. Repeat if necessary
MULT20015 Elements of Quantum Computing Lecture 13
Shor’s algorithm summary
• Efficient quantum algorithms for factoring semiprime numbers
• Best known classical algorithm is number field sieve (exponential in
bit-length).
• Underpins the RSA cryptosystem
• Hidden Subgroup Problems (eg. Discrete logarithm) similar.
Peter Shor
Shor, Proc 35th Ann Symp of Comp Sci, 26, (1995)
MULT20015 Elements of Quantum Computing Lecture 13
Subject outline
Lecture topics (by week)
1 – Introduction to quantum computing and maths basics 2 – Single qubit representations and logic operations
3 – Two qubit states and logic gates
4 – Multi-qubit states and quantum arithmetic
5 – Basic quantum algorithms
6 – Period finding, cryptography and quantum factoring
7 – Shor’s algorithm, post-quantum crypto, quantum key distribution 8 – Quantum search algorithms
9 – Grover search applications, optimisation problems
10 – Solving optimisation problems on quantum computers
11 – Applications in quantum machine learning
12 – Real quantum computer devices
Assignment schedule:
#1: Hand out in Week 2
#2: Hand out in Week 8