量子最適化アルゴリズム

量子最適化アルゴリズムは、最適化問題を解決するために使用される量子アルゴリズムです。 ^[1] 数学的最適化は、一連の可能な解から問題に対する最善の解（いくつかの基準に従って）を見つけることを扱います。ほとんどの場合、最適化問題は最小化問題として定式化され、解に依存する誤差を最小化しようとします。最適な解は誤差が最小です。さまざまな最適化手法が力学、経済学、工学などのさまざまな分野に適用されており、関連するデータの複雑さと量が増えるにつれて、最適化問題を解決するためのより効率的な方法が必要になります。量子コンピューティングにより、従来のコンピューターでは実際には実行できない問題を解決できるようになり、または最もよく知られている従来のアルゴリズムに比べて大幅な高速化が期待できます。

データ フィッティングは、一連のデータ ポイントに最もよく適合する数学関数を構築するプロセスです。適合の品質は、通常は関数とデータ ポイント間の距離などのいくつかの基準によって測定されます。

最も一般的なデータ フィッティングのタイプの 1 つは、最小二乗問題を解き、データ ポイントとフィッティングされた関数の差の二乗の合計を最小化することです。

アルゴリズムには入力データ ポイントと連続関数が与えられます。アルゴリズムは、次の線形結合である連続関数を見つけて出力します。 ${\displaystyle N}$${\displaystyle (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{N},y_{N})}$${\displaystyle M}$ ${\displaystyle f_{1},f_{2},...,f_{M}}$${\displaystyle f_{\vec {\lambda }}}$${\displaystyle f_{j}}$

${\displaystyle f_{\vec {\lambda}}(x)=\sum _{j=1}^{M}f_{j}(x)\lambda _{j}}$

言い換えると、アルゴリズムは複素係数、つまりベクトル を見つけます。 ${\displaystyle \lambda_{j}}$${\displaystyle {\vec {\lambda }}=(\lambda _{1},\lambda _{2},...,\lambda _{M})}$

このアルゴリズムは、次式で表される誤差を最小化することを目的としています。

${\displaystyle E=\sum _{i=1}^{N}\left\vert f_{\vec {\lambda }}(x_{i})-y_{i}\right\vert ^{2}=\sum _{i=1}^{N}\left\vert \sum _{j=1}^{M}f_{j}(x_{i})\lambda _{j}-y_{i}\right\vert ^{2}=\left\vert F{\vec {\lambda }}-{\vec {y}}\right\vert ^{2}}$

ここで、次の行列として定義されます。 ${\displaystyle F}$

${\displaystyle {F}={\begin{pmatrix}f_{1}(x_{1})&\cdots &f_{M}(x_{1})\\f_{1}(x_{2})&\cdots &f_{M}(x_{2})\\\vdots &\ddots &\vdots \\f_{1}(x_{N})&\cdots &f_{M}(x_{N})\\\end{pmatrix}}}$

量子最小二乗フィッティングアルゴリズム^[2]は、ハロー、ハシディム、ロイドの線形方程式系（HHL）に対する量子アルゴリズムのバージョンを利用し、係数とフィッティング品質の推定を出力します。これは、擬似逆演算を実行するためのアルゴリズム、フィッティング品質の推定のための1つのルーチン、およびフィッティングパラメータを学習するためのアルゴリズム の3つのサブルーチンで構成されています。${\displaystyle \lambda_{j}}$${\displaystyle E}$

量子アルゴリズムは主にHHLアルゴリズムに基づいているため、が疎で、との両方の条件数（つまり、最大固有値と最小固有値の比）が小さい場合に指数関数的な改善^[3]が示唆されます。 ${\displaystyle F}$${\displaystyle FF^{\dagger}}$${\displaystyle F^{\dagger }F}$

半正定値計画法(SDP) は、半正定値行列の円錐とアフィン空間との交差上で線形目的関数(最小化または最大化されるユーザー指定の関数) の最適化を扱う最適化サブフィールドです。目的関数は、行列(入力として指定) と変数の内積です。すべての対称行列の空間によって表します。変数は、半正定値対称行列 の (閉じた凸) 円錐 内にある必要があります。2 つの行列の内積は次のように定義されます。 ${\displaystyle C}$${\displaystyle X}$${\displaystyle \mathbb {S} ^{n}}$${\displaystyle n\times n}$${\displaystyle X}$${\displaystyle \mathbb {S} _{+}^{n}}$

