程序代写CS代考 algorithm MULT20015 Elements of Quantum Computing Lecture 12

MULT20015 Elements of Quantum Computing Lecture 12
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 12
Week 6
Lecture 11
11.1 Introduction to Cryptography 11.2 Public Key Cryptography
11.3 RSA Cryptography
11.4 Security of RSA
11.5 Factoring and Period Finding
Lecture 12
12.1 Quantum Phase Estimation 12.2 Quantum Fourier Transform 12.3 Phase as a periodic function
Practice class 6
RSA and Quantum Phase Estimation

MULT20015 Elements of Quantum Computing Lecture 12
Recap: Story of Cryptography
Alice (Sender)
– Uses an Encryption Function (E)
–
Eve (Adversary)
Uses network probes to attack communication
Tampering & eavesdropping
Bob (Receiver)
– Uses a Decryption Function (D)
Kd Decryption Key (Private);
m (Plain Text)
E
C
Ke
Encryption Key (Public/Private)
C’
D
m’
(Recovered Plain Text)
E, D are public; c is the ciphertext, c’ is received ciphertext; ideally m=m’;
Cryptography involves many conceptual ideas, we look at the basic functions Images: General Internet resources
= Sent ciphertext
= Received Cipher Text (Could be in error)

MULT20015 Elements of Quantum Computing Lecture 12
Recap: Factoring and Period finding
The security of RSA comes down to factoring. In turn factoring can be reduced to period finding:
If we can find the period of efficiently, we can factor efficiently.
f(k) = ak mod N
Classically, we do not have any efficient algorithm for the period finding problem. This lecture we’ll look at period finding on a quantum computer, extending what we’ve already seen in Simon’s algorithm.

MULT20015 Elements of Quantum Computing Lecture 12
12.1 Quantum Phase Estimation

MULT20015 Elements of Quantum Computing Lecture 12
The Problem
Consideraneigenvector| iofaunitarymatrix(anoperationwhichyoucould implement on a quantum computer) U:
U | i = exp(2⇡i✓)| i
Eigenvalue
Eigenvector
The Quantum Phase Estimation algorithm estimates the angle ✓. Notice that since U is unitary, all eigenvalues of U will be of this form.

MULT20015 Elements of Quantum Computing Lecture 12
The T gate
|0> = [1,0] ect For example, consider the T gate:  1 0
T= 0 exp(i⇡4) An eigenvector of the T gate is
T |1i = exp⇣i⇡4⌘|1i
Eigenvalue
Eigenvector
So in this case, we want to find:
✓ = 18
Quantum Phase Estimation gives a way to do this for arbitrary U on a quantum computer.
U | i = exp(2⇡i✓)| i

MULT20015 Elements of Quantum Computing Lecture 12
Quantum Phase Estimation Circuit
Looks daunting, but we will go through it step by step.
Measure an estimate of
✓
Eigenstate
Operation, U Inverse (controlled on QFT upper register)
(1) Prepare equal superposition, x in the upper register x and eigenstate 𝜓 .
(2) Apply Ux to lower register
(3) Apply (inverse) Quantum Fourier Transform (we will treat this as a black box) to
the upper register ! (4) Measure to obtain an estimate equal to 2 𝜃.

MULT20015 Elements of Quantum Computing Lecture 12
QPE Circuit in the QUI
(1)
T |1i = exp⇣i⇡4⌘|1i
(2) (3) (4)
(1) Prepare equal superposition, x and eigenstate 𝜓 .
(2) Apply Ux to lower register
(3) Apply (inverse) Quantum Fourier Transform to the x register (4) Measure to obtain an estimate equal to 2!𝜃.

MULT20015 Elements of Quantum Computing Lecture 12
Step 1: Equal Superposition
(1)
(2)
After the first step of the algorithm
(3) (4)
1
| i = p2n x=0 |xi |1i
Xn 2 1
(x is in decimal notation)

MULT20015 Elements of Quantum Computing Lecture 12
Step 2: Applying Tx
(1)
(2) X (3) (4) 1 2n1 ⇣ ⇡ ⌘
| i=p2n exp i4x |xi|1i x=0
Equal superposition, where each state has a phase proportional to x:
⇡ ⇡ 3⇡ ⇡ 5⇡ 3⇡ 7⇡ 4242424
0

MULT20015 Elements of Quantum Computing Lecture 12
The Fourier Transform
Original state
Quantum Fourier Transform
Resulting state
23✓ = 1

MULT20015 Elements of Quantum Computing Lecture 12
Step 3: Quantum Fourier Transform
(1)
(2)
| i=p2n
(3) (4)
exp i4x |xi|1i
Xn ⇣⌘
121 ⇡
You will not be tested on the details of the QFT circuit.
x=0
The QFT determines the period of the function, in this case it will exactly find the answer:
| i=|001i|1i

MULT20015 Elements of Quantum Computing Lecture 12
Step 4: Measure
(1) T4 T2 T (3) (4) (2)
Finally we measure an obtain the result 0012=1, so in this case:
2n✓ = 1 ✓ = 18
As we expected!
U | i = exp(2⇡i✓)| i
T |1i = exp⇣i⇡4⌘|1i

MULT20015 Elements of Quantum Computing Lecture 12
Quantum Phase Estimation Circuit
Measure an estimate of
✓
Eigenstate
Inverse QFT
Operation, U
(1) Prepare equal superposition, x and eigenstate 𝜓 .
(2) Apply Ux to lower register
(3) Apply (inverse) Quantum Fourier Transform to the x register (4) Measure to obtain an estimate equal to 2!𝜃.
U | i = exp(2⇡i✓)| i

MULT20015 Elements of Quantum Computing Lecture 12
12.2 Quantum Fourier Transform (will not be examined)

MULT20015 Elements of Quantum Computing Lecture 12
Introduction to Fourier Transform
Time domain
Frequency Domain
Fourier Transform

MULT20015 Elements of Quantum Computing Lecture 12
Discrete Fourier Transform
Maps a vector: According to:
(x0, x1, …, xN1) 2 CN to a vector:
1 NX1
yk = pN e.g. Frequency Domain
xj e2⇡ijk/N
(y0, y1, …, yN1) 2 CN
NB.
i = sqrt(-1)
j and k are integers
e.g. Time Domain
j=0
yk
xj
k
j

MULT20015 Elements of Quantum Computing Lecture 12
Circuit for QFT
p1 |0i+e2⇡i0.j1j2j3j4 |1i 2
p1 |0i+e2⇡i0.j2j3j4 |1i 2
p1 |0i+e2⇡i0.j3j4 |1i 2
p1 |0i+e2⇡i0.j4 |1i 2
Controlled rotations with:
Notice how ✓the required Q◆FT fo✓rm is recovere◆d by re-labelling qubits
|j1i |j2i |j3i |j4i
✓10◆ 0 e2⇡i/2k
10 10 Rz2 = 0 e2⇡ij2 /22 = 0 ei(j2 )⇡/2
Rzk =
!|j4i
!|j3i
!|j2i !|j1i

MULT20015 Elements of Quantum Computing Lecture 12
12.3 Phase as a periodic function

MULT20015 Elements of Quantum Computing Lecture 12
The phase is periodic
f (t) = exp (2⇡i✓t)
t

MULT20015 Elements of Quantum Computing Lecture 12
Quantum Phase Estimation as a function
Uf
t register (2n qubits)
Output Register (n qubits)
|i
U |ti| i = |tiexp(i2⇡✓t)| i
Quantum computers find periods of periodic functions efficiently!

Related Posts