ユーティリティ規模のQAOA

オリビア・レーンズによるユーティリティ・スケールのQAOAに関するビデオを見るか、 YouTube の別ウィンドウでビデオを開く

レッスン概要：

このコースではこれまで、量子コンピューターで実用規模の問題を解決するために必要なフレームワークとツールの基礎をしっかりと学んでいただけたと思います。さて、いよいよこれらのツールが実際に使われるのを見ることになる。

このレッスンでは、グラフ理論における有名な問題である「最大分割問題」について、実用規模の例を用いて具体的に取り上げます。この問題は、あるグラフを2つに分割する最適な方法に関するものです。まずは、量子コンピュータがこの問題の解決にどのように役立つのかを理解するための直感をつかむため、単純な5ノードのグラフから始め、その後、これを実用規模の問題に適用していきます。

このレッスンでは、この問題を解決するための私たちのアプローチについて、大まかな概要を説明します。ここではコードの解説は行いません。ただし、このレッスンには、量子コンピュータ上で最大カット問題を解くために実行できる実際のコードが掲載されたチュートリアルが付属しています。

問題

注意点として、すべての計算問題が量子コンピューティングに適しているわけではない。「なぜなら、古典的なコンピューターはすでにその問題を完璧に解いているからだ。

私たちが最も期待している3つのユースケースは次のとおりだ：

自然を模倣する
複雑な構造を持つデータの処理
最適化

今日は、3つ目のユースケースである最適化に焦点を当てる。最適化問題では一般的に、与えられた関数に対して取りうる最大値か最小値を探す。古典的な手法では、問題のサイズが大きくなるにつれて、これらの極値を見つける難易度は指数関数的に増大する可能性がある。

今日取り上げる最適化問題は「最大カット」と呼ばれており、これを「量子近似最適化アルゴリズム（QAOA）」と呼ばれるアルゴリズムを用いて解いていきます。

マックスカットとは何ですか？

まず、頂点（またはノード）の集合からなるグラフから始めます。これらの頂点の一部は辺で結ばれています。この問題では、グラフのノードを、それらを結ぶ辺を「切断」することで、2つの部分集合に分割することが求められています。この方法で切断される辺の数を最大化する分割を見つけたいのです。これが「最大切断（max-cut）」という名称の由来です

例えば、上の図は5ノードのグラフを示しており、右側には最大切断の解が示されています。これは5つの辺を横切りますが、このグラフではこれが最善の解です。

5つの頂点からなるグラフはとても小さいので、頭の中で計算したり、紙にいくつか切り分け方を書き出してみたりして、最大切断を導き出すのはそれほど難しくありません。しかし、ご想像の通り、頂点の数が多くなるにつれて問題はますます難しくなります。その理由の一つは、検討すべき切断の組み合わせの数が、ノードの数に比例して指数関数的に増加するためです。そしてある段階に至ると、既知の古典的アルゴリズムを用いても、スーパーコンピュータでさえこれを処理するのが困難になる。

こうした大規模で複雑なグラフに対して最大カット問題を解く方法を模索しています。なぜなら、この問題には、金融分野における不正検知、グラフのクラスタリング、ネットワーク設計、ソーシャルメディア分析など、多くの実用的な応用分野があるからです。 Max-cutは、より大規模な問題に対する特定のアプローチにおいて、しばしば部分問題として扱われる。つまり、私たちが単純に考えているよりも、はるかに一般的なことなのです。

解決策

それでは、量子コンピュータ上で最大カット問題を解くために私たちが用いる手法について、順を追って説明していきます。ここでは、5つのノードからなる単純なグラフを使って説明します。 Pythonノートブックのチュートリアルを見ながら進めてください。この簡単な例の次に、このチュートリアルでは、実用規模の事例を用いてこの問題について詳しく解説します。

最初のステップは、ノードの数と2つのノードを結ぶエッジを定義してグラフを作成することである。チュートリアルで示したように、 rustworkx というパッケージをインポートすることでこれを行うことができる。結果は次のようなグラフになる：

Qiskitのパターンフレームワークを使用して、量子コンピュータ上でこのグラフの最大切断解を求めます。

マップ

量子コンピューターに問題をマッピングする必要がある。そのためにまず、グラフのカット数を最大化することは数学的に次のように書けることに注意しよう：

\max\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {x_i + x_j - 2x_ix_j}

ここで、 $i$ と $j$ はグラフのノードであり、 $x_i$ と $x_j$ は、各ノードがどちらのパーティション側にあるかによって、0か1のどちらかになる（1つのグループには「0」、1つのグループには「1」というラベルが貼られる）。 $x_i$ と $x_j$ が仕切りの同じ側にある場合、和の式はゼロに等しい。両者が反対側にあり、両者の間に切れ目がある場合、式は1に等しくなる。つまり、カット数を最大化すれば、合計を最大化できる。

