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.