過去・現在・未来

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

【 量子チューリングマシンとBQPクラス 】 1993年に、Bernstein と Vazirani は、これまでのTuringマシンの拡大である「量子Turingマシン」を新しく定義して、その上で複雑性理論を展開しました。 ここから始まったこの複雑性理論の新しい分野を「量子複雑性理論」と呼びます。量子複雑性理論は、現在の複雑性理論の中心分野です。 量子複雑性理論で最も基本的なクラスは、BQPです。それは、従来の複雑性理論での多項式時間で決定可能な複雑性のクラス P に相当するものです。 ただし、量子Turingマシンの特性として、その出力は古典的なTuringマシンのように常に確定した値を返すのではなく確率分布として与えられます。 BQPは、“Bounded error, Quantum, Polynomial time” の略です。 この Bounded error は、このマシンの出力の「誤り」が一定の確率（一般には 1/3 を使う）以下であることを表しています。 その点では、BQPは古典的な複雑性理論でのBPP (bounded-error probabilistic polynomial time)によく似ています。 【 量子コンピュータの理論的可能性をめぐって先行した議論 】 「量子コンピュータ」は、今から約40年前(1982年)のFeynmanの洞察を発端とします。彼の論文に刺激を受けて DeutschがChurch=Turing Thesis を拡大することを提案します(1985年)。その後、 Vaziraniが量子チューリングマシンを構成し、量子複雑性の基本的クラスBQPを提案します。(1993年) この間の理論展開は、目覚ましいものです。 こうした流れの頂点は、1994年のShorの、量子コンピュータによる素因数分解のアルゴリズムを発見です。 「量子コンピュータ」が広く注目され研究者が爆発的に増大します。 このセッションでは、これらの議論の概略を紹介したいと思います。スライドを参照ください。 【 Church = Turing テーゼの拡大 】 この間の議論で注目すべきことは、「計算可能性理論」のエッセンスとしての「Church = T uring テーゼ」の拡大の動きです。 古典的なChurch = Turing テーゼは、次のようなものでし

【 確率的チューリングマシンとBPPクラス 】 #コンピュータと数学2 今回のセッションでは、「確率的チューリングマシン」と呼ばれるチューリングマシンの拡大の話をします。 「確率的チューリングマシン」の構成の仕方は、前回見た「非決定性チューリングマシン」の構成とよく似ています。 「確率的チューリングマシン」の振る舞いを説明する前に、「非決定性チューリングマシン」の振る舞いについて、少し補足しておこうと思います。 【 前回のセッションの補足 】 前回のセッションで、「非決定性チューリングマシン」の振る舞いを説明したblog記事で、「チューリングマシンの拡大では、新しい計算を定義することに意味がある」というような少し極端な議論を述べました。また、それに対して、一つの入力に対して実行のたびに異なる結果を返すような「計算」に意味はないという当然の意見も紹介しました。 ここで補足したいのは、「非決定性チューリングマシン」は、見かけほど無茶苦茶な計算を定義しているわけではないと言うことです。 次のことに注目してください。 一つには、「非決定性チューリングマシン」は、複数（それは膨大な数になるかもしれないのですが有限です）の並行に動作する「決定性チューリングマシン」でシミレート可能だということです。前回のセッションで見たように、「非決定性チューリングマシン」を、そのツリー構造の中で「決定性チューリングマシン」を表すパスを指定するテープを追加すれば、「決定性チューリングマシン」でシミュレートすることが可能です。 　 それが非決定論的に振る舞うように見えるのは、それが概念的には、無数の（有限個です）決定論的に振る舞うチューリングマシンの可能な全体を表現しているのに、我々が 見るのは、そのうちの一つのチューリングマシンの出力だけだからです。 【 非決定性チューリングマシンがある入力をaccept あるいは reject する条件 】 注目すべきもう一つのことは、先のことと関係しているのですが、「非決定性チューリングマシン」がある入力を「受理 (accept)」または「拒否 (reject)」する条件です。 大雑把に言えば、チューリングマシンがある入力を「accept」すると言うのは、その入力が表す命題が正しいと認めることで、「reject」すると言うのは、その入力が表す命題を正しく

【 非決定性チューリングマシンとNPクラス 】 このセッションから新しいPart 「チューリングマシンの拡大と複雑性クラス」が始まります。 「計算可能性理論」のエッセンスは、「計算可能な計算はすべて、ある帰納的チューリングマシンによって実行されるものである」という「チャーチ=チューリングのテーゼ」です。 このテーゼによれば、「計算可能な計算」という数学的な性質は、「あるチューリングマシンによって実行されるもの」として、ある機械（チューリングマシン）の振る舞いと対応づけられることで定義されています。 興味深いことは、「計算可能な計算」という数学的な性質と機械の振る舞いを結びつけるこの「テーゼ」自身は、数学的な命題では無いことです。それは、人間の数学的認識の特徴について語っているのですが、数学的に証明されるような性質のものではありません。 「チャーチ=チューリングのテーゼ」自体を拡大することも可能です。実は、「量子コンピュータ」の登場は、そうした「テーゼ」の見直しと深い関係があります。それについては、このあとのセッションで見ていきたいと思います。 【 チューリングマシンの振る舞いを変える 】 このセッションでは、「テーゼ」の枠組みを大きく変えるのではなく、チューリングマシンの概念を拡大してその振る舞いを変えることを考えてみましょう。新しい数学的性質を定義するのが目的です。 　　「ある数学的性質 Lの計算とは、ある拡大された 　　チューリングマシンMで実行されるものである」 こんな感じなのですが、一つ問題があります。それは、「チューリングマシンの拡大」は、口で言うほど簡単ではないからです。 そもそもチューリングマシンは数学的には万能で、「帰納的チューリングマシン」ならは、計算結果が返る計算可能なものは、すでにすべてカバーしています。（「帰納的」という条件を外した、一般のチューリングマシンには、「停止」する保証はありません。） このセッションで行う、チューリングマシンの拡大は次のようなものです。 「普通のチューリングマシンは、一つの入力に対して一つの出力を返す」 「それがどうした」 「我々は、チューリングマシンを、一つの入力に対して複数の出力を返すように拡大する」 「そんなのチューリングマシンと言わない」 「だから、「拡大」だと言っているだろ」 「どうすんの？」 「普通の