量子アニーリングマシンD-Waveで良い解を出すためのコツ（後編）

前編のご紹介

この記事は量子アニーリングマシンD-Waveで良い解を出すためのコツ（前編）の続きとなっています。
もしまだこちらの前編をお読みでない方はぜひ前編にも目を通していただければと思います

試しにやってみる（続き）

前編では★1の制約項の係数を調整するにはPyQUBOのプレースホルダーが便利という内容で書かせていただきました。
後編では★2チェーン強度の調整と、★3サンプリング回数の増やし方について書いていきたいと思います。

★2チェーン強度を調整する

チェーン強度ってそもそもなんだろう、という話をまずはしてみようと思います。
今回求解したいのは6都市のTSPだったので変数が36個となりますが、それだと説明がとても煩雑となってしまうので、もう少しデフォルメして説明します。

ということでここでは扱う問題の変数が5つだった場合を考えます。
5個の変数をQubitへ埋め込みするとき、全てのQubitが結合した次のようなトポロジーに落とし込む必要があります。

しかし、Qubitの配置が工夫されている最新の量子アニーリングマシン「D-Wave Advantage」ですら、次の通り変数とQubitを1対1に対応させることができません。
例えば1番のビットと2番のビットが結合しているべきなのにうまく結合させることができません。

そこで、次のように複数の物理Qubitを使って1つの仮想Qubitを構成させることで全ての変数の結合を実現しています。
（多分もう少し物理Qubitを節約した埋め込みができるかもしれないですが、説明のためにそこは突き詰めていません…。）

ここでは0番と1番でそれぞれ複数Qubitを利用していますが、0番（もしくは1番）として割り振られた2つのQubitがそれぞれ違う値を示してしまっては仮想的に同じQubitということができません。
そこで、同じ値を示させるためにチェーンというものが設定されており、そのチェーンが壊れないように強度を調整するためのパラメータがチェーン強度です。

今回扱う問題に立ち返ると、今回は6都市のTSPを解くわけですが、6都市のTSPでは6x6の36変数の結合を持った問題となります。
するとこの例よりもっとたくさんのQubitを使ってトポロジーを構成することとなります。

このチェーン強度ですが、強ければ強いほど良いじゃないか、と思われるかもしれません。
しかしD=Waveの仕様上、チェーン強度が強すぎるとせっかく作ったQUBOの影響度がどんどん低くなってしまうという特性があります。
要は、仮想的なQubit内での整合性は取れているが、肝心の定式化した問題の求解がされていない、といったことが起きてしまいます。

そのため、強すぎても弱すぎてもダメという、チューニングのしがいがある（？）パラメータとなっております。

チェーン強度のチューニング

基本的にはQUBO行列内の要素の最大値より少し大きいくらいの値を設定するとうまくいくような気がするのですが、もう少しチューニングっぽい手法をこの記事で提案します。

実は、D-Waveで求解をしたときにチェーンが壊れた割合を返してくれています。
それを確認するためにはdata_vectorsメソッドを利用してchain_break_fractionに格納された値を見ます。

実行コード

r = embedded_sampler.sample_qubo(qubo, chain_strength=162, num_reads=100)
r.data_vectors

data_vectorsメソッドの返却値

