Solve optimization problems with quantum annealing based on Python as easily as possible

What?

I'm not sure about quantum computers or Ising models, I'm not good at mathematical formulas like Σ, but I can read it with Python.

Since the source code is more intuitive than mathematical formulas and can be understood by moving it, I thought it would be a good idea to study "quantum annealing", which is one method of "quantum computer", in Python. I summarized it as.

Quantum computer and quantum annealing

The term "quantum computer" refers to a wide variety of words.

One of the so-called "quantum computers" is the method called "quantum annealing".

Roughly speaking, "quantum annealing" solves a "combination problem". It is not a replacement for the current personal computer, but a simple combination problem.

It may not be a combination problem, but it is a type of problem where you choose a better combination from many things. There are many such problems unexpectedly in the world, and it is a surprisingly common type of problem, such as choosing clothes, choosing the best transportation route, and choosing sweets for 300 yen.

Today's computers are fast enough, but it takes time to solve a large number of combinations of problems. "Quantum annealing" is a technology that has the potential to solve the combination problem more efficiently.

... So it's been a long preface, but I'll start with the source code.

Environmental preparation

First, prepare an environment where Python can run. Install the required libraries with pip.

pip install pyqubo

Let's make a quick and simple sample.

from pyqubo import Binary, solve_qubo

#Current gap time
sukima_jikan = 45

a = Binary("Anime")          #Half an hour
b = Binary("Funny video A")   #5 minutes
c = Binary("Funny video B")   #4 minutes
d = Binary("Funny video C")   #3 minutes
e = Binary("Drama")          #60 minutes

H = (sukima_jikan - a*30 - b*5 - c*4 - d*3 - e*60)**2

qubo, offset = H.compile().to_qubo()
solution = solve_qubo(qubo)
print(solution)

#Execution result:
# {'Funny video A': 1, 'Funny video B': 1, 'Funny video C': 1, 'Anime': 1, 'Drama': 0}

In this example, let's say you have "** 5 videos like a table " and now you have a gap of " 45 minutes **". What kind of combination of videos can I spend at that time? Is the problem.

Let's explain the code in order.

First, prepare variables that represent each video. Binary is a type that can be 0 or 1.

a = Binary("Anime")
b = Binary("Funny video A")
c = Binary("Funny video B")
d = Binary("Funny video C")
e = Binary("Drama")

And then, create something like a so-called evaluation function.

H = (sukima_jikan - a*30 - b*5 - c*4 - d*3 - e*60)**2

I would like to think about the combination of ʻa b` `c d ʻe so that the value of this evaluation function H is ** minimum **.

Explains the meaning of the expression H.

--ʻA b`` c d ʻe is Binary and can be a value of 0 or 1. --The meaning of Binary is" ** 1 to watch the video ** "and" ** 0 to not watch the video ** ". ――The smaller the "number obtained by subtracting" ** watching video time ** "from" ** gap time ** "", the higher the evaluation (that is, it is better to kill the free time). ――Although smaller is better, it is negative, that is, if you watch the video for more than the gap time, it will not be a problem even if it gets high evaluation, so ** square ** to erase the negative

Let's see an actual example.

For example, if you only watch "animation of variable a" with "clearance time 45 minutes", the variable ʻabecomes1 and the others become 0, so H = 225`.

H = (sukima_jikan - a*30 - b*5 - c*4 - d*3 - e*60)**2
  ↓
H = ( 45 - 1*30 - 0*5 - 0*4 - 0*3 - 0*60 )**2
  = ( 45 - 30 - 0 - 0 - 0 - 0 )**2
  = ( 15 )**2
  = 225

If you watch "Funny video of variable b" and "Funny video of variable c" in another pattern, the variable b``c becomes 1 and the others become 0, so H = 1296 It becomes .

H = (sukima_jikan - a*30 - b*5 - c*4 - d*3 - e*60)**2
  ↓
H = ( 45 - 0*30 - 1*5 - 1*4 - 0*3 - 0*60 )**2
  = ( 45 - 0 - 5 - 4 - 0 - 0)**2
  = ( 36 )**2
  = 1296

In other words, H = 225 of" animation of variable a "has smaller H than H = 1296 of" funny video of variable b + funny video of variable c ", so it was highly evaluated = time was killed. It can be said that.

So, if you look at the combination of ʻa b` `c d ʻe and the value of H, it looks like this.

With that feeling, I would like to select the combination with the smallest H, but normally I have to solve it one by one.

Here is the part that somehow solves this with a good feeling.

H = (sukima_jikan - a*30 - b*5 - c*4 - d*3 - e*60)**2
qubo, offset = H.compile().to_qubo()
solution = solve_qubo(qubo)
print(solution)

By creating an evaluation formula H (actually called a Hamiltonian instead of an evaluation formula), making a QUBO based on it (to_qubo () ), and solving it (solve_qubo () ) I have a solution. "Quantum annealing" is to select the combination that will be the solution from this Hamiltonian (≒ evaluation formula) by borrowing the characteristics of "quantum".

So, if you run it and see it, you will get the following as an answer.

{'Funny video A': 1, 'Funny video B': 1, 'Funny video C': 1, 'Anime': 1, 'Drama': 0}

In other words, if you have a gap of 45 minutes,

** 30 minutes + 5 minutes + 4 minutes + 3 minutes ** ** Total 42 minutes ** You will get a good combination.

Congratulations

In summary, it is important to be able to create an expression for H for the problem you want to solve without the details.

What to do after this

For example, it is interesting to try various things such as changing the gap time and increasing the number of videos. In addition, it is also recommended to add the number of ★ to the video so that you can watch as many videos with high ★ as possible (make such an evaluation formula of H).

Summary

that? Is my personal computer a "quantum computer"? Why did this code work? You may have thought, but the PyQUBO I used this time has a simulator, so it works on a normal PC (thanks!). If you can use a real quantum annealing machine like D-WAVE or Annealer (or a non-quantum but fast annealing machine), you can also perform actual quantum annealing by replacing the solve_qubo part of the above code. ..

Originally, I have to explain the Ising model, QUBO, Hamilton, etc. properly, but as a programmer / engineer like me, it is faster to understand with "program", so I tried to summarize it based on Python.

We welcome tsukkomi from experts, so please feel free to comment.