Advanced Concepts in Quantum Computing (TUM) - Script / Notes

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
=>
: + . - -