量子ランダムアクセス最適化 (QRAO) の背景：量子緩和、量子ランダムアクセス符号、丸めスキーム#

この資料では、量子ランダムアクセス最適化の背後にある概念について、より深く考察します。

緩和（リラクゼーション）#

バイナリ変数 \(m_i \in \{-1,1\}\) に対して定義されたバイナリ最適化問題を考えてみましょう。\(0/1\) 変数の代わりに \(\pm 1\) 変数を使用するという選択は重要ではありませんが、この問題を量子観測量の観点から再キャストし始めるときに、表記の点で便利です。私たちは主に 2 次の制約なし 2 値最適化 (QUBO) 問題に興味を持ちますが、このドキュメントのアイデアは 2 次以上の項を含む問題にも簡単に拡張でき、非 2 値変数または制約付き変数の問題は多くの場合 QUBO として再キャストできます。 (この変換にはある程度のオーバーヘッドが発生します)。

数理最適化において、緩和(リラクゼーション) とは、ある難問を取り上げ、その問題の類似バージョンにマッピングする戦略であり、(通常は) より簡単に解くことができます。ここでの核となる考え方は、有用な緩和の場合、緩和された問題の解が元の問題についての情報を与え、より良い解を発見することを可能にするということです。緩和の例としては、離散最適化問題を連続変数で最適化するという単純なものがあります。緩和された問題の解が得られると、ソルバーは連続値の緩和された解から離散解を抽出する戦略を見つけなければなりません。緩和解を元の問題の許容解集合にマッピングするこのプロセスは、しばしば 丸め(rounding) と呼ばれます。

緩和と丸めの具体的な例としては、 MaxCutのGoemans-Williamsonアルゴリズムを参照してください。

一般性を失うことなく、このドキュメントの残りの部分では、グラフ \(G = (V,E)\) 上で定義された MaxCut 目的関数を考えます。我々の目的は、頂点 \(V\) を2つの集合 (\(+1\) and \(-1\)) に分割し、両方の集合を結ぶ辺の数を最大にするような分割を見つけることです。より具体的には、 \(v_i \in V\) に2値変数 \(m_i \in \{-1, 1\}\) を代入し、変数代入の cut を次のように定義します：

\[\text{cut}(m) = \sum_{ij; e_{ij} \in E} \frac{1}{2}(1-m_i m_j)\]

量子緩和#

我々の目的は、MaxCut目的関数の緩和を定義することです。これは、目的関数の2値変数を単一量子ビットパウリ観測量の空間にマッピングし、 cut(\(m\)) への実行可能な入力の集合を単一量子ビット量子積状態の空間に埋め込むことによって行います。この埋め込みを \(F\) とします：

\[F: \{-1,1\}^{M} \mapsto \mathcal{D}(\mathbb{C}^{2^n}),\]

\[\text{cut}(m) \mapsto \text{Tr}\big(H\cdot F(m)\big),\]

ここで、 \(M = |V|\) であり、 \(H\) は目的関数を符号化した量子ハミルトニアンです。

これが我々の問題の有効な緩和であるためには、次のようでなければなりません：

\[\text{cut}(m) \geq \text{Tr}\big(H\cdot F(m)\big)\qquad \forall m \in \{-1,1\}^M.\]

これが真であることを保証するために、我々は緩和が目的関数と 交換する というより強い条件を強制します。言い換えると、 cut(\(m\)) は単に上限を定めるのではなく、 \(m \in \{-1,1\}^M\) に対する緩和された目的関数と等しくなります。この詳細は、量子緩和を明示的に定義するときにさらに重要になります。

簡単な量子緩和#

単一量子ビット量子ランダムアクセス符号（QRAC）に基づく完全な量子緩和スキームを説明する前に、まず、量子緩和と丸め込みの言語で議論された、ユーザーにとって馴染み深い量子最適化について説明することが役に立つかもしれません。

埋め込みを考慮して、

