四方山話（量子コンピューター） (2021年8月11日）
普通の計算機の内部で例えば足し算がどのように行われているか考えてみる：入力された $a, b$ に対し、$c=a+b$ を出力する手順を問題にする。われわれに取って本質的なことだけに着目したので、$a, b$ を負でない整数の範囲に限る。まず、$a, b, c$ をすべて二進法で書き表す。そうする理由は、$0, 1$ であれば物理的な状態で表すことが容易だから。例えば、電圧がある値より高ければ $1$ を表し、低ければ $0$ を表すというように約束すればよい。この方法によって $a=5$、二進法で
$$a=101=a_2a_1a_0$$を表すためには、$a_0, a_1, a_2$ のそれぞれを担う回線の部位を定めた上で、それぞれにかかる電圧を順に「高い、低い、高い」状態にすればよい。
非常に簡単な例として $0, 1$ の間の足し算を考えてみる。すなわち
$$a_0=0, 1, \hskip 5mm b_0=0, 1$$の場合で、この時
$$c=00, \hskip 2mm 01, \hskip 2mm 10, \hskip 2mm 11$$の可能性があるが、これらを
$$c=c_1c_0$$で表す。
$c_0, c_1$ を出力するには次の手続きを踏めばよい：
- まず、$c_0, c_1$ の初期値を $0$ と置く。
- $a_0=0$ であれば $c_0$ はそのままとし、$a_0=1$ であれば $c_0$ を反転させる。但し、反転とは $0$ を $1$ へ、$1$ を $0$ へ変えること。 （この段階の操作は、$a_0$ の値を $c_0$ へ読み込むことに等しい。）
- $b_0=0$ であれば $c_0$ をそのままとし、$b_0=1$ であれば $c_0$ を反転させる。（前の段階で $c_0=a_0$ となっているが、$b_0=0$ であれば $c_0$ はそのままでよい。$b_0=1$ であれば $c_0$ を変えなくてはいけない。どう変えるかと言うと、繰り上げが必要な時、つまり $c_0=1$ であれば $c_0=0$ とし、繰り上げがない時、つまり $c_0=0$ であれば $c_0=1$ にする。）
- $a_0, b_0$ が両方とも $1$ であれば $c_1$ を反転させ、そうでなければ $c_1$ は変化させない。（$c_1$ を変える必要があるのは $c_0$ の計算で繰り上げの必要が生じた時だけである。つまり $a_0$ と $b_0$ の双方が $1$ の時だけであり、その時は $c_1$ を $0$ から $1$ へ変える必要がある。）
例として
$$a_0=b_0=1$$の場合に上の手順を確かめてみる。この場合 $c=2$、二進法で $c=10$ だから
\begin{equation} c_0=0, \hskip 2mm c_1=1 \label{eq:c00c11} \end{equation}が最終的に出力されなくてはいけない。
まず第一段階で初期値
$$c_0=c_1=0$$が設定される。第二段階で、この場合 $a_0=1$ が $c_0$ へ読み込まれ $c_0=1$ となる。第三段階で、この場合 $b_0=1$ だから、$c_0$ を反転させて $c_0=0$ とする。第四段階で、$a_0, b_0$ は共に $1$ だから、$c_1$ を反転させて（$0$ から）$1$ へ変える。以上で確かに (\ref{eq:c00c11}) 式の通りの
$$c_0=0, \hskip 2mm c_1=1$$の出力が得られることになる。
段階を追うごとの $a_0, b_0, c_0, c_1$ の変化の様子は
$$(1, 1, 0, 0)\rightarrow (1, 1, 1, 0)\rightarrow (1, 1, 0, 0)\rightarrow (1, 1, 0, 1)$$のように書くと分かりやすい。同じように $a_0, b_0$ の他の組み合わせについては
$$(1, 0, 0, 0)\rightarrow (1, 0, 1, 0)\rightarrow (1, 0, 1, 0)\rightarrow (1, 0, 1, 0)$$ $$(0, 1, 0, 0)\rightarrow (0, 1, 0, 0)\rightarrow (0, 1, 1, 0)\rightarrow (0, 1, 1, 0)$$ $$(0, 0, 0, 0)\rightarrow (0, 0, 0, 0)\rightarrow (0, 0, 0, 0)\rightarrow (0, 0, 0, 0)$$のように変化する。
計算機の内部では、$a_0, b_0, c_0, c_1$ のそれぞれを担う部分が指定されていて、段階を追うごとにそれぞれの電圧が高くなったり低くなったりを繰り返し、最終的に $c_0, c_1$ に対応する部分の電圧が数値に置き直されて出力されると考えればよい。
ここで当たり前のことだが、一時にできる足し算は一組の $a_0, b_0$ に対する計算であり、別の $a_0, b_0$ を加えるためには、もう一度最初から計算機を走らせる必要がある。この状況は上で見た簡単な足し算のみならず、他のどんな計算にも言えることであって、従って、高価な計算機で計算したとしても、とてつもない時間がかかるということが起こり得る。非常に有名な例として、与えられた整数の因数分解がある。
与えられた整数 $N$ を因数分解する方法として最も基本的な方法は、
$$2\leq m\leq {\sqrt N}$$である整数 $m$ で $N$ を順番に割ってみる方法がある。例えば $N=2401$ が与えられたとすると、まず $m=2$ で割る。
$$N=2\times 1200+1$$となって割り切れない。次に $m=3$ で割る。
$$N=3\times 800+1$$でまた割り切れない。次々と進んで $m=7$ で割ってやっと
$$N=7\times 343$$となり割り切れる。$N$ が $4$ 桁の数でもこのようにかなり大変だが、$N$ が $n$ 桁の数とすれば $m$ の範囲はおおよそ
$$2\leq m\leq {\sqrt N}={\sqrt {10^n}}$$である。従って $N$ の桁が $1$ 増すごとに $m$ の個数は ${\sqrt {10}}$ 倍に増える。それだけ計算時間がかかることになる。
例えば $N$ が一万桁の場合
$${\sqrt {10}}^{10000}=10^{5000}$$となる。二桁くらいの $N$ であっても、私の計算力では少なくとも $1$ 秒はかかる。
$$1 年=365\times 24\times 60\times 60=3\times 10^7 秒$$であり、よってこの宇宙ができてから今までの $140$ 億年は
$$140 億年=4\times 10^{17} 秒$$であることを考えると、宇宙ができてからずっとこの計算に私がかかりきりになっていたとしても、必要な計算量に比べればまったく無に等しいだけの計算しか終えていないことになる。実は、もっと効率の良い計算方法で、しかも最先端のスーパーコンピューターを用いたとしても、$200$ 桁の因数分解で約 $10$ 年、一万桁ともなると $1000$ 億年かかるそうである。（二つの因数をかけて大きな桁数の整数を作ることは簡単だが、その逆の因数分解には多大な時間を要し、実質的に不可能であることに、現在の「公開鍵暗号」の技術は立脚している。）
この例のように、従来の計算手順を使う限り、計算量が膨大なものになる場合は他にもいくつかあるが、ミクロな世界の性質を使うとその困難を回避する方法が見えてくる：
前回までに光子の偏極を考えてきた。水平方向に偏極した状態を $b$ で表し、垂直方向に偏極した状態を $b'$ で表すことにすれば、$+45$ 度の方向に偏極した状態 $a$ は
$$a=b+b'$$に等しい。以前、方解石の結晶 $\Gamma $ とそれを裏返した ${\overline {\Gamma }}$ を用いた図のような装置
で考察したことだが、この状態 $a$ は、「$b$ かもしくは $b'$」を表すのではなく、敢えて言えば、「$b$ でもあり、かつ $b'$ でもある」ことを表す。
よって、例えば $b$ の状態にある光子は $0$ を、$b'$ の状態にある光子は $1$ を、それぞれ表すと約束するなら、一つの光子の状態で「$0$ でもあり、かつ $1$ でもある」ことを表し得ることになる。
$b+b'$ のような二つ、あるいはそれ以上の個数の状態の和を「重ね合わせ」の状態と呼ぶが、重ね合わせの状態が存在することがミクロな世界の顕著な特性である。実はこの特性を利用すると、計算量を大幅に減らせる可能性が生まれる。
例えば最初に考えた足し算をもう一度思い出す。$a_0, b_0$ を入力し、$(a_0, b_0, c_0, c_1)$ を段階を踏んで変形させ、最終的に $c_1c_0$ を出力させることによって $a_0+b_0$ を得た。入力値 $a_0, b_0$ の組み合わせは $4$ 通りあるので、すべてのケースに対し計算を行うためには $4$ 回計算機を走らせる必要があった。ところが、重ね合わせを使うと事情が違ってくる。つまり、$4$ 個の入力値の重ね合わせ
$$(0, 0)+(1, 0)+(0, 1)+(1, 1)$$の状態を計算機の中で作ることがもしできれば、その時の計算機はこれら $4$ 個の状態に同時にあるのだから、これらの初期入力値に対する計算がその後平行して進む、いわゆる並列計算が行われることになる。
因数分解の場合、
$$2\leq m\leq {\sqrt N}$$の範囲の $m$ を取っ替え引っ替えするために計算量が膨大になった。それがもし並列計算ができるのであれば、当然、計算量は大幅に減るだろうことは、おそらく容易に理解してもらえると思う。
目次を表示このページの先頭へ