Advanced Concepts in
Quantum
Computing
Lecture
,1
. The quantum Fourier transform and its
applications
Most famous
application
: Show's
algorithm for
factoring a n-bit
integer on
OCn-log(n) log(log(n)(
(polynomial scaling in n)
For
comparison
: best known classical
algorithm
: number field Sieve exp(8(n"3 logcn))
.1
1 Review of Fourier transformation
KN
"
Discrete Fourier transform defined
by Fn C
: --
Fr(x) =
y with
yn = V k =
0 ....
N -
1
Intuition : re c to r x is discretization of a
periodic function :
f [0:
,
] -
I
-
f(x)
Ceg sampling of audio
signal) Xj
- =
.
an
f Forner thatf
since is
periodic , analysis states can be decomposed
into a sum of oscillations (sin ,
cos) with different frequencies ( = Fourier series
2 ikt
[Yne
-
mathematically :
f(t) =
-
n oscillator" with
frequency I5K
If we
only consider - evaluated at discrete Curiformly spaced
points O , ...., then a finite sum [ yu
ikt
is sufficient e
-
to re c ove r -> lat these points)
The discrete Forner transform FN finds coefficients the discretization of f.
yo given X
E FN is a
unitary transformation ,
i e
.
. its matrix representation is
unitary .
El
Fr =
Fyt
E Forner modes (i) o ...
me are orthonormal vectors
↳ -k)/N =
Ok kVk, ,
k =
0 ...
n -
1
Since Fr =
Firt ,
we can
identify the inverse discrete Fourier transform
Fr(y) =
X with ym
-i =
f()
. 2
1 The quantum Fourier transform
Fourier transform (QFT)
Definition of
quantum acting on an
othonormal basis 2107 ,
1) . . . .
IN-13 :
(j) ↳ i
Thus for of basis states input
superposition as
a :
,
Xi (k) = Fr
, From assume that N of 2 ie . N 2" for some .
HEN
is
power
=
n ow on
:
a
,
[10 125-133 be computational basis
basis 1
regarded states
L as
can
=
, ...
of an
n-qubit quantum register
For 20 , 2"-13 binary representation Ijn--h
je . . .
use
1jn-2
j jn-1 je jo to describe the
input :
=
in
... .
I jo
For the
following :
↳ binary representationto floating pits,
-
with abod e [0 13 ,
QFT form
in
product
:
je ...
joh
M (10 + etojo 113) Clos + eliojjo 11) . . .
(10 + etioineion)()
Leck
:
(j)
= en Itn-ex
enti 1
=
-(10 eij29(1)) = + (10) +
g20j0(1))a(10) + extojj0()0 . . .
& 25i O Cd
giti
abcd
guiq 1
.
qeE
= =
e
=
(* ) can be realized
by the
following quantum circuit :
Cup to the order of the grbits at the end
reversing
with Rr: =
( Etisa &
operations on first qubit operations on second
qubit
To that this circuit
verify works as intended :
first arbit
consider with
Ijn-1)
:
input
·
Hadamard
gate can be represented as H(x =T (10) + (-1)
*
113) with x50 , 13)
zi
Note : (-1)
*
= patio . X
since e =
1 ; e
=
exi = -
1
=
State after first
H-gate
:
En (10) + eojn (12) Ijnz . .
jejoh
e2xi/4 -250
01
state first
C-R2-gate R
.
=>
after if and for
=
:
only jn-z
using
1
=
and that20 ju-e20
Ojn-2 etiojuju-2 .
.
=
,
E e
:
jujn2 (2) line
0 .
(10) + :
jejoh
state after all controlled-Ru first qubit
gates acted
=
have on :
110 patio jae jo (13) Ijne
. . .
jejo
.
+ . . .
state Hadarmard acted
after
gate qubit
:
=
on second
e (107 enti Ojue -jo 113) En (10) estiOja 112)
/jns---jo
-
+ +
i
En (10) etio in
jo () (102 24t0 jo(12 (
.
-....
+
.
output
=>
: + . - -
Quantum
Computing
Lecture
,1
. The quantum Fourier transform and its
applications
Most famous
application
: Show's
algorithm for
factoring a n-bit
integer on
OCn-log(n) log(log(n)(
(polynomial scaling in n)
For
comparison
: best known classical
algorithm
: number field Sieve exp(8(n"3 logcn))
.1
1 Review of Fourier transformation
KN
"
Discrete Fourier transform defined
by Fn C
: --
Fr(x) =
y with
yn = V k =
0 ....
N -
1
Intuition : re c to r x is discretization of a
periodic function :
f [0:
,
] -
I
-
f(x)
Ceg sampling of audio
signal) Xj
- =
.
an
f Forner thatf
since is
periodic , analysis states can be decomposed
into a sum of oscillations (sin ,
cos) with different frequencies ( = Fourier series
2 ikt
[Yne
-
mathematically :
f(t) =
-
n oscillator" with
frequency I5K
If we
only consider - evaluated at discrete Curiformly spaced
points O , ...., then a finite sum [ yu
ikt
is sufficient e
-
to re c ove r -> lat these points)
The discrete Forner transform FN finds coefficients the discretization of f.
yo given X
E FN is a
unitary transformation ,
i e
.
. its matrix representation is
unitary .
El
Fr =
Fyt
E Forner modes (i) o ...
me are orthonormal vectors
↳ -k)/N =
Ok kVk, ,
k =
0 ...
n -
1
Since Fr =
Firt ,
we can
identify the inverse discrete Fourier transform
Fr(y) =
X with ym
-i =
f()
. 2
1 The quantum Fourier transform
Fourier transform (QFT)
Definition of
quantum acting on an
othonormal basis 2107 ,
1) . . . .
IN-13 :
(j) ↳ i
Thus for of basis states input
superposition as
a :
,
Xi (k) = Fr
, From assume that N of 2 ie . N 2" for some .
HEN
is
power
=
n ow on
:
a
,
[10 125-133 be computational basis
basis 1
regarded states
L as
can
=
, ...
of an
n-qubit quantum register
For 20 , 2"-13 binary representation Ijn--h
je . . .
use
1jn-2
j jn-1 je jo to describe the
input :
=
in
... .
I jo
For the
following :
↳ binary representationto floating pits,
-
with abod e [0 13 ,
QFT form
in
product
:
je ...
joh
M (10 + etojo 113) Clos + eliojjo 11) . . .
(10 + etioineion)()
Leck
:
(j)
= en Itn-ex
enti 1
=
-(10 eij29(1)) = + (10) +
g20j0(1))a(10) + extojj0()0 . . .
& 25i O Cd
giti
abcd
guiq 1
.
qeE
= =
e
=
(* ) can be realized
by the
following quantum circuit :
Cup to the order of the grbits at the end
reversing
with Rr: =
( Etisa &
operations on first qubit operations on second
qubit
To that this circuit
verify works as intended :
first arbit
consider with
Ijn-1)
:
input
·
Hadamard
gate can be represented as H(x =T (10) + (-1)
*
113) with x50 , 13)
zi
Note : (-1)
*
= patio . X
since e =
1 ; e
=
exi = -
1
=
State after first
H-gate
:
En (10) + eojn (12) Ijnz . .
jejoh
e2xi/4 -250
01
state first
C-R2-gate R
.
=>
after if and for
=
:
only jn-z
using
1
=
and that20 ju-e20
Ojn-2 etiojuju-2 .
.
=
,
E e
:
jujn2 (2) line
0 .
(10) + :
jejoh
state after all controlled-Ru first qubit
gates acted
=
have on :
110 patio jae jo (13) Ijne
. . .
jejo
.
+ . . .
state Hadarmard acted
after
gate qubit
:
=
on second
e (107 enti Ojue -jo 113) En (10) estiOja 112)
/jns---jo
-
+ +
i
En (10) etio in
jo () (102 24t0 jo(12 (
.
-....
+
.
output
=>
: + . - -
