量子力学の反常識が創りだす量子コンピューティングの世界
—量子コンピュータの頭脳としての量子アルゴリズム—

コンピュータ理工学部 コンピュータサイエンス学科 外山 政文 教授

量子コンピュータの頭脳としての量子アルゴリズム

 未来のコンピュータと言われる量子コンピュータ。量子力学の原理を動作原理とし、従来の不可能を可能にするテクノロジーです。現在のコンピュータでは宇宙の年齢ほどの長い時間がかかってしまう計算でも、極めて短時間で解いてしまいます。しかしその実現には、コンピュータ上で効率よく機能する量子アルゴリズムが不可欠です。まだ誰も触れたことのないコンピュータを動かすための、全く新しいロジック、その最先端を研究する外山政文先生に、お話を伺いました。

2つの状態が重なりあった量子ビット

 従来のコンピュータ(量子コンピュータに対して「古典コンピュータ」と呼びます)では、全ての情報は0と1の組み合わせで表現されます。これを「ビット(bit)」と呼びます。古典コンピュータの中では、このビット列を変換し異なる状態にすることを繰り返して計算を行っています。例えば、5に1を足して6にするという計算は、5の2進数表記「101」の一番右側の1を0に、次の0を1にするという変換によって「110」を得るという形で理解されます。この変換規則は、論理回路と呼ばれるもので自由に作ることができます。

 現在主流となっている量子コンピュータの原理はドイチ(David Deutsch、1953-)という物理学者によって考案されたものです。その量子コンピュータも、同じような「量子ビット」を操作する機械ですが、量子ビットは上記の古典ビットとは違い、0か1かだけではなく、その“中間的”な状態も取ることができます。中間というと0.5などの値を思い浮かべるかも知れませんが、決してそうではありません。0の状態と1の状態を、同時にとることができるのです。一見、常識に反しているように思えますが、それは量子コンピュータが量子力学の原理に基づいているためです。量子力学は、ミクロの世界での物質の振る舞いを明らかにする力学で、直観とは全く異なる世界像を受け入れることを私たちに強います※コラム参照。だからこそ、量子コンピュータは従来とは全く異なるコンピュータになるのです。

 量子コンピュータのビットは|0>、|1>のようにケットと呼ばれる特殊な括弧の記号を使って表 現されます。これは古典ビットの0、1とは違い、いわゆる量子状態にラベルをつけたものです。この量子状態というものに量子力学の不思議が凝縮されています。1つの量子ビットは、例えば1/√2│0>+1/√2│1>※1といった、|0>と|1>が同じ確率で重なり合った状態をとります。これが先に述べた“中間的”という意味です。ただし、重なり合った状態が保たれるのは、誰も見ていない状態に限り、その状態を観測すると50%の確率で|0>に、50%の確率で|1>になります。量子力学では、これを測定による状態の収縮と言いますが、実は、これが量子計算にとって重要な要素になります。

 古典ビットは、例えば、3つ並べた<000>や<010>といった個々の情報を個別にしか扱えせん。しかし、量子ビットでは、|000>から|111>まで、8つの全ての状態を同時に扱えるのです。40個量子ビットを並べれば、扱える状態は1兆にもなります。この1兆個の状態に対してある処理を行うと1兆個の重ね合わさった全ての状態に対して並列的にその処理が行われます。

 もちろん、1兆個の状態で同時に処理が行えたとしても、一度測定すれば、その中のどれか1つの状態が確率的に選択されてしまいます。それでは意味がないので、最終的に、欲しい答の状態だけを取り出すために、欲しい答が測定により選択される確率を高めることが必要になります。このように、量子計算では測定が決定的な意味を持ち、測定という処理に至るまでにいかにして重ね合わせ状態を効率よく処理するかを考えるのが量子アルゴリズムの研究です。

※1 1/√2は確率の重みを表す係数。2乗すると確率になる。ここでの+は、足し算ではなく、状態が重なり合っていることを示す。