{'energy': array([ 略 ]),
 'num_occurrences': array([ 略 ]),
 'chain_break_fraction': array([0.        , 0.02777778, 0.        , 0.        , 0.02777778,
        0.        , 0.        , 0.        , 0.        , 0.        ,
        0.02777778, 0.        , 0.05555556, 0.        , 0.02777778,
        0.02777778, 0.02777778, 0.        , 0.02777778, 0.        ,
        0.08333333, 0.        , 0.02777778, 0.05555556, 0.        ,
        0.        , 0.        , 0.        , 0.02777778, 0.        ,
        0.08333333, 0.08333333, 0.02777778, 0.02777778, 0.02777778,
        0.02777778, 0.        , 0.02777778, 0.05555556, 0.        ,
        0.        , 0.05555556, 0.02777778, 0.        , 0.02777778,
        0.        , 0.02777778, 0.        , 0.        , 0.02777778,
        0.02777778, 0.02777778, 0.        , 0.02777778, 0.05555556,
        0.        , 0.02777778, 0.        , 0.02777778, 0.05555556,
        0.02777778, 0.02777778, 0.02777778, 0.05555556, 0.05555556,
        0.        , 0.02777778, 0.02777778, 0.        , 0.02777778,
        0.05555556, 0.02777778, 0.        , 0.        , 0.05555556,
        0.02777778, 0.02777778, 0.        , 0.        , 0.02777778,
        0.02777778, 0.        , 0.        , 0.05555556, 0.05555556,
        0.02777778, 0.05555556, 0.02777778, 0.        , 0.05555556,
        0.        , 0.02777778, 0.        , 0.        , 0.13888889,
        0.02777778, 0.05555556, 0.        , 0.05555556])}

この例では、0～0.13888889の割合でチェーンが壊れているということを示しています。
この例のような割合でチェーンが壊れているのであればかなり優秀なのですが、チェーン強度を示すパラメータchain_strengthの指定なしで求解を実行すると平気で1とか0.9とかの割合でチェーンが壊れたりします。

また、先述したようにチェーン強度は強ければ強いほどよいというものでもないのですが、それをdata_vectorsメソッドで見極めるならば、私の経験上chain_break_fractionが0～0.03付近の値しかない場合は強すぎです。
chain_break_fractionに0.1～0.2付近の数字がたまに出てくるくらいのチェーン強度に調整してやることで良い解が出やすいと思います。

★3サンプリング回数を増やす

サンプリング回数の話をする前に、D-Wave含め量子コンピュータの仕組みについてお話させていただきます。

量子コンピュータは量子の確率的な振る舞いを活用したデバイスですが、あくまで確率に基づく挙動を示します。
（「神はサイコロを振らない」と言ってこの曖昧な振る舞いを否定したアインシュタインの言葉が有名ですが、現状の科学の到達点としてはやはり確率に基づいた挙動をしていると捉えた方が整合性が取れるということのようです。）
確率的な挙動をしている故に、定式化したハミルトニアンの最小化問題を解いていても必ず厳密解が出力されるわけではなく、近似解が出力されるケースもあります。
そしてその解の出力は量子系の状態を観測される、すなわちサンプリングされることで行われます。
そのため、厳密解を出力する必要がある場合は特にサンプリング回数は多ければ多いほど有効となります。

では、無尽蔵にサンプリング回数を増やすことができるのか？と言うとそうでもありません。
まず第一に、D-Waveの仕様としてサンプリング回数の上限は10000回と決まっています。
では、10000回で良いではないだろうかと思うかもしれませんが、そうとも言い切れない観点が2つあります。
それは求解にかける時間と金額です。

時間については、D-Wave社も以下のようにQPU内で行われる処理のタイムラインを公開しています。
この中で1回のサンプリングにかかる時間は$T_a+T_r+T_d$となります。
1回だけであればほんの一瞬（0.1msのオーダー）で終わるのですが、やはりチリツモ的なところはあり、10000回となるとまあまあ待つことになります。

次に金額ですが、Amazon Braketの場合$0.30 / Task + $0.00019 / Shotという金額体系となっております。
ここで、

• 1Taskと言っているものが、1回APIを実行すること
• 1Shotと言っているものが、1回サンプリングをすること

となります。
課金としてShotの比重は大したことないのですが、こちらもやはりチリツモ的な部分はあるので、注意はした方がいいと思います。

こういった点に注意しながらサンプリング回数を調整するのですが、パラメータの指定はD-Waveに投げるAPIの引数の中でnum_reads=[回数]という形で指定すればOKです。

実行コード

r = embedded_sampler.sample_qubo(qubo, num_reads=1000)

実行結果

