複雑性理論と人工知能技術（４） ファインマン

「計算可能性」の理論として出発した「複雑性理論」が、質的な深化を果たすのは、1980年代になってからである。

大きな転回点になったのは、1982年のファインマンの論文 "Simulating Physics with Computers" https://goo.gl/ueVbdp である。

この論文は、複雑性理論の進化の重要な画期を与えるとともに、現在の量子コンピュータのアイデアの出発点ともなる重要な論文である。（同時に、現在の量子コンピュータ技術の到達点は、ある意味、この論文への「回帰」として特徴付けられるのは、興味ふかいことである。）

ファインマンは、次のように述べる。

「コンピューターが、正確に自然と同じように振る舞う、正確なシミュレーションが存在する可能性について話そうと思う。 」

「それが証明されて、そのコンピュータのタイプが先に説明したようなものであるなら、必然的に、有限の大きさの時空の中で起きる全てのものは、有限な数の論理的な操作で正確に分析可能でなければならないことになるだろう。」

「量子論的なシステムは、古典的な万能計算機で、確率論的にシミュレートされるだろうか？」

「 別の言い方をすれば、コンピューターは、量子論的なシステムが行うのと、同じ確率を与えるだろうか？　コンピューターを今まで述べてきたような古典的なものだとすれば（前節で述べたような量子論的なものではないとすれば）、また法則はすべて変更されないままで、ごまかしもないとすれば、答えは明らかにノーである。」

「それは、新しいタイプのコンピューター、量子コンピューターで可能になるだろう。」

「 私が理解する限りでは、それは量子論的なシステムによって、量子コンピューターの要素によって、シミュレート出来るようになることは、いまや、明らかになった。それはチューリング・マシンではない。別のタイプのマシンである。」