HHLアルゴリズム

このアルゴリズムは、以下の前提条件を満たす必要がある。

1. このアルゴリズムでは、Aがエルミート行列である必要があり、そうすることでユニタリ演算子に指数化できます。Aがエルミート行列でない場合は、エルミート行列を定義できます。${\displaystyle \mathbf {C} ={\begin{bmatrix}0&A\\A^{\dagger }&0\end{bmatrix}}}$そして解決する${\displaystyle Cy={\begin{bmatrix}b\\0\end{bmatrix}}}$取得する${\displaystyle y={\begin{bmatrix}0\\x\end{bmatrix}}}$。
2. アルゴリズムは、効率的な準備手順を必要とする${\displaystyle |b\rangle }$次のいずれかであると想定される${\displaystyle |b\rangle }$既に準備されているか、何らかの量子状態をとるBが存在する${\displaystyle |\mathrm {initial} \rangle }$に${\displaystyle |b\rangle }$効率的に。${\displaystyle |b\rangle }$無視される。
3. このアルゴリズムは、状態が${\displaystyle |\psi _{0}\rangle }$効率的に準備できる場所${\displaystyle |\psi _{0}\rangle$ :={\sqrt {2/T}}\sum _{\tau \mathop {=} 0}^{T-1}\sin \pi \left({\tfrac {\tau +{\tfrac {1}{2}}}{T}}\right)|\tau \rangle } は、 ある大きなTに対して成り立つ。係数は${\displaystyle |\psi _{0}\rangle }$は、ある二次損失関数を最小化するように選択され、それによってエラーが発生します。${\displaystyle U_{\mathrm {invert} }}$以下に説明するサブルーチン。
4. このアルゴリズムは、ユニタリ演算子が${\displaystyle e^{iAt}}$効率的に適用できます。これは、 Aがsスパースで効率的に行計算可能、つまり行インデックスが与えられた場合に O( s ) の時間で計算できる行あたり最大s個の非ゼロエントリを持つ場合、ハミルトニアン シミュレーションを使用して可能です。その後、適用できます。${\displaystyle e^{iAt}}$時間が経つにつれて${\displaystyle O(\log(N)s^{2}t)}$。

アルゴリズムのキーサブルーチンは、${\displaystyle U_{\mathrm {invert} }}$は、位相推定を用いて以下のように定義される。

1. 準備する${\displaystyle |\psi _{0}\rangle ^{C}}$レジスタCで
2. 条件付きハミルトニアン発展（和）を適用する
3. レジスタCにフーリエ変換を適用する。結果として得られる基底状態を次のように表す。 ${\displaystyle |k\rangle }$k  =  0,  ..., T − 1に対して、次のように定義する。   ${\displaystyle \lambda _{k}:=2\pi k/t_{0}}$。
4. 3次元レジスタSを状態に隣接させる

${\displaystyle |h(\lambda _{k})\rangle ^{S}:={\sqrt {1-f(\lambda _{k})^{2}-g(\lambda _{k})^{2}}}|\mathrm {nothing} \rangle ^{S}+f(\lambda _{k})|\mathrm {well} \rangle ^{S}+g(\lambda _{k})|\mathrm {ill} \rangle ^{S},}$

1. 手順1～3を逆に行い、その過程で生成された不要なデータはすべて削除します。

ステップ1～3の位相推定手順では、誤差の範囲内でAの固有値を推定します。${\displaystyle \epsilon }$。

ステップ4の補助レジスタは、 Aの対角化された逆行列に対応する反転固有値を持つ状態を構築するために必要です。状態「nothing」、「well」、「ill」はループ本体を制御するために使用されます。「nothing」は行列の反転がまだ行われていないことを示し、「well」は反転が行われておりループを停止する必要があることを示し、「ill」は行列の一部が反転していないことを示します。${\displaystyle |b\rangle }$はAの条件の悪い部分空間にあり、アルゴリズムでは目的の反転を生成できません。Aの逆数に比例する状態を生成するには、「 well」を測定する必要があり、その後、全体の状態は目的の出力に収束します。

メインループは振幅増幅に従います。${\displaystyle U_{\mathrm {invert} }B|\mathrm {initial} \rangle }$繰り返し適用する

${\displaystyle U_{\mathrm {invert} }B(I-2|\mathrm {initial} \rangle \langle \mathrm {initial} |)B^{\dagger }U_{\mathrm {invert} }^{\dagger }(I-2|\mathrm {well} \rangle \langle \mathrm {well} |).}$