${\displaystyle \langle A,B\rangle _{\mathbb {S} ^{n}}={\rm {tr}}(A^{T}B)=\sum _{i=1,j=1}^{n}A_{ij}B_{ij}.}$

問題には追加の制約（入力として与えられる）がある場合があり、これも通常は内積として定式化されます。各制約は、最適化変数（入力として与えられる）と行列の内積が指定された値（入力として与えられる）よりも小さくなるように強制します。最終的に、SDP 問題は次のように記述できます。 ${\displaystyle A_{k}}$${\displaystyle X}$${\displaystyle b_{k}}$

${\displaystyle {\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{subject to}}&\langle A_{k},X\rangle _{\mathbb {S} ^{n}}\leq b_{k},\quad k=1,\ldots ,m\\&X\succeq 0\end{array}}}$

最良の古典的アルゴリズムは、無条件に多項式時間で実行できることは知られていない。対応する実行可能性問題は、NPとco-NPの複雑性クラスの和集合の外側にあるか、NPとco-NPの積集合にあることが知られている。^[4]

アルゴリズムの入力は、ソリューションのトレースと精度、最適値（最適点における目的関数の値）に関するパラメータです。 ${\displaystyle A_{1}...A_{m},C,b_{1}...b_{m}}$

量子アルゴリズム^[5]は複数の反復から構成されています。各反復では、実現可能性問題、つまり、以下の条件を満たす解を見つけます（しきい値を与えます）。 ${\displaystyle t}$

${\displaystyle {\begin{array}{lr}\langle C,X\rangle _{\mathbb {S} ^{n}}\leq t\\\langle A_{k},X\rangle _{\mathbb {S} ^{n}}\leq b_{k},\quad k=1,\ldots ,m\\X\succeq 0\end{array}}}$

各反復では、異なるしきい値が選択され、アルゴリズムは、（他の制約も満たされる）ようなソリューション、またはそのようなソリューションが存在しないという表示のいずれかを出力します。アルゴリズムは、ソリューションがまだ存在する最小のしきい値を見つけるためにバイナリ検索を実行します。これにより、SDP 問題に対する最小のソリューションが得られます。 ${\displaystyle t}$${\displaystyle X}$${\displaystyle \langle C,X\rangle _{\mathbb {S} ^{n}}\leq t}$${\displaystyle t}$${\displaystyle X}$

量子アルゴリズムは、一般的な場合には最良の古典的アルゴリズムに比べて 2 次的な改善をもたらし、入力行列のランクが低い場合には指数的な改善をもたらします。

組み合わせ最適化問題は、有限のオブジェクト集合から最適なオブジェクトを見つけることを目的とします。この問題は、ブール関数の合計である目的関数の最大化として表現できます。各ブール関数は、入力としてビット文字列を受け取り、出力として1ビット（0または1）を返します。ビットと節の組み合わせ最適化問題は、関数を最大化する ビット文字列を見つけることです。${\displaystyle \,C_{\alpha }\colon \lbrace {0,1\rbrace }^{n}\rightarrow \lbrace {0,1}\rbrace }$${\displaystyle n}$${\displaystyle z=z_{1}z_{2}\ldots z_{n}}$${\displaystyle n}$${\displaystyle m}$${\displaystyle n}$${\displaystyle z}$

${\displaystyle C(z)=\sum _{\alpha =1}^{m}C_{\alpha }(z)}$

近似最適化は、多くの場合NP 困難である最適化問題の近似解を見つける方法です。組み合わせ最適化問題の近似解は、を最大化することに近い文字列です。 ${\displaystyle z}$${\displaystyle C(z)}$

組合せ最適化に関しては、量子近似最適化アルゴリズム（QAOA）^[6]は、特定の問題に対して、既知の多項式時間古典アルゴリズムよりも優れた近似率を一時的に達成しましたが、 ^[7]より効果的な古典アルゴリズムが提案されるまでは^[8]、量子アルゴリズムの相対的な高速化は未解決の研究課題です。

