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に基づきます。