少ない量子ビットでMaxCut

量子ビット数を選び、測定結果を試しながら、グラフの最適な分け方が出る確率を比べるデモ。

グラフの頂点を二つのグループに分けて、異なるグループを結ぶ辺をできるだけ多くする問題を考えます。 その辺が1本につき1点になり、最高得点の分け方が MaxCutの最適解 です。

まず12量子ビットで試してから、量子ビット数を減らしてみてください。 「1回試す」 で一つの結果を、「100回試す」 で最適解の出やすさを確認できます。

このデモは生成AIを活用して制作しました。

デモを準備しています…

画面の見方

青とオレンジの頂点が二つのグループです。 強調された辺が得点になります。 グラフの横の得点は今回の結果で、最高得点はグラフごとに決まっています。

大きな百分率は、1回の測定で最適解を得る確率です。 その下の試行回数は、実際に試して最適解が何回出たかを示します。 少ない試行では、偶然によって割合が大きく変わることがあります。

量子ビットを減らすと資源を節約できますが、最適解が出にくくなる場合があります。 その確率は、グラフと符号化の方法によって変わります。 このデモは、理想的な量子状態を計算したうえで、その測定結果を抽選して表示します。

12個の頂点を、それぞれ1個の古典ビットで表します。 四つの選択肢は、量子ランダムアクセス符号(QRAC)を使った次の符号化に対応します。

量子ビット数 符号 頂点のまとめ方
12 (1,1) 1頂点に1量子ビット
6 (2,1) 2頂点に1量子ビット
4 (3,1) 3頂点に1量子ビット
8 (3,2) 3頂点に2量子ビット

アプリは、辺でつながった頂点ができるだけ別の符号ブロックに入るよう、自動で頂点をまとめます。 測定を繰り返している間、この組合せは固定します。 頂点のまとめ方を変えると、表示する確率も変わる場合があります。

分け方sに対し、異なるグループを結ぶ辺の本数を\operatorname{Cut}(s)とします。 すべての頂点のビットを同時に読み出す測定\{M_s\}から、次のハミルトニアンを作ります。

H_{\mathcal D}=\sum_s \operatorname{Cut}(s)M_s.

この演算子は、測定後に得る点数の期待値を表します。 アプリは、その期待値が最大になる理想状態を計算します。 最大固有値を持つ状態が複数ある場合は、その空間上の等重み混合状態を使います。

\rho_\star=\frac{\Pi_{\max}}{\operatorname{Tr}\Pi_{\max}}.

この選び方により、任意の固有ベクトルを一つ選ぶことによる偏りを避けます。 画面の「最適解が出る確率」は、

p_{\mathrm{opt}} =\sum_{s:\,\operatorname{Cut}(s)=\mathrm{OPT}} \operatorname{Tr}(M_s\rho_\star)

です。 二つのグループの名前を入れ替えた分け方も含め、すべての最適解の確率を足しています。 最高得点は、2^{12}=4096通りの古典的な分け方を全列挙して求めます。

12量子ビットの基準が100%なのは、理想的な最適状態を用意できたと仮定しているためです。 その状態をどう用意するかは別の課題であり、このデモが扱うのは状態を用意した後の測定です。 各試行は同じ確率分布から独立に抽選し、実機のノイズは加えていません。

計算の規約は、Decoder-Consistent Hamiltonians for POVM-Based Quantum Relaxationsに基づきます。 1量子ビットの符号はApproximate Solutions of Combinatorial Problems via Quantum Relaxationsに、(3,2)符号はQuantum-Relaxation Based Optimization Algorithms: Theoretical Extensionsに基づきます。