(upbeat music)
- [Jin] Welcome back to coding with Qiskit.
I'm your host Jin.
If you're joining us for the first time
in this series we talk about quantum algorithms each week.
So be sure to like and subscribe.
A few weeks ago, we talked about how a quantum computer
can find a certain element of a database
faster than a classical computer.
Using an algorithm called Grover's algorithm.
This week we're gonna talk about how to extend
Grover's algorithm.
In order to do an optimization problem called
the satisfiability problem.
So let's talk about what the satisfiability problem is.
Let's imagine that I want to order something for lunch.
So obviously I want to order from someplace that's open.
Ah, they're nearby.
They deliver.
And maybe I'm feeling tight food.
So I've just listed my four constraints there.
My question is if I have a list of available restaurants
which restaurant satisfies all four of my constraints?
By encoding my constraints into a quantum Oracle,
I could theoretically figure out which restaurant
I should order from.
Faster than if I were using a classical computer.
For a reasonable number of restaurants.
My phone can do this dress fine.
But what if we're thinking about,
"Big data sets."
For big data sets, we can have a quantum speed up.
Because we can recast this problem into a search problem.
We can search over every combination of inputs
and determine which input evaluates to true,
given our constraints.
Another useful example
of a satisfiability problem
that we're going to implement today using Grover's search
is the Grover's dinner party.
So imagine I wanna invite some friends over for a party.
I'm gonna invite, Abe and Olivia
and they're good friends from Qiskit camp.
And I also wanna invite my friend Amira.
However, Abe and Amira just had a big fight
and then they don't wanna hang.
So how can I invite as many friends as possible
while making sure everyone gets along?
Fortunately, Grover search can be used
for bullying satisfiability problems.
And the constraints for our party planning problem
can be formulated with the following bullying expression.
So we can have Olivia and Abe
or Jin and Amira
and not even Amira.
And we can simplify this a little bit just by saying
A and B
or C and D.
And not A and D.
So let's see what this looks like in Qiskit.
So I'm going to first activate
my environment
going with Qiskit.
This is where I have Qiskit installed.
And I'm gonna open up a Jupiter notebook.
So from Qiskit, I'm going to import
my simulator basic error.
From Qiskit,
Aqua algorithms.
Import my Grover search
from Qiskit.aqua components.
Got Oracle's import my Oracle.
From Qiskit tools,
visualization import
plot histogram.
So I can see my results.
So I'm gonna encode my logical expression in here.
So it's going to be,
Olivia and Abe,
or Jin and Amira.
Okay.
And,
not Abe and Amira.
Amira.
Okay.
I'll plug this into my algorithm.
Which is my Grover search.
Logical expression,
Oracle,
get my logical expression.
Okay good.
I'm going to get my backend.
So I'm gonna grab the basic air
simulator.
From which I'll grab the chasm simulator.
Okay good.
Now let's run this algorithm.
Okay. Good.
All right. Let's plot our results.
That measurement results
possible party combinations
are labels and is true.
Okay. Good.
So what we're seeing here is the possible combinations
of people I can invite to the party.
So each number represents whether or not each person
should be invited or not.
And these are organized alphabetically.
So this will go,
Abe, Amira, Jin, Olivia.
So one possible combination is Amira and Jin are invited.
That's what this first column is saying.
The next possibility is Abe and Olivia should be invited.
The next possibility is Abe, Jin L and Olivia
should be invited.
And the last possibility is Amira, Jin and Olivia
should be invited.
So why run this on a quantum computer?
In the small example, my laptop can
handle this calculation just fine.
But suppose we want to add six more people to the equation.
And each one of them has their own constraints.
If I had a total of 10 guests, the number
of combinations blows up to one thousand twenty four.
And every time I add another guest to the list
this number doubles.
So solving this problem on a classical computer
would take off order N time
where N is the number of combinations.
- [Male narrator] Versus of order square, root.
- [Jin] N time
on a quantum computer.
Why don't you try to map Grover's algorithm
onto your own satisfiability problem.
And let us know what you get in the comments below.
That's it for this episode,
make sure to like, and subscribe
and tune in next week where we'll talk
about quantum machine learning.
See you then.
This week was brought to you by Dunkin donuts.
- [Male narrator] Dunkin. Say Dunkin man.
- [Jin] This week was brought to you by Dunkin.
Quantum runs on Dunkin.
(chuckles)
(upbeat music)