量子コンピュータをちょっとだけ正確に理解する

量子コンピュータの開発に直接、携わっているわけではないのですが、量子コンピュータ研究に関する計算機環境の整備のお手伝いをさせていただいています。

門前の小僧程度の知識ではありますが、最近ニュースなどで取り上げられるようになってきた量子コンピュータの解説がだいたい間違っている¹のを感じますので、少しだけ正確に量子コンピュータを説明したいと思います。

量子ビット

量子コンピュータとは？という質問に対して、よく聞く回答は「量子の状態の重ね合わせを用いて普通のコンピュータが何万年もかかる計算を一度に計算することができる」というものです。それは本当なのか、まずは量子の状態を利用した量子ビットからみていきましょう。

デジタルコンピュータ（量子コンピュータ界隈では古典コンピュータとよびます）は情報を0と1で表します。通常それらを8bit, 32bit, 64bitと束ねたものを一つのレジスタとして値を保持し、さまざまな演算を行うことができます。

それに対して、量子コンピュータでは量子ビット (qubit) を用いて情報を扱います。量子ビットが保持するのはデジタルコンピュータと同じく0あるいは1のビットです。「0から1までの中間の値を持つことができる」わけではありません。

ただし、量子ビットでは0か1のどちらか一つではなく、両方が重ね合わさった状態を保持します。0が確率0.8で、1が確率0.2で観測されるといった状態を保持することができます。

間違い１：量子ビットには0が確率0.8で、1が確率0.2でと格納されている。

0か1のどちらか一つの値が確率的に入っているのではなく、0と1が重ね合わさった状態の量子が格納されています。0と1が重ね合わさったといわれても想像するのが難しいかもしれませんが、それが量子の姿でありnature of realityです。²

間違い２：量子コンピュータは1量子ビットだけで0あるいは1の確率を用いて0.9238...といった任意の精度の数を表現できる。

量子ビットの0あるいは1の確率（振幅）は任意の実数となりえますが、その確率が直接観察されるわけではありません³。 量子ビットを観測しても0あるいは1が観測されるだけです。しかも、一度観測すると何度観測しても、その量子ビットはずっと同じ値を返します。

表現するのにデジタルコンピュータにおいて$n$ビットが必要な情報は、量子コンピュータにおいても$n$量子ビットが必要です。

ただし、量子ビットは0か1のどちらかではなく、0と1の重ね合わせを保持するのでした。

量子ビットが1つだけでは0と1の重ね合わせ状態しか表せませんが、2個の量子ビットがあると2ビットの00, 01, 10, 11、つまり10進数の0から3の重ね合わせを表現できます。$n$個の量子ビットを用いると0から$2^n - 1$までの数の重ね合わせを表現できます。

$n$個の量子ビットに対して、それらを等確率な0と1の重ね合わせ状態にするには、次のような量子プログラムです⁴。

Qubit qs[n];
for q in qs {
  H(q);
}

Hはアダマールゲートという量子ビットに対する操作です。最初は0に初期化されているそれぞれの量子ビットqにHを適用することで0と1が等確率に重ね合わされた状態になります。結果として、qsは0から$2^n -1$までの全ての数を等確率に重ね合わせものを表現します。

では、等確率でない重ね合わせは？

ひとつの量子ビットを任意の確率に設定することはRyゲートを用いることで可能です⁵。

Qubit q;
Ry(2.0 * alpha, q);

この操作の後、qの状態は0である確率が $\cos\alpha$、1である確率が$\sin\alpha$となります。

Ryを用いて量子ビット$q_1$の0の確率を$a$に、量子ビット$q_2$の0の確率を$b$としたとします。このとき$q_1 q_2$が表す00, 01, 10, 11の確率は、$q_1$と$q_2$、それぞれが0あるいは1となる確率は独立ですので、$ab$, $a(1-b)$, $(1-a)b$, $(1-a)(1-b)$ となります。

ここから分かるように各量子ビットを独立に操作するだけでは、00, 11となる確率が共に1/2という状態や、00, 01, 10が1/3だが11がとなることはないといった状態を作りだすことができません。

