断熱量子計算

断熱量子計算（AQC ）は、計算を実行するために断熱定理に依存する量子計算の一形態であり^{[ 1 ]} 、量子アニーリングと密接に関連している^{[ 2 ] [ 3 ] [ 4 ] [ 5 ]}。

まず、（場合によっては複雑な）ハミルトニアンが見つかり、その基底状態が対象となる問題の解を表します。次に、単純なハミルトニアンを持つシステムが準備され、基底状態に初期化されます。最後に、単純なハミルトニアンが断熱的に目的の複雑なハミルトニアンへと進化します。断熱定理により、システムは基底状態に留まるため、最終的にシステムの状態が問題の解を表します。断熱量子コンピューティングは、回路モデルにおいて従来の量子コンピューティングと多項式的に等価であることが示されています。^{[ 6 ]}

断熱アルゴリズムの時間計算量は、断熱進化を完了するのにかかる時間であり、これはハミルトニアンのエネルギー固有値のギャップ（スペクトルギャップ）に依存します。具体的には、システムを基底状態に維持する場合、基底状態と最初の励起状態の間のエネルギーギャップは、${\displaystyle H(t)}$これは、時刻におけるハミルトニアンが進化できる速度の上限値を提供する。${\displaystyle t}$[ ^{7 ]}スペクトルギャップが小さい場合、ハミルトニアンはゆっくりと進化させる必要がある。アルゴリズム全体の実行時間は、以下の式で制限される^。

${\displaystyle T=O\left({\frac {1}{g_{min}^{2}}}\right)}$

どこ${\displaystyle g_{min}}$は最小スペクトルギャップです${\displaystyle H(t)}$。

AQCは、エネルギー緩和の問題を回避する有効な手段の一つです。量子系は基底状態にあるため、外部からの干渉によってより低い状態へ移行することはできません。外部のエネルギー（すなわち「熱浴の温度」）を基底状態と次の高エネルギー状態とのエネルギーギャップよりも低く保つことで、系がより高いエネルギー状態へ移行する確率は比例的に低くなります。したがって、系は必要な限り単一の固有状態に留まることができます。

断熱モデルにおける普遍性の結果は、量子複雑性とQMA困難問題に関連しています。k 局所ハミルトニアンは k ≥ 2 に対して QMA 完全です。^{[ 8 ]} QMA 困難性の結果は、^{[ 9 ]}のような物理的に現実的な量子ビットの格子モデルで知られています。

${\displaystyle H=\sum _{i}h_{i}Z_{i}+\sum _{i<j}J^{ij}Z_{i}Z_{j}+\sum _{i<j}K^{ij}X_{i}X_{j}}$

どこ${\displaystyle Z,X}$パウリ行列を表す$\displaystyle \sigma _{z},\sigma _{x}}$このようなモデルは、普遍的な断熱量子計算に使用されます。QMA完全問題のハミルトニアンは、2次元の量子ビットグリッド^{[ 10 ]}または粒子ごとに12の状態を持つ量子粒子の列^{[ 11 ]}に作用するように制限することもできます。このようなモデルが物理的に実現可能であることが判明した場合、それらも普遍的な断熱量子コンピュータの構成要素を形成するために使用できます。

実際には、計算中に問題が発生する。ハミルトニアンを徐々に変化させていくと、興味深い部分（古典的挙動とは対照的な量子的挙動）は、複数の量子ビットが転換点に近づいたときに現れる。まさにこの時点で、基底状態（量子ビットの向きの1つのセット）が、最初のエネルギー状態（向きの異なる配置）に非常に近づく。わずかなエネルギー（外部浴から、あるいはハミルトニアンをゆっくりと変化させた結果として）を加えると、システムが基底状態から外れ、計算が失敗する可能性がある。計算をより速く実行しようとすると、外部エネルギーが増加する。量子ビットの数を増やすと、転換点におけるエネルギーギャップが小さくなる。

断熱量子計算は、充足可能性問題やその他の組み合わせ探索問題、特にイジングモデルの基底状態やQUBO問題として定式化できるような問題を解決する。

