I might as well get started now. I can see why we needed the bigger lecture hall.

So I'm very sorry that I couldn't make it to last week's tutorial, but I'm going to make up for it this week.

You get two extra doses of SAM, in fact this week I'll be taking the lecture and a double tutorial later in the afternoon.

So today we're going to be, I think last time, last lecture you talked about Simon's problem very briefly.

And Michael should have told you about the classical complexity of that problem, right?

So we've got Simon's problem where in Simon's problem we've got some function and this function is periodic in a special way that

f of x is equal to f of x plus s or some s.

Where this is bitwise addition mod two and s is our secret string and the point of Simon's problem is to find s.

Now classically you need to evaluate this function. How many times do you need to evaluate that?

It's two to the n on two times, which is exponential in n.

So it's only here being the length of your secret string s. But quantum mechanically, with a quantum algorithm,

we can do it in something of the order of n, something linear in n.

So we get an exponential speed up from a quantum algorithm, which is the entire reason why this problem is interesting.

So we're going to run through what this quantum algorithm is step by step here.

So that's the basic quantum system.

So that's the basic quantum circuit that will solve Simon's problem.

And we're just going to show what this does and how it does it and to prove that we get this exponential speed up,

we're going to look at what it does step by step.

So we just divide it into time slices.

We're going to see what the state of our quantum computer is at each of these points in time.

This here means that we have n qubits over here, all initialized at zero, and then we have another register of n qubits all initialized at zero.

These are Hadamard gates. These are measurements.

This fellow here, we've encountered him once before, that is the same U of F that we saw in Deutche's problem.

So what that does, U of F of some state jk takes us to some state.

So it kind of evaluates this periodic function we've got, which remember we don't know what this function is.

If we knew what that the problem would already be solved, which means that we don't really know what U of F does.

It's a black box.

Sometimes we call it an oracle because it's mysterious and the whole point of the algorithm is to figure out what exactly it is doing.

So let's, alright, we initialize everything at zero, and then before time t0, we apply this Hadamard gate to the first n qubits.

So that gives us a state like this.

Yep.

So what this Hadamard gate on the first n qubits does is it gives us this funky bit here, that should be an n there, this x summed over every single bit string of length n.

Now you can see that that just comes out of this product of n different Hadamard states there.

When you multiply all these together, you're going to get every single combination of length n of zeros and ones.

This just comes from multiplying out that product there, and this is just a more convenient way to write it.

Then at t1, we have applied our black box operation.

So we've got this operation here, so then this will give us a state that looks like this.

Okay, that just follows out of the definition from what that function does, but applied to this state here.

And remember that because x is all sets of strings that are length n, these are still n qubits here and n qubits here, because we've got x in it, right?

Then we have a measurement. We measure the outcome of that second qubit.

Now, given the way that Simon's problem is set up, we know that for a given output of the function, a given measurement at this end here, there are two different inputs that could have caused it.

That's the f of x and f of x plus s have to be the same, so we have two different possible inputs for the one output, which means that when we measure the second state, we get the state for the unmeasured qubit.

The one that's left is a superposition of those two possibilities.

These are just the two possible inputs or the two possible states of the first qubit that could give us the measured state of the second qubit, the second register of qubits rather.

And now we finally apply another Hadamard at the end there.

So, at one.

Um.

Okay, this is.

This is just what Hadamard gates do, right?

Give us a superposition of zero or one states, and it can be a symmetric or anti-symmetric superposition depending on what the initial state was, and what the initial state was depends on these x's here.