出題日：12月8日
提出日：12月24日
学籍番号：g99p136
氏名：村松敦
大きな数を小さな数の積に分けるにはいろいろなやり方があるが本質的に「全ての 数で割ってみる」というやり方（例えば、８を１、２、３、４、５、６、７で割って みて、４と２で割り切れるから８＝４×２だ、と解るというやり方）よりも効率の良 いやり方は無い、と信じられている。大きな数、例えば、２０桁とか４０桁の数にな ると、こういう単純な計算をするのにもあまりにも計算量が膨大すぎて計算しきれな くなる。
これを量子計算機でやるには次の様にする（といっても、あくまでも比喩的な説 明にすぎない。実際にこういうことをするわけではないが）。まず、分解したい大き な数より小さい全ての数の「中間状態」をつくる。（例えば、１５４７を分解したけ れば、１、２、３、.......１５４６の全ての状態を重ねあわせた中間状態を作 る。）そして、１５４７をこの「中間状態」で割り算して「余り」を求める。する と、たった一回の割り算で１５４７を１５４７未満の全ての数で割った「余り」の重 ねあわせの「中間状態」を得ることが出来る。つまり、分解したい数が２０桁だろう が４０桁だろうが、たった一回の割り算で全ての「余り」を求めることが出来るとい う魔法の計算機が量子計算機というわけである。この「余り」が「ゼロ」になってい る数だけを集めてくれば一回で分解が完了するのである。 だが、問題が一個だけある。「どの数のあまりがゼロになっているか」をどう やって調べるのかである。一個一個の数について調べていたら結局、大きな数の大き さ回だけ（１５４７なら１５４７回）演算をしなくてはいけなくなるので結局、速く ならない。答えが求まっていても「読みだし操作」に時間がかかってしまう。
これを 回避するには、余りがゼロになった数だけを切り出す方法が必要だが、量子力学の原 理で動いている量子計算機ではこれをうまくやることが出来る。この方法を用いて求 めた答えは、５０％の確率で正しい。５０％と聞くと低いように感じられるが、例え ば、５０％の確率でも１０回も繰り返せば、１０回全て外れる確率は0.5の１０乗で 大体１０００分の一くらいになる。それでも１０００分の一の確率で正しくないとい うことになるが、２０乗でも１００乗でも何回でも繰り返せば、いつか「回路のハー ド的なエラー率」より小さくなる。量子計算機といえども、ある「装置」の上の「プ ログラム」に過ぎない。ハードの正確さ以上に正確なプログラムは必要ないというわ けである。量子力学の原理を用いることにより、データの読みだしをせずに余りが 「ゼロ」になっている数だけをある確率精度で導き出すことに成功したことが、量子 計算機の成功の秘密である。
量子の世界では「どこに電気が流れているか解らない」のであるが、実は解らな いのは場所だけでなくて、どのくらい電流が流れているかも良く解らない。うまく状 態を作ってやれば「流れている状態」と「流れていない状態」の中間の状態を作るこ とが出来る。つまり、流れている状態（「１」状態）と流れていない状態（「０」の 状態）の「中間状態」を作れる。つまり、これは計算の規則で言うと違う２つの数の 中間の状態をつくれるということである。（例えば、「２」と「３」の中間の状態、 とか）この中間状態の足し算を行うと一度に複数の計算をすることが出来る。例え ば、「２」と「３」の中間状態と「５」と「６」の中間状態を「足す」と答えは「２ ＋５＝７」と「３＋６＝９」で「７」と「９」の中間状態を作ることが出来る。つま り、２回分の計算を「一回で」することができるわけである。これはいくらでも拡張 できる「１」から「１００」までの状態全ての中間状態を「１００１」から「１１０ ０」までの状態全ての中間状態に加えると、たった一回の足し算で１００回分の足し 算をたった一回の足し算で出来ることが出来る。これが、「量子計算機は今までの計 算機が出来ないほどのたくさんの計算を一度に出来る理由」である。理論的には「量 子計算機はいくらでも早くなる驚異の計算機」ということになる。
インターネットで広く利用されている暗号系として代表されるものに RSA 暗号系 がある。この暗号系は、秘密鍵とよばれる数字の組みを知らない第 3 者が、暗号を 解読することがきわめて困難であることが知られている。これは、RSA 暗号系が、整 数論で知られている次の事実による暗号系であることによる。すなわち、大きな数の 因数分解を多項式時間で効率的に解くことのできるアルゴリズムが、いまだ知られて いないという事実である。 1994 年に Shor は、この因数分解を量子コンピュータで、きわめて効果 的に解 けることを示した。これにより、それまで理論的で抽象的なイメージの大きかった量 子コンピュータの有効性が明らかになるとともに、量子コンピュータの研究を大きく 前進させる契機となった。 Shor のアルゴリズムは、量子コンピュータによる計算部分と、古典的な計算によ る部分とに大別 される。このシミュレータでおこなえるのは、量子コンピュータに 依存した計算部分のみである。すなわち、以下に示す手順のステップ 1〜ステップ 4 の部分のみのシミュレーションとなる。 Nを因数分解する Shor のアルゴリズムの手順は、次の通り。 (準備) をみたすqを選ぶ。Nと互いに素な整数Xをランダムに選ぶ。
(初期化)、(ステップ 1) 〜 (ステップ 4)、(測定) を繰り返す。
(初期化) レジスタ 1 とレジスタ 2 を 0 に初期化する。
(注意) 量子ビットをいくつかまとめたものを、量子ビット列、もしくはレジスタ (register) という。
(ステップ 1) レジスタ 1 のすべての量 子ビットに ゲートを作用させる。このときのレジスタの 状態は で与えられる。
ステップ 2) レジスタ 1 を入力のパラメータとして を計算する。これによりレジスタの状態は となる。
(ステップ 3) レジスタ 2 を測定すｒ。このとき、レジスタ 2 の値がKになったとすると、レジス タ 1 とレジスタ 2 の値の組みは、 とし、 を集合Aの要素数とすると で与えられる。
(ステップ 4) レジスタ 1 の離散フーリエ変換 (DFT) を計算する。 離散フーリエ変換は なる写像であるから、レジスタの値の組みは で与えられる。
(測定) レジスタ 1 を測定する。 レジスタ 1 を測定した結果が であるなら、このは、求めたい周期をとしたときの の値の整数倍になっている。を連分数展開することにより、周期が決定される。
(準備)、(ステップ 1) 〜 (ステップ 4)、(測定) を だけ繰り返すことにより正確 な周期を決定することができる。 周期 が決定されたのであれば N の因数は を計算することにより得られる。 Shor のアルゴリズムを理解する上で、重要な部分は手順で示される (測定) の部 分である。アルゴリズムは、非常に高い確率で、求めたい周期 ? を決定するために 必要な情報を返すが、まれに、望まない結果 を返す。これは、量子計算における測 定が、確率的なものであることに起因している。
一言で言うと難しかった(というよりも分からなかったというほうが正しいかもしれ ない)。 それらしいホームページを見つけて参考にしながら書いたが、難しかった。 でも、授業中「量子コンピュータ」という言葉の意味をまったく理解していなかった が、このレポートのためにいろいろとホームページを見ていたらぼんやりと分かった ような気がした。
©Waseda University
URI: http://www.oishi.info.waseda.ac.jp/~oishi/phy/ensyu7.htm
最終変更 2000/12/24