代写代考 MULT90063 Introduction to Quantum Computing

MULT90063 Introduction to Quantum Computing
Lecture 11
Fourier Transformations, Regular Fourier Transform, Fourier Transform as a matrix, Quantum Fourier Transform, QUI examples, Inverse QFT
Lecture 12

Simon’s algorithm, Shor’s Quantum Factoring algorithm, Shor’s algorithm for factoring and discrete logarithm, HSP Problem
QFT and Shor’s algorithm

MULT90063 Introduction to Quantum Computing
Third Quantum Algorithm: Simon’s algorithm

MULT90063 Introduction to Quantum Computing
Simon’s Problem
Given a 2-to-1 function, f, such that
f(x) = f(x a)
Unlike the previous two examples, here the range of f(x) is Z, integers.
Simon’s algorithm is an example of a “Hidden (Abelian) subgroup problem” (HSP) and was the inspiration for Shor’s factoring algorithm.

MULT90063 Introduction to Quantum Computing
Example of a hidden a
f(001) = f(111)
We would like to find the hidden ‘a’ s.t.
f(x) = f(x a)
In this case:

MULT90063 Introduction to Quantum Computing
Solving Simon’s problem classically
Just try different inputs until you see a collision:
f(000) = 0 f(011) = 3 f(111) = 1 f(010) = 2 f(001) = 1
Actually this is equivalent to the famous “birthday” problem, and takes fewer queries than you might expect. Probabilistically, if there are N different inputs we need p
Evaluations of the function before we find a collision.
Simon’s algorithm does the same with O(n) queries.

MULT90063 Introduction to Quantum Computing
Simon’s algorithm circuit
Randomly measure a result of the function. Collapse to a superposition of inputs which give that value. Send these through Hadamard gates, and measure:
|xi |xi
|0i |0f(x)i
Measure to find a
f(x0),f(x0 a)

MULT90063 Introduction to Quantum Computing
Simon’s algorithm
After the initial Hadamard gates:
| i=pN x |xi|0i

MULT90063 Introduction to Quantum Computing
Simon’s algorithm
After evaluation of the function:
Uf|xi|0i |xi|f(x)i
|xi |xi
|0i |0f(x)i

MULT90063 Introduction to Quantum Computing
Simon’s algorithm
It’s easiest to consider that the bottom register is measured first. Before measurement the state is: X
| i=pN x |xi|f(x)i
Some value, f(x0) will be measured at random, and the top register collapses
|x0i+|x0 ai |i= p2

MULT90063 Introduction to Quantum Computing
Example: Measuring function
| i=pN x |xi|f(x)i
= p8(|0i|0i+|1i|1i+|2i|2i+|3i|3i+|4i|2i+|5i|3i+|6i|0i+|7i|1i)
If we measure the second register, and measure obtain “3”, the state collapses to only those states compatible with this measurement:
Firstregister:
0 |3i |3i + |5i |3i |i= p2
|x0i+|x0 ai | i= p2

MULT90063 Introduction to Quantum Computing
Simon’s algorithm
We now apply Hadamard to the top register:
⌦n|x0i+|x0 ai | i=H p2

MULT90063 Introduction to Quantum Computing
Hadamard applied to a general state
Amplitude ay -> how many times does the binary reXpresentation of y and x have 1’s in the same location?
H |xi=p az|zi
ay |yi x0y0 +x1y1 +x2y2 +…+xnyn n
x · y = When 1’s in the same location, we get a sign change -> (1)x·y
Shorthand for the bitwise dot product is:
Hadamards applied to a general state (n qubits, N = 2n):
H⌦n |xi = pN (1)x·y |yi
(changed dummy index to y)

MULT90063 Introduction to Quantum Computing
Simon’s algorithm
| i=p1 X(1)x0·y|yi 2n1 a·y=0
Each time we measure, we randomly measure a “y” which is orthogonal to “a”: Obtain n random y’s this way and perform Gauss/Jordan elimination to obtain “a”
a·y=0 mod2

MULT90063 Introduction to Quantum Computing
Example of Simon’s algorithm
We would like to find the hidden ‘a’ s.t.
f(x) = f(x a) In this case, a=1102=6

MULT90063 Introduction to Quantum Computing
Running the circuit
a·y=0 mod2 We run the circuit, and at random, obtain measure the results:
We want to find, a=1102=6

MULT90063 Introduction to Quantum Computing
In matrix form
Weknowthat a·y=0 mod2
We have three values of ‘y’ for which this is true, so we can write a
system of linear equations for the bits of ‘a’:
24 0 0 1 0 35 1100 211103
Measured values
0010 ⇠411005
Solving for a Solution is degenerate. a=(0,0,0) or a1=a2=1 ie. a=(1,1,0)

MULT90063 Introduction to Quantum Computing
Simon’s Algorithm
Given a 2-to-1 function, f, such that
f(x) = f(x a)
Classical algorithm: O(pN)
Queries to the oracle (probabilistically)
Quantum algorithm:
O(n) Queries to the oracle

MULT90063 Introduction to Quantum Computing
Quantum Factoring Algorithm
Lecture 12

MULT90063 Introduction to Quantum Computing
Quantum factoring algorithm
• Shor’s Factoring algorithm
– Shor’s algorithm for factoring and
discrete logarithm – HSP Problem
– RSA cryptography
Reiffel, Chapter 8
Kaye, Chapter 7
Nielsen and Chuang, Chapter 5

MULT90063 Introduction to Quantum Computing
Shor’s algorithm
• Efficientquantumalgorithmsforfactoringsemiprime numbers
• Bestknownclassicalalgorithmisnumberfieldsieve (exponential in bit-length).
• UnderpinstheRSAcryptosystem
• HiddenSubgroupProblems(eg.Discretelogarithm)similar.

