量子計算学習ノート - 計算モデル

---

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。

---

どんな大きな数でも2つの自然数を足し合わせるといった手法を私たちは学校で学ぶ。これも立派なアルゴリズムである。ではこの何らかのタスクをするときのアルゴリズムを数学的に厳密に定義することができるだろうか。この答えはYesであり、実際にチャーチとチューリングという数学者が、アルゴリズムの近代的理論と計算機科学の近代的理論の基礎を作った。

この理論が生み出されるきっかけになったのがヒルベルトの解決問題だ。これは任意の数学問題に対し、それを解くことのできるアルゴリズムは存在するだろうか？ という問いである。この問題に対してチャーチとチューリングは否定的な結論を下した。つまり少なくともある数学問題に対し、アルゴリズム、要は計算によって解くことができない問題が存在することを示したのだ。この洞察を示すためにチャーチとチューリングは、アルゴリズムを扱うときに私たちが直観的概念としていたものに対し、数学的に厳密な定義を与えたのだ。それがチューリング機械だ。

以降、計算理論を展開するためのアプローチとして2つのアプローチをとることになる。1つは前述のチューリング機械であり、計算タスクを行うアルゴリズムという考えを数学的に取り入れるためにチューリングによって提唱された。もう1つは回路モデルを通じたアプローチである。これは特に私たちにとっては量子コンピュータを研究する準備として便利なものとなる。

これらのアプローチ、計算モデルは表面上別物に見えるが、実は等価であることがわかっている。しかし、等価な異なるアプローチがあることによって、特定の問題に対して異なる見通しが与えられるため、興味ある問題に対する考察がより深くなることがある。