量子アニーリングは、このサイトで扱う他のあらゆるものとは異なる量子コンピューティングのモデルです。回路もゲートもなく、ハードウェア上でGroverやShorのアルゴリズムが動くこともありません。アニーラーが解くのは最適化というただ一種類の問題であり、問題をハードウェアの物理現象に直接エンコードし、システムを低エネルギーな解へと落ち着かせることで答えを得ます。
このガイドでは、QAOAチュートリアルと同じMax-Cut問題をアニーリング問題として定式化し、D-WaveのOcean SDKを使って無料で解き、おもちゃのような例から実機ハードウェアへ移行する際にほぼ誰もがはまる実践的な落とし穴を扱います。
物理的な発想
最適化問題は量子ビットの系にマッピングされ、その系のエネルギーが最も低い配置、つまり基底状態が最良の解に対応するようにします。量子ビットは準備しやすい状態から出発し、問題のエネルギー地形に向かってゆっくりと発展していきます。これを可能にしているのが断熱定理です。基底状態から出発した量子系は、系のエネルギーギャップに対して発展が十分にゆっくりであれば、発展の過程を通じてずっと基底状態にとどまり続けます。最後に量子ビットを読み出せば、低エネルギーな、うまくいけば最適な解が得られます。
これはゲート方式のコンピューティングとは根本的に異なります。ゲート方式のQPUは、あなたが指定した任意の操作列を実行します。アニーラーが実行するのは、最小値に向かって物理的に緩和していくという、たった一つの固定されたプロセスであり、あなたが唯一コントロールできるのは、問題をこのエネルギー地形へどうエンコードするかだけです。
Max-CutをQUBOとして定式化する
アニーラーが解くのは、QUBO（Quadratic Unconstrained Binary Optimization、制約なし二次二値最適化）として表現された問題です。線形項とペアごとの二次項のみからなり、それより高次の相互作用を含まない、二値変数 x_i ∈ {0, 1} の式を最小化します。
Max-Cutの場合、各エッジ (i, j) は目的関数に 2·x_i·x_j − x_i − x_j を寄与します。4通りのケースを確認してみましょう。x_i と x_j が一致する場合（両方とも同じ側にある場合）、この項は0です。両者が異なる場合（そのエッジが切断されている場合）、この項は−1になります。したがって、すべてのエッジにわたる合計を最小化することは、切断されたエッジの数を最大化することと同じであり、これはまさにMax-Cutの目的関数を最小化問題として書き換えたものにほかなりません。
QAOAガイドと同じ4ノードの巡回グラフを使うと：
import dimod
from neal import SimulatedAnnealingSampler
edges = [(0, 1), (1, 2), (2, 3), (3, 0)]
Q = {}
for i, j in edges:
Q[(i, i)] = Q.get((i, i), 0) - 1
Q[(j, j)] = Q.get((j, j), 0) - 1
Q[(i, j)] = Q.get((i, j), 0) + 2
bqm = dimod.BinaryQuadraticModel.from_qubo(Q)
このグラフではすべてのエッジを同時に切断できます。グラフが2部グラフだからです（{0, 2} 対 {1, 3}）。そのため基底状態のエネルギーはちょうど−4になり、エッジ1本につき−1の寄与という計算になります。この数値はQUBOの構成そのものから直接導かれるものであり、まだ何かを実行した結果ではありません。そして、これこそが以下のサンプラーが到達しようとしている目標です。
シミュレーテッドアニーリングで無料に解く
D-WaveのOcean SDKには neal が同梱されており、これは自分のマシン上だけで完結する古典的なシミュレーテッドアニーリングサンプラーです。QPUのアカウントも、待ち行列も、コストも一切必要ありません。これはまた、実機に触れる前にアニーリング問題を開発するための標準的な最初のステップでもあり、このサイトの他の場所でゲート方式の回路に対して AerSimulator が果たしているのと同じ役割を担っています。
sampler = SimulatedAnnealingSampler()
sampleset = sampler.sample(bqm, num_reads=1000)
best = sampleset.first
print(best.sample, best.energy)
num_reads=1000 は、アニーリングのプロセスを1,000回独立に実行し、そのすべての結果を保持します。シミュレーテッドアニーリングも量子アニーリングも、どちらもヒューリスティックな手法だからです。1回の実行だけでは基底状態に到達する保証はないため、複数回の読み取りをまとめて行い、その中で最もエネルギーの低い結果を採用するのが標準的なやり方です。このグラフの場合、best.energy は−4に落ち着くはずで、best.sample は2通りの等価な二分割のどちらか、つまり {0, 2} が片側で {1, 3} がもう片側、あるいはその逆を読み出します。どちらも正しい結果です。Max-Cutには、どちらの側が「先」であるかという概念がそもそも存在しないため、これは問題そのものに内在する本物の対称性であり、サンプラーの不具合ではありません。
よくある間違い：埋め込みを無視してしまう
ここまでの内容はすべて、接続性に制限のない古典的なシミュレーテッドアニーラー上で動いており、任意の変数がほかの任意の変数と自由に相互作用できます。実機のD-Waveハードウェアはこれとは事情が異なります。物理的な量子ビットは固定された疎なトポロジー上に配置されており（世代によってPegasusまたはZephyr）、量子ビットのペアの大半はそもそも直接配線されていません。
変数 i が変数 j と相互作用する必要があるにもかかわらず、その接続を提供する物理的な量子ビットのペアが存在しない問題を配置するために、Oceanのマイナー埋め込みというステップは、複数の物理量子ビットを鎖状につなぎ、それらをまとめて1つの論理変数として機能させます。これは自動的に行われ、dwave-system の EmbeddingComposite がこのプロセスを担いますが、無料ではありません。鎖には追加の量子ビットが必要ですし、鎖が時に「切れる」こともあります。本来は一致するはずの物理量子ビットがアニーリング後に食い違ってしまい、その変数の読み取り結果を気づかないうちに損なってしまうのです。問題が大きくなったり密になったりするほど、必要な鎖は長くなり、切れる頻度も増えます。そして十分に密な問題は、あるチップ上ではついに埋め込むことすらできなくなります。これは、うまく動いていたシミュレーテッドアニーリングの問題を初めて実機に移す人のほとんどが経験する、最もよくある驚きです。アルゴリズムが悪くなったのではなく、チップの物理的な接続性がボトルネックになったのです。
アニーリングにできないこと
アニーラーはGroverの探索を実行できませんし、Shorの素因数分解も実行できず、そもそも「回路」という一般的な概念自体を持ちません。その量子ビットは、ゲート方式の量子ビットと直接比較できるものではありません。D-Waveのシステムは5,000量子ビットを超え、どのゲート方式QPUよりもはるかに多いですが、この数字が示しているのはあくまでQUBO/イジング型の問題クラスに特化した最適化能力であって、汎用的な計算能力ではありません。実際の問題において、アニーリングが最良の古典的な最適化ヒューリスティックに対して本当に速度面で優位性を持つかどうかは、文献上でも真剣に議論が分かれるところであり、具体的な問題の構造に大きく左右されるようです。これはデフォルトで前提としてよいことではありません。
実機のD-Waveハードウェアで実行する
サンプラーを差し替えるだけで、残りのコードはそのままです：
from dwave.system import DWaveSampler, EmbeddingComposite
sampler = EmbeddingComposite(DWaveSampler())
sampleset = sampler.sample(bqm, num_reads=1000)
D-WaveのLeapクラウドサービスは、まさにこの種の実験のために、毎月無料のQPU利用時間枠を提供しています。これは、ゲート方式ハードウェアにおけるIBM Quantumの無料枠に相当する、アニーリング版の存在だと言えます。EmbeddingComposite はマイナー埋め込みのステップを自動的に処理しますが、ちょっとしたおもちゃの問題を超える規模の結果を信頼する前には、返ってきた sampleset.info で鎖の切断に関する統計を確認してください。
次のステップ
- QAOAチュートリアル: 同じMax-Cut問題へのゲート方式でのアプローチ
- 量子アニーリングの用語集エントリ: この概念の要約
- D-Waveのデュアルレール消去量子ビットゲート: アニーリング路線と並行して進むD-Waveのゲート方式ハードウェアへの動き
- 用語集: QAOA、量子優位性、その他の関連用語