Okay. So, in this video I'm going to
describe Simon's algorithm. Which includes
a new way of setting up quantum state
which we are going to perform, perform for
a sampling on. In such a way that it gives
us an exponential speed up over any
classical algorithm. So here's the, here's
the problem that we are going to be
solving. We are given a function from n
bits to n bits and we have, we have a
promise that it's a two to one function.
And it's two to one in this very special
way. So there's a secret string s, which
is an n bit string, such that f of x equal
to f of x plus s where plus in this, in
this funny symbol means it's bit-wise sum
of two. So, so for example you know, if n
is three and s is one, zero, one, then, we
must have the case that, for example,
zero, zero, zero plus one, zero, one. If
you do a bit-wise sum, that's one, zero,
one. Then, f of this must be equal to f of
that. Or, for example, if let's do a more
non-trivial example, so suppose x is zero,
one, one. This was s, was one, zero, one,
and x bit by sum with s is just zero, one,
one, zero. So, you just threw out all the
carries when you do the summation. So
here's, here's our table for f of x so, so
you can, you can see that you know, this,
this table has f of zero, one, one is, is
that and f of one, one, zero is also the
same value, right? This is the property
that, that we wanted that, that the
function is two to one. They're, they're
exactly two values of x which, which map
to the same thing, in this case, one,
zero, zero. And what are these two values?
They are, you know, they, they satisfy
this relations that this is equal to this
plus one, zero, one. Or, this is equal to
this plus one, zero, one in this bit wise
sum manner. So now, our challenge is to
find s. So, how we can do this? Well,
let's first try to understand how we could
do this classical, you know? What would a
classical algorithm look like? So, once
again, we are given this function f in the
form of a circuit which compu tes it. And
moreover, the circuit you know, is, is, is
i n the form of a b lack box so we can't
open up the circuit to look what's going
on inside. All we can do is feed in
different inputs. And so, well, we could
just keep trying different inputs. But,
until we see two different inputs which,
which give us the same output, we are out
of luck because there's no way we could
know what s is until we see a collision.
But how, how many, how many x's do we have
to sample before we see a collision? Well,
since there are, n different values, it
turns out you know, you, you know, that by
the birthday paradox, you, you, you can
actually find a collision in, if you
sample square root n of these values at
random, which is two to the n over two.
But, it turns out that also, in addition
to the birthday paradox giving you that,
this is a, this is a good bound, you can
do it within this number of steps, it
actually turns out that you don't get, you
know, the chances that you can find a
collision in much less than this number of
trials is negligible. And so, classically,
you can do no better than two to the n
over two steps. So it takes exponential
time to solve this problem classically.
So, what we're going to see is how to use
again, this Hadamard transform, this
Fourier sampling to solve this problem
using a quantum algorithm in only
polynomial time, polynomial n number
steps. Okay. So, so, this, this algorithm
Simon's algorithm works like this. So, it
works, it works in three steps. In the
first step, we set up an appropriate
superposition. The superposition is going
to be an equal superposition over these
two strings, r and r plus s, where r is a
random and bit string. Okay. In the second
step, we are going to, we are going to do
a four year sampling of this, of this
superposition. So remember, this is a
superposition over two n bit strings you
know, there's n bit string r. And then
there's the bit-wise sum of r and s, where
s is what we are looking for. So it turns
out when you do, when you compute the
Hadamard tran sform and you sample, and
you measure, what you see is a rando m n
bit string y, where y satisfies the linear
equation y dot s is zero mark two. So,
what do I mean by that? I mean that if, if
y equal to y1 through yn, so these are the
bits of y. S is equal to s1 through sn,
then the linear equation is, that we have,
is that y1, s1 plus yn, sn is polynomial
to zero mark two. And so now, what we are
going to do is repeat this process n minus
one times. So we get n minus one such,
such linear equations. Okay? So, so we
have linear equations, let, let me call
it, let me call it you know, let me call
this the first linear equation and this is
the n minus first linear equation.
Remember these, y's are all known. And so
what you can do is, you can solve these
linear equations and as long as they are
full rank, the n minus one equations, n
unknown so you'll get exactly two
solutions, since we are working more two.
And so you'll be able to pin down all but
one of the variables that takes on two
different values, and it turns out one of
the solutions will be of course the all
zero solution because, because it's a
homogeneous set. And the other solution
will give us what the value of s is. Okay,
that's the overall plan for the, for the
algorithm. So now, what we have to show
you is, how to set up this initial
superposition to show that for your
sampling will give us such a linear
equation and that if you repeat n minus
one times, there is a very good chance
that we'll get all these n minus one,
linear equations are going to be
independent so that when we solve them, we
can, we, we actually get a unique solution
s. Okay. So, remember as before since we
are given this function f, we can create a
quantum circuit that input, on input x and
zeroes outputs x and f of x. Okay. So, so
now, how do we proceed? So, what we want,
okay, so we, we start with, with I said
you know, inputs in all in the states
zero. We first do a Hadamard transform on
any of these input bits. So, so we, we end
of the superposition over all x of n bits,
of x with amplitude one over two to the n
over two. Now we feed t his, this
superposition through the, through the,
in, through our circuit for computing f.
And so what this output of this circuit is
going to be is, in the second register,
it'll, it'll contain f of x. And now we go
ahead and measure this, this second
register to see what f of x looks like. So
now, what does f of x look like? Well, if
we were to, if we were to look at this
example, then we'd have a super position
over all these values. Right? So the first
register would contain, you know, with,
with, with amplitude one over two, one
over square root of eight. It would
contain, the first register would be zero,
zero, zero and the second register would
be zero, zero, zero, with amplitude one
over square root eight. This would be the
first two registers and so on. But now we
go ahead and measure the second register.
Okay. So we'll get one of these, you know,
each of the outcomes with equal
probability. And suppose we happen to pick
out suppose the outcome happened to be
one, zero, zero. So what's the, what's
the, what's the new state of the system?
Well, the answer is, in order to figure
out the new state of the system what we
must do is, we must, we must cross out all
the parts of the superposition which are
inconsistent with this, which is these and
all of these. And then, what's the new
state of the system? It's a superposition
over, over this value and that value,
right? We'd get an equal superposition
over this value of x and that value of x.
Meaning, it's an equal superposition of
zero, one, one and zero, one, one plus s.
Okay. So, so that's the main principle. So
what, what we, what we see is, when we,
when we do a measurement here, we'll end
up seeing a superposition, we'll pick out
a random value x as well as x plus s
because, because for both of those values,
x and x plus s, we'll see the same value
of f of x, okay? So, when we measure with
c, f of some value r, some random number
x, r and then the first register. I t's
state looks like one over square root two
r plus one over square root two r plus s,
r ight? This is what we wanted. Okay. So
now, now that we have this state, one over
square root two r plus one over square
root two r plus s, we are going to do four
year sampling on it and we want to
understand what the output looks like. So,
let's say that this output state before we
sampled it, before we've measured it is
sum over all y of beta sub y, y. So what's
beta sub y? Okay. So, with what amplitude
do you go from r to y? Remember you go
from r to y with amplitude minus one to
the r dot y over two to the n over two.
Okay. But, but you already started with
amplitude one over square root two, so
it's going to be two to the one over
square root two times two to the n over
two which is two to the n plus one over
two. And then, with what amplitude do you
go from r plus s to this? It's 2y. It's
minus one to the r plus s dot y divided by
two to the n plus one over two. Okay. You
can further factor this out to minus one
to the r dot y divided by two to the n
plus one over two times one plus minus one
to the s dot y. Now you have two cases,
case one s dot y is combined to, is equal
to one. Mark two in which case, in which
case beta sub y equal to zero. Case two, s
dot y is common to zero mark two in which
case, beta sub y is, is what? Well, it's
minus one to the r dot y, s dot by zero so
this is times two. So, it's times two
divided by two to the n plus one over two.
So it's, two to the n minus one over two.
So when you sample, you see each such y
with amplitude square of this, so beta sub
y squared which is a probability of c and
y is just one over two to the n minus one.
So, what's this telling us? So, exactly
half the y's have, have the property that
y dot s is combined to zero mark two. So
two, out of the two to the n possible
ambit strings, half them have this
property and they are sampling each one
with equal probability exactly one over
two to the minus one. Okay. So, so the net
effectors, after the foray sampling we ha
ve a random linear equation on s. So now,
we want to reconstruct s. So, how do we
recons truct S? So we have, we have a
random linear equation y dot s is zero
mark two, so this is y1, s1 plus yn, sn is
zero mark two. We're working, it's, it's
zero if you're working, working over the
field of two elements. And so we can write
down n minus one such linear equations and
we want to know what's the chance that
they're not, none of these equations are
dependent on previous ones? Well, what's
the, what's the chance that the first such
equation is nontrivial? Well, the, the
only way it could be trivial is if y
happens to be zero. So the chance that the
first equation is, is bad is one over two
to the n. What about the second equation?
What's the chance that the second equation
is bad given that the first one is not?
Well the, the, the only, only way it can
be bad is if it was the all zero string or
if it was equal to exactly, equal to y,
you know, equal to y, the first string.
Right? So, so let's, let's call the, you
know, so let's say we sample y sub one, y
sub two through y sub n minus one. These
are n, n minus one linear equations. The
chance that the second one is bad is if,
if the second one happens to be the all
zero string, or y1. There are two ways
that could be so it's one over two to the,
two over two to the n which is one over
two to n minus one. What about the third
one? The third one is bad if, if it's,
it's a linear combination of the first
two. If it's either, either the zero
string, or if it's y1 or y2, or y1 plus
y2. So there are four ways it could be bad
so the chance is one over two to the n
minus two and so on, okay? So how many
terms are there? There are n minus one
terms. So, all the way up to one quarter.
We sum up this geometric series, it's,
this is the chance of being of, of, of
dependency. This is a probability that we
could dependent linear equations is utmost
a half therefore, we have full rank. They
are all independent with probability
greater than or equal to a half. Okay. So
half th e time this algorithm is going to
work. If it doesn't, we can rerun the
algorithm. So, so what we're going to do
is, is you know, run the algorithm n minus
one times create these n minus one linear
equations. Solve them, get a value for s,
check whether s looks good. So, how do you
check? What you do is, you compute f of x
and f of x plus s for some random value of
x, and check if they're equal. If they
are, then you know you found the correct
you know, you know, try this a few times
and if you, if you, if you always find
equality then you know, that you found the
right value of s with very high
probability and you can stop. Okay. So, so
putting it altogether, this is what
Simon's algorithm looks like. You start
off with your inputs, input qubits in the
state zero. You do a Hadamard transform.
You compute f, do a Hadamard transform and
measure, and that's it. This, this, this,
this measurement gives the linear equation
on the s that s must satisfy. Repeat this
process n minus one times, collect n minus
one linear equations. Solve them and you
find your secret string s.