そこで、量子コンピュータでは 「量子もつれ」 を利用して、各量子ビットが独立ではない状態を作り出します。先ほどの「00, 11となる確率が共に1/2という状態」には名前がついておりベル状態というのですが、次のようにアダマールゲートHと制御NOTゲートCNOTを用いて実現できます⁶。

Qubit qs[2];
H(qs[0]);  
CNOT(qs[0], qs[1]);

このプログラムでは、

1. 2つの量子ビットは0状態（確率1.0で0が観測される）に初期化されています。
2. qs[0]をアダマールゲートを用いて0と1が等確率の重ね合わせ状態にします。
3. CNOTを用いて、qs[0]が0のときはqs[1]はそのまま0状態、1の時はqs[1]は1状態（確率1.0で1が観測される）にします。qs[1] = qs[0] XOR qs[1]といった方が分かりやすいでしょうか。

ここで、CNOTはqs[0]を観測するわけではないことに注意してください。qs[0]は重ね合わせ状態のまま、つまり、0か1かという確率は1/2のまま、qs[1]を変化させます。⁷

このプログラムを実行すると、qs[0]を観測すると1/2の確率で0か1となり、その後 qs[1]を観測すると必ずqs[0]の値と同じになります。（観測の順序を逆にしても同じ）つまり、qsは00と11の等確率の重ね合わせになります。

この現象だけだと、qs[0]とqs[1]に予め1/2の確率で0か1か同じ値が格納されていると考えれば説明できます。他にも01, 10といった組み合わせも。そして、このようなH, CNOT（およびS）だけの量子回路であれば通常のコンピュータで多項式時間でシミュレートできます。（Gottesman-Knill定理）

デジタルコンピュータでは2ビットで、00, 01, 10, 11のうちの1つを表現することができます。それに対して、量子コンピュータでは2量子ビットを用いて00, 01, 10, 11、それぞれが異なる確率である重ね合わせ状態を表現します。

一般化すると、デジタルコンピュータは$n$ビットで0から $2^n - 1$ の数のひとつを表現できます。それに対して、量子コンピュータでは$n$量子ビットを用いて0から $2^n - 1$ のそれぞれが異なる確率をもった重ね合わせ状態を表現します。

これは$2^n$個の実数の要素を持つ巨大な確率ベクトルをたった$n$量子ビットを用いて表現できるということを意味します。このことは量子コンピュータのデジタルコンピュータに対する大きな優位性です。

ただし、$2^n$ 個の要素を一つ一つ設定するようなプログラムでは結局、指数的な時間がかかってしまいます。この量子ビットが表す広大な状態空間をいかに効率よく操作し答えを見つけ出すかが課題となります。

一度に計算

この量子の重ね合わせ状態を用いて、 「普通のコンピュータが何万年もかかる計算を一度に計算することができる」 とはどういうことでしょうか。

普通のコンピュータが何万年もかかる計算として、よく例に出されるのが素因数分解です。
ある数$a$の素因数の一つを求める素朴なアルゴリズムは次のようなものです。

for i in 2..a {
  if a mod i == 0 {
    return i;
  }
}
return 0;

通常、このようなシンプルなループによるアルゴリズムの計算量は線形時間オーダー$O(N)$といいますが、$a$がとても大きい数で、実際には1つのレジスタに格納できるサイズではないことから、$a$のビット数を$n$として指数時間オーダー$O(2^n)$と考えます。

量子コンピュータでxをyで割った余りを求める関数をMod(x, y)としましょう。Mod(x, y)を実行するとxは余りになるとします。この関数の詳細には立ち入りませんが、論理回路を量子回路で表すことができることから、デジタルコンピュータで計算できるものは量子コンピュータでも定数倍程度の時間で計算できます。

余りが0のときは$qs$を出力し、それ以外のときは0を出力したいので、上のプログラムの量子コンピュータ版は次のようになります。

Mod(a, qs);
for i in 0..n { // aのビットがすべて0か？
	if a[i] != 0 {
	  return 0;
	}
}
return qs;

