未来の情報通信を変える計算機
−量子計算と計算機の物理−
1．驚異の計算力の脅威
量子計算機が脚光を浴びたのは、一昨年のある日Internet上で一篇の未発表原稿が公開されたことに始まります。それは、ﾓAlgorithms for quantum
computation: Discrete log and factoringﾓと題されていました。後に、コンピュータサイエンスの権威ある会議で発表されることになるこの原稿の内容は、仮想的な計算機を仮定することにより、因数分解の問題が“解ける”ようになると主張していました。これが、なぜ驚異で、脅威となるのかを理解するためには、問題が“解ける”ということの意味と因数分解の問題の重要性を知る必要があります。
因数分解の重要性は、RSA暗号という現在もっとも安全だと思われている公開鍵暗号の基礎になっているところにあります。公開鍵暗号とは、暗号の鍵を大勢の人に配付する有力な方法で、現状のネットワークのセキュリティ上においても必須な技術です。その安全性は、大きな素数を掛け合わせた数の因数分解（以降簡単に因数分解と書きます）が、ほとんど不可能なほど難しいというところによっています。もう少し具体的に表現しますと、因数分解するべき数が大きくなる（2進表示のビット数）につれて、解くために必要な最小時間が爆発（指数）的に増えていくということです。つまり、ある8ビット表示の数の因数分解が1時間で解ける計算機に、16ビットの数を与えると28倍で256時間かかり、32ビットの数とすると224倍で約1963年間かかるということになります。もし、ハードウエアの進歩で、224倍計算機が速くなっても、64ビットの数で用意すれば、49万年かかるようになります。これが、“解けない”ということなのですが、新しいアルゴリズムが発見されて、指数関数的でなくたかだかべき乗時間で解けるようにならないという保証もありません。そうすると、因数分解は“解ける”問題となりRSA暗号は安全なものでなくなるわけです。そんなやっかいな（ネットワークセキュリティの観点で）アルゴリズムは発見されそうになかったのですが、その太平を醒ましたのが、冒頭に記した原稿なわけです。そのポイントは、使う計算機をいままでの概念にないものに変えるという、ちょっと反則っぽいところにあるのです。しかし、その計算機が現実のものとなれば、ルールは拡大されて、反則でなくなるでしょう。この計算機が量子計算機なのです。いまのところ実現されていませんが、将来的に実現の可能性が多いにありそうなのです。
2．古典計算と量子計算
従来概念に従った計算機と、量子計算機はどこがちがうのでしょうか？ 世の中には色々な計算機がありますが、それらはほとんどチューリングマシンという仮想機械に置き換えることができます。
チューリングマシンは、記憶用テープとその上を移動し読み書きできる機能をもったヘッドとで構成される原始的な計算機で、通常の論理的動作をする計算機であれば、その全てを模倣することができます。もちろん、実際に原始的な計算機に置き換る意味はないのですが、大事な点は、チューリングマシンで模倣できる計算機であれば、どんなに巧妙に設計されても“解ける”問題の範囲はチューリングマシンと同じになるという点です。
チューリングマシンは、仮想機械とはいえ物理系を想定していたわけですが、古典的な範囲に限定しています。これを、量子的な範囲にまで拡張したものが量子チューリングです。古典的チューリングマシンが、テープや、ヘッドの内部状態として、0.1の2状態のbit信号をもっているわけですが、その量子版は、それに加えて、2つの状態の、あらゆる割合での重ね合わせをもつことができ、量子力学的なこの状態の表現は、α｜0>+β｜1>となります。｜0>,｜1>は、おのおの、0.1の状態を表す量子状態で係数α，βは、成分の割合を表します。α＝0，β＝1や、α＝1，β＝0の場合には、古典的なbitのとりうる状態になります。その他の状態、たとえばα=βだったとすると、この量子的bit（qubitと呼びます）は、0と1の両方の状態を半分づつもっていることになります。この｜0>,｜1>の重なりあった状態は、実際はどちらかにあるのだけれども我々が知らないだけ、という確率的なものでもなく、常に両方の間を往き来しているというものでもありません。本質的に半分づつ状態が重なっている、古典的には表現が不可能な状態です。光の偏光がよい例です。45度の方向に直線偏光した光は、垂直の偏光フィルタを通しても、水平の偏光フィルタを通しても半分だけ透過してきます。つまり、水平偏光、垂直偏光の光の成分を半分づつもっているということです。光は、光子という量子（最小のエネルギー単位）からできていますが、光子一つ一つが、そのような重ね合わせになっています。この状態の重ね合わせによる表現の豊かさが、量子チューリングマシンの利点の一つです。探索問題を解くために全ての可能性を試したいとしたら、古典的な場合は、その可能性の数だけ試さなければなりません。量子チューリングマシンならば、qubitを｜0>+｜1>に準備することによって、全ての可能性を均等に含んだ一つの状態を作ることができます。この状態を用いることによって、並列的な計算が可能になるのです。
もう一つ大事な特徴は、可干渉性です。この性質によって、一つの量子状態が分身のようにいろいろな可能性を検索していき、求める結果に到達するときに再び合体して、それを指し示すことが可能になります。量子力学の言葉でいいますと、最終状態では、求める答えを示す状態をもっとも大きく含んだ確率分布が実現し、これを観測することによって、高い確率（間違うこともあるが、数度やればほとんど当たる）で、確率最大の状態が選択される、となります。この過程は、波束の収縮といわれる量子力学におけるもっとも興味深い現象ですが、これが計算の「高速」化に貢献しているのです。この分布が量子的でないとすれば、確率分布の最大のところを比較検索しなければならず、「解けない」問題になってしまいます。このため、一見同じようなことができそうな、普通の光や電波のような古典波動では、量子計算ができないのです。
このように、大きなインパクトが約束されている量子計算機ですが、完全に量子的な計算機はできないので、実現不可能だという悲観論もあります。しかし、完全な量子性がなければ何もできないというほうが、非現実的です。量子性が悪くなれば、性能が低下するでしょうが、その定量的評価が必要です。量子系をコントロールするときに、どれだけ量子性を壊すか、それがどの程度計算機の能力を損なうか、ということを定量的に考察することは、量子計算機の設計指針の第一歩と考え、我々の研究課題の一つとしています。また、逆に、古典的な計算機はどこまでいけるのか、という原理的な限界を押えることも大事な研究課題です。
3．自然による計算と、計算機の物理
古典チューリングマシン的計算は、論理手順を自動的にしただけの、いわば人為的計算ともいえるものです。量子計算は、量子力学の基本原理という自然の摂理を利用することにより、それを超える性能を得たわけですが、量子力学でない、別の自然の摂理を利用することもできるでしょう。たとえば、古典的であっても、高次元、非線形運動を利用することによって、特異な計算能力が得られるのではないかということも我々の検討課題です。
このような新しい自然による計算に期待する性能は、量子計算機のように速度である必要はありません。たとえば、エネルギー消費が0の計算機でもよいでしょう。本来、計算機を物理的に見たときの基本特性は、速度、エネルギー消費、サイズ、3つがあり、計算精度をパラメータにして、各々が相反関係にあるからです。優れた計算機としての評価は、これらの特性を総合して、判断されるべきなのです。
究極的な計算機を一般的に考えていくためには、このような総合的な評価指針を定量的なかたちで与えることが必要なのですが、そのためには、計算機の使用者の要求など、人間の行為、さらには、社会的要請まで考えることが必要になり、単純な物理的評価ではすまないため、これも大きな研究課題になっています。
Copyright(c)2002（株）国際電気通信基礎技術研究所
