本ページでは、量子コンピュータの基礎となる量子ビットや量子アルゴリズムの基本的な考え方について説明します。
量子コンピュータの原理 #
通常のコンピュータでは、入力値が同じなら常に同じ結果が得られます（疑似乱数であってもシードが同じなら再現されます)。 それに対し、量子コンピュータでは、入力値が同じでも「計算」結果は異なる可能性があります。 この違いを生み出しているのが、量子コンピュータで使用される「量子ビット」です。
また、量子コンピュータでは、通常のコンピュータのように計算している訳ではなく、
- 量子ビットに対して量子力学的な操作を行う
- 操作後に量子ビットを測定する
という2段階で計算と結果の出力を実現することになります。
量子ビットとは #
通常のビットと量子ビットの大きな違いとして、
- ビットの状態（0か1か）は確率的に決まる
- 測定(出力)するまで値が確定しない
等が挙げられます。これらの性質を「重ね合わせの原理」と呼びます。ビットが0である状態と、1である状態とが重なって（両方の状態を同時に持って）いると解釈されます。「アナログ的な中間の値をとる」という意味ではなく、例えばビットが 0.5 等の値になるわけではないことに注意してください。
量子力学の結果を利用して天下り的にこの性質を表現すると、量子ビットの状態は下記の式で表されます。
\[ \left | \psi \right \rangle = \alpha \left |0 \right \rangle + \beta \left | 1 \right \rangle \]ここで左辺 \(|\psi\rangle \) は、量子ビットを、右辺の \(\left |0 \right \rangle, \left | 1 \right \rangle \) はそれぞれ、通常のビットと等価の状態 0 と 1 を表します。量子力学で使われているブラケット記法を用いているため、情報系の人にとっては馴染みが薄いかもしれませんが、 \(\left | \psi \right \rangle \) はベクトルで、 \(\alpha, \beta \) はそれぞれ量子ビットが 0 と 1 になる確率のような値 (確率振幅と呼ばれます) を表す複素数の値です。確率振幅は絶対値の二乗をとると通常の意味での確率になります。
\[ p(0) = {\left | \alpha \right |}^2, \quad p(1) = {\left | \beta \right |}^2 \]ここで複素数の絶対値をとるので、例えば \(\alpha = a + ib \) とおくと、
\[ p(0) = (a + ib)(a-ib) = a^2 + b^2 \]がビット0になる確率です。 そして、ビット 0 になる確率とビット 1 になる確率の合計は 1 になる必要があるので、
\[ {\left | \alpha \right |}^2 + {\left | \beta \right |}^2 = 1 \]が満たされます。0と1が等しい重ね合わせ状態（0と1になる確率が共に0.5）にある時、 \(\left | \psi \right \rangle \) は例えば、
\[ \left | \psi \right \rangle = \frac{1}{\sqrt{2}} \left |0 \right \rangle + \frac{1}{\sqrt{2}} \left | 1 \right \rangle \]となります。
もし、 \(\alpha \) や \(\beta \) が0または1しか取らないことにすると、通常のコンピュータのビットと全く同一になります。つまり、量子ビットは通常のビットの拡張になっていると考えることもできます。
さて、ここまでさらっと説明してきましたが、下記のような疑問点については言及していません。
- 重ね合わせの性質がどこから現われたのか
- なぜ絶対値の二乗が確率なのか
- なぜ確率振幅は複素数なのか
- 量子ビットはどこに存在するのか
量子力学では、このような性質を共通して持つ対象が頻繁に登場します。この共通した性質をもつ対象を「量子ビット」として扱い計算に利用しよう、というのが量子コンピュータのアイデアです。 ひとまず起源や具体性は置いておいて、もしこういう量子ビットが存在したらという仮定で進めたいと思います。
ここでのまとめ:
- 量子コンピュータは量子力学の性質を利用している
- 量子ビットは0と1が重ね合わせの状態にある
量子計算とは #
通常のビットに対する計算の最小単位は、単一/複数ビットの状態を変更するという操作です。量子ビットと通常のビットの大きな違いは、量子ビットの状態は確率振幅で確率的に表されることでした。そのため、ビットの状態変更を計算の最小単位と考えると、量子ビットによる量子計算とは確率振幅を変更する操作が対応します。
ここまでは1量子ビットしか 扱ってきませんでしたが、ここからは \(n \) 量子ビットを考えます。1量子ビットの状態を表す式と同様に、 \(n \) 量子ビットの等しい重ね合わせ状態を式で書くと、
\[\left|\psi_{n-1}\right\rangle \cdots\left|\psi_{1}\right\rangle\left|\psi_{0}\right\rangle=\frac{1}{2^{n / 2}}|1 \cdots 11\rangle+\cdots+\frac{1}{2^{n / 2}}|0 \cdots 01\rangle+\frac{1}{2^{n / 2}}|0 \cdots 00\rangle\]と表すことが出来ます。 \(n \) ビットには \(2^{n} \) 通りのビットの組合わせがあるため、右辺の項数は \(2^{n} \) となります。また、係数の確率振幅は等しい重ね合わせ状態ということから絶対値を2乗して全て足し合わせて1になるように決まります。
仮に、計算前の初期状態を上の式で表される重ね合わせ状態とします。この \(n \) 量子ビットに対して量子計算を実行してみます。量子計算とは確率振幅を変更する操作なので、以下の重ね合わせ状態に変化したとします。
\[\left | \psi_{n-1} \right \rangle \cdots \left | \psi_{1} \right \rangle \left | \psi_{0} \right \rangle = c_{2^n-1} \left | 1\cdots 11 \right \rangle + \cdots + c_{1} \left | 0 \cdots 01 \right \rangle + c_{0} \left | 0 \cdots 00 \right \rangle\]それぞれの項を見比べると、
\[ \begin{aligned} \left | 0 \cdots 00 \right \rangle: \quad 1/2^{n/2} &\rightarrow& c_{0} \\ \left | 0 \cdots 01 \right \rangle: \quad 1/2^{n/2} &\rightarrow& c_{1} \\ &\vdots& \\ \left | 1 \cdots 11 \right \rangle: \quad 1/2^{n/2} &\rightarrow& c_{2^n-1} \end{aligned} \]というように確率振幅の変化すなわち量子計算が実行されています。このように、 \(n \) ビットに対する操作で \(2^n \) 通りのビット状態が変化することが量子的な並列性を表しています。
しかしこれは通常の並列計算とは意味合いが異なることに注意が必要です。通常のコンピュータでの並列計算とは、複数の入力に対して同時に計算を行い入力数だけの出力を返します。しかし、量子計算では計算完了後に測定(出力)を行うと、 \(2^n \) 個ある量子ビット状態のうち1状態だけが出力されます。
以上を踏まえると、複数の入力に対してそれぞれに対応する複数の出力が必要な演算には、量子計算を行う必要があまりないことに気づきます。 そのため、量子計算に向いている計算とは、複数の答えの候補(ビットの組合わせ)の中から1つ(または少ない数)を選び出してくるような計算です。どのビットの組合わせが測定されるかは確率 \({\left | c_{i} \right |}^2 \) で決まることから、ある狙った答え(ビットの組合わせ)が出力として欲しい場合には、 \(1/{\left | c_{i} \right |}^2 \) 回程度の量子計算と測定が必要になります。
つまり量子計算における計算量の評価は、 \[ \text{量子計算の計算量} \propto \text{量子ビットに対する操作回数}/\text{測定確率} \] となります。
量子アルゴリズムとは #
計算量を小さくするには単純に計算回数が少ないというだけでは駄目で、(当然ながら未知の) 欲しい計算結果の測定確率が高くなるような工夫も必要になります。これが量子アルゴリズムと呼ばれます。
量子アルゴリズムを考える上での基本戦略は、全ての可能性の中から欲しい答えを得られる確率を上げることにあります。NP困難などの通常のコンピュータでは今のところ全通り ( \(2^n \) 通り) 試さなくてはわからないような難しい問題に対し、ある量子ビット操作を行うことで確率振幅が
\[ O(n) \leq \frac{1}{\left|c_{i}\right|^{2}}<O\left(2^{n}\right) \]を満たすように出来れば、通常のコンピュータに比べて効率的なアルゴリズムであると言える可能性があります。
量子コンピュータが大きな注目を集めることになった、ショアのアルゴリズムを用いると量子コンピュータで素因数分解が高速に解けることが知られています。このアルゴリズムでは mod の周期性を離散フーリエ変換により確率に変換し、欲しい答えがわかっていなくても答えに対応する確率に偏りを生じさせることで答えを得ます。
量子アルゴリズム構築のアプローチとしては、
- 論理回路の拡張として: 量子ゲート回路
- 組合せ最適化問題に特化: 量子アニーリング、量子断熱発展
が提案されています。具体的な各量子アルゴリズムのアプローチについては別のページにて紹介します。
ここでのまとめ: #
- 量子コンピュータは並列計算を行うがそのままでは役に立たない
- 狙った結果を現実的な確率で出力するアルゴリズムの構築が必要