ただの箱に命を吹き込む量子アルゴリズム

 量子コンピュータは、残念ながらまだ完成していません。実験機はできていますが、実用的な量子コンピュータは実現できていないのです。

 さらに、量子コンピュータが仮に完成したとしても、先に触れたように、量子アルゴリズムがなければ何の意味もありません。私たちの使っているパソコンである計算処理をする場合でも、目的に対して最適な処理のルールを与えることではじめて欲しい答が得られます。このルールこそがアルゴリズムです。

 古典コンピュータがビットを論理回路で操作して計算を行うのと同じように、量子ビットは、量子コンピュータの中にある論理回路で操作されます。具体的には、 |0>と|1>を入れ替えたり、 |1>の符号を反転させて-|1>にしたり、|0>を1/√2│0>+1/√2│1>のような重ね合わせにするなど、様々な操作が可能です。このような操作を行うものを「量子ゲート」と呼び、これらを組み合わせたものを量子回路と呼びます。そして、どの量子ゲートをどんな順番で組み合わせれば望む処理を実現できるかというところが、まさに量子アルゴリズムそのものなのです。

 量子コンピュータの研究というと、実用的な量子ビットを物理的にどう実現するかを想像しがちですが、実際には量子ビットをどのように操作して目的の状態に持っていくかというアルゴリズムがなくては量子コンピュータの実現はありえません。

 実用性があると言われる量子アルゴリズムは、現在わずか2種類だけです。一つは、ショアのアルゴリズムといって、大きな桁数の素因数分解に威力を発揮するアルゴリズムです。そしてもう一つが、私が最近その改良を目的として手がけたグローバーのアルゴリズムです。

グローバーのアルゴリズムの欠点を克服

 グローバーのアルゴリズムは、量子探索アルゴリズムと呼ばれます。これは、大量のデータの中から、ある条件に合致するデータを見つけるためのアルゴリズムです。

 例えば、3つの古典ビットの並びを入力できるブラックボックスを考えます。これに、特定の1と0の並びを入力したときのみ、ランプが光るとします。正解は<010>かもしれませんし、<110>かもしれません。取り得る状態は 23=8通りなので、古典コンピュータで正解を探すには、最大で8回、平均でも4回は試行して、条件と合致するか確かめなくてはいけません。ところが、量子コンピュータではこの8通りの場合をまとめて一度に量子回路に入力できます。これは、先に述べたように、量子コンピュータでは8通りの状態の重ね合わせを一度に並列に処理出来るからです。ただし、その1回の試行後に測定したのでは、(答が仮に1つあったとして)必ずしもその正しい答えが得られるとは限らず、間違った答えが得られる確率がかなり大きいのが普通です。そこで正しい答えを得るために、さらに連続して複数回同じ量子回路に入力を繰り返す必要があります。そうすることにより、量子干渉という量子力学特有の干渉効果により正しい答えを得る確率を大きくすることができます。グローバーのアルゴリズムは、 N個の取り得る状態に対し、√N回程度の回数の連続入力で求めるデータを見つけることができます。今の例の場合は2〜3回程度の繰り返し入力で、高い確率で1個の正しい答えの探索に成功します。

 データ数が増えれば増えるほど、グローバーのアルゴリズムは威力を発揮します。100億個のデータを探索する場合、古典コンピュータは平均で50億回の探索が必要なのに対して、わずか10万回程度の探索ですむのです。

 問題は何回探索を行うのか、すなわち何回量子回路に通すのかを決定するためには、「00……00 」から「11……11 」という全データの中で「目当てのデータが何個あるのか(隠されているか)」が分からなくてはいけないということです。グローバーのアルゴリズムでは複数回の探索で確実性が上がりますが、最適な探索の回数は、全体のデータに対する欲しいデータの数で決まります。探索すればするほど確実性が増すように思うかもしれませんが、この量子アルゴリズムでは、最適な探索数よりも多く探索すると、答が見つかる確率はかえって低くなってしまうのです。

 そこで考えたのは、求めたい状態の数を一切知らなくても、いつでもほぼ確率1で答えを出してくれるアルゴリズムの開発でした。私が最近発表した「多重位相整合」と呼ばれる手法では、探索回数は予め一定の回数に決めておきますが、欲しい状態の数を知らなくても、1または極めて1に近い確率で欲しい状態を見つけることが出来ます。いわば、グローバーのアルゴリズムの改良版であり、応用的にも非常に意義があります。ここで注意して欲しいのは、探索回数と探索の成功の確率および探索に必要な多重位相パラメータは、古典コンピュータ上でのシミュレーションで予め決められる、ということです。これが重要なポイントです。ここでは詳しく立ち入りませんが、この改良アルゴリズムの探索効率と量子ビット間の「量子絡み合い」(エンタングルメントと言う)による「非局所相関」とは複雑な関係があることが分かっています。これは、「量子力学の非局所性」という量子力学の最も摩訶不思議な話です。

 これは、「実用的な量子コンピュータができたとしたら」という仮定に基づいた、とても数学的で抽象的な分野の研究です。今はまだ理論のみに留まっていますが、やがて量子コンピュータのハードウェアが実現し、この研究が目に見える形で役立つ日がやってくることを期待しています。