充足可能性問題は、 ${\displaystyle C_{1}\wedge C_{2}\wedge \cdots \wedge C_{M}}$この式には、M 節の充足可能性が含まれています。どの節が充足可能か。${\displaystyle C_{i}}$値はTrueまたはFalseで、nビットを含むことができます。各ビットは変数です。${\displaystyle x_{j}\in \{0,1\}}$そのため${\displaystyle C_{i}}$はブール値関数です${\displaystyle x_{1},x_{2},\dots ,x_{n}}$QAAは量子断熱発展を用いてこの種の問題を解決します。初期ハミルトニアンから始まります。${\displaystyle H_{B}}$:

${\displaystyle H_{B}=H_{B_{1}}+H_{B_{2}}+\dots +H_{B_{M}}}$

どこ${\displaystyle H_{B_{i}}}$この節に対応するハミルトニアンを示します${\displaystyle C_{i}}$通常、${\displaystyle H_{B_{i}}}$異なる節に依存しないため、各ビットがすべての節に関与する合計回数だけが重要になります。次に、断熱進化を経て、問題のハミルトニアンに終わります。${\displaystyle H_{P}}$:

${\displaystyle H_{P}=\sum \limits _{C}^{}H_{P,C}}$

どこ${\displaystyle H_{P,C}}$は、条項Cの充足ハミルトニアンである。

固有値は以下のとおりです。

${\displaystyle h_{C}(z_{1C},z_{2C}\dots z_{nC})={\begin{cases}0&{\mbox{条項}}C{\mbox{が満たされている}}\\1&{\mbox{条項}}C{\mbox{が違反している}}\end{cases}}}$

実行時間Tの単純な断熱進化経路については、以下を考慮してください。

${\displaystyle H(t)=(1-t/T)H_{B}+(t/T)H_{P}}$

そして${\displaystyle s=t/T}$その結果、以下のようになります。

${\displaystyle {\tilde {H}}(s)=(1-s)H_{B}+sH_{P}}$これは、アルゴリズムの断熱発展ハミルトニアンです。

断熱定理に従って、ハミルトニアンの基底状態から始める。${\displaystyle H_{B}}$最初は断熱過程を経て、問題のハミルトニアンの基底状態に至る。${\displaystyle H_{P}}$。

次に、最終状態におけるn個のスピンそれぞれのz成分を測定する。これにより、ストリングが生成される。${\displaystyle z_{1},z_{2},\dots ,z_{n}}$これは充足可能性問題の結果である可能性が非常に高い。実行時間 T は結果の正しさを保証するために十分に長くなければならない。断熱定理によれば、T は約${\displaystyle \varepsilon /g_{\mathrm {分} }^{2}}$、 どこ ${\displaystyle g_{\mathrm {min} }=\min _{0\leq s\leq 1}(E_{1}(s)-E_{0}(s))}$は、基底状態と第一励起状態の間の最小エネルギーギャップである。^{[ 12 ]}

断熱量子コンピューティングは、任意のユニタリ演算を実行する標準的なゲートベースの量子コンピューティングと同等の能力を持つ。ただし、ゲートベースの量子デバイスにおけるマッピングの課題は、論理変数が単一の量子ビットにのみマッピングされ、チェーンにはマッピングされないため、量子アニーリングとは大きく異なる。 ^{[ 13 ]}

D -Wave Oneは、最適化問題を解決するために量子アニーリングを使用していると主張するカナダの企業D-Wave Systemsが製造したデバイスです。 ^{[ 14 ] [ 15 ]} 2011年5月25日、ロッキード・マーティンは約1,000万米ドルでD-Wave Oneを購入しました。^{[ 15 ]} 2013年5月、Googleは512量子ビットのD-Wave Twoを購入しました。^{[ 16 ]}

D-Waveプロセッサが従来のプロセッサよりも高速化を実現できるかどうかという疑問は、まだ解決されていません。量子人工知能研究所（NASA）、南カリフォルニア大学、チューリッヒ工科大学、Googleの研究者によるテストでは、2015年の時点で量子優位性の証拠は見つかっていません。^{[ 17 ] [ 18 ] [ 19 ]}