QUANTUM GAMING

Nobisuke

Dekisugi

autoQAOA

量子コンピュータ学ぶなら。最適化と機械学習を量子ゲートで始める。

Yuichiro Minato

2024/12/24 14:46

こんちは。量子コンピュータ始めたいけど、敷居が高いですね。今回は始めやすい最適化と機械学習について量子コンピュータの始め方を解説します。

０、方針と利用するツール

とりあえず今のコンピュータに馴染んでいる方が量子コンピュータのプロジェクトをどこから手をつけていいか分かりづらいという相談が多々あります。そういった際に、まずは既存コンピュータと共通する知識から始められないかというのが今回の始まりです。

利用するツールは通常、IBMのQiskitという量子コンピュータのプログラムを司るSDKと呼ばれるツールを使いますが、こちらはPython環境で、

pip install qiskit

でインストールします。しかし、結構使い方や問題への落とし込みが分かりづらかったり、そもそも更新が頻繁なので難しかったりします。今回は、歴史的な変遷などは一旦おいておいて、通常の古典コンピュータ側の視点から少しずつ量子を深掘りする方向に解説を進めたいと思います。

１−１、量子コンピュータでの最適化

量子コンピュータの現在の量子ビット数はかなり限られていて、実機やシミュレーションで意味のある計算をしようとすると20-30量子ビット程度に限られてしまいます。例えば小数点を使った複雑な計算(小数を表現するのにたくさんビットが必要)や量子ビットをたくさん利用するものは苦手です。

組合せ最適化問題は現在量子コンピュータでも分かりやすいものですが、01のバイナリの値を使うため、量子ビットが少なくてもある程度わかりやすい答えが出るため重宝されます。

ここでは、説明変数から目的変数を最小化する組合せ最適化問題を見ます。組合せ最適化問題は目的は同じでも、より効率的な解を求めるための計算で、古典計算でのタブーサーチや遺伝アルゴ、シミュレーテッドアニーリングなどのアルゴリズムに相当します。量子でもいくつかあるのですが、基本的にはシミュレーテッドアニーリングに似たアルゴリズムを使うのが普通です。

１−１ー１、定式化

まずは、定式化と言って問題を式の形にします。よく界隈で聞くQUBO（キューボ）という定式がありますが、これは0か1のバイナリ値を利用して、二つの変数の掛け算までの２次式を扱って問題を定式化します。

なぜ二次式かというと、2012年にカナダで登場した量子アニーリングマシンというマシンが量子ビットの接続が２つまでだったので、その名残りで二次式になっています。しかし、実際にその後2015年に登場したIBMやGoogleのマシンでは特に二次式に囚われることなく三次以上の計算ができます。HOBO（ホーボ）という名前で区別されることがありますが、まだこのあたりは業界では確実に名称は決まっていません。QUBOとHOBOは似ているようで、使うテクニックが意外と違うので、今後発展するかも？しれません。

Numerical Exploration of the Pythagorean Theorem Using HOBO Algorithm

Shoya Yasuda, Naoaki Mochida, Shunsuke Sotobayashi, Devanshu Garg, Yuichiro Minato

https://arxiv.org/abs/2408.11076

さて、最初にQUBOの定式化を見てみると基本的に式はソフト制約と呼ばれる、条件を全て式の形にしたものを準備する必要があります。

Q(x) = \sum_i c_ix_i + \sum_{i<j}q_{ij}x_ix_j

ここで、 $Q(x)$ は求めたい値、 $x$ は0もしくは1をとる変数です。 $c_i$ は $x$ の一次の項にかかります。 $q_{ij}$ は $x_i$ と $x_j$ の二つの変数の間に設定する値です。HOBOはさらに字数を上げても大丈夫です。

H(x) = \sum_i c_ix_i + \sum_{i<j}q_{ij}x_ix_j + \sum_{i<j<k} h_{ijk}x_ix_jx_k + \cdots

１−１−２、少し具体例

少し具体例をQUBOで確認します。量子コンピュータでのアルゴリズムは式を作ったら、それを最小化するように計算をしてくれます。ですので、我々は行うのは、各問題を定式化することになります。量子ビット単体で考えてみます。一つの量子ビットは0か1を取ると考えると、

Q(x) = 2 * x_0

の式は、例えば、 $x_0 = 0$ の時20=0となり、 $x_0=1$ の時、21=2となります。0と2を比較すると0の方が小さくなるので、 $x_0 = 0$ が導き出されます。量子ビットが二つの時は、

Q(x) = 2 * x_0 * x_1

だと、 00=0, 10=0, 01=0, 11=1で、二つの量子ビットが11以外は等しく0となるため、上記の式を満たす答えは三つ存在します。これをより複雑に定式化したのが量子における組合せ最適化です。

１−１−３、制約条件

正確には制約条件をハード制約といい、式から外すこともできるのですが、一般には問題の制約やコストは全て式の形にします。例えば、「三人のうち一人だけがシフトに入る」というような満たすべき前提の条件を制約条件とします。一方、「一人当たりの仕事量はなるべく少なくなるようにする」のようにできるだけを満たすようなコストを最小にするような関数もあります。別々に設計して最終的に繋げます。

Q(x) = (制約条件) + (コスト)

この辺りはオンラインでもたくさん記事がありますし、最近ではTYTANのチュートリアルや日本量子コンピューティング協会での検定試験が程よく難しく実用的なのでお勧めしています。

TYTAN

https://github.com/tytansdk/tytan

日本量子コンピューティング協会

https://www.jqca.org/

- １−２−１、最適化をゲートにする１