★1～★3でポイントとなりそうな事柄をまとめてみましたが、最後に実行結果例を掲載いたします。

全くチューニングしない場合

制約項の係数：5
チェーン強度：1（デフォルト）
サンプリング回数：10（デフォルトの1だと微妙なので…。）

最良解

'c[0][0]': 0, 'c[0][1]': 0, 'c[0][2]': 1, 'c[0][3]': 1, 'c[0][4]': 0, 'c[0][5]': 0, 
'c[1][0]': 0, 'c[1][1]': 0, 'c[1][2]': 0, 'c[1][3]': 0, 'c[1][4]': 0, 'c[1][5]': 0, 
'c[2][0]': 0, 'c[2][1]': 0, 'c[2][2]': 0, 'c[2][3]': 0, 'c[2][4]': 1, 'c[2][5]': 1, 
'c[3][0]': 0, 'c[3][1]': 0, 'c[3][2]': 0, 'c[3][3]': 0, 'c[3][4]': 0, 'c[3][5]': 0, 
'c[4][0]': 0, 'c[4][1]': 0, 'c[4][2]': 0, 'c[4][3]': 0, 'c[4][4]': 0, 'c[4][5]': 0, 
'c[5][0]': 0, 'c[5][1]': 0, 'c[5][2]': 0, 'c[5][3]': 0, 'c[5][4]': 0, 'c[5][5]': 0

→全然制約を満たしていない不適解が出力

制約項だけチューニングした場合

制約項の係数：100
チェーン強度：1（デフォルト）
サンプリング回数：10

最良解

'c[0][0]': 0, 'c[0][1]': 0, 'c[0][2]': 0, 'c[0][3]': 0, 'c[0][4]': 1, 'c[0][5]': 0, 
'c[1][0]': 0, 'c[1][1]': 0, 'c[1][2]': 0, 'c[1][3]': 0, 'c[1][4]': 0, 'c[1][5]': 1, 
'c[2][0]': 0, 'c[2][1]': 0, 'c[2][2]': 1, 'c[2][3]': 0, 'c[2][4]': 0, 'c[2][5]': 0, 
'c[3][0]': 0, 'c[3][1]': 0, 'c[3][2]': 0, 'c[3][3]': 1, 'c[3][4]': 0, 'c[3][5]': 0, 
'c[4][0]': 1, 'c[4][1]': 1, 'c[4][2]': 0, 'c[4][3]': 0, 'c[4][4]': 0, 'c[4][5]': 0, 
'c[5][0]': 0, 'c[5][1]': 0, 'c[5][2]': 0, 'c[5][3]': 1, 'c[5][4]': 0, 'c[5][5]': 0

→少し惜しいが、制約を満たしていない不適解が出力

チェーン強度だけチューニングした場合

制約項の係数：5
チェーン強度：43
サンプリング回数：10

最良解

'c[0][0]': 0, 'c[0][1]': 0, 'c[0][2]': 0, 'c[0][3]': 0, 'c[0][4]': 0, 'c[0][5]': 0, 
'c[1][0]': 0, 'c[1][1]': 1, 'c[1][2]': 0, 'c[1][3]': 0, 'c[1][4]': 1, 'c[1][5]': 0, 
'c[2][0]': 0, 'c[2][1]': 0, 'c[2][2]': 0, 'c[2][3]': 0, 'c[2][4]': 0, 'c[2][5]': 0, 
'c[3][0]': 1, 'c[3][1]': 0, 'c[3][2]': 0, 'c[3][3]': 0, 'c[3][4]': 0, 'c[3][5]': 1, 
'c[4][0]': 0, 'c[4][1]': 0, 'c[4][2]': 0, 'c[4][3]': 0, 'c[4][4]': 0, 'c[4][5]': 0, 
'c[5][0]': 0, 'c[5][1]': 0, 'c[5][2]': 0, 'c[5][3]': 1, 'c[5][4]': 0, 'c[5][5]': 0

