第4回、量子コンピュータ(第3回)


前口上

まずは、大幅にアップロードが遅れたことをお詫びいたします。

先日、国際会議にいってきました。量子力学の基礎に関する国際会議なのですが、そこでは量子コンピュータをいかにして実現するか、というのが、一つの大きなトピックスになっていました。量子コンピュータという話題が、最先端のトピックスであり、しかもそれが、量子力学やそのほかの分野と大いにつながりがある、本質的に面白いテーマであることを再認識しました。

最先端のテーマをわかりやすく解説するのは、本当に深い理解が必要で、私のような者が負えるような課題かどうかは、わかりませんが、なんとか解説を試みることにします。

今回は、いよいよ、最後の目標である、「量子コンピュータによって、因数分解を効率的に行えること」(シューアの定理)の証明をみてみることにしましょう。完全な証明をすべてここで示すことは、分量の関係で不可能なので、ここでは、概略だけをさらっていくことにします。

因数分解を行うには、何をすればいいか

因数分解を行うために、どのようなやり方で計算を行うか、を考えることが重要です。計算のやり方のことを、計算のアルゴリズムといいます。因数分解の計算アルゴリズムはいろいろ考えられますが、量子コンピュータに最適なアルゴリズムを選ぶ必要があります。ここでは、シューアが選んだアルゴリズムを紹介することにしましょう。

因数分解を行いたい正の整数をNと書くことにします。この数をN=mnと、二つの1より大きい整数m, nの積でかけることを見つけることが目標です。

まずNと互いに素である正の整数xを探します。xを見つけるには次のようにします。

(1) 適当な整数x(x<N)をとってくる。(コンピュータの中ででたらめな数を生成することができます。これを乱数といいます。乱数を使えばでたらめに整数xをとることが可能です。)
(2) もとの数Nと新しくとったxの最大公約数を計算する。(最大公約数を効率よく計算するユークリッドの互除法という名のアルゴリズムが存在するので、これはすばやく行える。)
(3) それが1なら目的のxである。(もし1でないなら、その公約数はNの因数であるので、因数分解ができたことになる。)

このように決めたxを用いて、

となるような整数rをなんとか計算します。計算方法は、次の章以降で詳しく述べます。ここではなんとかrが計算できたとして、その後を考えましょう。まずrについて、以下の条件が満たされているかどうかをチェックします。

(条件A)
(1) rは偶数である
(2) (1)の条件のもとで、さらに次の二式が成立する

まず、この条件が成り立つかどうかは、効率的に計算することができます。つまり、mod Nのもとでのxのr/2乗がどのようになるか、ということは、計算時間が数xの桁数の多項式時間でチェックできることが知られているのです。(証明は略しますが、要はrを二進数表示し、その各桁ごとにmod Nの元でのx^aの値を計算して、最後に足す、というようなことをします。)

この条件Aが満たされなかったときには、別の整数xを探して、再びrを計算し、条件Aを満たすものが見つかるまで繰り返します。

こうして条件Aが満たされたとしましょう。すると、まずは式

より、rが偶数であることをつかって、

と変形することができます。この最後の式は、

を意味します。(kは整数)一方、条件Aの(2)は、

を意味します。これらの3式から、がNの因数であることが結論できます。(任意課題:これを示せ。)こうして、Nの因数を見つけることができました。

まだが不十分な部分が残っています。それは、まずNとxから

となる整数rをいかにして見つけるか、です。ここに、量子コンピュータの威力が発揮されます。これは次の節でみることにします。

それともう一つ。途中で、条件Aを満たすまで、xを変えていくのですが、もし条件Aを満たすxがとても少なかったら、条件Aを満たすxを見つけるのに時間がかかりすぎて、効率的に計算ができません。でも、幸運なことに次の定理が知られているので、この点は大丈夫なのです。

(定理) Nを奇数とし、Nと互いに素なx(<N)の数をMとする。このM個のうち、条件Aを満たすxの数は、M/2個以上ある。つまりでたらめにNと互いに素な数xをとったとき、それが条件Aを満たす確率は1/2以上である。

この定理があるので、例えば10回までに条件Aを満たすxがみつからない確率は、1/1024より小さくなり、ほどんどみつけていることになります。

この定理は中国の剰余定理という名の整数論では有名な定理を用いて証明されるのですが、かなり長くなるので、この講義では証明を省略します。

シューアの定理の核心部

因数分解で残された問題は、与えられたN, xから

を満たすrをみつけることです。量子コンピュータの講義の第一回目でのべたように、このようなrを普通のコンピュータで効率よく解くことはできません。効率よく解けない、ということは、Nが大きくなると、計算に時間がかかって、事実上解けなくなることを意味します。いいかえれば、もし量子コンピュータによって、この問題を効率よく解くことができれば、因数分解の計算が事実上始めて可能になるのです。

シューアのアルゴリズムの核心は、この問題を、量子ビットの重ねあわせ状態をうまく使って解くことです。

それには、前回の講義で紹介した、離散フーリエ変換をつかいます。記号の整理をしましょう。二進法で表示された量子ビットの状態を例えば| 11011>などとかき、これと同じ状態で、状態を10進法に書き直したものを、| 27)などとかくことにします。また、数を表現するのに必要なビット数をnとします。さっきの例では、n=5です。

前回紹介した量子ビットの操作によって、まず離散フーリエ変換を行ない、状態

という状態をつくります。さらに、状態|a)に、重ねあわせ状態を保ったまま操作を行ないます。aがかかれている量子ビットの値を用いて、xのa乗のmod Nの元での値(要はxaをNで割った余り)を計算し、その結果を再び書き込みます。つまり、

という状態をつくります。この計算は、古典コンピュータでも効率的にできますし、もちろん量子コンピュータでも効率的に実行できます。しかも、重ねあわせ状態をそのままにして、この計算が可能なのです。(量子コンピュータでも、ANDやORなど、古典コンピュータの基本演算が実行できることに注意。)

ここで、観測を行うのです。するとどうなるか?ポイントは、まず後ろの|c)はともかく、前の| xa mod N)というところです。この部分を観測したとき、実は、異なるaに対しても、xa mod Nの値が同じになることがある。もっとはっきりいうと、異なるa, a'に対して、

となるのです。これがポイント。この関係は、実は、

となるような最小のrをとってくると、この式の両辺をk乗し、さらにxのa'乗を掛けて、

となるので、

が成り立つのです。(任意課題、ここでの証明はまだ論理的ではない。必要条件を述べただけである。十分条件でもあることを証明せよ。)

これにより、仮に| xa mod N )という値を観測したとしても、これと同じ値を与える他のa' = kr + aと区別できないのです。このことをちゃんと念頭に置き、| xa mod N )|c)を観測する確率を計算します。すると、

となります。kについての和は、考えられるa'=a+krについてすべてとるとします。この観測確率は量子力学の基本定理から得られます。やや複雑なですが、基本的に| 前の係数の和 |2という形をしていることに注意してください。(やっていることは、要はこういうこと。例えば、a|0>|0> + b|1>|0> + c|0>|1> + d|1>|1>という状態があったとして、第一ビットだけ観測を行ったとしたとき、例えば第一ビットが0となる確率が|a+b|2となる。なぜかというと、第二ビットを関知していないから、第一ビットだけで考えればよく、そのとき状態は(a+b)|0> + (c+d)|1>となるから。a+bは、観測する可能性のある状態の前の係数の和で、その二乗が確率になるわけです。)

さて、この観測確率ですが、もう少し計算すると、

という形にまでもっていくことができます。最後の等式では、|exp(i x)| = 1 (i: 虚数、x: 実数)を用いました。この最後の形が重要です。

もしも、rc/2nが整数に近かったとしましょう。すると、expの中身は 2πi ×整数×kと近似できます。このとき、和の中身は、kの値によらずに1に近くなります。この場合は、kについての和をとると、和は、1×(kのとりうる値の個数)という結果をだします。実はこの場合を観測する確率が、一番高いのです。

もしも、rc/2nからずれているとしますと、和の中身は、kの値によって、+1になったり-1になったり、iになったり-iになったり(iは虚数)、もっともっといろいろな値をとりえます。もっと正確にいうと、前回の講義でやったように、和の中身の複素数を矢印で表現した時、この矢印がいろいろな方向を向くので、全部で和をとってしまうと、0に近くなってしまうのです。少なくとも、さっきのように、和の中身が常に1に近いときに比べたら、確率はとても小さくなってしまう。(ここでの説明は直感的ですが、もっと厳密に評価することも、もちろんできる。)

よって、このような観測を何回も繰り返したとき、もっともよく観測されるのは、cが

のとき、言い換えると、cが

の値をとる場合を、よく観測することになります。観測を繰り返した結果のcについての分布図はだいたい下のようになります。

図のように、分布図は等間隔でピーク構造をもち、そのピークの間隔が1/rに比例するのです。この観測に必要な観測回数は、それほど多くなくて済むので、このようにして、rを効率よく求められることになります。

ここでの説明と、前の節での議論を組み合わせて、ようやく目標であった、「因数分解を量子コンピュータで効率よく行う方法」を示すことができました、、、、長い道のりでした。

終わりに

この遅れがちな講義に、最後までお付き合いくださいまして、ありがとうございました。

いろいろとつたないところがあったと思います。ご容赦ください。

量子コンピュータというホットな話題の、一側面をすこしでもお伝えできたならば、幸いです。

講師: 加藤岳生