代写代考 MULT90063 Introduction to Quantum Computing

MULT90063 Introduction to Quantum Computing
Lecture 11
Quantum Phase Estimation, Fourier Transformations, Quantum Fourier Transform, QUI examples, Inverse QFT
Lecture 12

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
Lecture 11 overview
• Fourier Transformations
– Quantum Phase estimation
– Regular Fourier Transform
– Fourier Transform as a matrix
– Quantum Fourier Transform (QFT) – QUI examples
– Inverse QFT
Reiffel, Chapter 8
Kaye, Chapter 7
Nielsen and Chuang, Chapter 5

MULT90063 Introduction to Quantum Computing
Last lecture: Quantum Counting
Dimension: N’ Dimension: N
| i = Xsin(2x+1)✓|xi⌦| gi x
After Fourier transforming a periodic function, we get a good approximation to frequency.

MULT90063 Introduction to Quantum Computing
Last Lecture: Quantum Counting
| i = Xsin(2x+1)✓|xi⌦| gi x
After Fourier transform of a periodic function, we get a good approximation to frequency. Example of quantum phase estimation.

MULT90063 Introduction to Quantum Computing
Quantum Phase Estimation

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

MULT90063 Introduction to Quantum Computing
The T gate
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:
Quantum Phase Estimation gives a way to do this on a quantum computer.
U | i = exp(2⇡i✓)| i

MULT90063 Introduction to Quantum Computing
Quantum Phase Estimation Circuit
Measure an estimate of
Eigenstate
Quantum Fourier Transform
Operation, U
(1) Prepare equal superposition, x in the upper register x and eigenstate 𝜓 . (2) Apply Ux to lower register
(3) Apply (inverse) Quantum Fourier Transform to the upper register
(4) Measure to obtain an estimate equal to 2!𝜃.