各反復の後、${\displaystyle S}$が測定され、「なし」、「良好」、「不良」のいずれかの値が得られます。ループは「良好」が測定されるまで繰り返されます。これはある確率で発生します。${\displaystyle p}$振幅増幅を使用すると、特定の誤差が達成されます。${\displaystyle O(1/{\sqrt {p}})}$クエリとは対照的に、${\displaystyle 1/p}$単純な反復法を用いる。

測定に成功した後、${\displaystyle S}$システムは、

${\displaystyle \sum _{i\mathop {=} 1}^{N}\beta _{i}\lambda _{j}^{-1}|u_{j}\rangle =A^{-1}|b\rangle =|x\rangle .}$

Mに対応する量子測定は、次の推定値を与える。${\displaystyle {\vec {x}}^{T}M{\vec {x}}}$。

実際の解ベクトルを生成する最良の古典的アルゴリズム${\displaystyle {\vec {x}}}$はガウス消去法であり、${\displaystyle O(N^{3})}$時間。

Aがsスパースかつ正半定値行列である場合、共役勾配法を用いて解ベクトルを求めることができる。${\displaystyle {\vec {x}}}$これは、${\displaystyle O(Ns\kappa )}$二次関数を最小化することによって時間を計算する${\displaystyle \lVert A{\vec {x}}-{\vec {b}}\rVert ^{2}}$。

解ベクトルの要約統計量のみの場合${\displaystyle {\vec {x}}}$HHLアルゴリズムの場合と同様に、古典的なコンピュータは推定値を求めることができる。${\displaystyle {\vec {x}}^{\dagger }M{\vec {x}}}$で${\displaystyle O(N{\sqrt {\kappa }})}$。

Harrowらが最初に提案したアルゴリズムの実行時間は、${\displaystyle O(\kappa ^{2}\log N/\varepsilon )}$、 どこ${\displaystyle \varepsilon >0}$は誤差パラメータであり、${\displaystyle \kappa }$条件番号は${\displaystyle A}$。これはその後改良され、${\displaystyle O(\kappa \log ^{3}\kappa \log N/\varepsilon ^{3})}$アンドリス・アンバイニス著^{[ 7 ]}と${\displaystyle O(\kappa \log N/\varepsilon )}$Peniel Tsemo らによる条件数が多い場合の^{[ 8 ]}と、実行時間が多項式である量子アルゴリズム${\displaystyle \log(1/\varepsilon )}$Childsらによって開発された^{[ 9 ]} HHLアルゴリズムは対数スケーリングを維持するため、${\displaystyle N}$疎行列または低ランク行列の場合のみ、Wossnig ら^{[ 10 ]}は量子特異値推定技術に基づいて HHL アルゴリズムを拡張し、密行列用の線形システムアルゴリズムを提供しました。${\displaystyle O({\sqrt {N}}\log N\kappa ^{2})}$時間と比べると${\displaystyle O(N\log N\kappa ^{2})}$標準HHLアルゴリズムの。

行列反転アルゴリズムの性能は条件数に依存する${\displaystyle \kappa }$Aの、最大固有値と最小固有値の比。${\displaystyle \kappa }$Aが増加すると非可逆性に近づくため、解ベクトルは不安定になり、勾配降下法の性能が低下します。HHL アルゴリズムは、すべての特異値が${\displaystyle A}$寝そべる${\displaystyle [1/\kappa ,1]}$この場合、実行時間は${\displaystyle \kappa ^{2}}$さらにスピードアップを図ると${\displaystyle \kappa }$は${\displaystyle \mathrm {poly} (\log(N))}$[ ^{1 ]​}

多対数実行時間を持つ線形システムのための量子アルゴリズム${\displaystyle \kappa }$これは、 BQP がPSPACEと等しいことを示唆するが、これは誤りであると考えられている。^{[ 1 ]}

主なエラーの原因は、${\displaystyle e^{iAt}}$ハミルトニアンシミュレーションを使用する場合。${\displaystyle A}$これはs-スパースであり、誤差を定数で制限して実行できます。${\displaystyle \varepsilon }$これは出力状態に加算誤差をもたらします${\displaystyle |x\rangle }$。

位相推定ステップの誤差は${\displaystyle O(1/t_{0})}$推定において${\displaystyle \lambda }$相対誤差は${\displaystyle O((\lambda t_{0})^{-1})}$で${\displaystyle 1/\lambda }$。 もし${\displaystyle \lambda \geq 1/\kappa }$取って${\displaystyle t_{0}=O(\kappa \varepsilon )}$最終的なエラーを引き起こす${\displaystyle \varepsilon }$これには、全体の実行時間が比例して増加する必要がある。${\displaystyle O(1/\varepsilon )}$エラーを最小限に抑えるため。