西野哲朗

コンピュータと量子力学の出会い

西野哲朗『中国人郵便配達問題＝コンピュータサイエンス最大の難関』講談社選書メチエ

文化大革命で「下放」された、ある中国の数学者は、毎日、郵便配達をしながら、どうすれば最短距離で配達できるかを考えているうちに、これが数学的にきわめてむずかしい問題であることを発見したという。この問題は、一見単純に見えるが、通る道が増えるにつれて組み合わせの爆発が起こり、恐ろしく複雑になる。本書は、こうした計算複雑性の問題と解法（アルゴリズム）を研究する「理論計算機科学」の最近の話題を紹介したものである。

中国人郵便配達問題のような本質的に複雑な問題（ＮＰ完全問題）は、日常生活にもよく見られる。たとえば将棋のようなゲームの必勝法を求める問題は、それを解くことは論理的には可能である（解は存在する）が、実際には計算量が膨大なため、不可能である。人間の脳は、日常的にこうした問題を何気なく解いている。それはコンピュータのようにしらみつぶしに調べて最善を求めるのではなく、経験によって「定跡」を学習して「比較的よい手」を見つけるわけだ。このような学習メカニズムをコンピュータに実装したのが「ニューラル・ネット」である。本書ではその最新版である「ニューロイダル・ネット」を紹介し、言語の学習に応用している。

本書の中心テーマは、著者の専門である「量子コンピュータ」である。これまでのすべてのコンピュータは、一九三六年にアラン・チューリングが発案した「チューリング機械」の変種だが、量子力学を応用すれば、これとはまったく違う構造のコンピュータを作ることができるかもしれない。古典力学では物質の状態は一意的に決まるが、量子力学では、素粒子の状態は多くの波の「重ね合わせ」としてあらわされる。理論的には、この一つ一つの波によって計算を行えば、多数の計算を並列に行うことができる。一九九四年、こうした方法で素因数分解を現在のあらゆる方法よりも速く解くアルゴリズムが発見された。

これは、ビジネスの世界でも注目されている。「電子商取引」で本人確認などに使われるＲＳＡ暗号は、素因数分解を行う効率的なアルゴリズムがないという前提にもとづいているからだ。量子コンピュータによって今までよりもはるかに速く素因数分解が解ければ、現在の暗号方式はすべて見直さなければならないかもしれない。今のところ、分子レベルの素子を実現する半導体技術がないため、まだ暗号が破られる心配はないが、アルゴリズムの存在が証明された意味は大きい。

本書は、この分野への入門書としてやさしく書かれているが、いろいろな話題を紹介しているため、一つ一つは必ずしもわかりやすいとはいえない。特に量子コンピュータについては、量子力学の基本的な知識がないと理解しにくいかもしれない。量子力学が常識と異なるのは、素粒子の状態が一つに決まらず、確率的に分布しているという点である。これが観測上の限界によるものにすぎないのか、物質の本質的な性格なのか、という「観測問題」は、半世紀以上にわたって続いている大論争だが、量子コンピュータは、これに決着をつけようとしている。それは、電子の中に重ね合わされている多くの「並行宇宙」によってそれぞれ計算をさせることができる、という量子力学の「多世界解釈」を実証するものだからである。

物理学者は、観測問題を単なる「哲学論争」として軽視してきたが、このような実用とは最も遠い問題から画期的なコンピュータが生まれる可能性があるのは興味深い。著者もなげくように、自然科学の研究が工学系にかたより、基礎研究が軽視されている限り、日本からは歴史を変えるような技術革新は生まれないだろう。

HOME