加藤 仁徳
出題日 １２月６日（水）
提出日 １月７日（日）
量子コンピュータ（量子計算機）、というのは既に限界に近づきつつある計算機の進歩を更に一段階飛躍させるための夢のアーキテクチャーである。現在のような計算機の隆盛を生むアーキテクチャーは基本的に半導体技術の進歩なくしては語れない。非常に初期の電子計算機は真空管で作られていて、ごく簡単な回路を組むのにも部屋一つくらいの面積が必要で、まともな計算機を組み上げようと思ったら、それこそ体育館くらいの大きさの空間が必要だった。このような状況を救ったのが、大規模集積回路技術、ＬＳＩである。この技術を使えば、回路をあらかじめ基板の上に描いておくだけで望みどおりの回路を組み上げることが出来る。あとから配線する手間は一切無い。しかも、絵を描くことさえ出来ればいいのだから、事実上「印刷できる最小の大きさ」で回路を組むことが出来る。最近の計算機の進歩とは突き詰めればいかに小さく回路が作れるか、という絶え間ない技術的進歩そのものだったと言える。小さければ小さいほど、安くて高速な計算機が作れるからである。しかし、物事には限度というものがある。回路を描くための線をどんどん細かくしていけばいずれ、物質を構成している最小単位である「原子」レベルに到達する。回路の中の配線の太さと原子の大きさが同じくらいになる日は近い。実際には限界は、配線の太さが原子の太さになる前にやってくる。計算機の基本である電子回路を司る法則が普通の電気回路の法則から量子力学の法則に移行するからだ。量子力学の世界では配線の中を流れる電子が隣の配線ににじみ出てしまう。配線の何処にどれだけ電気が流れているのか解らなくなってしまう。これでは回路なんて組める訳が無い。だが、最初からそういう前提で回路を組めばよい。結局計算機というのは足し算、引き算のような四則演算を行っているに過ぎないから、それを「何処に電流が流れているか解らない」という前提のもとに実行する回路が作れればよい。これだけでも普通の電気回路として動作しないような小さな回路を作ることが出来る、という意味で十分価値があったのだが、「量子力学の原理を使って普通の電気回路の計算を超える演算が出来る回路を作れないか」と考えた人がいた。その原理は簡単に言うと「今までは一度に出来なかった計算を一度にやる」というやり方である。量子力学の世界では、配線のどの部分に電子がいるのか区別できない。逆にいうと「配線の何処にでも電子がある」ということである。あるいは、「回路に電気が流れている状態の全てを重ね合わせた状態」といってもよい。普通の電気回路で足し算と引き算を同時に行うことは出来ない。なぜなら、足し算の時と引き算の時は電気の流れ方が異なるからである。だが、量子力学の電子回路では「引き算の時の電気の流れ方」と「足し算の時の電気の流れ方」を両方同時に計算できる。このやり方を使うと、今までとは比較にならないほどの計算を一度に行うことが出来る。この原理を取り入れたのが量子計算機である。しかし、「全ての計算を同時にやったら答えも同時に出てくる。つまり、答えも色々な答えの重ね合わせの状態になってしまうのではないか。」という疑問が出てくる。“１＋１”と“１−１”を同時にやったら答えも“１＋１”の答え“２”と“１−１”の答え“０”との重ねあわせで２と０の混じった回路の状態が出てくるはずである。これからどうやって答えを分離するのだろうか。これこそが、量子計算機実用化の最大の難点であった。
最近、量子計算機が注目されている理由は、現実にこの困難を回避できる素晴らしいアルゴリズムが発見されたことによる。このアルゴリズムを使うと、非常に難しい問題とされていた大きな整数を小さな数の積で表す問題を「ごく短い計算時間で行うことが出来る」のだ。大きな整数を小さな数の積に簡単に分けられるようになると、これからの計算機＋ネットワーク社会で印鑑や鍵の役割を担うと思われている計算機暗号が簡単に破られてしまうのである。ただ、現実には暗号破りに使えるような高性能の量子計算機は当分出来ないだろうと言われている。様々な技術的な困難、があるからである。
大きな数を小さな数の積に分けるには色々なやり方があるが、本質的に「全ての数で割ってみる」というやり方（例えば、８を１，２，３，４，５，６，７で割ってみて、４と２で割り切れるから８＝４×２だ、と解るやり方）よりも効率の良いやり方は無い、と信じられている。大きな数、例えば２０桁とか４０桁の数になると、こういう単純な計算をするのにもあまりにも計算量が膨大すぎて計算しきれなくなる。これを量子計算機でやるには次のようにする。まず、分解したい大きな数より小さい全ての数の「中間状態」を作る。（例えば、１５４７を分解したければ、１，２，３，･･･，１５４６の全ての状態を重ね合わせた中間状態を作る）。そして、１５４７をこの「中間状態」で割り算して「余り」を求める。すると、たった一回の割り算で１５４７を１５４７未満の全ての数で割った「余り」の重ね合わせの「中間状態」を得ることが出来る。つまり、分解したい数が２０桁であろうが４０桁であろうが、たった一回の割り算で全ての「余り」を求めることが出来るという魔法の計算機が量子計算機という訳だ。この「余り」が“０”になっている数だけを集めてくれば一回で分解が完了する。しかし、一つだけ問題がある。「どの数の余りが０になっているか」をどうやって調べるのか。一個一個の数について調べていたら結局、大きな数の大きさ回だけ（１５４７なら１５４７回）演算をしなくてはいけなくなるので結局、速くならない。答えが求まっていても「読み出し操作」に時間がかかってしまう。これを回避するために、余りが０になった数だけを切り出す方法が必要だが、「量子力学の原理」で動いている量子計算機ではこれをうまくやることが出来る。この方法を用いて求めた答えは、５０％の確率で正しい。例え、５０％の確率でも１０回繰り返せば、１０回全て外れる確率は０．５の１０乗で大体１０００分の１くらいになる。これを何回でも繰り返せば、いつか「回路のハード的なエラー率」より小さくなる。量子計算機といえども、ある装置の上のプログラムに過ぎない。ハードの正確さ以上に正確なプログラムは必要ない。量子力学の原理を用いることにより、データの読み出しをせずに余りが０になっている数だけをある確率制度で導き出すことに成功したことが、量子計算機の成功の秘密であった。
ブール代数における要素０，１を量子直行状態に対応させた時、それらは基本量子ビット（qubit）と呼ばれ、この直行状態の様々な組み合わせ（重ね合わせ）もまた、量子ビットとなる。一般に空間的に異なるシステムのｎ個の基本量子ビットを配列した時古典ブール代数ではその可能な組は2n個となる。しかし、量子ではこの数の基本量子ビットによる組み合わせによって定義される量子状態もまた量子ビットとして扱えるため、ほぼ無限の組み合わせが可能となる。量子計算とはそれらを一つのベクトルとして処理するベクトル変換過程であり、無限の成分を含むそのベクトルが瞬時に計算されるので計算時間を極めて小さく出来る。古典の計算問題を解くためにこのようなベクトルの変換過程を設計することを量子アルゴリズムという。
一方、量子アルゴリズムを物理的に実現するためには量子論理回路が必要である。しかし、近年、Controlled NOTと位相回転を行う論理回路の組み合わせで任意の量子アルゴリズムが実現できることが証明された。これにより、量子コンピュータの実現は量子論理回路による量子ネットワークの実現問題となっている。
ここでControlled NOTの数学的モデルは、
|e1>|e2> ・・・
U12|e1>|e2> = |e1>|e1
+ e2>
U21|e2>|e1> = |e1 + e2>|e2>
ただし、|e1>|e2>は直交状態であり、ケットのなかの＋は排他的論理和（XOR）を表す。
上式は計算基底{ |0>, |1> }に関する量子Controlled NOTゲートU12を定義する。
既に、このような量子Controlled NOTがアメリカのNISTにおいて実験的に実現されている。量子現象を計算に用いる新しいコンピュータは計算速度、メモリーサイズなどの評価基準において想像を遥かに超える性能が期待できる。
（参考ホームページ）
http://www2.math.human.nagoya-u.ac.jp/~oku/qc/qc.html
http://www.tamagawa.ac.jp/SISETU/GAKUJUTU/pderc/rqcs/kaisetsu.html