※コラム:量子力学の不思議と面白さ

 量子力学は、ミクロの世界を扱う物理学で、20世紀初めに生まれ1930年代には一応理論的完成を得た学問分野です。これまで、量子力学が解決できなかった問題はないとまでしばしば言われるほど成功を収めてきました。しかしその原理に関しては未だにはっきりしない問題が残されています。不確定性原理に代表されるように、ある意味で“あいまいさ?”が最大の売り物であった自然科学としての量子力学が、今や確定的な結果に導く情報処理科学へと変貌しようというのだからその研究は一筋縄では行きません。量子情報では量子力学の原理が情報処理や量子コンピュータのプロトコルや動作原理と直結しています。そして、量子情報の研究の進展に伴って逆に量子力学の原理的な問題が再検討されるという大変おもしろい時代を迎えています。

 この量子力学が記述するミクロの世界では、私たちが見慣れたマクロな世界の常識が通じません。例えば、ミクロの粒子の挙動は確率的にしか予測ができないし、測定して初めてミクロの粒子の状態が確定します。これをミクロの粒子のスピンという量で説明しましょう。

 ミクロの粒子は、スピンと呼ばれる量を持っています。歴史的な経緯でスピンと名付けられていますが、古典的な自転というイメージで捉えるのは間違いです。このスピンこそ最も量子力学的な量で量子力学でしか記述できません。例えば電子の場合、スピン1/2を持っていると言いますが、この電子のスピンの基本的な状態は2つです。この2つの状態を右回りスピン状態、左回りスピン状態、或いはもう少し量子力学的に上向きスピン、下向きスピンとも言ったりもしますが、それはあくまでも方便であることに注意してください。例え話として、この電子を箱の中に入れ磁場をかけたとします(これは正に最もシンプルな量子ビット系のトーイモデルです)。すると誰かが箱を開けて観測するまでは、例えば「右回りの状態が50%、左回りの状態が50%で重なり合っている」という奇妙な状態にすることができます。この状態の重ね合わせは、箱の蓋を開けて観測することによってどちらかに100%確定します。このように状態が1つに定まるプロセスを測定による「収縮」と呼びます。

 「重ね合わせ」という概念は、日常経験からは直観的には理解できません。現に量子力学の研究者の間でも、重ね合わせは存在するが実在はしないとか、重ね合わせ状態が収縮してある一つの状態が 確定すると残りの状態はどうなったのか、とか未だに様々な一見奇妙な議論が為されます。例えば、複数の並行世界が重なりあっていて、観測する度に世界が分岐しているというSFのような解釈(多世界解釈)も存在するくらいです。これは量子力学の解釈問題といって古くて新しい“非実用的”だけれども我々を魅了してやまない“永遠?”の課題です。先に触れたドイチがこの多世界解釈の代表的な推進者です。

 この量子的な状態の重ね合わせと測定による状態の収縮という奇妙な事象こそが、量子コンピュータの根本原理になっています。ドイチにとっては、実用的な目的というより上記の多世界解釈を実証するのが、量子コンピュータ開発の目的だったという話もあります。

アドバイス

 数学や物理の勉強ではただの暗記ではなく意味を理解することが重要です。100個の公式を丸暗記するより1つの公式の意味を理解することの方が今のみなさんには大切です。

 例えばxを微分したら1になる、という計算があります。この計算はできても、なぜ1になるのか?それを直線の傾きというイメージと結びつけて理解することが必要です。もちろん、一人で本質的な理解にたどり着くのは大変かも知れません。しかし、一つうまい方法があります。それは“先生を困らせる”ことです。先生を困らせるなどと言えば叱られそうですが、要するに、納得できるまで質問をすることです。その議論を通じて本質的な理解に到達出来ることもあります。何よりも先ず知的好奇心を旺盛にすること、これに尽きます。

 最後に、この記事を読んで訳が分からないことが多くて戸惑った人もいるでしょう。しかし、大学ではこのようなことを勉強出来ると意欲を持ってください。

コンピュータ理工学部 コンピュータサイエンス学科 外山 政文 教授

プロフィール

理学博士。現在の専攻は量子論を中心とした数理物理学、量子情報物理。元々の専門は中エネルギー核物理学だが、関連領域として量子情報物理の研究を行い、量子コンピュータの量子アルゴリズムの改良などに成果をあげる。最近の興味は非可換量子力学。奈良県立御所工業高校OB。

PAGE TOP