NTT物性科学基礎研究所 R&Dフェローの高柳英明氏

公開鍵暗号方式をご存知だろうか。これは情報の秘密通信方式の一つで、暗号の安全性の根拠として巨大数の素因数分解が現在のコンピュータの能力では現実的な時間では行えないこと(因数分解問題)、などを用いている。インターネットが普及するにつれて、この公開鍵暗号方式はネット上の秘密情報通信の仕組みを担うようになってきており、社会的に重要になってきている。1994年、AT&T Bell研究所のPeter W. Shor氏が、量子コンピュータを使うと公開鍵暗号を解くために必要な因数分解問題と離散対数問題を高速に解くことができるというアルゴリズムを発見した。この事は現在の秘密情報通信の安全性を根底から覆す可能性があるということで大きな話題となり、特に米軍などはその実現可能性について大きな関心を抱き、積極的に研究を進め始めた。ここで表舞台に表れてきた量子コンピュータとはいかなる機械なのか。日本において量子コンピュータの研究をリードしているNTT物性科学基礎研究所 R&Dフェローの高柳英明氏にお話を伺うことができたので、ご紹介していきたい。

○量子コンピュータとは

「量子力学的重ね合わせの状態を使って超並列計算ができる」
量子コンピュータを端的に表す言葉として高柳氏が述べた言葉である。量子コンピュータというのは、超高速に動作する素子を使ったコンピュータではないという。ひとつひとつの素子が高速であるわけではなく、量子力学的重ね合わせの状態を使って超並列計算を行うことができる超高速コンピュータである、ということだ。

古典物理に沿っている現在のコンピュータは、古典ビットが初期状態としてあり、これに複数の演算がなされて、結果の古典ビットが得られる。これに対して量子コンピュータでは量子ビット(qubit)が初期状態としてあり、複数の演算がなされて結果の量子ビットが得られる。ここまでは古典コンピュータと似ているが、量子ビットは古典ビットと異なり、複数の重ねあわされた量子状態に対応しているところが量子コンピュータの特徴であるという。では、重ねあわされた量子状態とはいかなるものなのだろうか。

極めて微細なスケールの世界で顕在化してくる量子力学の世界では、複数の状態が同時に実現している。たとえば、電子はスピンという属性を持つが、量子力学の世界では一つの電子がスピン上向きの状態と下向きの状態を同時に実現している、ということが起きる。これは、スピン上向きの状態と下向きの状態が重ねあわされた量子状態と呼ばれる。これはたとえて言うと、一台の車が右向きに走っている状態と左向きに走っている状態が同時に成立しているということになる。このように、現実の我々の世界では目にすることができず、同時に成立することがありえないと思われる事象が、量子力学の世界では同時に実現しているとみなされている。

しかし実際我々が見る(観測する)状態というのはどちらかに確定しているので、複数の重ねあわされた量子状態を観測すると、そのうち一つの状態が確率的に観測されると解釈する。そして、観測される確率は量子状態の重ね合わせの係数に従って定まっている(ここで、その重ね合わせの係数は、複素数である)。量子コンピュータではこの量子力学的な重ねあわされた状態をqubitという情報のまとまりと考え、このqubitに演算を行うことで計算を進めていく。ここで、"演算"の物理的な姿とは、qubitを担う物理系に対して外からパルス電波を与えたりする操作を指す。qubitを担う特定の物理系では、パルス電波を与えることがqubitに対して量子力学的演算操作をすることになるのである。

例えば4bitの素子で表現できる全ての状態についてある演算を行うという問題を考えよう。古典コンピュータでは4bitで表現できる16の状態のうち一つについて1回づつ演算を行い、合計16回計算して16通りの結果を出力する。量子コンピュータでは4bitで表現できる16の状態を同時に実現している重ねあわされた量子状態に対して1回の演算を行い、結果を出力する。自明なように処理bit数が増えるほど、量子コンピュータの威力は大きくなる。こうしたことから量子コンピュータが超高速であると言われているようだ。

しかしここで一つの疑問が現れてくる。量子力学的重ね合わせの状態は観測することによって一つの状態に確定してしまう。仮に入力時に複数の重ね合わせの状態を作り出して演算を行い、最終的に複数の重ね合わせの状態が結果として得られたとしても、その最終結果を見よう(観測しよう)とすると、重なり合った結果の量子状態のうちの一つしか得られない。結果の量子状態が持つ全ての情報を一度に得ることはできないのだ。この問題はどのように考えられているのだろうか。

○量子コンピュータのアルゴリズム

「量子コンピュータの発展には、量子コンピュータで使えるアルゴリズムが必要です」と高柳氏は述べる。つまり、上述のようなプロセス(1回の測定)によって所望の結果が得られるような量子コンピュータ向けの計算アルゴリズムが必要だというのだ。量子コンピュータに注目を集めるきっかけとなったShorのアルゴリズムは、こうした問題を解決し、結果を測定するプロセスを通じて所望の結果が得られるようになっているという。Shorのアルゴリズムは量子コンピュータに適用できる現実的なアルゴリズムということで、量子コンピュータの教科書には必ず登場するものである。

このアルゴリズムは、量子演算を繰り返すことで、所望の状態に量子状態が強められていくものとなっている。(任意に小さくできる誤り確率を含んだ)確定的な結果が出力されるアルゴリズムなのである。正しく因数分解されたかどうかの確認は古典コンピュータを用いた逆算により簡単に行うことができる。この確認処理を含めてトータルで素因数分解の問題を解くことができるように設計されている。

数"N"の素因数分解問題の処理ステップ数の評価が高柳氏により示された。Nの素因数分解は1) 数列Fn=m^n(mod N)を作る。 2) 数列Fnの周期rを求める。 3) Nとm^r/2±1の最大公約数dを求める という3つのステップで解かれるという。ここで、一番時間がかかるのがステップ2)の数列の周期を求める問題で、これはフーリエ変換という手法を用いることになる。このフーリエ変換の処理時間を評価してみると、N=2^pであった場合、不連続フーリエ変換の方法では2^p×2^p、高速フーリエ変換では2^p×p、量子フーリエ変換ではp×(p+1)/2となるという。実際、p=64としたとき、高速フーリエ変換では1.18×10^21になるが、量子フーリエ変換では2080になる。現在のパソコンのレベルである1ステップを1nsで実行すると考えたとき、高速フーリエ変換では1万年、量子フーリエ変換では2μsとなる(!)。量子コンピュータが因数分解問題に対して極めて強力であることがわかる。

(古林高)

【レポート】量子コンピュータとは(2) - 鉄腕アトムの時代に向けて に続きます
http://pcweb.mycom.co.jp/news/2003/01/01/06.html

NTT先端技術総合研究所
http://www.sctlg.ecl.ntt.co.jp/profile/

NTT R&Dフェロー 高柳英明氏
http://www.sctlg.ecl.ntt.co.jp/fellow/takayanagi.html