Good morning. So let me get started as always with a more repetition what the

last lecture was about. So the main subject of last lecture was quantum

Fourier transform.

Or also Q of t. And that's a problem that considers an n-dimensional Hilbert

space. This H. And then, so for such an n-dimensional Hilbert space you can

choose one basis. I denote this by x, where this x is a discrete label for

this basis state and runs from 0 to n-1. And so what a quantum Fourier

transform does is transform these basis states into a new basis. And states in

this new basis we have denoted with y tilde. They are 1 over root n times a

sum over all these x's, omega to the x times y as the amplitude of the state x.

So a superposition of all x states with these amplitudes where omega is e to

the 2 pi i divided by n.

Yeah.

So what the quantum Fourier transform does is that this Fourier transform on

a Hilbert space of dimension n on a state y will produce a state y tilde. And then

for doing the quantum algorithm of that.

So the first thing that you do is you represent the whole thing on qubits.

So this means each state x is actually a product state x n minus 1, x n minus 2,

and so on. x1, x0. And you do this in a way such that these x's are the binary

representation of that number x here. So x is x n minus 1 times 2 to the n minus

1 plus x n minus 2 times 2 to the n minus 2 and so on and so forth. Plus x1

times 2 to the power 1 or 2 plus x0 to the power 0. Yeah. So that's just one way

of representing this state.

So then this n dimensional Hilbert space is the joint Hilbert space of small n

qubits. So capital N is 2 to the power n or lowercase n. Yeah. And it's a way of

representing this n dimensional space on the qubits. So then I wanted to say

something about which hasn't been discussed actually in last lecture about

the representation of this state on this n qubits. So if I look at the Fourier

transform on some state y, that's a special case of this x state. Yeah. And

this will be a y tilde. So I can write this as 1 over root 2 to the n. So

that's capital N. Sum over x0 to x n minus 1 and they all run from 0 to 1.

Omega to the x y, x0, x1, x n minus 1. Let me choose the ordering

consistent. So this is x n minus 1, x n minus 2, that's x0. Now let's have a look

at what this factor here is. So this is omega to the y times x0, okay, x n minus

1, 2 to the n minus 1 plus and so on plus x1 times 2 plus x0. And I can also

write this as a product of j over all j's from 0 to n minus 1, omega to the y

to the x j, 2 to the power j. And then I can write this state here actually. So

that's when I expand everything out. I see that this is actually a product of

j to the n, 0 n minus 1. 1 over root 2, 0 j plus omega to the y to the power 2 to

the power j, 1 j. Basically this means each qubit, it's actually a product state

and each qubit, so not each qubit, so qubit j is in the state 0 j plus to the

y j, 1 j and it's correctly normalized. That's the way this output state is also

represented on these n qubits. Then just as a reminder, so the actual algorithm,

how this Fourier transform is implemented is, one can build this up in an

in a recursive way. So Fourier transform on n qubits is actually the same as

just doing the Fourier transform on n minus 2 qubits. So this means the Hilbert

space, this Fourier transform act on is divided by 2. So if I take away one

qubit, the Hilbert space dimension is divided by 2 and then I do conditional

phase shifts on the state of the last qubit. So this is Rn, Rn minus 1 on all

the other qubits, R2 and then finally a Hadamard on this last qubit, where these