The classical computer that you have right now
can do this in six tries
but what's even more impressive
is that a quantum computer can do this in one try.
(upbeat music)
Hi, welcome back to Coding With Qiskit, this is Abe.
Let's say there's a secret number hidden inside a box.
And that number is described by six bits,
so six strings of zeroes and ones.
How many attempts do you think you need
in order to guess that number correctly?
If you had a classical computer,
you could find that secret six-bit number in six tries.
And in fact, if that six-bit number was, instead 60 bits,
that would take you 60 tries.
And in general, if it had N bits, you'd need N tries
in order to find that secret number.
So this thing can quickly add up, right?
But if you had a quantum computer,
then you can use what's known as the
Bernstein-Vazirani Algorithm
to determine that secret number in one shot,
independent of the size of that number.
So what I hope to do in this video
is show you how to implement this algorithm in Qiskit.
So the Bernstein Vazirani Algorithm is an example
of many quantum algorithms,
where a quantum computer outperforms a classical computer.
So let's ask our computer to guess a secret number.
And in particular, this is going to be a binary number.
So it's going to be described by bits,
strings of ones and zeros.
And let's say we write down the secret number.
In this case, I'm going to pick a specific one.
It's going to be 1-0-1-0-0-1.
And I put that secret number in a box.
Now, the point of this box is to give us one function,
and that function is, if you feed it a guess,
it will tell you yes or no.
So how would you determine the secret number given this box
where you don't know what's inside it?
One way to do it, would be to ask this box,
"Hey, is the number inside 0-0-0-0-0-0?"
And the box would say no, that's not the number in here.
So then you'd change the number and ask,
"Is the box having the number 0-0-0-0-0-1 inside?"
And the box would tell you no, that's not the number.
And you do this until you stumbled upon the right answer,
which is the secret number inside the box.
Here's how your computer would do it.
So, your computer would write down
the number 0-0-0-0-0-1
next to the box,
and it would apply what's called an end operation.
And when it does this,
the end operation is effectively going to tell it,
one, wherever the two numbers are one.
And zero, when they're not one together.
So this gives you zero, this gives you zero,
this gives you zero, this gives you zero,
and this gives you zero.
So by doing this, what your computer has done,
is figured out that this digit
is one, in the box.
And then your computer would continue
by doing the same operation, using 0-1-0 here.
And as you can see, what it's doing,
is trying to figure out if that second number is also one.
And by doing this with
a third
end operation,
a fourth end operation,
and doing effectively,
six end operations, it would figure out
how many digits in the secret number, are one.
And by doing so, the computer would be able to find out
what the secret number is inside the box in six tries,
instead of the 64 that it took by just guessing randomly.
So where did we start off?
64 tries to find that secret number
seems like a lot of work.
The classical computer that you have right now
can do this in six tries.
But what's even more impressive is that a quantum computer
can do this in one try.
And what I'd like to do is show you
how this algorithm works on Qiskit.
So as always, I'm going to first import Qiskit.
So I'm going to say, from Qiskit import everything,
and I'm going to prepare to visualize my results
by saying
map plot lib inline
and from Qiskit dot tools dot visualazation
import
plot
histogram.
So now we're ready to start working with Qiskit
and I'm now going to say the secret number is 1-0-1-0-0-1.
So this is the secret number
that we've been talking about so far.
So let's start by building a circuit made from,
six, which is the number of bits
that we have in the secret number plus one qubits
and six classical bits on which we'll store results.
And what I'll do is start off
by applying a Hadamard Gate
to the first six qubits
out of the seven qubits that I'm using.
So I'll say Hadamard on
zero, one, two, three, four, and five.
So these are the first six qubits.
All right, so let's apply that,
and as always lets do circuit dot draw
output
equals
matplotlib.
And that's how our circuit looks right now.
For the last qubit I'm going to do one more thing,
which is to ask for an X gate before a Hadamard on it,
so I'm going to say circuit dot x on qubit six,
and circuit dot h on qubit six.
All right, let's see how that looks.
So now this is how our circuit looks.
We have Hadamards on all of the qubits
with this additional X gate on the last qubit.
I'll put a barrier here
so that things are a bit clearer for us.
A barrier simply adds
this vertical line that you're seeing here.
And now what I'm going to do is build the box
that contains the secret number.
So remember that the secret number is written here,
and what I'm going to do is,
for every one that I see in the secret number,
I'm going to put a cX gate.
And in particular the way I'm going to apply the cX gate
is as follows.
So I'm going to say circuit dot cX.
You see this one on this first bit,
so I'm going to go from
the last
qubit that we didn't have the X on,
up to that qubit that is the last qubit in the lines.
So I'm going to say cX from five to six,
and see how that works.
Yep, so that's the first one in our secret number.
So let's keep doing this.
(keys clacking)
So the secret number is 1-0-1-0-0-1,
so the fifth bit is going to have a controlled X,
the third bit is going to have a controlled X,
so I'll do three.
And finally the zeroes bit is going to have a controlled X.
So this is how our circuit looks.
Let's draw it.
So now the easiest way to see that the secret number
is encoded into this box is by reading off one
when you see a controlled X, and zero when you don't.
So one,
zero,
one,
zero,
one here.
And that's the box that encodes the secret number.
So I'll make it clear by applying a barrier here again.
And this is how our circuit looks.
And finally what I'm going to do
is apply another set of Hadamard gates.
So I'm going to apply that operation again.
And that's how our circuit looks.
And that's it.
We've now built the Bernstein-Vazirani algorithm.
So in order to understand how this circuit works,
I'm going to add measurements at the end.
So put another barrier,
(keys clacking)
and I'll say circuit dot measure,
and in particular put the results from bits,
zero, one, two, three, four, five
into the classical bits,
zero, one, two, three, four, five.
And that's how the circuit looks.
Now we're done and we're ready to simulate the circuit.
So let's run the circuit to see that it's working.
So what I'm going to do is say the simulator
is err dot get backend,
chasm
simulator,
and I'm going to execute the circuit
that we've built that we've built so far.
I'm going to choose the backend to be the simulator,
and I'm going to say I want one shot, because,
I promised you that this would all be done in one shot.
I'm going to take the result of this execution,
and store it into a variable called result.
And then I'm going to say count is result dot get count.
And then what I'll do is print out the count,
so that we see what the output is.
And as you can see here,
in that one shot that we did,
the result was 1-0-1-0-0-1.
So the circuit was able to guess our secret number
in that one shot.
Now let's try a little bit of an advanced example.
So what I'm going to try to do here,
is to generalize the code
so that it works on any secret number.
So to make this a bit more general,
here are the changes that I'm going to do.
So instead of saying apply the Hadamard gate
to qubits zero through five,
what I'm going to say is apply the circuit dot h,
going through
range length
of secret number.
So in Python what this does is return exactly the array
zero through five for this particular secret number.
And again what I'm going to do is comment this line out
and say apply this to the
(keys clacking)
last qubit,
and then apply this Hadamard also to the last qubit.
Okay.
So again let's rerun our piece of code,
see how the circuit looks.
Nothing has changed.
So what we've done is change this part
to be a bit more general.
Now let's change the box.
So how was the box encoded?
We simply applied controlled X's
wherever we saw a one in the secret number.
So how would I write down this logic in Python?
So I would say four
I I
yes no
and enumerate
the secret number.
And in particular, remember that
we built the circuit from top to bottom,
meaning when we saw a one, the control dex
was applied to the bottommost qubit.
And so what we're going to do is not take the secret number,
but reverse it.
So I'm going to say reverse secret number.
I'm going to say if
that string contains one,
then I'm going to apply a controlled X,
going from the index of that qubit
to the last qubit.
Okay, that should do it.
So that replaces these lines of code,
so I'll comment these out.
And finally,
so let's check again,
how our circuit looks.
Again we have 1-0-1-0-0-1 here.
We're going to say all these Hadamard gates again
can get replaced with this line of code.
I'll comment this out,
look at the drawing again,
see that nothing has changed,
and the measurements of course going from
this range again,
to this range.
And that's it.
So we've now rebuilt the circuit
in a more general piece of code.
The last change I'm going to make is change this number
so the quantum circuit that we're building
is not just composed of six qubits anymore,
but the length of the secret number plus one,
and it's going to have as many classical bits
as there are bits in the secret number.
So that's it.
This builds our circuit in a more general form
and in particular if I were to go and change
the secret number, from 1-0-1-0-0-1 to something like
1-1-1-0-0-0,
the circuit would be updated,
and I can use this circuit
to find that secret number in one shot.
And again, it's not just that I can change
the secret number in these two forms,
but I can also change the length of the secret number
and the quantum circuit should update to accommodate
that change in the length of the secret number.
So hey, Paul.
Do you want to give me a hand here?
So what I'd like you to do
is change the secret number up top
to something that you'd like,
and I'll cover my eyes as you do this
and remember to hit shift+enter after you're done
and scroll so that I don't see that secret number.
Okay.
Any number?
Any number. Any amount of numbers.
Yep.
(upbeat music)
Shift+enter.
So that I don't see it.
Okay.
Okay so I'm claiming here
that I can find your secret number, Paul,
by running the quantum circuit,
and it looks like your secret number was...
(laughs) 1-1-0, Mmhmm.
(laughs) 0-1-0,
1-0-0,
0-1-1,
1-0-1,
0-1-0.
Was that your secret number?
Say it again?
(laughter)
Instead of talking to Paul,
I have a better way here, which is that
I'm going to go up and look at the secret number,
and do a comparison side by side
by pasting it here.
So I'm confident now, looking at this,
that I did find the right number.
(hands clapping) (upbeat music)
So this is cool, right?
So for the classical computer we needed
six tries to find the secret number,
but as it turns out,
for the quantum computer we only needed one try.
If you'd like to learn more
about the mathematics behind the algorithm,
we suggest that you take a look at the link below
to the online Qiskit textbook.
And in fact, now that you're equipped
with the knowledge to understand these quantum circuits
and write them and execute them,
what you can do is take a look at the other
quantum algorithms in the Qiskit textbook,
and see if you can run those as well.
So one thing that you can do
is also to try to run this quantum circuit
on real hardware.
Tell us in the comments down below
what results you find when you do this.
As always, thanks for watching,
and we'll see you next week.
(upbeat music)