Shor, Proc 35th of Comp Sci, 26, (1995)

MULT90063 Introduction to Quantum Computing
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, 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(x+r) = f(x).

MULT90063 Introduction to Quantum Computing
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 ar1=0 modN
(ar/2+1)(ar/21)=0 modN ar/2 1=24/2 1=3
ar/2 +1=24/2 +1=5 3 ⇥ 5 = 15
In our case,

MULT90063 Introduction to Quantum Computing
Divisors of N
In our case 3 and 5 divide N=15 exactly, but we’re not guaranteed that always, only that:
(ar/2+1)(ar/21)=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 even or if the factors found are trivial, we repeat the algorithm with a different choice of a.

MULT90063 Introduction to Quantum Computing
TLDR: Factoring and Period finding
If we can find the period of
f(k) = ak mod N
efficiently, we can factor efficiently.
Shor’s algorithm finds this period efficiently, and we can then use classical techniques to factor semi-prime numbers into their prime factors.

MULT90063 Introduction to Quantum Computing
Shor’s algorithm
Two registers*:
2L qubits L qubits
(1) Equal superposition
(2) Calculate function:
f(x) = ax mod N
* L = number of bits in N
Shor, Proc 35th of Comp Sci, 26, (1995)
(4) Measure result

MULT90063 Introduction to Quantum Computing
Shor’s algorithm explained
After the Hadamard gates, the top register is in the equal superposition:
| i = pN x=0 |xi |1i

MULT90063 Introduction to Quantum Computing
Modular Exponentiation
2L qubits L qubits
Most Significant Bit
Least Significant Bit
Multiplication by a1, a2, a4 … mod N
For example if the top register contained x = 101, 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

MULT90063 Introduction to Quantum Computing
Example of Modular Exponentiaion
|xi |ax mod Ni
After modular exponentiation: 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:

MULT90063 Introduction to Quantum Computing
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

MULT90063 Introduction to Quantum Computing
The 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.

MULT90063 Introduction to Quantum Computing
Taking the QFT
|xi |ax mod Ni

MULT90063 Introduction to Quantum Computing
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):
n (2L) is number of qubits in the top register r is the period being determined

MULT90063 Introduction to Quantum Computing
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:
Here is an example for r=3 and 2n=256.

MULT90063 Introduction to Quantum Computing
Measurement
|xi |ax mod Ni
Measurement will randomly give one of these values, close to:
m = k 2n r
We need a rational approximation of m/2n to find r.

MULT90063 Introduction to Quantum Computing
Example for a=2, N=15
In our example:
k = m r 2n
We might randomly measure m=4
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

MULT90063 Introduction to Quantum Computing
Continued Fractions
The result of taking a Fourier transform is a spectrum peaked around (for integer, k):
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

MULT90063 Introduction to Quantum Computing
Continued Fraction of Pi
As an example, let’s try to make a rational approximation to pi. Our first approximation is
approximation:
The remaining decimal part is 0.14159265… = 1/7.0625… This gives a second
⇡ ⇡ 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.

MULT90063 Introduction to Quantum Computing
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

MULT90063 Introduction to Quantum Computing
Shor’s algorithm Summary
1. Randomly pick integer 0 < a < N (and check a is not a factor of N) 2. Apply the circuit above, using modular exponentiation to calculate ax, QFT x. 3. Measure to obtain and approximation to m = k 2n/r 4. Use continued fractions of m/2n to obtain even r 5. Use Euclidean algorithm to find common factors of N with (ar/2+1) and (ar/2-1) 6. Repeat if necessary MULT90063 Introduction to Quantum Computing Shor’s algorithm • Efficientquantumalgorithmsforfactoringsemiprime numbers • Bestknownclassicalalgorithmisnumberfieldsieve (exponential in bit-length). • UnderpinstheRSAcryptosystem • HiddenSubgroupProblems(eg.Discretelogarithm)similar. Shor, Proc 35th of Comp Sci, 26, (1995) MULT90063 Introduction to Quantum Computing Private Key Cryptography Much of internet security relies on ‘public key cryptography’. RSA cryptography relies on the difficulty of factoring large semi-primes. The best known classical algorithm is the number field sieve: O(e1.9(log N )1/3 (log log N )2/3 ) Shor’s factoring quantum algorithm solves the same problem in poly-log time: O((log N)2(log log N)(log log log N)) MULT90063 Introduction to Quantum Computing RSA Factoring Challenge RSA Factoring Challenge, Wikipedia Factoring a 768 bit number took ~1,500 years CPU time (largest RSA factoring challenge solved). Factoring a 2048 bit number is estimated will take ~1 day on a large scale quantum computer (running at typical speeds, and low error). MULT90063 Introduction to Quantum Computing Discrete Logarithm A closely related class of problems which are important for cryptography are solving discrete logarithm problems: Given, a, b and N, st. find t. RSA is based on factoring. Diffie-Hellman key exchange, and elliptic curve cryptography rely on discrete logarithm being a hard problem. MULT90063 Introduction to Quantum Computing Circuit for Discrete Logarithm Measurement of the second register reveals: k/r Measurement of the first register reveals: kt/r mod r Note: same k! At least in principle we can know r by Shor’s factoring algorithm, so only t is unknown, and can easily found: k-1kt = t mod r MULT90063 Introduction to Quantum Computing Hidden Subgroup Problems The generalisation of Shor’s algorithm to arbitrary groups is known as the Hidden Subgroup Problem: Let G be a group. Suppose a subgroup H

Related Posts