\[F^{(1)}: m \in \{-1,1\}^M \mapsto \{|0\rangle,|1\rangle\}^{\otimes M},\]

\[\text{cut}(m) \mapsto \text{Tr}\big(H^{(1)}F^{(1)}(m)\big),\quad H^{(1)} = \sum_{ij; e_{ij} \in E} \frac{1}{2}(1-Z_i Z_j),\]

ここで、 \(Z_i\) は \(i\)’ 番目の量子ビットで定義される単一量子ビットのPauli-Z観測量と、他のすべての量子ビットの恒等項を表します。この変換が我々の問題の有効な緩和であることを納得するのは十分です。特に：

\[\text{cut}(m) = \text{Tr}\big(H^{(1)}F^{(1)}(m)\big) \quad \forall m \in \{-1,1\}^M\]

この種の埋め込みは、現在、多くの QAOAやVQEベースのアプローチを含む、多くの近未来量子最適化アルゴリズムで使用されています。私たちの問題の緩和版では \(\{|0\rangle,|1\rangle\}^{\otimes M}\) の形式の入力に対する目的関数 cut(\(m\)) を正確に再現できますが、そのような状態の連続的な重ね合わせを使って \(H^{(1)}\) を自由に評価することもできます。これは、連続値を用いて目的関数を最適化するような最適化問題を古典的に緩和する方法と類似しています。

重要なことは、 丸められた 緩和解を元の問題の許容解の集合に戻す実用的な方法がある場合にのみ、緩和は有用であるということです。この特殊な量子緩和では、緩和された解の各量子ビットを \(Z\)- 基底で測定することで、丸めを行います。測定は、任意の量子状態を計算基底状態の集合に投影し、その結果、 \(F^{(1)}\) のイメージに投影します。

量子ランダムアクセスコード（QRAC）による量子緩和#

量子ランダムアクセスコードは、 1983年に Stephen Wiesner によって初めて概説され[2] 、通信複雑性理論の文脈で使用されました。我々は、QRACを当初考えられていたように使うのではなく、量子緩和を定義するためにQRACを利用します。このため、RACやQRACの完全な紹介はしませんが、興味のある読者には、より詳しい情報を探すことを推奨します。

\((1,1,1)\) , \((2,1,p)\) , :math:`(3,1,p)』の量子ランダムアクセスコード#

\((k,1,p)\)-QRAC とは、1量子ビットの状態に \(k\) 個の古典ビットを埋め込むスキームで、この状態のコピーが1つあれば、何らかの測定を行うことで \(k\) 個のビットのどれかを確率 \(p\) で復元することができます。前節で説明した単純な量子緩和は、自明な \((1,1,1)\)-QRAC の一例です。便宜上、 \((2,1,0.854)\) と \((3,1,0.789)\) のQRACをそれぞれ \((2,1,p)\) と \((3,1,p)\) と書きます。 \((4, 1, p)\)-QRAC \((p > 1/2)\) は`不可能であることが証明されています。[3]<https://iopscience.iop.org/article/10.1088/1367-2630/8/8/129>`__

上の単純な例を一般化すると、単一量子ビットの状態をパウリ観測量のエルミート基底で分解して書き出すのが役に立つでしょう。

\[\rho = \frac{1}{2}\left(I + aX + bY + cZ \right),\quad |a|^2 + |b|^2 + |c|^2 = 1\]

\((1,1,1), (2,1,p),\) \((3,1,p)\) のQRACにそれぞれ関連する埋め込み \(F^{(1)}\) 、 \(F^{(2)}\) 、 \(F^{(3)}\) は次のように書くことができます：