QAOA は次の手順で構成されます。

1. コスト ハミルトニアンを 定義して、その基底状態が最適化問題の解をエンコードするようにします。${\displaystyle H_{C}}$
2. ミキサーハミルトニアンを 定義します。${\displaystyle H_{M}}$
3. パラメータおよび α を使用して、オラクルおよびを定義します。${\displaystyle U_{C}(\gamma )=\exp(-\imath \gamma H_{C})}$${\displaystyle U_{M}(\alpha )=\exp(-\imath \alpha H_{M})}$${\displaystyle \gamma}$
4. オラクルおよびを次の順序で繰り返し適用します。${\displaystyle U_{C}}$${\displaystyle U_{M}}$${\displaystyle U({\boldsymbol {\gamma }},{\boldsymbol {\alpha }})=\coprod _{i=1}^{N}(U_{C}(\gamma _{i})U_{M}(\alpha _{i}))}$
5. すべての可能な状態の重ね合わせである初期状態を準備し、その状態に適用します。${\displaystyle U({\boldsymbol {\gamma }},{\boldsymbol {\alpha }})}$
6. 古典的な方法を使用してパラメータを最適化し、最適化された回路の出力状態を測定して、コスト ハミルトニアンの近似最適解を取得します。最適解は、コスト ハミルトニアンの期待値を最大化する解になります。${\displaystyle {\boldsymbol {\gamma }},{\boldsymbol {\alpha }}}$${\displaystyle H_{C}}$

アルゴリズムのレイアウト、つまりコスト ハミルトニアンとミキサー ハミルトニアンの使用は、量子断熱定理からヒントを得ています。量子断熱定理では、時間依存ハミルトニアンの基底状態から開始して、ハミルトニアンが十分にゆっくりと進化すると、最終状態は最終ハミルトニアンの基底状態になると述べています。さらに、断熱定理は、進化の過程で異なる固有状態間に重複 (縮退) がない限り、他の任意の固有状態に一般化できます。初期ハミルトニアンを、最終ハミルトニアンを と同一視すると、その基底状態が対象の最適化問題の解をエンコードするため、最適化問題を、初期ハミルトニアンから最終ハミルトニアンの断熱進化として近似することができ、その基底 (固有) 状態が最適解を与えます。一般に、QAOA は角度(パラメータ)に依存するユニタリ演算子の使用に依存しています。ここで、は入力整数であり、オラクル の層の数として識別できます。これらの演算子は、計算基底内のすべての可能な状態の等重み量子重ね合わせである状態に反復的に適用されます。各反復で、状態は計算基底で測定され、ブール関数が推定されます。次に、角度が古典的に更新され、 が増加します。この手順が十分な回数繰り返されると、 の値はほぼ最適になり、測定されている状態も最適に近くなります。量子コンピューターで QAOA を実装するサンプル回路を図に示します。この手順は、グラフの最小頂点カバーを見つける次の例を使用して強調表示されます。 ^[9]${\displaystyle H_{M}}$${\displaystyle H_{C}}$${\displaystyle 2p}$ ${\displaystyle p>1}$${\displaystyle U({\boldsymbol {\gamma }},{\boldsymbol {\alpha }})}$${\displaystyle C(z)}$${\displaystyle C(z)}$${\displaystyle C(z)}$

ここでの目標は、グラフの最小頂点カバーを見つけることです。これは、グラフの各辺にカバー内の頂点の少なくとも 1 つが含まれるような頂点の集合です。したがって、これらの頂点はすべての辺を「カバー」します。頂点の数が可能な限り少ない頂点カバーを見つけたいのです。頂点カバーはビット文字列で表すことができます。各ビットは、対応する頂点がカバー内に存在するかどうかを示します。たとえば、ビット文字列 0101 は、4 つの頂点を持つグラフの 2 番目と 4 番目の頂点で構成されるカバーを表します。

