Help us understand the problem. What is going on with this article?

可能な限り簡単にPythonベースで量子アニーリングで最適化問題をとく

なに?

量子コンピュータとかヨクワカラナイし、イジングモデルとかよくわからない、数式もΣとか苦手、でもPythonなら読める。

数式よりもソースコードの方が直感的で何といっても動かして理解できるので「量子コンピュータ」の1方式である「量子アニーリング」のお勉強をPythonでしてみるのもいいかな、と、メモとしてまとめました。

量子コンピュータと量子アニーリング

「量子コンピュータ」と言うとそこそこ広い範囲の言葉で色々なものをさします。

そんな「量子コンピュータ」と呼ばれるものの1つに「量子アニーリング」と言われる方式があります。

ざっくり言うと「量子アニーリング」は「組み合わせ問題」を解くものです。今のパソコンに取って代わるようなものではなくシンプルに組み合わせ問題を解けるだけのものです。

組み合わせ問題といってもパッとこないかもしれませんが、たくさんの物の中からBetterな組み合わせを選ぶタイプの問題です。世の中意外とそういう問題は多くて、、、お洋服を選んだり、最適な交通経路を選んだり、300円で駄菓子を選んだり、意外とよくあるタイプの問題です。

今のコンピュータも十分に高速とは言え、数が多い組み合わせの問題を解くのには時間がかかってしまいます。「量子アニーリング」はその組み合わせ問題をより効率的に解ける可能性がある技術です。

・・・ということで前置き長くなりましたがさっそくソースコードでいきます。

環境準備

まずPythonが動く環境を用意してください。
pip で必要なライブラリをインストールします。

pip install pyqubo

さくっと簡単なサンプルを作ってみます。

from pyqubo import Binary, solve_qubo

# 今あるスキマ時間
sukima_jikan = 45

a = Binary("アニメ")          # 30分
b = Binary("おもしろ動画 A")   # 5分
c = Binary("おもしろ動画 B")   # 4分
d = Binary("おもしろ動画 C")   # 3分
e = Binary("ドラマ")          # 60分

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)

# 実行結果:
# {'おもしろ動画 A': 1, 'おもしろ動画 B': 1, 'おもしろ動画 C': 1, 'アニメ': 1, 'ドラマ': 0}

今回の例題は、「表のような5つの動画」があって、今スキマ時間としてぽっかり「45分」時間があいたとします。その時にどういう組み合わせの動画を見ればスキマ時間を過ごせるか?という問題です。

変数 動画 時間
a アニメ 30分
b おもしろ動画 A 5分
c おもしろ動画 B 4分
d おもしろ動画 C 3分
e ドラマ 60分

それでは順番にコードを説明していきます。

まず各動画を表す変数を準備します。
Binary とは 0 または 1 になってくれる型です。

a = Binary("アニメ")
b = Binary("おもしろ動画 A")
c = Binary("おもしろ動画 B")
d = Binary("おもしろ動画 C")
e = Binary("ドラマ")

そして次に、いわゆる評価関数みたいなものを作ります。

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

この評価関数 H の値が最小になるように a b c d e の組み合わせをイイ感じに考えようと思います。

H の意味について説明します。

  • a b c d eBinary0 または 1 の値になってくれる。
  • その Binary の意味を 「1は動画を見る」「0は動画は見ない」とする。
  • 「『スキマ時間』から『見る動画の時間』を引いた数」が小さくなるほど高評価とします(つまりヒマな時間つぶせる方を良しとする)
  • 小さい方がいいとはいえマイナス、つまり、スキマ時間以上に動画を見られた場合に高評価になっても困るので二乗することでマイナスをかき消す

では実際の例を見てみます。

例えば、「スキマ時間 45分」で「変数 a のアニメ」だけを見る場合、変数 a1 になって他は 0 になるので、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

別のパターンで、「変数 b のおもしろ動画」と「変数 c のおもしろ動画」を見る場合、変数 b c1 になって他は 0 なるので、H=1296 になります。

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

つまり、「変数 b のおもしろ動画 + 変数 c のおもしろ動画」の H=1296 より「変数 a のアニメ」の H=225 の方が H が小さいので高い評価=時間をつぶせた、と言えます。

という感じで、a b c d e の組み合わせと H の値を見ていくとこんな感じになります。

a b c d e H
0 0 0 0 0 2025
1 0 0 0 0 225
0 1 0 0 0 1600
0 0 1 0 0 1681
0 0 0 1 0 1764
0 0 0 0 1 225
1 1 0 0 0 100
1 0 1 0 0 121
1 0 0 1 0 144
: : : : : :
1 1 1 1 0 9
: : : : : :
1 1 1 1 1 3249
: : : : : :

という感じでこの中から一番 H が小さい組み合わせを選びたいのですが、普通なら1つ1つ解いていくしかありません。

これをなんとなくイイ感じに解いてくれている部分がここです。

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)

評価式 H (本当は評価式ではなくハミルトニアンと呼びます)を作って、それを元に QUBO というものを作って(to_qubo())、それを解く(solve_qubo())ことで解を得ています。 このハミルトニアン(≒評価式)から解となる組み合わせを「量子」の特性を借りて選び出すのが「量子アニーリング」と言われるものです。

ということで実行して見ると答えとして以下が得られます。

{'おもしろ動画 A': 1, 'おもしろ動画 B': 1, 'おもしろ動画 C': 1, 'アニメ': 1, 'ドラマ': 0}

つまり、45分のスキマ時間があったら、

変数 動画 時間 視聴
a アニメ 30分 見る
b おもしろ動画 A 5分 見る
c おもしろ動画 B 4分 見る
d おもしろ動画 C 3分 見る
e ドラマ 60分 見ない

30分 + 5分 + 4分 + 3分合計42分 見ると良いという組み合わせが得られます。

めでたしめでたし

まとめると、細かいことは抜きにして解きたい問題に対して H の式を作れるかが大事ってことです。

この後にやること

例えば、スキマ時間を変えてみる、動画の数を増やしてみる、とかして色々試すと面白いです。 他にも、動画に★の数とかつけてなるべくたくさん★の高い動画を見れるようにする(そんな H の評価式を作る)とかもおススメです。

まとめ

あれ? 自分のパソコンは「量子コンピュータ」だっけ? なんでこのコード動いたの? と思ったかもしれませんが、今回使わせていただいた PyQUBO はシミュレータが入っているので普通のPCでも動いてくれます(感謝!)。もしD-WAVEやなんとかアニーラみたいな本物の量子アニーリングマシン(とか量子ではないけど高速なアニーリングマシン)を使える方がいたら上のコードの solve_qubo あたりを差し替えることで実際の量子アニーリングも実行できます。

本来はイジングモデルやQUBOとかハミルトンとかきちんと説明しないといけないのでしょうが、、、私のようなプログラマ/エンジニアのとっかかりとしては「プログラム」で理解できる方が早いのでPythonベースでまとめてみました。

識者からのツッコミ大歓迎ですのでコメント欄でぜひ何卒です。

567000
組み込みからWebサービスから機械学習からオブジェクト指向から開発プロセスから認定ScrumMasterからなんならUI/UX/HCD/デザイン思考まで。 投稿した内容でなにかあったらTwitterなどへ気軽にどうぞです。
https://twitter.com/aka567000
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした