過去・現在・未来

【 Church-Turing Thesisの変化と量子情報理論 】 このセッションが、今回のセミナーに向けた最後のセッションになります。 このセッションでは、「計算可能性理論」から「計算複雑性理論」への発展を、 Church-Turing Thesisの変化・発展として振り返り、あわせてそれが現時点でどのように変化を続けているのかを見ていきたいと思います。 以下は、その大雑把な流れです。 【 1920年代 -- ヒルベルト・プログラム 】 ヒルベルトは、全ての数学的命題の真または偽を決定する方法が 存在すること、数学の形式化が矛盾を含まないことが証明しようと しました。 【 1930年代 -- ゲーデルの不完全性定理 】 ゲーデルは、真または偽を決定する方法が存在しない命題が 存在すること、また、数学の形式化が矛盾を含まないことの証明 が不可能であることを示しました。それはヒルベルトのプログラムが、 遂行できないことを意味しました。 【 1950年代 -- チャーチ＝チューリングのテーゼ 】 「証明可能＝計算可能」なものには限界があることは、1950年代 には、チャーチ=チューリングのテーゼとして定式化され、一般に 広く認められるようになりました。ただ、それは、我々の認識の「限界」と しては、非常に荒い、かつ、抽象的で原理的な限界を与えるもので しかありませんでした。 【 1970年代 -- 計算複雑性理論の登場 】 クック、レビン、カープらは、計算可能だが実際には手に負えない 計算である領域を精緻に分類しようとし、計算複雑性理論が生ま れます。 「難しい計算」が「易しい計算」には還元できないことを主張する 「P = NP ? 問題」は、現在も未解決です。 【 1980年代 --  チャーチ＝チューリング＝ドイッチェのテーゼ 】 ドイッチェは、ファインマンの自然をシミュレートする量子コンピュータというアイデアに刺激を受けて、計算は、物理的な過程として実現されると主張して、チャーチ=チューリングのテーゼを拡大しました。ただ、80年代は、まだ、量子コンピュータは物理学者の頭の中の概念としてしか存在していませんでした。 【 1990年代 -- 量子複雑性理論とショアのアルゴリズム 】 ベルンシュタインとバジラーニによって、量子複雑性の理論が登場し、BQPという新しい複雑