→全くチューニングしない場合よりマシだが、制約を満たしていない不適解が出力

サンプリング回数だけチューニングした場合

制約項の係数：5
チェーン強度：1（デフォルト）
サンプリング回数：10

最良解

'c[0][0]': 0, 'c[0][1]': 0, 'c[0][2]': 0, 'c[0][3]': 0, 'c[0][4]': 0, 'c[0][5]': 0, 
'c[1][0]': 1, 'c[1][1]': 0, 'c[1][2]': 1, 'c[1][3]': 0, 'c[1][4]': 0, 'c[1][5]': 0, 
'c[2][0]': 0, 'c[2][1]': 0, 'c[2][2]': 0, 'c[2][3]': 0, 'c[2][4]': 0, 'c[2][5]': 0, 
'c[3][0]': 0, 'c[3][1]': 0, 'c[3][2]': 0, 'c[3][3]': 1, 'c[3][4]': 0, 'c[3][5]': 1, 
'c[4][0]': 0, 'c[4][1]': 0, 'c[4][2]': 0, 'c[4][3]': 0, 'c[4][4]': 0, 'c[4][5]': 0, 
'c[5][0]': 0, 'c[5][1]': 1, 'c[5][2]': 0, 'c[5][3]': 0, 'c[5][4]': 0, 'c[5][5]': 0

→全くチューニングしない場合よりマシだが、制約を満たしていない不適解が出力

全部チューニングした場合

制約項の係数：100
チェーン強度：162（チェーン強度はQUBO内要素のによって、つまり制約項の係数によってチューニングが必要）
サンプリング回数：1000

最良解

'c[0][0]': 0, 'c[0][1]': 0, 'c[0][2]': 0, 'c[0][3]': 0, 'c[0][4]': 0, 'c[0][5]': 1, 
'c[1][0]': 0, 'c[1][1]': 0, 'c[1][2]': 0, 'c[1][3]': 0, 'c[1][4]': 1, 'c[1][5]': 0, 
'c[2][0]': 0, 'c[2][1]': 0, 'c[2][2]': 0, 'c[2][3]': 1, 'c[2][4]': 0, 'c[2][5]': 0, 
'c[3][0]': 0, 'c[3][1]': 1, 'c[3][2]': 0, 'c[3][3]': 0, 'c[3][4]': 0, 'c[3][5]': 0, 
'c[4][0]': 1, 'c[4][1]': 0, 'c[4][2]': 0, 'c[4][3]': 0, 'c[4][4]': 0, 'c[4][5]': 0, 
'c[5][0]': 0, 'c[5][1]': 0, 'c[5][2]': 1, 'c[5][3]': 0, 'c[5][4]': 0, 'c[5][5]': 0

→制約を満たしており、かつ、TSPとしても最適な解が出力！

まとめ

ということで、チューニングポイントは「制約項の係数」「チェーン強度」「サンプリング回数」の3つがありそうだなということを個人的な経験から導いた内容となりましたが、

• 制約項の係数を調整するにはPyQUBOのプレースホルダーをうまく活用する
• チェーン強度は強くするべきだが、QUBO内の値を意識しながら強くしすぎないように調整する
• サンプリング回数は多ければ多いほどいいが、時間・金額の問題や上限が10000回であることに注意する

といった点が重要となってくるかと思います。

試行錯誤の結果このような記事となりましたが、D-Waveにはまだまだ触ったことの無いパラメータがたくさんあります。
D-Waveのドキュメントも読みながら、一つ一つどんな意味があるのか理解していくのも面白いかもしれませんね。
D-Waveの日本法人によって日本語化ドキュメントも公開されているので、こちらも合わせてご確認いただくとより理解が深まると思います。
（@YuichiroMinato さん、日本語化ドキュメントのご紹介ありがとうございます！）

なお、量子コンピュータ関係の他の記事は、こちらのページで一覧にしています。
よろしければこちらの記事も参照いただければと思います！