このプログラムの入力である$a$は素因数を求めたい数を表す量子状態であり、その数に対応する確率だけが1.0になっています。$qs$は0, 1, aを除くすべての数の等確率な重ね合わせ状態としましょう。Mod(a, qs)を実行すると、$a$は$qs$で割ったときの余りとなるのでした。

このプログラムによって、指数時間オーダーの原因となっていた$O(2^n)$ のfor i in 2..aのループが不要になりました。

例えば、n = 3, a = 6 (110)を考えましょう。$qs$は0, 1, $a$を除くすべての3ビットの数 2, 3, 4, 5, 7 (=010, 011, 100, 101, 110, 111) の等確率な重ね合わせ状態です。それぞれの数で6を割った余り 0, 0, 2, 1, 6 (= 000, 000, 010, 001, 110) が新たな$a$となるので、$a$は 000 が2/5, それ以外数がそれぞれ1/5の重ね合わせ状態となります。確かに余りが0となる数2, 3をこのプログラムは見つけているといえます。

$n$がとても大きいとき膨大な個数の余りの計算を一度に計算することができ、「普通のコンピュータが何万年もかかる計算を一度に計算することができる」といえそうです。

待ってください。このプログラムには問題があります。

$a$や$qs$は量子ビットですから、その値は計測して初めて分かります。計測を行うことなしにa[i] != 0のように比較することもreturn qsとして出力することもできません。

計測していることを明示すると

Mod(a, qs);
for i in 0..n {
	let r = Measure(a[i]);
	if r != 0 { // aのビットがすべて0か？
	  return 0;
	}
}
return MeasureAll(qs);

ここでMeasureは量子ビットを計測してその値（0か1か）を返す操作とします。Measureの返す値はもはや重ね合わせではありません。⁸

このプログラムを実行すると、値が1つだけ出力されます。その値はaの重ね合わせ状態のうちの一つです。先ほどの例 n = 3, a = 6 の場合では、aが0となるのは確率2/5でそのときは素因数が出力されますが、それ以外の場合は見つからなかったとして0が出力されます。

aが巨大素数2つs, tを掛けたものであったとすると、ほとんどの実行で0が出力されます。求めたい素因数sあるいはtが出力される確率はわずか $2 / (2^n - 2)$ 。

つまり、このプログラムは乱数を用いた

let b = rand(a);
if a mod b != 0 {
  return 0;
}
return b;

と正解を得る確率は同等だということが分かります。このプログラムが0以外の値を出力するまで実行を繰り返すのであれば計算量は $O(2^n)$ から変わりません。

最初にあげた量子コンピュータの説明「無数の状態を量子の重ね合わせを用いて表現することで、普通のコンピュータが何万年もかかる計算を一度に計算することができる」は間違いではありません。問題は、 我々はそのうち一つの計算結果しか一度に得ることはできない ということにあります。⁹

アルゴリズムのループになっている部分を重ね合わせを用いて表現することで、量子コンピュータでそのアルゴリズムの単純な並列化を行っても、得られる結果はそのループなのかの一つを実行した結果に過ぎません。

量子アルゴリズム

では、量子コンピュータを用いてもいまのコンピュータよりも速く計算することはできないのか？

いいえ、いくつかの問題で、今のコンピュータよりも速く計算することができるアルゴリズムは存在します。それらは上記のような単純なループの展開ではなく量子状態の干渉を利用します。そうすることによって、正解を出力する確率を高め、総当たりで答えを求めるよりも速く答えを得ることができます。

先にあげたプログラムではqsはすべての$2^n$個の状態が等確率な重ね合わせでした。そして、計算結果をそのまま計測して出力を行いました。

そうするのではなく、異なる$q \in qs$に対するa mod qが0であるかどうか（qが素因数であるかどうか）に応じて、それぞれの状態の確率を変化させます。qが素因数であればその状態の確率を上げ、素因数でなければその確率を下げましょう。このときa mod q == 0が真か偽か計測してはいけません。計測するのではなくa mod q == 0が真か偽かに応じてqの確率が上下するようにqsを変化させる。そのような量子操作が可能であれば、この操作を十分に繰り返した後にqsを計測すれば正解となるqを得ることができます。

