Okay, good morning. I start. Welcome to this next lecture in the quantum computing course.

So before talking about any content of the lecture, I'd like to make two announcements for the two coming weeks.

So the first thing is the next lecture.

So on 13th of November, we'll be at 10 sharp.

That's only next week. It's because the people after us need a room really at 12 or a few minutes before.

And so I moved the lecture like 15 minutes earlier.

Then on the same day, the tutorial class on the 13th will be at 5pm, because Sam unfortunately can't do earlier on that day.

And the final announcement that I would like to make is the lecture the week after.

That should be on the 20th of November.

So this will be given by Sam, because I can't do it myself in that week.

It's going to be like he's just delivering the lecture for me. It's the same lecture notes that I'll hand over to him.

Okay, good.

Then, as usual, let me start with a brief recap of what I talked about in the last lecture.

So I discussed the first real quantum algorithm, and that was a fairly basic one, so-called Deutschproblem.

And that considers a function, and this function is from values 0 or 1, and the output is also a 0 or a 1.

So one bit of binary information to one bit of binary information, like a very elementary computer science problem.

And then the question is whether f of 0 is equal to f of 1 or not.

That's what the algorithm should clarify.

So classically, it's obvious that we need to evaluate f twice to find f of 0 and f of 1.

Because to decide whether they are equal or not, we need both values.

Now the quantum algorithm is as follows.

So there is one qubit that starts in a state 0. We apply a Hadamard gate on it.

And we use an Ancilla qubit that starts in a state 1, also apply a Hadamard gate on it.

So Hadamards are a very typical first gate in an algorithm, because they bring a state 0 or 1 into a superposition of 0 and 1.

And then there is a unitary two qubit gate that applies the function to the qubit 1.

And we'll have another Hadamard and then measure the qubit 1.

And the second qubit is an Ancilla qubit, so we don't do anything with that anymore. That is just needed to be able to construct this unitary that applies the function f.

So what do the specific gates do?

The action of the Hadamard gate on a qubit is to bring this qubit into a state 1 over root 2, 0 plus minus 1 to the power j, 1.

So if the j is a 0, then this will be 0 plus 1. If the j is a 1, this will be 0 minus 1. That's what the Hadamard does.

The action of the unitary uf on a state jk, where k is the state of the Ancilla, so I've taken here. So here this would be the state k would be 0 minus 1 after this Hadamard.

So this maps to a state which is j for the first and f of j, x or so addition modulo 2, k for the Ancilla.

So this here, addition modulo 2 means this is 0 if they are both the same or is 1 if they are both different.

So the key thing is that here we have only one application of uf.

In contrast to the classical version where you need two evaluations of f, here a single application of the corresponding uf is sufficient.

So this in computer science language needs two queries, whereas this needs only one query to f.

And in the way I set this up, this qubit will end up in a state 0 if f of 0 is equal to f of 1 and will end up in a state 1 if they are not equal.

And that's what you detect in the measurement.

Okay, any further questions to Noitsch's problem or algorithm?

One thing you might ask is, okay, what's the explicit form of f? That of course depends on what the function f is, right?

But if you say if you want to, so the matrix elements of uf you find, so these are the matrix elements of uf.

So here j tilde a tilde, yeah, and of course from this one you will see that this is a 1 if that guy here is f of j or a.

And should be a 0 otherwise.

Okay.

So then I started discussing more generally classical circuits

which are composed of AND, OR, and NOT-gates, but these are classical gates and quantum circuits

which I can write of the form that there is a state which I call psi tilde which emerges from applying some unitary on a state psi which is the input state.

And this input state is often one where all the qubits are in zero.

And... so the fortunate thing is that we do not need to construct any unitary that we would like to implement here.

Because this guy you can typically write as a product for executing many unitaries one after the other.