多くの人にとってはここからが問題になるかもしれません。式を作って解くところまでは量子アニーリングと呼ばれる分野だったり、最悪普通の古典計算でもできます。しかし、上記の定式化を量子コンピュータで計算するためにはもう数ステップ必要になります。手順は一般的な方法では自動化もできるのであまり学ばなくてもいいのかもしれませんが、中身を見てみます。

まず、量子コンピュータで組合せ最適化を解くためのアルゴリズムとして量子断熱計算を利用したものがあります。量子断熱計算は、量子断熱定理に基づいた手順で計算すると上記の定式化を最小値に導くというものです。量子断熱計算では、最初に簡単な式の答えを準備して、おいてゆっくりと定式化を簡単な問題から難しい問題へとすり替えることで実現されます。すり替える手順は離散化されており、全体のスケジュールTに対して、途中の時間tを考えると、

H(x) = \frac{1-t}{T} * H_{easy}(x) + \frac{t}{T} * H_{difficult}(x)

二つの式はそれぞれ同じ変数を使って実装されますが、一般的に $H_{easy}$ は答えがわかっていて作りやすい問題として、量子特有の重ね合わせ状態が利用されます。よりテクニックを使いたい時は初期に準備する答えと利用する初期の式を変更することもありますが、一般的には上記の式を使うのが普通です。

- １−２−２、最適化をゲートにする２

全体の方向性は量子断熱計算を利用して、簡単な式から難しい式にすり替える手順を確認しました。より具体的にみます。まず、変数ですが、0か1を使ってきましたが、量子回路のパラメータを決めるために変数を1と-1に変換をする必要があります。定式化の変数は0か1のバイナリの値として扱ってきましたが、量子計算の途中式を表現するために定式化はバイナリの値ではなく、行列の演算子で表現され、量子状態と組み合わせて期待値で値が求められます。最終的な答えは古典的な状態を表すので結局0か1にはなるのですが、途中式ではより複雑な状態が計算され、0と1の重ね合わせやもつれ状態を表現する必要があるため、元の0を+1、元の1を-1に変換して計算します。変換の方法は簡単で、 $1-2*x =z$ と計算すればよく、 $1-0*2=1$ と $1-1*2=-1$ と計算をすることで、0を1に、1を-1に変換できます。これによって定式化の係数が多少変化します。

- １−２−３、最適化をゲートにする３

もとまった係数をもとに、量子ゲートに直します。あまり深く考える必要はないですが、例えば変更した後の式が、

H(x) = 2*z_0 + 3*z_0*z_1

の場合、係数2と3は角度に変換されます。

$Rz(-2*2t')$ と $Rzz(-2*3t')$ に変換されます。細かい導出は時間がかかりますので、ここでは割愛します。初期の式も同様に変換するとRx(-2*t'')のゲートも加わり、

|0> - H - Rz(-2*2t') - Rzz(-2*3t')-Rx(-2*t'')--
                       |
|0> - H - ------------ Rzz(-2*3t')-Rx(-2*t'')--

のような形式になります。最初のHは $H_{easy}$ の答えとなる重ね合わせ状態です。これを繰り返すこともあります。量子断熱計算はゆっくりと変化させるというのが前提になってるのですが、これをステップ数を刻むことで変化をゆっくりと表現することもできますので。

かなり説明を省略してしまいましたが、定式化を量子ゲートに治す方法があることだけざっくりと覚えてもらえればいいかなと思っています。

あとは計算すると所望の答えに対応する解答が確率的に出てきます。
数理最適化の知識も量子計算の知識も両方必要なので意外と大変な分野かもしれません。
さらにQAOAというアルゴリズムは角度のところをぼかして変数としてその変数を最適化することによって解に近づける変分計算を導入したものになっています。

２、量子コンピュータでの機械学習

量子コンピュータで機械学習をしたいとにはこれもいくつか方法がありますが、簡単なのは量子ニューラルネットワークっぽいものを導入することです。量子コンピュータでの量子回路でそれっぽいものを作ります。

基本的にニューラルネットワークは、バイアスとウェイトで構成されており、それを量子ゲートで表現すればOKです。

バイアス値は1量子ビットのゲート、ウェイトは2量子ビットゲートで代替します。異なるのは、量子計算の場合、量子ビットの取りうる値の範囲が2次元球面を取りますので、RX,RY,RZのような1量子ビットで自由に角度を調整できる量子ゲートを利用し、その角度を変数として最適化します。

|0>-RX(theta0)-RY(theta1)-RZ(theta2)-
|0>-RX(theta3)-RY(theta4)-RZ(theta5)-

のように個別の量子ビットに個別に量子ゲートをかけます。RXだけでもいいかもしれませんし、RX-RYのようにしてもいいです。よくある例では、RX-RY-RZなど豊富に入れてしまいます。計算は重たくなります。

次にウェイトは2量子ビットゲートを使います。2量子ビットゲートはCXやCZなどがありますので、先ほどのバイアスに続いて、

|0>-RX(theta0)-RY(theta1)-RZ(theta2)-C---
                                     |
|0>-RX(theta3)-RY(theta4)-RZ(theta5)-X---

機械学習の場合には、これといった決定打がないので、なんとなくこういう量子ゲートを重ねて古典のニューラルネットや機械学習と似た構造を作ることが多いと思います。2量子ビットゲートにはパラメータが入ってないですが、CX-RZ-CXみたいにしてRZにパラメータを入れるなどもできます。

どちらにしろ機械学習の場合、パラメータが多くなりすぎるのですが、それらを最適化する手法は今のところ見つかってはいません。