断熱量子計算

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

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

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

${\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}}$

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

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

断熱量子計算は、充足可能性問題やその他の組み合わせ探索問題を解決します。具体的には、この種の問題は を満たす状態を求めます 。この式には、M 個の節の充足可能性が含まれており、その節の値は True または False で、n ビットを含むことができます。各ビットは、が のブール値関数であるような変数です。QAA は、量子断熱進化を使用してこの種の問題を解決します。これは、初期ハミルトニアン から始まります。 ${\displaystyle C_{1}\wedge C_{2}\wedge \cdots \wedge C_{M}}$${\displaystyle C_{i}}$${\displaystyle x_{j}\in \{0,1\}}$${\displaystyle C_{i}}$${\displaystyle x_{1},x_{2},\dots ,x_{n}}$${\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}}$

ここで、節 C を満たすハミルトニアンです。 ${\displaystyle H_{P,C}}$

固有値は次のとおりです。

${\displaystyle h_{C}(z_{1C},z_{2C}\dots z_{nC})={\begin{cases}0&{\mbox{clause }}C{\mbox{ 満足}}\\1&{\mbox{clause }}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成分を測定します。これにより、満足可能性問題の結果である可能性が非常に高い文字列が生成されます。実行時間Tは、結果の正確性を保証するために十分に長くなければなりません。断熱定理によると、Tは約 であり、ここで は 基底状態と最初の励起状態の間の最小エネルギーギャップです。^[12]${\displaystyle z_{1},z_{2},\dots ,z_{n}}$${\displaystyle \varepsilon /g_{\mathrm {分} }^{2}}$${\displaystyle g_{\mathrm {min} }=\min _{0\leq s\leq 1}(E_{1}(s)-E_{0}(s))}$

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

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

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