long-termアルゴリズム

Long-termアルゴリズムとは、多数の量子ビットが利用可能で、かつ量子誤り訂正が可能という仮定のもとで初めて実行できる量子アルゴリズムのことです。Long-termアルゴリズムには、ショアの素因数分解アルゴリズムやグローバーの探索アルゴリズムなどがあります。これらのアルゴリズムは、古典コンピュータでは指数的に時間がかかる問題を、多項式時間で解くことができると期待されています。しかし、現在の量子コンピュータの技術水準では、これらのアルゴリズムを実行するのは非常に困難です。なぜなら、量子ビットの数や量子ゲートの精度が十分に高くないと、計算途中で起こる誤りの影響が無視できなくなるからです。例えば、ショアのアルゴリズムで2048ビットのRSA暗号を解読するには、約2000万個のノイジーな量子ビットと、約0.1%のゲートエラーレートが必要とされています¹。これは、現在の量子コンピュータの目標と比べても、非常に高い要求です。したがって、Long-termアルゴリズムを実現するには、量子コンピュータの技術革新が必要です。