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.