これを逆にして、それぞれの値にマイナス1を掛けて最小値を探すこともできる。

\min\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {2x_ix_j - x_i - x_j}

さて、地図の準備は整った。今描いたようなグラフから量子回路に至るまでを考えるのは、ちょっと大変かもしれない。でも、一歩ずつ前進していこう。

忘れないでください。私たちはQAOAを使って最大カット問題を解こうとしています。 QAOA法においては、最終的には、ハイブリッドアルゴリズムのコスト関数を表現するために用いられる演算子（言い換えればハミルトニアン）と、問題の可能な解を表現するために用いるパラメータ化された回路（アンザッツ）を得ることが目的である。

クボ

これらの解の候補からサンプリングし、コスト関数を用いて評価することができる。そのために、組合せ最適化問題を符号化する便利な方法である2次制約なし2値最適化表記法（略してQUBO）を含む、一連の数学的再定式化を利用する。 QUBOで私たちは見つけたい：

\min\limits_{x\in\{0,1\}^n} x^TQx

ここで、 $Q$ は実数の $n\times n$ 行列であり、 $n$ はグラフのノード数（ここでは5）に対応する。

QAOAを適用するためには、問題をハミルトニアンとして定式化する必要がある。ハミルトニアンとは、システムの全エネルギーを表す関数または行列である。具体的には、基底状態が関数の最小値に対応するという性質を持つコスト関数のハミルトニアンを作りたい。そこで、最適化問題を解決するために、 $H$ の基底状態を量子コンピューター上で準備してみることにする。そして、この状態からサンプリングすれば、高い確率で $\min 𝑓(𝑥)$ 。

ハミルトン量へのマッピング

というのも、QUBO問題は、物理学で最も有名でどこにでもあるハミルトニアンのひとつであるイジング・ハミルトニアンと非常に密接に関係しており、実際に計算上も等価だからである。

QUBO問題をイジング・ハミルトニアンとして記述するために必要なのは、実は簡単な変数の変更だけである：

x_i = \frac{1-z_i}{2}.

ここではすべての手順を説明しないが、添付のノートに説明がある。結局、QUBO式の最小化はこの式の最小化と同じである：

\min_{x\in\{0,1\}^n} x^TQx\Longleftrightarrow \min_{z\in\{-1,1\}^n}z^TQz + b^Tz

ここで式の最小値は基底状態を表し、 Z はパウリZ演算子、 $b$ は実数スカラー係数である：

H_C=\sum_{ij}Q_{ij}Z_iZ_j + \sum_i b_i Z_i

ハミルトニアンが得られたので、それを2ローカルのパウリZZ演算子で書き換える必要がある。最終的には6つのオブジェクト、つまりパウリ文字列ができ、それぞれがグラフの6つのエッジに対応する。文字列の5つの要素はそれぞれ、ノードに対する操作を表している。ノードが特定のエッジに接続されていない場合はID、接続されている場合はパウリZ演算子である。 Qiskitでは、量子ビットを表すビット列は後ろ向きに索引付けされる。例えば、ノード 0 とノード 1 の間のエッジは IIIZZ と符号化され、ノード 2 とノード 4 の間のエッジは ZIZII と符号化される。

量子回路を構築する

ハミルトニアンがパウリ作用素で記述できたので、量子回路を構築する準備ができた：

QAOAアルゴリズムは、時間依存ハミルトニアンの基底状態からスタートした場合、ハミルトニアンが十分にゆっくりと進化し、十分な時間があれば、最終状態は最終ハミルトニアンの基底状態になるという断熱定理からヒントを得ている。 QAOAは、この量子断熱アルゴリズムの離散的なトロッター化バージョンと考えることができ、各トロッターステップはQAOAアルゴリズムのレイヤーを表している。つまり、1つの状態から他の状態へ進化するのではなく、各レイヤーにおいて、コスト関数のハミルトニアンと、いわゆる「ミキサー」のハミルトニアンとの間を行ったり来たりすることになる。

QAOAの利点は、量子断熱アルゴリズムよりも高速であることだが、最適解ではなく近似解を返す。レイヤー数が無限大になる極限では、QAOAはQAAのケースに収束するが、もちろんこれは非常に計算コストがかかる。

量子回路を作るために、 $\gamma$ と $\beta$ でパラメータ化された交互作用素を適用し、時間発展の離散化を表現する。

つまり、QAOAサーキットの3つの主要部分は以下の通りだ：