\[\begin{split}\begin{array}{l|ll} \text{QRAC} & &\text{Embedding into } \rho = \vert \psi(m)\rangle\langle\psi(m)\vert \\ \hline (1,1,1)&F^{(1)}(m): \{-1,1\} &\mapsto\ \vert\psi^{(1)}_m\rangle \langle\psi^{(1)}_m\vert = \frac{1}{2}\Big(I + {m_0}Z \Big) \\ (2,1,p)&F^{(2)}(m): \{-1,1\}^2 &\mapsto\ \vert\psi^{(2)}_m\rangle \langle\psi^{(2)}_m\vert = \frac{1}{2}\left(I + \frac{1}{\sqrt{2}}\big({m_0}X+ {m_1}Z \big)\right) \\ (3,1,p)&F^{(3)}(m): \{-1,1\}^3 &\mapsto\ \vert\psi^{(3)}_m\rangle \langle\psi^{(3)}_m\vert = \frac{1}{2}\left(I + \frac{1}{\sqrt{3}}\big({m_0}X+ {m_1}Y + {m_2}Z\big)\right) \\ \end{array}\end{split}\]

\[\text{Table 1: QRAC states}\]

ビット列 \(m \in \{-1,1\}^M, M > k\) を持つ \((k,1,p)\)-QRAC を使う場合、これらの埋め込みはテンソル積による合成で自然にスケールすることに注意してください。

\[m \in \{-1,1\}^6,\quad F^{(3)}(m) = F^{(3)}(m_0,m_1,m_2)\otimes F^{(3)}(m_3,m_4,m_5)\]

同様に、 \(k \nmid M\) のとき、入力ビット列を適切な数の \(+1\) 値でパディングすればよいです。

\[m \in \{-1,1\}^4,\quad F^{(3)}(m) = F^{(3)}(m_0,m_1,m_2)\otimes F^{(3)}(m_3,+1,+1)\]

符号化されたビットの復元#

QRACの状態が与えられた場合、各ビットの対応する観測値の期待値を推定することで、符号化されたビットの値を復元することができます。QRACの密度に依存する再スケーリング係数があることに注意してください。

\[\begin{split}\begin{array}{l|l|l|l} \text{Embedding} & m_0 & m_1 & m_2\\ \hline \rho = F^{(1)}(m_0) &\text{Tr}\big(\rho Z\big) & & \\ \rho = F^{(2)}(m_0,m_1) &\sqrt{2}\cdot\text{Tr}\big(\rho X\big) &\sqrt{2}\cdot\text{Tr}\big(\rho Z\big) & \\ \rho = F^{(3)}(m_0,m_1,m_2) & \sqrt{3}\cdot\text{Tr}\big(\rho X\big) & \sqrt{3}\cdot\text{Tr}\big(\rho Y\big) & \sqrt{3}\cdot\text{Tr}\big(\rho Z\big) \end{array}\end{split}\]

\[\text{Table 2: Bit recovery from QRAC states}\]

符号化された問題のハミルトニアン#

上記で概説したツールを用いて、MaxCut問題の緩和されたバージョンを符号化するハミルトニアンを明示的に書き出すことができます。これは、各決定変数を、埋め込み \(F\) のもとでその変数に割り当てられているユニークな観測量に置き換えることで行います。

\[\begin{split}\begin{array}{l|ll} \text{QRAC} & \text{Problem Hamiltonian}\\ \hline (1,1,1)&H^{(1)} = \sum_{ij; e_{ij} \in E} \frac{1}{2}(1-Z_i Z_j)\\ (2,1,p)&H^{(2)} = \sum_{ij; e_{ij} \in E} \frac{1}{2}(1-2\cdot P_{[i]} P_{[j]}),\quad P_{[i]} \in \{X,Z\}\\ (3,1,p)&H^{(3)} = \sum_{ij; e_{ij} \in E} \frac{1}{2}(1-3\cdot P_{[i]} P_{[j]}),\quad P_{[i]} \in \{X,Y,Z\}\\ \end{array}\end{split}\]

\[\text{Table 3: Relaxed MaxCut Hamiltonians after QRAC embedding}\]

