量子コンピュータに関する誤解No.1?
「量子力学では、量子は確率的な振る舞いをするから、量子コンピュータは確率的な答えを返す。それは、従来のコンピュータにはなかった全く新しい性質である」
こういった理解をされている方も多いかもしれません。
けれど、それは誤解である、ということを、本記事では説明します。
今の量子コンピュータは外乱に弱く、計算を非常によく間違えるため、確率的でない答えを返す計算であっても、それなりの確率で答えを間違えるのは事実です。ですが、それはあくまでデバイスの特性で、仮に完璧なデバイスを作るか、「量子誤り訂正」と呼ばれる手法で誤りをなくせば、そのような問題は克服できると考えられています。
もちろん、量子アルゴリズムの中には、確率的に答えを返すものもあります。
ですが、本記事では、確率的な答えを返さない量子アルゴリズムと、通常のコンピュータ向けの確率的な答えを返すアルゴリズムを見ることで、上述の誤解を解消します。
人類史上初の量子アルゴリズム
人類史上初めて、通常のコンピュータよりも量子コンピュータで解いた方が指数関数的に速いことが示された量子アルゴリズムは「ドイチュ・ジョサのアルゴリズム」だと言われています。
このアルゴリズムはどういった問題を解くのでしょうか? 問題設定を見てみましょう。
問題
N個のビット(つまり、0または1がN個)を入力すると、1個の答えを返す関数fがある。
このfは、次の挙動のうちの、どれかの振る舞いをする。
- どんな入力に対しても、0を返す
- どんな入力に対しても、1を返す
- 入力によって、0を返す場合も1を返す場合もある。ただし、入力が全部で$2^N$通りあるうち、ちょうど半分($2^{N-1}$通り)の入力に対しては0を返し、残りの半分の入力に対しては1を返す
できるだけ少ないfの呼び出し回数で、fが、どんな入力に対しても同じ答えを返す(定値)のか、ちょうど半々で0または1を返す(均等)のかを判定せよ。
どういう問題設定だよ。これ解けてどんなとき役に立つんだよ。
例
N = 2の場合を考えてみましょう。
このとき、fは以下のいずれかです。
- どんな入力に対しても0を返す(定値)
- どんな入力に対しても1を返す(定値)
- [0, 0], [0, 1]に対しては0を返し、[1, 0], [1, 1]に対しては1を返す(均等)
- [1, 0], [1, 1]に対しては0を返し、[0, 0], [0, 1]に対しては1を返す(均等)
- [0, 0], [1, 0]に対しては0を返し、[0, 1], [1, 1]に対しては1を返す(均等)
- [0, 1], [1, 1]に対しては0を返し、[0, 0], [1, 0]に対しては1を返す(均等)
- [0, 0], [1, 1]に対しては0を返し、[0, 1], [1, 0]に対しては1を返す(均等)
- [0, 1], [1, 0]に対しては0を返し、[0, 0], [1, 1]に対しては1を返す(均等)
通常のコンピュータで解く場合は、[0, 0], [0, 1], [1, 0]など、適当に3通りの入力してみたら答えが得られます。
通常のコンピュータでのアルゴリズム
$2^N$通りある入力のうち、$2^{N-1} + 1$通りを試して、全部0あるいは全部1だったら定値、そうでなければ均等であるといえます。
上述のN = 2の場合、$2^{2-1} +1 = 3$ですので、3通り試す必要がありました。
$2^{N-1} + 1$通り全部を試す前に0と1の両方が出たら、その時点で均等であると確定しますが、定値であることを確定するためには$2^{N-1} + 1$通りを試すことが必要です。
この方法は、ビット数が増えるとfの呼び出し回数が指数関数的に増える$O(2^N)$のアルゴリズムと言えます。
ドイチュ・ジョサの量子アルゴリズム
このアルゴリズムでは、重ね合わせができるという性質を使い、入力を、すべてのパターンの重ね合わせ状態にして、fを呼び出します。
係数を派手に省略しますが、入力を全部アダマールゲートで重ね合わせた状態(つまりN個の$(|0>+|1>)$状態)と$(|0>-|1>)$状態を用意して
$$|\Psi_0> = \sum_{x=0}^{2^N-1}|x>(|0>-|1>)$$
を作り、$(|0>-|1>)$のビットに、fの答えをXORします。fを呼び出して結果をXORする計算をUで表すと
$$\begin{eqnarray}U|\Psi_0>& = &\sum_{x=0}^{2^N-1}|x>(|0\oplus f(x)>-|1\oplus f(x)>) \
& = & \sum_{x=0}^{2^N-1}(-1)^{f(x)}|x>(|0> - |1>)\end{eqnarray}$$
となります。
再度、すべての入力部分にアダマールゲートをかけて、それらを観測すると、「定値」の場合は、すべての観測結果が0に、「均等」の場合は、少なくとも1つは観測結果が1になります。
ドイチュ・ジョサのアルゴリズムの実装
Blueqatで実装してみます。
入力と、出力用に1ビットを用意します。
出力には$(|0>-|1>)$をあらかじめセットしておくので、HゲートとZゲートをかけておきます。
続いて、入力全部にHゲートをかけて、f(x)に相当するゲートをかけて、入力全部にHゲートをかけ、入力全部を観測します。
つまり、次のような実装になります。
from blueqat import Circuit
n_input = 2
c = Circuit().h[n_input].z[n_input] # 末尾の量子ビットを |0> - |1> にする
c.h[:n_input] # 入力全部にHゲートをかける
# c.????? ==> f(x)に相当するゲートをかける
c.h[:n_input] # 入力全部に再度Hゲートをかける
c.m[:n_input] # 入力全部を観測する
print(c.run(shots=100)) # 量子回路を動かして結果を表示する。同じ回路を100回動かすことにする
f(x)が、どんな入力に対しても0を返す場合(定値)
f(x)が必ず0を返す場合、状態は何も変わりません。なので、何もしないのと同じです。
from blueqat import Circuit
n_input = 2
c = Circuit().h[n_input].z[n_input] # 末尾の量子ビットを |0> - |1> にする
c.h[:n_input] # 入力全部にHゲートをかける
# f(x): 何もしない
c.h[:n_input] # 入力全部に再度Hゲートをかける
c.m[:n_input] # 入力全部を観測する
print(c.run(shots=100)) # 量子回路を動かして結果を表示する。同じ回路を100回動かすことにする
結果: Counter({'000': 100})
回路を100回動かして、'000'が100回返ってきました。全部ゼロなので「定値」だと分かります。
f(x)が、[0, 0], [0, 1]に対しては0を返し、[1, 0], [1, 1]に対しては1を返す場合(均等)
2ビット目の符号を反転したいので、Zゲートで反転してみます。
from blueqat import Circuit
n_input = 2
c = Circuit().h[n_input].z[n_input] # 末尾の量子ビットを |0> - |1> にする
c.h[:n_input] # 入力全部にHゲートをかける
c.z[1] # f(x): 2ビット目(インデックスは0から数えるので、1を指定する)を反転する
c.h[:n_input] # 入力全部に再度Hゲートをかける
c.m[:n_input] # 入力全部を観測する
print(c.run(shots=100)) # 量子回路を動かして結果を表示する。同じ回路を100回動かすことにする
結果: Counter({'010': 100})
回路を100回動かして、'010'が100回返ってきました。ゼロ以外の観測結果が含まれているので、「均等」だと分かります。
実装結果より
確かに、ドイチュ・ジョサのアルゴリズムで「定値」「均等」の判定ができそうだということが分かりました。
また、今回、回路を100回動かしましたが、100回とも同じ結果が返ってきました。
ドイチュ・ジョサのアルゴリズムは、確率的ではなく確実に答えを返すアルゴリズムなので、何度動かしても同じ答えが返ってきます。
通常のコンピュータでの確率的アルゴリズム
通常のコンピュータでは、
$2^{N-1} + 1$通り全部を試す前に0と1の両方が出たら、その時点で均等であると確定しますが、定値であることを確定するためには$2^{N-1} + 1$通りを試すことが必要だ、と先程書きました。
確かにそれはそうなのですが、よくよく考えてください。
1万枚のカードが裏返しになっていて、カードは
- 全部赤、または全部黒 (定値)
- ちょうど半分が赤で、ちょうど半分が黒 (均等)
のいずれかです。全部赤、または全部黒であることを確定するためには、5001枚を表に向けないと分かりません。
……理屈の上では、確かにそうなのですが、適当に10枚くらいひっくり返して、全部赤だったら、おそらくは全部赤だろうって思いませんか?
実際に、そうである確率は非常に高く、10枚めくって決める方法の正解率は99.9%以上です。
それでもまだ不安なら、表にする枚数を増やせばよく、例えば50枚くらい表にすると間違う確率は1億分の1の、さらに1億分の1くらいになります。
この方法は嬉しいことに、カードの枚数が1万枚から1億枚に増えても、1京倍に増えても、カードを表にする枚数を増やす必要がありません。
これは非常に大きな改善です。ドイチュ・ジョサのアルゴリズムのように厳密に1回、とはいかないですが、この「適当に何枚かめくって決める方法」は、問題がどれだけ複雑になってもfの呼び出し回数を増やさなくてもよい、アルゴリズム好きの間で「定数オーダー」と呼ばれる $O(1)$ のアルゴリズムです。オーダーだけを比較すれば、ドイチュ・ジョサのアルゴリズムと実質同じであると言えます。
つまり、小さい確率で間違えることを許容するなら、この問題は通常のコンピュータでも量子コンピュータと同じ、定数オーダーのアルゴリズムで解けるんですね。
まとめ
今回は、答えが確実に出る量子アルゴリズムである「ドイチュ・ジョサのアルゴリズム」と、それを通常のコンピュータで確実に解く方法、確率的に解く方法を紹介しました。
- 量子コンピュータでも、確率的でない答えを出すアルゴリズムがある
- 通常のコンピュータでも、確率的な答えを出すアルゴリズムがあり、ときにはそれが強力である
ということが、お分かりいただけたかと思います。
余談: 全入力を重ね合わせにできるって無敵じゃね?
これもよくある誤解なのですが、実はそうじゃありません。
全部の入力を重ね合わせ状態にして、一度で処理すること自体は可能です。
実際に、重ね合わせ状態を使って一度に処理できることは量子コンピュータの強みではあります。
ですが、量子アルゴリズムの難しさは、重ね合わせ状態にして計算した結果をどう取り出すかにあります。
ただ闇雲に、重ね合わせ状態を入力して、観測しただけでは、通常のコンピュータで闇雲にデータを入力して計算をするのと同じで、あまり有益ではありません。
ほしい結果が観測される確率が高くなるようにアルゴリズムを作るのが、量子アルゴリズム作りで一番難しい部分です。
(あまりに難しいので、今のところ、量子アルゴリズムの数はあまり多くなく、また、似通ったものが多いです)
おまけ: ドイチュ・ジョサのアルゴリズムの解説
回路自体は単純ですが、式はやや複雑です。
$\sum_{x=0}^{2^N-1}(-1)^{f(x)}|x>$の部分に注目しましょう。$\Sigma$を展開して書くと、
$$\sum_{x=0}^{2^N-1}(-1)^{f(x)}|x> = (-1)^{f(0)}|0>|0>\dots|0> + (-1)^{f(1)}|0>|0>\dots|1> + \dots + (-1)^{f(2^N-1)}|1>|1>\dots|1> = (|0>+|1>)(|0>+|1>)\dots(|0>+|1>)$$
のようになります。
話を簡単にするために2量子ビットで考えます。
2量子ビットでは、上式は
$$\sum_{x=0}^{2^N-1}(-1)^{f(x)}|x> = (-1)^{f(0)}|0>|0> + (-1)^{f(1)}|0>|1> + (-1)^{f(2)}|1>|0> + (-1)^{f(3)}|1>|1>$$
と表せます。
f(x)が常に0を返す「定値」の場合は、上式を計算すると
$$\sum_{x=0}^{2^N-1}(-1)^{f(x)}|x> = |0>|0> + |0>|1> + |1>|0> + |1>|1> = (|0>+|1>)(|0>+|1>)$$
となります。
また、f(x)が常に1を返す「定値」の場合は、上式を計算すると
$$\sum_{x=0}^{2^N-1}(-1)^{f(x)}|x> = -|0>|0> - |0>|1> - |1>|0> - |1>|1> = -(|0>+|1>)(|0>+|1>)$$
となります。このように「定値」の場合は、$(|0>+|1>)$のみの積で書き表せることが分かります。
$(|0>+|1>)$にアダマールゲートをかけると$|0>$になるので、観測結果はすべて0になります。
続いて、ちょうど半分が0、半分が1を返す「均等」の場合を考えましょう。
数が多いので全ては試しませんが、結論から言うと、これらは$(|0>+|1>)$と$(|0>-|1>)$の積で書き表せます。
必ずどこかに$(|0>-|1>)$が出てくるのがポイントで、$(|0>-|1>)$はアダマールゲートをかけると$|1>$になるので、「均等」の場合は、必ずどこかのビットの観測結果が1になります。
例えば、
[0, 0], [0, 1]に対しては0を返し、[1, 0], [1, 1]に対しては1を返す
の場合、
$|0>|0> + |0>|1> - |1>|0> - |1>|1> = (|0> - |1>)(|0> + |1>)$
となります。$(|0> - |1>)$が現れていますね。
また、
[0, 0], [1, 1]に対しては0を返し、[0, 1], [1, 0]に対しては1を返す
の場合は、
$|0>|0> - |0>|1> - |1>|0> + |1>|1> = (|0> - |1>)(|0> - |1>)$
となります。こちらでも$(|0> - |1>)$が現れました。
他のどの「均等」の場合でも、同じように$(|0> - |1>)$が現れます。
よって、どこかの観測結果に1が現れます。
参考文献
日本語版Wikipediaと英語版Wikipedia
Aaronson先生の講義資料
IBMの量子コンピュータを使ってみた