灰色の初期試行状態。これはミキサーの基底状態であり、ハダマードゲートをすべての量子ビットに適用することによって作成される
コスト関数の進化を濃い紫色で示す
ミキサー・ハミルトニアンの下での進化は、まだ取り上げていないが、薄紫色である。

我々の出発ハミルトニアンはミキサーと呼ばれるが、それはその基底状態が、対象となるすべての可能なビット列の重ね合わせであるからである。

ミキサーのハミルトニアンは、グラフの各ノードに対するパウリ-X演算の単純な和である。 Qiskitでは、お望みであれば別のカスタムミキサー演算子を使用することができますが、ここでは標準のものを使用します。つまり、Qiskitを使えば、ミキサー・ハミルトニアンと開始状態を考えるのが簡単になり、多くの作業が不要になることがお分かりいただけるでしょう。私たちがしなければならなかった唯一の仕事は、コスト関数を見つけることだった。

これらの演算子の各反復をレイヤーと呼ぶ。これらの層は、先に述べたように、システムの時間発展の離散化と見ることができる。交互パターンはトロッター分解に由来し、非共約行列の指数関数を近似する。一般的に、レイヤーやステップの数が多ければ多いほど、QAAのような連続的な時間進化に近づくので、理論的にはより正確な結果が得られる。しかし、この例では、まず1つのレイヤーからサンプリングする。 $\gamma$ コスト関数のハミルトニアンとミキサーはどちらもパラメータ化されている。 $\beta.$

最適化

今作った回路はとてもシンプルに見えるし、直感的な理解を構築するのに役立つが、量子チップはQAOAゲートが何であるかを理解していないことを忘れないでほしい。これを、ハードウェア上で直接実行できる一連の1量子ビットと2量子ビットの "ネイティブ "ゲートに変える必要がある。ネイティブ・ゲートとは、量子ビットに直接作用するゲートである。このような回路は、バックエンドの命令セット・アーキテクチャ（ISA）で書かれていると言われている。

Qiskitライブラリは、幅広い回路変換に対応する一連のトランスピレーション・パスを提供します。回路が我々の目的に最適化されていることを確認したい。

前回のレッスンで、移籍のプロセスにはいくつかの段階があることを思い出してほしい：

回路内の量子ビット（つまり決定変数）とデバイス上の物理量子ビットの初期マッピング。
量子回路の命令を、バックエンドが理解できるハードウェア・ネイティブ命令にアンロールする。
相互作用する回路内のあらゆる量子ビットを、互いに隣接する物理量子ビットにルーティングする。

また、いつものように、この件に関する詳細はドキュメントに記載されている。

しかし、トランスパイルする前に、どのバックエンドで回路を走らせるかを選択する必要がある。トランスパイラーが最適化するプロセッサーが異なるからだ。これは、自動トランスパイラを使用することが重要であるもう1つの理由である。手作業で回路を最適化する時間のかかるプロセスを経て、実際には特性の異なる別のプロセッサで回路を実行したいことに気づいたくないだろう。

選択したバックエンドをトランスパイラ関数に通し、最適化レベルを指定する。チュートリアルでは、最も高く徹底的なレベルであるレベル3を選択する。

これで、ハードウェア上で実行可能なトランスパイルド回路が完成した！

実行

ここまでは、パラメータgammaとbetaだけを残して回路をトランスパイルしたが、これらのパラメータを指定しなければ、実際に回路を動かすことはできない。 QAOAワークフローでは、最適なQAOAパラメータは反復最適化ループの中で見つけられます。そこでは、一連の回路評価を実行し、次に古典的なオプティマイザを使用して最適なǽとǾパラメータを見つけます。しかし、どこかから始める必要があるので、 $\gamma=\pi/2$ 。 $\beta=\pi.$

実行モード

これでサーキットを走る準備はほぼ整った！しかしその前に、実行モードと呼ばれるさまざまな方法でジョブを送信できることに注意することが重要だ。

実行モード：コンテキストマネージャーを使用せずに、Estimator プリミティブまたは Sampler プリミティブに対して単一のプリミティブリクエストを実行します。回路と入力は、プリミティブ統合ブロック（PUB）としてパッケージ化され、量子コンピュータ上で実行タスクとして送信される。
バッチモード：独立したジョブの束からなる実験を効率的に実行するためのマルチジョブマネージャ。バッチモードを使用して複数のプリミティブジョブを同時に送信する
セッションモード：複数ジョブのワークロードを実行するための専用ウィンドウ。これにより、ユーザーはより予測可能な方法で変分アルゴリズムを実験することができ、スタックの並列性を利用して複数の実験を同時に実行することもできる。専用アクセスが必要な反復作業負荷や実験には、セッションを使用する。例については、セッション内でのジョブの実行を参照してください。

