Okay. So now, let's try to understand Simon's algorithm, in a very different
way, in a much more physical way. So, in terms of something we talked about in the
very first lecture, which was the double-slit experiment. So remember, the
double slit experiment, we had we had a source of light a screen with a, with a
slit in it. Another screen with two slits a backdrop where we had a detector and
when we had both slits open, even though the light was turned down so that it was
being emitted as single photons. We get, got this interference pattern which,
which, you know, the intensity of light that was, that was hitting the probability
that the photon ended up at point x was given by this interference pattern. Okay,
so, let me argue that you can, you can view Simon's algorithm as a sophisticated
kind of double-slit experiment. As a, as a kind of interference experiment. So, okay,
let, let's say, let's say that we have n qubits. We do Hadamard transform, and then
we do another Hadamard transform. So, and let's say that instead of starting off in
this, in this state all of them in this state zero, let's say that we start in the
state, in some particular state like, you know, U1, U2 through Un. So, we have an n
bit string, U1, U2 through Un . U = U1 through Un. So now, what's the, what's the
superposition in the middle here? What, what does this middle superposition look
like? Well, remember, we, in the middle, we are in a superposition over all the n
bit strings. So, we are in a superposition over all n bit strings, x. Where each and
between x has amplitude plus or -one / two^n/2 And whether, whether, whether it's
in the plus or whether the phase is plus or minus, it depends upon u.x, right? U1,
X1, + U2, X2, plus so on. Okay. Now, what happens when you do another Hadamard
Transform here? Well, what happens is that you, you knew Hadamard transform
transforms this into summation over y beta y , y . And what's beta sub y?. Okay, so
let's compute beta sub y. Beta sub y i s going to be sum over all x of the
amplitude of X, which is -one^u.x / two^n/2 times the amplitude of going from
x to y when you do a Hadamard transform. Okay. What's the, what's the amplitude
with which you go from x to y? It's -one^x.y / two^n/2. So now, there are two
cases. Case one, y is equal to U. If y is equal to U, then, this is equal to that,
and so then, so then beta y is just a summation of x of these minus ones, these,
these two are exactly equal to the square and, and you get one / two^n. They are
exactly two^n x, so you get one. So, it's completely constructive interference. All
the two^n contributions line up and they all give value +one. Case two, is y is not
equal to U. In the case, y is not equal to u. You should convince yourself that, for
exactly half the values of x, these two signs are equal. And for exactly half the
values of x, these two signs are unequal. So, you get +one-half the time -one-half
the time. So, beta sub y ends up these two, you know, half these values cancel
with the other half and you, you get beta sub y = zero. So, you get completely
destructive interference. Right? So, this is as though you had two^n virtual slits.
And, you know, as your light goes through this two^n virtual slits, then this, this
Hadamard transform makes them refocus and, and what happens? Well, you get completely
constructive interference at y = U, and destructive interference everywhere else.
Of course, you can see this by just observing that the Hadamard transform has
its own inverse. And so, if you start from U, you apply the Hadamard twice, you get
back U. Okay. So, what does this have to do with Simon's algorithm? Well, what we'd
like to do is we'd like to somehow change the slit pattern in the middle. So, that
the pattern of slits in the middle is determined by the input to the problem
that we are trying to solve. And then, we are going to see where the constructive
interference happens. And that's going to give us the answer to the problem. Okay.
So, remember what, what, what Simon's problem is, you're given a, a two to one f
unction, f, wher e there's a secret string, s, such that f ( x ),, = f ( x ),,
+ s. So now, what do we do? Well, remember the, the, Simon's algorithm looks like
this. You have these two Hadamard transforms which is, very much like what
we were, what we were doing in the, in our previous slide. But then in the middle, we
put in this quantum circuit for computing f. And what does this quantum circuit for
computing f do? Remember, okay. So, at this point, we had, we had a super
position over all x, and with strings of X. Alright? At this point, what we do is,
imagine just, just moving this measurement on these qubits back here. So, what do we
end up with? Well, we measure these qubits, and now, the first n cubits are
in, in some superposition one / square root 2r + one / square root 2r + s. Right?
So, it's as though, out of the two^n virtual slits, we've picked out exactly
two of them. Which two? Well, each of them by themselves looks random, but they are
related to each other in this very special way that they differ by exactly s. So,
what we've done is we've picked out two random slits, two slits which, which are
randomly positioned among, among these exponentially many. But they differ by
exactly s. And now, when we, now when we look at the interference pattern, the
interference pattern is interesting, there's constructive interference on
exactly half the two, half of the two^n and the strings, and completely
destructive interference on the other half. But if you, and so when we, when we
do our measurement we, we'd see a random one of these two^n and minus one strings
on which there's constructive interference. But the interesting thing
that we said is that, if we sample any one of them, so if y is a string that is
constructing interference, then it satisfies this condition that y.s is zero.
And this gives us a linear equation that s must satisfy. Okay. So, you could see
Simon's algorithm, as this very interesting double-slit experiment. Okay,
the slits are virtual and they reflect the input to the problem that we are trying t
o s olve. And then, when we look at the output, we look at, well, you know, when,
when we do a measurement, we pick out one of the, one of the strings at which
there's constructive interference, and then random such string. But that random
string yields a linear equation which, which gives us a constraint on the secret
string s that we are trying to find. Okay. And these linear equations allow us to
reconstruct this.