ここで、 \(P_{[i]}\) は、決定変数 \(i\) に対応する1量子ビットのパウリ観測量を示していることに注意してください。ここでの括弧付きインデックスは、 \((2,1,p)\) と \((3,1,p)\) は、もはや量子ビットと決定変数の間に1:1の関係を持たないため、 \(P_{[i]}\) は必ずしも量子ビット \(i\) に作用しないことを明確にするためです。

量子緩和の交換#

\((2,1,p)\) と \((3,1,p)\) のQRACでは、各量子ビットに複数の決定変数を割り当てていることに注意してください。これは、各決定変数に ユニーク な1量子ビットのパウリ観測変数が割り当てられ、これらのパウリ観測変数のいくつかのサブセットが同じ量子ビット上で定義されることを意味します。このことは、先に説明した可換性を保証する際に問題となる可能性があります。

\((3,1,p)\) -QRACの下では、 \((1 - x_i x_j)\) の形の目的関数の任意の項は、\((1-3\cdot P_{[i]} P_{[j]})\) の形のハミルトニアン項にマップされることに注意してください。 \(P_{[i]}\) と \(P_{[j]}\) の両方が異なる量子ビットに作用する場合、 \(P_{[i]}\cdot P_{[j]} = P_{[i]}\otimes P_{[j]}\) となり、ハミルトニアンのこの項は期待通りの振る舞いをします。

しかし、\(P_{[i]}\) と \(P_{[j]}\) が同じ量子ビットに作用する場合、2つのパウリは直接合成されます。パウリ行列は群を形成し、自己逆行列であることを思い出してください。したがって、2つの異なるパウリの積は群の別の要素をもたらし、それは恒等式にはならないことが推測できます。

実用的には、これは交換関係が崩れて、 \(\text{cut}(m) \not= \text{Tr}\big(H^{(1)}F^{(3)}(m)\big)\) になることを意味します。

符号化と目的関数の交換性を復元するためには、問題のハミルトニアンの形に追加の制約を導入する必要があります。具体的には、入力グラフ \(G\) のエッジを共有する決定変数は、埋め込み \(F\) のもとでは同じ量子ビットに割り当てられないことを保証しなければなりません。

\[\forall e_{ij} \in E,\quad F^{(3)}(\dots,m_i,\dots,m_j,\dots) = F^{(3)}(\dots,m_i,\dots)\otimes F^{(3)}(\dots,m_j,\dots)\]

[1] では、同じ色を持つ頂点がエッジを共有しないようなグラフGのカラーリングを見つけ、同じ色を持つ場合にのみ同じ量子ビットに変数を割り当てることで実現しています。

量子丸めスキーム#

緩和問題 \(\rho_\text{relax}\) に対して得られる最終的な解は \(F\) マッピングの画像内にある可能性は低いため、抽出できるように \(\rho_\text{relax}\) を \(F\) の画像にマッピングする戦略が必要です。私たちの元々の問題に対する解決策です。

[1] では、 \(\rho_\text{relax}\) を \(m \in \{-1,1\}^M\) に丸めるために 2 つの戦略が提案されています。

半決定論的丸め#

解を抽出するための自然な選択は、表 \(2\) の結果を使用し、各変数 \(m_i\) に値を割り当てるためにすべての \(i\) について単純に \(\text{Tr}(P_{[i]}\rho_\text{relax})\) を推定することです。表 \(2\) で説明されている手順は、\(F\) の画像内の状態で使用することを目的としていましたが、現在はそれを任意の入力状態に適用しています。実際の結果として、\((1,1,1)\), \((2,1,p)\) や \((3,1,p)\) QRACに対して期待されるような、{\(\pm 1\)}, {\(\pm \sqrt{2}\)}, または {\(\pm \sqrt{3}\)} に近い値は測定されなくなります。

期待値の符号を返すことでこれを処理し、以下のような丸めスキームを導き出します。