QAOA実験では、最適なパラメータ値を見つけるために、異なるパラメータ値で回路を何度もサンプリングする必要があるため、セッションを利用できるのであれば、それを進めるのが良い選択だろう。

最適化問題に戻ろう。ガンマとベータについて、大まかな最初の推測値よりももっと良い値を見つける必要がある。 scipy のオプティマイザ COBYLA に、コスト関数と初期推測値を入力します。

ここでは、繰り返しのコスト関数の値を見ることができる。最初は少し不安定で上下するが、やがて低い値に落ち着く。ここでは、scipyが見つけたコスト関数の最小評価に対応する値を使用する。

パラメータのより適切な値を見出すことでコスト関数を低減できたので、γとβについて求めた新しい値を用いて回路を実行します。ここでは私が使用している具体的な値を記載しましたが、実際に試してみる際や、同じチュートリアルノートブックを再実行する際にも、これらの値は多少異なる場合があることを覚えておいてください。それでは、これらの値を用いて最適化された回路を実行し、最大カット問題の解候補を求めます。

後処理の段階では、データを分析し、量子アルゴリズムが正しい解を見つけたかどうかを確認するために、これらの結果を表示する。

後処理

では、データのヒストグラムをプロットして、最終解を見てみよう：

ビット列は、各ノードがカットによってどのように2つのグループ（"0 "と "1 "のラベル付き）に分割されたかを表している。エッジカットの最大値を与える4つの解があるはずだ。この4つは紫色で示されている。 4つの解が他のどれよりも確率が高いことはすぐにわかるだろう。最も確率の高いビット列の解は0,1,0,1,1である。 (プロットのビット列では、量子ビットの順序が逆になっていることを忘れないでください！）

このプロットから、最も可能性の高いビット列を取り出し、5つのエッジを通るカットを持つ分割グラフとして表現することができる：

つまり、これはまさに最大カット解ですね。でも、それだけじゃない！このグラフは対称であるため、正解は複数存在します。ノード0と3をカット内に含める代わりに、ノード2と4を含めることも可能です。ご覧の通り、私がやったのは、切り取った部分を回転させてこれらの新しい点を含めることだけでした。切断された辺の数は依然として5本である。最大カット解は4つあることが判明した。というのも、先に挙げた2つの解にはそれぞれ「対となる」解が存在し、そこでは紫のノードが灰色になり、灰色のノードが紫になるからだ。つまり、カット自体は変わらないが、各ノードが実質的に分割の反対側へと入れ替わるのである。

ヒストグラムと、最も可能性の高い4つの解について、もう一度見てみましょう。理想を言えば、それらは4つの真の最大カット解のそれぞれであるべきだ。問題は、アルゴリズムが実際には、4つ目にして最後の解答を、最も可能性の高い4つの解答の一つとして特定できなかったという点にある。それは5番目に可能性が高かった。アルゴリズムが特定した4番目の解は間違っています。図に描いてみればわかるように、この解には切り込みが4つしかありません。

しかし、これは近似的なアルゴリズムであることを忘れないでほしい。無謬ではないし、常に100％正しいわけでもない。その解決策を正当にチェックするために、あなた自身の知識と理解を活用する必要がある。

このエラーはいくつかの場所で発生する可能性がある：

アルゴリズム自体の近似性と、私が採用したレイヤー数の少なさが原因かもしれない。
有限のサンプリングエラーかもしれないが、これは実験のショット数を増やせば減らせるだろう。
第4の実数解は1ビットしかずれていないので、読み出しエラーである可能性もある。

このようなエラー分析こそが、量子コンピューティングの実践者になるために必要なことなのだ。ハードウェアの性能を理解し、それがある種のエラーにどのように影響し、どのように修正するかを理解する必要がある。

とはいえ、32通りのビット列があり、4つの正解が上位5つの有力候補に含まれていたことを忘れてはならない。しかも、これを見つけるのに使ったのはたった2層だけでした。一般的に、毎回最適なマックスカットを見つける確率を高めたいのであれば、層の深さを増やすことができます。これにはいくつかの細かい点がありますが、それについては後のレッスンで説明します。

ユーティリティ規模で

量子コンピュータで小規模な最大切断問題の解法プロセスを体験したところで、次はより大規模な問題に挑戦してみてください。リンク先のチュートリアルに従って、125ノードのグラフで何通りの切り分けができるか確認してみてください。

このページは役に立ちましたか？

バグや誤字の報告、またはコンテンツの要求はGitHubで行ってください。