MaxCut圧縮と復号
12頂点のグラフと符号を選択してください。 同じ量子ブロックへ入れる頂点を変えると、必要量子ビット数、理想的な最大固有空間、期待cut値、最適解の復号確率がどのように変わるかを確認できます。
このデモは生成AIを活用して制作しました。
MaxCutモデルを準備しています…
ハミルトニアンと復号の規約
cut割当をs\in\{-1,1\}^{12}とし、cutを横切る辺の本数を\operatorname{Cut}(s)とします。 各符号は、古典解sを同時に出力するPOVM \{M_s\}を定めます。 アプリが使う復号整合ハミルトニアンは、次の演算子です。
H_{\mathcal D}[\operatorname{Cut}] =\sum_s \operatorname{Cut}(s)M_s.
アプリはH_{\mathcal D}を最大化します。 基底状態を求める規約では、-H_{\mathcal D}を最小化することと同じです。
同じブロックに入った二頂点を辺が結ぶ場合も、この式はPOVMによる正しい引き戻しを使います。 この項を一ビット観測量の積へ機械的に置き換えることはしません。 任意の状態\rhoに対して、
\operatorname{Tr}(H_{\mathcal D}\rho) =\sum_s \operatorname{Cut}(s)\operatorname{Tr}(M_s\rho) =\mathbb E_\rho[\operatorname{Cut}]
が成り立ちます。 したがって、アプリが表示する最大固有値は、最大固有空間上の理想状態を一度同時復号したときの期待cut値でもあります。
状態と最適解確率
最大固有値が縮退している場合、固有ベクトルを一つ選ぶと、復号確率が任意の基底選択に依存します。 アプリは、最大固有空間上の基底に依存しない等重み混合状態
\rho_\star=\frac{\Pi_{\max}}{\operatorname{Tr}\Pi_{\max}}
を使います。 古典的な2^{12}=4096個のcutを全列挙してすべての最適解を求めた後、アプリは
p_{\mathrm{opt}} =\sum_{s:\,\operatorname{Cut}(s)=\mathrm{OPT}} \operatorname{Tr}(M_s\rho_\star)
を表示します。 これは、一回の同時復号が相補的なcutを含むいずれかの最適割当を返す確率です。
| 符号 | ブロック数 | 量子ビット数 | Hilbert空間の次元 |
|---|---|---|---|
| (1,1) | 12 | 12 | 4096 |
| (2,1) | 6 | 6 | 64 |
| (3,1) | 4 | 4 | 16 |
| (3,2) | 4 | 8 | 256 |
このアプリで使う同時POVMでは、(2,1)符号と(3,1)符号の同一ブロック内辺から二体情報が失われます。 一方、(3,2)符号では、同一ブロック内辺にも非零の二体信号が残ります。 グラフは同一ブロック内辺を破線で描き、頂点の配置を変える意味を可視化します。
アプリが扱う範囲
(1,1)は、QAOAでも使われる通常の対角なMaxCutコストハミルトニアンに対応する非圧縮の基準です。 ただし、アプリは理想的な最大固有空間を直接計算します。 有限深さQAOAの角度最適化を再現するものでも、有限深さの回路が必ず最大固有空間へ到達すると主張するものでもありません。 すべての計算はノイズのない数値計算であり、ブラウザ内だけで実行します。
復号からハミルトニアンを定める規約は、Decoder-Consistent Hamiltonians for POVM-Based Quantum Relaxationsに基づきます。 1量子ビットQRAO符号はApproximate Solutions of Combinatorial Problems via Quantum Relaxationsに、(3,2)符号はQuantum-Relaxation Based Optimization Algorithms: Theoretical Extensionsに基づきます。