\[\begin{split}m_i = \left\{\begin{array}{rl} +1 & \text{Tr}(P_{[i]}\rho_\text{relax}) > 0 \\ X \sim\{-1,1\} & \text{Tr}(P_{[i]}\rho_\text{relax}) = 0 \\ -1 & \text{Tr}(P_{[i]}\rho_\text{relax}) < 0 \end{array}\right.\end{split}\]

ここで \(X\) は-1か1を等確率で返す確率変数です。

半決定論的丸めは、各 \(\text{Tr}(P_{[i]}\rho_\text{relax})\) の推定に使用されるショットの数に応じて指数関数的に減少する失敗確率で \(F(m)\) から \(m\) を忠実に復元することに注意してください。

マジック状態丸め#

../_images/magic_state_rounding.svg — 図 1 3つの異なる符号化、状態および測定規定、1つの量子ビットへの変数のエンコーディング。(a) 1量子ビットあたり1変数。(b) 1量子ビットあたり2変数。(c) 1量子ビットあたり3変数。 [1] から引用。#

マジック状態丸めでは、各 \(m_i\) を独立して区別しようとするのではなく、直交 QRAC 状態の特定のペア \(\{ F(m), F(\bar m)\}\) を完全に区別する測定基底がランダムに選択されます。ここで、 \(\bar m\) は、\(m\) のすべてのビットが反転されていることを示します。

\(\mathcal{M}\) およびを、状態 \(\rho_\text{relax}\) を入力として受け取り、ランダムに選択されたマジック基底で測定することによってビット列 \(m\) をサンプリングするランダム化された丸め手順とします。

\[\mathcal{M}^{\otimes n}(\rho_\text{relax}) \rightarrow F(m)\]

まず、 \((1,1,1)\)-QRAC の場合、選択する基底は1つだけであり、マジック状態丸め方式は本質的に半決定論的丸め方式と等価であることに注意してください。

\((2,1,p)\) と \((3,1,p)\) のQRACでは、 \(n\) 量子ビットのQRAC状態 \(F(m)\) にマジック状態丸めスキームを適用すると、解 \(m\) を完全に抽出するために各量子ビットの正しい基底を選ぶ確率は \(2^{-n}\) と \(4^{-n}\) pになります。言い換えると、未知の状態 \(F(m)\) が与えられた場合、 \(\mathcal{M}^{\otimes n}(F(m))\mapsto F(m)\) の確率は、測定される量子ビットの数とともに指数関数的に減少します。他の \(F(m^*)\) にマッピングされる可能性がはるかに高くなります。同様に、任意の状態 \(\rho_\text{relax}\) でマジック丸めを実行する場合、すべての \(n\) 量子ビットに対して最適なマジック基底がランダムに選択される確率は同様に低くなります。幸いなことに、マジック状態丸めは、特定の条件下で近似比の下限を提供します。

\(F(m^*)\) を F の画像内の最高エネルギー状態とし、 \(\rho^*\) を H の最大固有状態とします。

\[\forall \rho_\text{relax}\quad \text{s.t.}\quad \text{Tr}\left(F(m^*)\cdot H\right) \leq \text{Tr}\left(\rho_\text{relax}\cdot H\right)\leq \text{Tr}\left(\rho^*\cdot H\right)\]

\[\frac{\text{expected fval}}{\text{optimal fval}} = \frac{\mathbb{E}\left[\text{Tr}\left(H\cdot \mathcal{M}^{\otimes n}(\rho_\text{relax})\right)\right]}{\text{Tr}\left(H\cdot F(m^*)\right)} \geq \frac{5}{9}\]

参考文献#

[1] Bryce Fuller et al., “Approximate solutions of combinatorial problems via quantum relaxations,” (2021), arXiv:2111.03167,

[2] Stephen Wiesner, “Conjugate coding,” SIGACT News, vol. 15, issue 1, pp. 78-88, 1983. link

[3] Masahito Hayashi et al., “(4,1)-Quantum random access coding does not exist—one qubit is not enough to recover one of four bits,” New Journal of Physics, vol. 8, number 8, pp. 129, 2006. link