ハミルトンシミュレーション

ハミルトンシミュレーション（量子シミュレーションとも呼ばれる）は、量子システムをシミュレートするために必要な計算量と量子アルゴリズムを見つけようとする量子情報科学の問題です。ハミルトンシミュレーションは、量子状態の進化を効率的に実装するアルゴリズムを要求する問題です。ハミルトンシミュレーション問題は、1982年にリチャード・ファインマンによって提唱され、一般的なハミルトニアンのシミュレーションはシステムサイズに対して指数関数的に増加するように見えることから、量子コンピュータを可能な解決策として提案しました。^[1]

ハミルトニアンシミュレーション問題では、ハミルトニアン （量子ビットに作用するエルミート行列）、時間、最大シミュレーション誤差が与えられた場合、を近似するアルゴリズムを見つけることが目標です。ここで、 は理想的な進化であり、はスペクトルノルムです。ハミルトニアンシミュレーション問題の特殊なケースは、局所ハミルトニアンシミュレーション問題です。これは、 が量子ビット上のk局所ハミルトニアンであり、 が量子ビットではなく最大で 量子ビットに非自明に作用する場合です。^[2]局所ハミルトニアンシミュレーション問題は、自然界に発生するほとんどのハミルトニアンはk局所であるため重要です。^[2]${\displaystyle H}$${\displaystyle 2^{n}\times 2^{n}}$ ${\displaystyle n}$${\displaystyle t}$${\displaystyle \epsilon }$${\displaystyle U}$${\displaystyle ||Ue^{-iHt}||\leq \epsilon }$${\displaystyle e^{-iHt}}$${\displaystyle ||\cdot ||}$${\displaystyle H}$${\displaystyle n}$${\displaystyle H=\sum _{j\mathop {=} 1}^{m}H_{j}}$${\displaystyle H_{j}}$${\displaystyle k}$${\displaystyle n}$

トロッター公式またはトロッター・スズキ分解としても知られる積公式は、ハミルトニアンの項の和を、それぞれを小さな時間スライスで個別にシミュレートすることによってシミュレートします。^{[3] [4]} の場合、大きな に対して となります。ここで はシミュレートする時間ステップの数です。 が大きいほど、シミュレーションの精度が高まります。 ${\displaystyle H=A+B+C}$${\displaystyle U=e^{-i(A+B+C)t}=(e^{-iAt/r}e^{-iBt/r}e^{-iCt/r})^{r}}$${\displaystyle r}$${\displaystyle r}$${\displaystyle r}$

ハミルトニアンが疎行列として表現される場合、分散エッジカラーリングアルゴリズムを使用してそれを項の和に分解することができ、その後トロッター・スズキアルゴリズムでシミュレートすることができます。^[5]

${\displaystyle e^{-iHt}=\sum _{n\mathop {=} 0}^{\infty }{\frac {(-iHt)^{n}}{n!}}=I-iHt-{\frac {H^{2}t^{2}}{2}}+{\frac {iH^{3}t^{3}}{6}}+\cdots }$テイラー級数展開によって。 ^[6]これは、量子状態の発展の過程で、ハミルトニアンが様々な回数繰り返してシステムに何度も適用されることを意味します。第 1 項は単位行列であるため、適用時にシステムは変化しませんが、第 2 項ではハミルトニアンは 1 回適用されます。実用的な実装では、級数は に切り捨てられなければならず、 が大きいほど、シミュレーションの精度が高くなります。^[7]この切り捨てられた展開は、ハミルトニアン シミュレーションのユニタリの線形結合 (LCU) 手法によって実装されます。^[6]つまり、ハミルトニアンをそれぞれがユニタリになるように分解し(たとえば、パウリ演算子は常にそのような基底を提供します)、それぞれがユニタリの線形結合でもあるようにします。 ${\displaystyle \left(\sum _{n\mathop {=} 0}^{N}{\frac {(-iHt)^{n}}{n!}}\right)}$${\displaystyle N}$${\displaystyle H=\sum _{\ell =1}^{L}\alpha _{\ell }H_{\ell }}$${\displaystyle H_{\ell}}$${\displaystyle H^{n}=\sum _{\ell _{1},\ldots ,\ell _{n}=1}^{L}\alpha _{\ell _{1}}\cdots \alpha _{\ell _{n}}H_{\ell _{1}}\cdots H_{\ell _{n}}}$

量子ウォークでは、スペクトルがハミルトニアンと関連するユニタリー演算が実装され、量子位相推定アルゴリズムを使用して固有値を調整します。これにより、トロッター-スズキ法のようにハミルトニアンを項の和に分解する必要がなくなります。^[6]

量子信号処理アルゴリズムは、ハミルトニアンの固有値を補助量子ビットに変換し、その固有値を単一量子ビット回転で変換し、最後に補助を投影することによって機能します。^[8]ハミルトニアンのシミュレーションに関しては、クエリの複雑さが最適であることが証明されています。^[8]

上記のハミルトニアン シミュレーション アルゴリズムの複雑さの表。ハミルトニアン シミュレーションは 2 つの方法で研究できます。これは、ハミルトニアンの与え方によって異なります。明示的に与えられた場合、ゲートの複雑さはクエリの複雑さよりも重要になります。ハミルトニアンがオラクル (ブラック ボックス) として記述されている場合、オラクルへのクエリの数は回路のゲート数よりも重要です。次の表は、前述の手法のゲートとクエリの複雑さを示しています。

の最大のエントリはどこですか。 ${\displaystyle ||H||_{\rm {max}}}$${\displaystyle H}$

• 量子シミュレータ