図に示すグラフを考えてみましょう。このグラフには 4 つの頂点があり、このグラフには 2 つの最小頂点カバーがあります。頂点 0 と 2、および頂点 1 と 2 です。これらはそれぞれ、ビット文字列 1010 と 0110 で表すことができます。アルゴリズムの目的は、これらのビット文字列を高い確率でサンプリングすることです。この場合、コスト ハミルトニアンは、問題の解と一致する 2 つの基底状態 |1010⟩ と |0110⟩ を持ちます。ミキサー ハミルトニアンは、グラフの各ノードに対するPauli-X操作の単純な非可換合計であり、次のように表されます。

${\displaystyle H_{C}=-0.25Z_{3}+0.5Z_{0}+0.5Z_{1}+1.25Z_{2}+0.75(Z_{0}Z_{1}+Z_{0}Z_{2}+Z_{2}Z_{3}+Z_{1}Z_{2})}$

${\displaystyle H_{M}=X_{0}+X_{1}+X_{2}+X_{3}}$

qiskit の 2 層の仮説を使用してこの 4 量子ビット回路に QAOA アルゴリズムを実装し (図を参照)、最適化すると、図に示す状態の確率分布が得られます。これは、予想どおり、状態 |0110⟩ と |1010⟩ が測定される確率が最も高いことを示しています。

原理的には、の最適値は任意の精度まで到達可能であり、これは断熱定理^{[10] [11]}またはQAOAユニタリの普遍性によって保証されています。^[12]しかし、これが実行可能な方法で実行できるかどうかは未解決の問題です。たとえば、QAOAは問題の制約と変数の比率（問題密度）に強く依存し、対応する目的関数を最小化するアルゴリズムの能力に制限をかけることが示されています。^[13]${\displaystyle C(z)}$

QAOAプロセスの一般化は、本質的には、基礎となるグラフ上で連続時間量子ウォークを交互に適用し、その後、各解の状態に品質依存の位相シフトを適用することであることがすぐに認識されました。この一般化されたQAOAは、QWOA（量子ウォークベースの最適化アルゴリズム）と呼ばれました。^[14]

arXivに投稿された論文「量子計算の超越性にはいくつの量子ビットが必要か」 ^{[15]では、著者らは、420}量子ビットと500の制約を持つQAOA回路を最先端の スーパーコンピュータで実行される古典的なシミュレーションアルゴリズムを使用してシミュレートするには少なくとも1世紀かかるため、量子計算の超越性には十分であると結論付けています。

QAOAと古典的なアルゴリズムを厳密に比較すると、量子優位性に必要な量子ビットの深さと数を推定できます。QAOAとMaxCutアルゴリズムの研究では、スケーラブルな優位性には量子ビットが必要であることが示されています。^[16]${\displaystyle p}$${\displaystyle p>11}$

QAOAの基本構造にはいくつかのバリエーションが提案されており、^[17]基本アルゴリズムの仮説のバリエーションも含まれています。仮説の選択は通常、グラフとして表現される組み合わせ問題やハードウェア設計の影響を強く受ける問題など、問題の種類によって異なります。ただし、仮説の設計では、過剰適合を回避し、幅広い問題への適用性を維持するために、特異性と一般性のバランスを取る必要があります。このため、QAOAに最適な仮説を設計することは、広範囲に研究され、幅広く調査されているトピックです。提案されているバリエーションには次のものがあります。

1. マルチアングルQAOA ^[18]
2. QAOA+ ^[19]
3. デジタル化された反断熱QAOA ^[20]
4. 量子交代演算子仮説^[21]は最適化問題などに制約を与える。

QAOA の別のバリエーションは、パラメータ最適化のテクニックに焦点を当てており、特定の問題に対して最適な初期パラメータ セットを選択し、コスト ハミルトニアンのエネルギー ランドスケープ内のプラトーに対応する固有状態につながるパラメータを表す不毛なプラトーを回避することを目的としています。

最後に、トラップイオン、中性原子、超伝導量子ビット、光子量子コンピュータなど、さまざまなプラットフォームで QAOA のパフォーマンスを向上させるために特定のハードウェアを活用することには、大きな研究上の関心が寄せられています。これらのアプローチの目標には、ハードウェア接続の制限を克服し、ノイズ関連の問題を軽減して、QAOA の適用範囲を幅広い組み合わせ最適化問題に広げることが含まれます。

• 断熱量子計算
• 量子アニーリング

• Classiq によるナップサック問題に対する QAOA アルゴリズムの実装