これはGloverのアルゴリズムと呼ばれ、実際に量子コンピュータ上で実現可能です。N個の状態に1つだけ答えがあるとき、その答えを求めるGloverのアルゴリズムの計算量は $O(\sqrt{N})$ となります。nビットの数の素因数を求めるために$N = 2^n$の総当たりが必要だったのに対して、$O(\sqrt{N}) = O(2^{n \over 2})$ 回の繰り返しで求まるということになります。

指数時間オーダーであることには変わりはないのですが、nを暗号鍵の長さと考えると、Gloverのアルゴリズムは暗号鍵の長さを半分にする効果があるということになります。おおよそ10年ごとに推奨される暗号鍵の長さは倍になってきた経緯からすると、Gloverのアルゴリズムだけでも大規模な量子コンピュータが実現すれば10年分のコンピュータの進歩に相当するといえるかもしれません。

$\sqrt{N}$ の加速が限界か？

これはyesでありnoでもあります。

$N$個の構造を持たない要素から1つのものをオラクルを用いて見つけるという問題に対しては、BBBV（Bennett-Bernstein-Brassard-Vazirani）の下界定理が存在し、少なくともオラクルを$\Omega(\sqrt{N})$回呼ばなくてはいけないことが成り立ちます¹⁰。Gloverのアルゴリズムはその計算量がこの下界に一致していますので最善であることが分かります。（オーダーを変えない改善は可能です）

一方で、Gloverのアルゴリズムは問題の特性を考慮せずオラクルのみを用いるアルゴリズムです。問題の特性を用いたアルゴリズムの存在を否定するものではありません。実際に、素因数分解に関してShorのアルゴリズムが知られており多項式時間$O(n^3)$の計算量で素因数分解を行うことができます。これは最良でも指数時間オーダー $O(e^{n^{1 \over 3}})$ の解法（一般数体篩法 GNFS）しか知られてこなかった素因数分解に対する大きな改善です。

どちらのアルゴリズムも量子状態の重ね合わせを用いた単純な並列計算によって高速化されるのではなく、問題の特性を利用して量子状態の確率分布を巧みに操作することによって、より効率的に正解を得る確率を増幅するというものです。

量子コンピュータのより正確な特徴

以上のことから、「無数の状態を量子の重ね合わせを用いて表現することで、デジタルコンピュータが何万年もかかる計算を一度に計算することができる」は正確性に欠けることが分かります。

より正確に表現すると量子コンピュータは 「複数の量子状態の重ね合わせと干渉を利用して、特定の問題に対してデジタルコンピュータよりも効率的に正解の確率を増幅することができる」 ということができます。

1. 大物理学者の方々が間違った理解をしているわけがなく、量子力学というものを数式を使わず一般常識に照らし合わせて説明するのは本当に難しい、あるいは不可能であるということです。もちろん、この記事も間違っていることを最初に断っておきます。 ↩

2. 自然が人間の直観で理解できるようにできている保証はどこにもありません。 ↩

3. 位相推定という確率を観測できるように変換する手法は存在します。 ↩

4. https://quantum.microsoft.com/en-us/tools/quantum-katas?kataId=preparing_states&sectionId=preparing_states__all_basis_vectors ↩

5. https://quantum.microsoft.com/en-us/tools/quantum-katas?kataId=preparing_states&sectionId=preparing_states__unequal_superposition ↩

6. https://quantum.microsoft.com/en-us/tools/quantum-katas?kataId=preparing_states&sectionId=preparing_states__bell_state ↩

7. 実際にはqs[1]の状態に応じてqs[0]の状態も変化します。 ↩

8. $n$回の$a$の計測をCC...CNOTのような演算を用いて1回だけにすることはできますが、計測が必要なのは同じです。 ↩

9. あるいは、あなたが正解を得る世界は存在するが、あなたには他の世界のことは分からない。 ↩

10. ものすごくざっくりというと、少しだけ違う状態に対する量子ゲートの作用結果はその違った分だけ違う結果になるはずということから、初期状態からいきなり遠くにある答えにはたどり着けないよという定理。 ↩