こんにちは、よくニュースで量子コンピュータを使った組合せ最適化問題と話題になりますが、今回は超簡単に説明にトライしてみます。
まず、組合せ最適化問題はたくさんあるものから一番いいものを選ぶという問題です。一番いいというのは人によって価値観が違ったりしますので、そこをきっちりと式の形で表現して機械的に解かせる必要があります。
まずは有名なのはカーナビですね。今回は社会人１年目のA君が、車で山にドライブにいくというシチュエーションを考えます。カーナビのルートは３種類あり、５分、１時間、３時間それぞれかかります。
価値観は人それぞれです。時間が余ってるので、３時間かけてゆっくり行きたいという人もいれば、一刻も早く着きたいという人もいます。まずは目的を決めます。今回の目的は時間を短くとします。A君は社会人ですので時間がありません。
今回は後述する量子コンピュータが自動的に一番低い値を選んでくれる機能を使って、上の目的を数式の形にします。これがコスト関数とか目的関数と呼ばれるものです。今回は時間が短くなるようにしました。それぞれのルートが選ばれたら1、選ばれなかったら0になるとします。数式は上のようにかかる時間をかけて全部足します。こうすることによって、q1のルートが選ばれたときにこの数式は最小になるようになっています。
これだけでは実は足りません。実はこの式は全部0の時、つまりどのルートも選ばないときに式は最小値0を取ってしまいます。全部選ばないというのは許されず、必ずどれか選んでもらいたいので、条件を付けます。これが制約条件というものです。
条件の付け方は２種類あって、式の形で表現するものと量子もつれを使うものです。式の形で表現するものは、全部足して-1してから2乗するとつくれます。これはどれか一つが1で、残りが0の時に最も小さい値の0を取るからです。
つぎに量子もつれを紹介します。
量子もつれは前回紹介しました、複数の量子ビットの値が連動する機能です。今回は３つの量子ビットを使って、上記のような量子もつれを作ります。そうすることによって、どれかが1の時に、ほかが0になるような値だけを作り出すことができます。
なぜ量子コンピュータを使うと一番小さい値が取れるのでしょうか。それには、オムレツを考えてみます。卵の形からフライパンをゆっくり熱しながら丁寧にかき混ぜるときれいで半熟なオムレツができます。このゆっくり熱してかき混ぜるという操作が重要です。量子コンピュータも同じように、量子シミュレーションを使って、最終的な問題の一番小さい値を取るようにきれいに整頓された状態を、ゆっくりかき混ぜながら進めると選ぶことができるというのがあります。これを使って問題を設定し、ゆっくりと計算をします。
量子コンピュータでの組合せ最適化問題は簡単です。一番小さい値を自動的に選んでくれるアプリを使って問題を式の形にします。その時に破ってほしくない前提条件は式の形もしくは量子もつれを使って表現します。こうすることによりカーナビのような計算をすることが可能となっています。
現在の量子コンピュータは性能が低いのであまり難しい問題はできません。しかしblueqat SDKを使ってやってみたいとおもいます。blueqatには、上記のゆっくりかき混ぜて答えを出すためのアプリが実装されています。QAOAといいます。使い方を確認します。
from blueqat import vqe
from blueqat.pauli import qubo_bit as q
hamiltonian = 5*q(0)+60*q(1)+180*q(2)
step = 1
result = vqe.Vqe(vqe.QaoaAnsatz(hamiltonian, step)).run()
print(result.most_common(1))
最初の二行はツールの読み込みです。
次にhamiltonianと書いてあるのが数式の入れるところになります。かかる時間と量子ビットが掛け算されて全部足されています。
stepはゆっくりかき混ぜる速度のようなものです。数字が大きいほど丁寧になりますが、今回は問題が簡単なので1とか2で十分かと思います。
そしてあとは勝手に計算させます。
こたえは、000とか100とかが出ます。上の数式は全部0の時が一番小さいのですが、かき混ぜ速度が速いので間違えることもあり、100も時々選ばれます。式にさらに制約などをかけて計算すると正解に行くことができます。制約条件を入れるのは話が長くなるのでまた別の機会にしたいと思います。
今回は基本的な計算の仕組みと問題の設定の仕方を確認しました。ぜひ興味を持っていただいて取り掛かってみてください。以上です。