MULT90063 Introduction to Quantum Computing
QPE Circuit in the QUI
(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!𝜃.

MULT90063 Introduction to Quantum Computing
Step 1: Equal Superposition
After the first step of the algorithm
| i = p2n x=0 |xi |1i

MULT90063 Introduction to Quantum Computing
Step 2: Applying Ux
exp i4x |xi|1i
Equal superposition, where each state has a phase proportional to x:

MULT90063 Introduction to Quantum Computing
Step 3: Quantum Fourier Transform
(1) T T2 T4
The QFT determines the period of the function, in this case it will exactly find the answer:
| i=|001i|1i

MULT90063 Introduction to Quantum Computing
Step 4: Measure
(1) T T2 T4
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

MULT90063 Introduction to Quantum Computing
Quantum Phase Estimation Circuit
Measure an estimate of
Eigenstate
Quantum Fourier Transform
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

MULT90063 Introduction to Quantum Computing
Quantum Fourier Transform

MULT90063 Introduction to Quantum Computing
Fourier Transform in Quantum Computing
In QC the equivalent of the Fourier Transform – quantum Fourier Transform (QFT) – is important in a number of algorithms, most notably Shor’s Factoring algorithm…
Hence, before we can cover Shor’s algorithm we need to understand the QFT and how to implement it in a QC (and on the QUI)…

MULT90063 Introduction to Quantum Computing
Introduction to Fourier Transform
Time domain
Frequency Domain
Fourier Transform

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

MULT90063 Introduction to Quantum Computing
Example: Fourier transform of periodic function
Imagine that we had a periodic function:
Complex number, i2=-1 u=1
The frequency, u
xj =exp✓2⇡iuj◆ N

MULT90063 Introduction to Quantum Computing
Example: Periodic function
✓jk◆ xjexp 2⇡iN
= pN 1NX1
✓ uj◆ ✓ jk◆ 2⇡iN exp 2⇡iN
=pN If k=u then
✓ j(ku)◆ N

MULT90063 Introduction to Quantum Computing
Example: Periodic function
For any other value of k, X ✓ ◆ 1 N1 j(ku)
yk = pN exp 2⇡i j=0
Recall, for a geometric series, 1 rN 1+r+r2+…+rN1= 1r
Where for us, And therefore
Except for k=u,
r = exp ✓2⇡i k u ◆ N

MULT90063 Introduction to Quantum Computing
Fourier Transform as a Matrix
We define the Fourier transformation matrix as follows:
yk =XFkjxj j
Forexample:
N=2:F=p2 1 1
xje2⇡ijk/N
Fkj = pN e
1 2⇡ijk/N 2 1 1 1
We will see that the quantum Fourier transform for one qubit is a Hadamard gate!
1 3 161 i1i7
N=4: F=241 1 1 15 1 i 1 i

MULT90063 Introduction to Quantum Computing
Quantum Fourier Transform (QFT)
The Fourier transform, written in this matrix form is unitary. It can make a valid
quantum operation:
yk = Fkjxj j=0
N1 N1 X QFT 0 X
yj|ji with
On an individual basis state |ai (i.e. j = a only non-zero xj) we have:
| i= xj|ji!| i=
1 2⇡ijk/N Fkj = pN e
X 1 2⇡ika/N
yk |ki , yk = Fkj xj = Fka = pN e j=0
2⇡i ka e N
(more familiar form relating variables a and k by Fourier transform)
QFT |ai = p
Question: How can we systematically make this operation using quantum gates?

MULT90063 Introduction to Quantum Computing
Product Form of QFT
The Fourier transform can be expressed in a product notation:
|0i + e2⇡i 0.jn |1i |0i + e2⇡i 0.jn1jn |1i |0i + e2⇡i 0.j1j2…jn1jn |1i |j1, . . . , jni ! p2 ⌦ p2 ⌦ . . . ⌦ p2
(this is not obvious – see appendix at end)
Where the notation 0.j1j2…jn = j1 + j2 + … + jn1 + jn 2 22 2n1 2n
is shorthand for writing a fraction in binary notation. That is,
0 . 1 = 12
0.11 = 1 + 1 = 3
0.101 = 1 + 1 = 5 2 23 8

MULT90063 Introduction to Quantum Computing
Product Form: One Qubit
|0i + e2⇡i 0.jn |1i |0i + e2⇡i 0.jn1jn |1i |0i + e2⇡i 0.j1j2…jn1jn |1i |j1, . . . , jni ! p2 ⌦ p2 ⌦ . . . ⌦ p2
For one qubit (ie. n=1, N=2):
|0i+e2⇡i0.j1 |1i
|j1i ! p2 j1 = 0, 1
|0i + e2⇡i 0.0 |1i |0i + |1i |0i! p2 =p2
|0i+e2⇡i 0.1 |1i |0i+e⇡i |1i |0i|1i |1i! p2 = p2 = p2
Beware binary fraction! 0.1 = 1/2 etc
As before, we get:
11 1 F=p2 1 1
(i.e. a Hadamard)

MULT90063 Introduction to Quantum Computing
Product Form: Two Qubits
|0i+e2⇡i0.j2 |1i |0i+e2⇡i0.j1j2 |1i j1j2i ! p2 ⌦ p2
|0i+|1i |0i+|1i |00i+|01i+|10i+|11i
|00i! p2 ⌦ p2 =
|0i + ei2⇡ 0.1 |1i |0i + ei2⇡ 0.01 |1i |00i + i|01i |10i i|11i
2 |01i! p2 ⌦ p2 =
2 |0i+|1i |0i+ei2⇡ 0.1 |1i |00i|01i+|10i|11i
|10i!p2⌦ p2 =
|0i + ei2⇡ 0.1 |1i |0i + ei2⇡ 0.11 |1i |00i i|01i |10i + i|11i
|11i! p2 ⌦ p2 =
|0i + e2⇡i 0.jn |1i |0i + e2⇡i 0.jn1jn |1i |0i + e2⇡i 0.j1j2…jn1jn |1i |j1, . . . , jni ! p2 ⌦ p2 ⌦ . . . ⌦ p2

MULT90063 Introduction to Quantum Computing
Product Notation: Two Qubits
|0i+|1i |0i+|1i |00i+|01i+|10i+|11i
|00i! p2 ⌦ p2 =
|0i + ei2⇡ 0.1 |1i |0i + ei2⇡ 0.01 |1i |00i + i|01i |10i i|11i
2 |01i! p2 ⌦ p2 =
2 |0i+|1i |0i+ei2⇡ 0.1 |1i |00i|01i+|10i|11i
|10i!p2⌦ p2 =
|0i + ei2⇡ 0.1 |1i |0i + ei2⇡ 0.11 |1i |00i i|01i |10i + i|11i
2 |11i! p2 ⌦ p2 =
As before:
F=641 i1i75 2 1 1 1 1
2 1261 1 1 137
|0i + e2⇡i 0.jn |1i |0i + e2⇡i 0.jn1jn |1i |0i + e2⇡i 0.j1j2…jn1jn |1i |j1, . . . , jni ! p2 ⌦ p2 ⌦ . . . ⌦ p2

MULT90063 Introduction to Quantum Computing
Pick it apart…
Look a little bit more closely:
|0i + e2⇡i 0.jn |1i |0i + e2⇡i 0.jn1jn |1i
|0i + e2⇡i 0.j1j2…jn1jn |1i ⌦ . . . ⌦ p2
Each qubit acquires a phase dependent on (the original state of) all prior qubits.
|j1, . . . , jni ! p2 ⌦
Very similar to equal superposition. All qubits have an equal amplitude, just not an equal phase.
2⇡i[j1 +j2 +…+jn ] |0i+e2⇡i0.j1j2…jn |1i |0i+e 2 22 2n
|0i + e2⇡i j1 e2⇡i j2 …e2⇡i jn |1i
Product of phases applied, i.e. of theRform= zk
0 e2⇡ijk/2
e.g. rotation by 𝜃 = !”
controlled by jk

MULT90063 Introduction to Quantum Computing
Circuit for QFT
Look carefully at the product form:
|0i + e2⇡i 0.jn |1i |j1, . . . , jni ! p2
|0i + e2⇡i 0.jn1jn |1i p2
|0i + e2⇡i 0.j1j2…jn1jn |1i p2
p1 |0i+e2⇡i0.j1j2j3j4 |1i
p1 |0i+e2⇡i0.j2j3j4 |1i 2
p1 |0i+e2⇡i0.j3j4 |1i 2
p1 |0i+e2⇡i0.j4 |1i 2
⌦ . . . ⌦ Suggests an efficient circuit implementation – e.g. for n=4:
|j1i |j2i |j3i |j4i
✓10◆ 0 e2⇡i/2k
Controlled rotations with:
Notice how the required QFT form is recovered by re-labelling qubits
!|j2i !|j1i

MULT90063 Introduction to Quantum Computing
One qubit QFT circuit
Look at the pattern of the circuit:
|j1 i |j2 i |j3 i |j4 i
|j2 i |j1 i
For one qubit we have just a H-gate:
|0i+e2⇡i0.j1 |1i |j1i ! p2
|0i + e2⇡i 0.0 |1i |0i + |1i |0i! p2 =p2
|0i+e2⇡i 0.1 |1i |0i+e⇡i |1i
|1i! p2 = p2 = p2

MULT90063 Introduction to Quantum Computing
Two Qubit QFT circuit
|j1i |j2i |j3i |j4i
QUI gates:
✓10◆ Rzk = 0 e2⇡i/2k
|j1i |j2ik 0 e2⇡i/2 |j1i ✓10◆✓10◆
◆✓◆✓✓ ◆✓✓ ◆ 10i✓g ✓R10✓R i✓g cos2R 0 sin2R 0
|j1i 1 0 |j2i |j2i Rz = k
Rz2 = 0 e2⇡i/22 = 0 ei⇡/2
R (✓ )=e Icos iZsin =e
2⇡i/2 2 i⇡/2 2
0 sin 0e0e✓2 ◆2
i✓ cos✓R isin✓R 0
=eg 20 2 cos✓R+isin✓R
=ei✓g ✓ ei✓R/2 0 ◆ 0 e+i✓R /2
=ei✓gei✓R/2✓1 0 ◆ 0 ei✓R
Rz2 = 0 ei⇡/2 ⌘ RZ 2 with ✓g = 4 Global phase cancels prefactor

MULT90063 Introduction to Quantum Computing
Two Qubit QFT circuit – walkthrough
|j1,…,jni! Rz p= ⌦
k 20e2⇡i/2
✓10◆✓10◆ Rz2 = 0 e2⇡i/22 = 0 ei⇡/2
Check it gives the product form:
| ai = p2 |0i+e 1 |1i ⌦|j2i
p ⌦…⌦ p 2
n n1n 12 n1n |0i+e2⇡i 0.j1|1i 0|0i+e2⇡i 0.j j |1i |0i+e2⇡i 0.j j …j j |1i
| ai | bi | ci Hadamard has negative sign on |1> if j1 = 1
1 ⇣ i⇡j i(⇡/2)j ⌘
| bi= p2 |0i+e 1e 2 |1i ⌦|j2i Rz2 appliedonlywhenj2 =1
1⇣ i⇡j i(⇡/2)j ⌘ 1 i⇡j
| ci = p2 |0i + e 1 e 2 |1i ⌦ p2 |0i + e 2 |1i Hadamard on |j2 >
Binary fractions: ei⇡j1 ei(⇡/2)j2 = e2⇡i(j1 /2+j2 /4) = e2⇡i 0.j1 j2
i.e. circuit gives product form with j1 and j2 order reversed
1 2⇡i0.j j 1 2⇡i0.j
| ci = p2 |0i + e 1 2 |1i ⌦ p2 |0i + e 2 |1i

MULT90063 Introduction to Quantum Computing
Two Qubit QFT circuit – QUI
Note: inserted SWAP gate so ordering is same c/f ket expression
|j1i |j1i |j2i |j2i
All phases zero
|0i+|1i |0i+|1i |00i+|01i+|10i+|11i
! p2 ⌦ p2 =

MULT90063 Introduction to Quantum Computing
Two Qubit QFT circuit – QUI
|0i + ei2⇡ 0.1 |1i
! p2 ⌦ p2 =
|00i + i|01i |10i i|11i 2
|0i + ei2⇡ 0.01 |1i

MULT90063 Introduction to Quantum Computing
Two Qubit QFT circuit – QUI
|0i+|1i ! p2 ⌦
|0i+ei2⇡ 0.1 |1i p2 =
|00i|01i+|10i|11i 2

MULT90063 Introduction to Quantum Computing
Two Qubit QFT circuit – QUI
|0i + ei2⇡ 0.1 |1i
! p2 ⌦ p2 =
|00i i|01i |10i + i|11i 2
|0i + ei2⇡ 0.11 |1i

MULT90063 Introduction to Quantum Computing
Three Qubit QFT circuit
|j1 i |j2 i |j3 i |j4 i
Rotation gates in the QUI:
|j2 i |j1 i
Rz=✓1 0◆⌘RZ⇣⇡⌘ with✓g=⇡ 2 0ei⇡/2 2 4
Rz=✓1 0◆⌘RZ⇣⇡⌘ with✓g=⇡ 3 0ei⇡/4 4 8
|j1 i |j2 i |j3 i
|j1 i |j2 i |j3 i
SWAP gate reverses order, so same as input

MULT90063 Introduction to Quantum Computing
Three Qubit QFT – QUI
Example: |011>
|j1 i |j2 i |j3 i
✓ 1 ◆3 ⇣ 3⇡i/4 3⇡i/2 9⇡i/4 ⌘ ! p2 |000i+e |001i+e |010i+e |011i
|j1 i |j2 i |j3 i
NB. same as 𝜋/4 etc
+ei⇡ |100i + e7⇡i/4 |101i + e5⇡i/2 |110i + e13⇡i/4 |111i

MULT90063 Introduction to Quantum Computing
Step back for a moment
After all that, let’s check on what we were trying to achieve:
✓ 1 ◆3 ⇣ ⌘
1 On a single basis state QFT|ai = pN
e N ka |ki
e.g. |011i ! p2 |000i + e3⇡i/4 |001i + e3⇡i/2 |010i + e9⇡i/4 |011i +ei⇡ |100i + e7⇡i/4 |101i + e5⇡i/2 |110i + e13⇡i/4 |111i
i.e. 3=101 |3i !
p2 |0i + e3⇡i/4 |1i + e3⇡i/2 |2i + e9⇡i/4 |3i
+ei⇡ |4i + e7⇡i/4 |5i + e5⇡i/2 |6i + e13⇡i/4 |7i
QFT |3i = p It obeys: 1
2⇡i 3k e 8
(check it!)
NX1 8 k=0

MULT90063 Introduction to Quantum Computing
Programing the Inverse QFT
As with any circuit: invert the QFT by inverting every gate and reversing the order:
e.g. |011>
RZ(✓R) = ei✓g
= ei✓ 2 ✓ i 4 1 0 ✓ ⇣⇡⌘✓ ⇡
✓ 1 ◆3 ⇣ 3⇡i/4 3⇡i/2 9⇡i/4 ⌘
z2✓R iZ sin
 R=✓✓⌘ ◆✓
R with ✓ = i⇡/2cos✓Z 0 sign✓
2 2✓ ◆0cos2R 0
cos R isin R 0 R=i✓ ⌘R with✓=
3 0ei⇡/4 4 ✓ 8✓
0 cos R +isin R ✓ i✓ /2 ◆ 2 ✓✓ 2
e✓0✓ cos i✓g R R i✓
= ei✓g ei✓R/2
i✓ +i✓ /2
i✓ cos ✓ =e g 2
Z 0eR i.e. Reverse signs of 𝜃R and 𝜃g
R (✓R)=e ge R i✓
R (✓ )=e g Icos iZsin =e g
Z R 0 e+i✓R/2 0
0 ei✓R ✓✓◆✓◆
= ei✓g ei✓R/2
+ei⇡ |100i + e7⇡i/4 |101i + e5⇡i/2 |110i + e13⇡i/4 |111i
|010i + e |011i

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

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts