演習問題 ７
整数を２つの整数の積に分解する高速アルゴリズムを実現する量子コンピュータの計算方式を説明せよ。
演習問題 ７´
量子コンピュータによる計算を適当な例をもとに説明せよ。
（解答）
今回の課題は、現在のコンピュータと量子コンピュータを対比させることによって、“量子コンピュータによる計算を適当な例をもとに説明せよ。”という課題に対してわかりやすく答えられ、また、“整数を２つの整数の積に分解する高速アルゴリズムを実現する量子コンピュータの計算方式”をより深く理解できると思い、二つのコンピュータを対比させながら考えていくことにした。
（１）現在のコンピュータと量子コンピューター
現在のコンピュータは、Turing機械というコンピュータの数学的モデルに基づいて構築されている。ここでは、Turing機械についての詳しい説明は避けることにする。量子コンピュータは、１９８５年にDavid・Deutsch が、量子Turing機械という新しい計算モデルを提唱したことにより生まれた。Turing機械が提唱された１９３６年ごろに現在のコンピュータがどういったものになるか誰にも予想できなかったように、現在は量子コンピュータがどのようなものになるか不明である。
（２）現在のコンピュータと量子コンピュータの属する物理系
現在のコンピュータと量子コンピュータは、両方とも物理的装置であるが、現在のコンピュータが古典力学により説明されるのに対し、量子コンピュータは古典力学では説明のしようがないミクロな世界の現象を利用するため、量子力学を用いて説明される。量子コンピュータの動作を正しく理解するためには、“波動と粒子の二重性”と呼ばれる量子力学に置ける特性を理解しなければならない。
（３）波動と粒子の二重性
波動と粒子の二重性とは、“原子のような、普通は粒子と考えられているものが、ある環境のもとでは波のように振る舞い、逆に、光のような、我々か波だと考えているものが、時として粒子のように振舞う”現象を指している。量子コンピュータにはこの粒子が持つ波のような振る舞いによる“量子力学的波は水面の波と同じく重ね合わせることが出来る”という性質が利用される。
（４）量子コンピュータの直感的イメージ
量子コンピュータは、現在のコンピュータに比べて飛躍的に計算速度を向上することができる。例として、関数 ｆ（ｘ）の値をコンピュータに計算させることを考える。この時、変数ｘの取りうる値はｘ１、ｘ２、…、ｘ７の七通りのみとする。いま、ある入力xi（１＜＝ｉ＜＝７）に対して、ｆ（xi）= aとなる値があるかどうか知りたいとする。現在のコンピュータ（逐次方）を用いて、この問題をなるべく速く解くには、７台のコンピュータを用意して、それらにそれぞれ違う一つずつの入力を与え、それらを並列に動作させれば良い。この処理がTn時間で行えるとする。これと同じ作業を、量子コンピュータでは一台で、しかも、Tn時間で行うことが出来る。
実際にはどのように行うかというと、次のようになる。まず、量子コンピュータにおいては、通常の７台のコンピュータの計算結果がある波として表現される。これらの波の波長や振幅は、計算結果が違うと異なっているものとする。また、同じ計算結果に対応する波でも、位相が違っていることもある。量子コンピュータでは、通常の７台のコンピュータが別々に行う計算でも、７つの波を一つに重ねてしまうことにより、１台で行うことが出来る。しかも、このように波を重ね合わせた時に、位相の異なる波は打ち消しあって消えてしまう（負の干渉）。一方、波長の同じ波同士は強め合う。量子コンピュータでは、望む結果を出す過程がお互いに強め合い、その他の結果は逆に弱め合うようにすることが出来れば、計算終了後に出力を観察した時に高い確率で望む結果を読み出せる。
（５）量子コンピュータの実力
量子コンピュータは、エラーを起こしやすく、誤り訂正が深刻な問題になる。これは上で挙げた例でもわかるように、量子コンピュータが確率によっていることによる。実際の数学的問題を量子コンピュータが現在のコンピュータより速く解けるかどうかは不明であったが、１９９４年に Shor が “量子Turing機械を用いると、因数分解問題と離散確率問題が非常に小さな誤り確率で高速に解ける” 事を示した。
（６）効率の良いアルゴリズム
アルゴリズムは、その実行ステップ数が入力長の多項式で押さえられるときに、多項式時間で動作するという。因数分解の場合入力として与えられる整数NはlogNビットで表現されるから、因数分解のアルゴリズムAが多項式時間で動作するとしたら、ある多項式Pに対し、Aの実行ステップ数がP（logN）以下とならなければならない。理論上は、多項式時間で動作するアルゴリズムが、“効率の良いアルゴリズム”であるといわれている。
（７）因数分解問題における効率の良いアルゴリズム
もっとも素朴な因数分解法は、“エラトステネスのふるい”である。しかしこの方法は少なくとも
ステップを必要とする。しかし、
はlogNに関する指数関数であり、したがって、このアルゴリズムは多項式時間では動作しない。現在知られている最良のアルゴリズムは、
のオーダーステップ数で動作する。これも多項式時間では動作しない。
（８）Shorの量子アルゴリズム
因数分解に対するShorの量子アルゴリズムは、確率的な多項式時間アルゴリズムである。Shorが考案した因数分解の量子アルゴリズムにおいて中心的な役割を果たすのが離散Fourier変換（DFT）である。DFTは量子コイン投げとも呼ばれている。DFTを用いることにより、２＾ｎ個の状態の重ね合わせがｎステップの処理で得られる。Shorの離散対数問題に対するアルゴリズムは２段フーリエ変換が基礎となっている。Shorの因数分解問題に対するアルゴリズムは、離散対数問題に対するアルゴリズムを少し変形することで得られる。
（９）Simonの流儀による直観的な因数分解問題に対するShorのアルゴリズムの動作原理
オイラーのφ関数は自然数上でその値が定義され、自然数Nに対するφ（N）の値は、「Nと互いに素なN以下の整数の個数」と定義される。 ａとNが互いに素の時、ａのmod Nのオーダｒとは、
を満たす最小の整数ｒのことをいう。ａとNが互いに素の時、ａのｍｏｄＮのオーダを発見できれば、Nの因数分解が比較的容易に出来ることが、整数論の結果から知られている。いま、整数Nを因数分解したい時に量子Turing機械（QTM）の処理に先立って、Eulerのφ関数φ（N）の値がわかっていると仮定した時に、Shorのアルゴリズムの動作を説明しているのが次の図である。
これは、２段Fourier変換の計算木において、
１、DFTにおける二股の分岐が、量子φ(n)面サイコロ投げによるφ(n)個の分岐に置きかえられている。
２、さらに、量子並列計算を行う関数ｆとして、ｆ(a,x)= a^x という関数が具体的に指定されている。
ものである。
このとき、ａとNが互いに素であり、ｒがａのｍｏｄＮのオーダであり、しかも、ｒｂがφ(N)の倍数ならば、様相［a,b,x］に対応する葉同士は正の干渉を起こす。しかし、それ以外の様相に対応する葉同士は負の干渉を起こし、それらの振幅の合計は０になる。したがって、上図で示された計算が終了した後で、QTMのテープを観測すると、ある整数kに対しrb＝ｋφ(N)を満たすｂが観測でき、この関係式からｒを求めることが出来る。
（１０）上記のアルゴリズムの問題点と解決法
上記のアルゴリズムには以下の二つの問題点がある。
１．整数Nの因数分解に先立ってφ(N)の値を知らなければならないが、その値の計算を多項式時間で行う方法は知られていない。
２．量子φ(n)面サイコロ投げは、QTMを用いても多項式時間で計算できるかどうかはわからない。
以上の理由により、上記のアルゴリズムではうまく行かない。
しかし、このアルゴリズムの動作を確率的に近似することで、若干の誤り確率を伴うが因数分解を多項式時間で行える量子アルゴリズムができる。また、この誤り確率はいくらでも小さく出来る。
（感想）
今回の課題を解くにあたって、「量子コンピュータ入門」と「量子コンピュータの数理」という二つの本を読んだ。「量子コンピュータ入門」の方が、さすがに入門と書いてあるだけあってわかりやすく、始めから読んでいくと大体理解できるように書いてあったため、今回は主に「量子コンピュータ入門」を利用した。毎回のことであるが、記号の入力や図の作成に時間がかかり、レポートを書くのに相当な時間がかかった。もっと詳しく書きたかったのだが、図を書くのに手間がかかりすぎるためにちょっと端折ってしまった。先生が紹介してくださっている物理関係のリンク集にはいろいろと面白いページものっていて、毎回の課題のたびに回り道をしてしまったりするのだが、同じことについていろいろな人が、いろいろな考えを述べているのでためになる。今回の課題である、量子コンピュータについてのことでも、量子の波の重ね合わせの説明の仕方一つとってもいろいろあって、このイメージしにくいことも、イメージしやすかった。集積回路の技術の進歩によってコンピュータの発展がもたらされたが、マクロな世界とミクロな世界の物質の振舞い方の違いでこんなにもコンピュータが違ったものになるというのは面白いと思った。
参考文献
量子コンピュータ入門 西野哲郎
量子コンピュータの数理 大矢雅則