量子探索アルゴリズムの幾何学的な描像

石渡 康恵

6月13日 (金) 13時30分

量子コンピュータは量子力学の基本原理に基づく、 今までの計算機(古典計算機)とは全く違う新しい計算機である。 1985年頃概念が提案され、1994年のSchorによる因数分解のアルゴリズムの 発表以来、理論的な進歩が著しい。
今回題材にする量子探索アルゴリズムも、量子コンピュータに用いると 効率のよいアルゴリズムであり、1996年、L.K.Groverにより発表された。 しかし、このアルゴリズムは量子的に最適であるといえるのかどうかは 自明ではない。よって今回は、このアルゴリズムが最適であることを示す という目標を念頭におきながら、幾何的な描像からこのアルゴリズムが 何をしているのかを理解していきたいと思う。

戻る