量子コンピューター： 「1」と「0」が“同時に存在できる”？？

質問

量子力学を良く知らないのですが、量子コンピュータはすごそうなので興味があります。

量子コンピュータの記事：
http://www.zdnet.co.jp/news/0302/20/nj00_quantumcom.html

に次のような文章が載っていました。一見わかりやすそうですが、やはり、さっぱりチンプンカンプンです。

「・・・・ところが、量子コンピュータではこの“常識”から異なってくる。量子力学の特徴の1つである「量子の重ね合わせ」と呼ばれる現象によって、ビットの単位である1つの量子が、「1」でもあり「0」でもある可能性が特定の確率であるからだ。既存のコンピュータ風に言うと、1ビットの中に「1」と「0」が“同時に存在できる”のである。」

普通のメモリの場合は電気が流れているかいないかで（とか磁力の方向によって）、０／１を区別するのですよね。
１ビットの中に「1」と「0」が同時に存在できるというのがまったく具体的に想像できないのですが、直感的に、どういう状況なのでしょうか？

やはり量子力学を分かっていないと理解できないことなのでしょうか？

回答No.5

774 · ベストアンサー

量子力学は勉強しましたが、量子コンピュータはちょっと別なので、間違ってるかもしれませんが…

> 2.かせね合わせた状態で計算をするので、同種の計算は一回で行うことが できる。便利！

正確には、多数の計算対象に対する同じ計算を一度に行うことができる、って感じです。

> 3.出力状態は、774さんがおっしゃるように観測したときに一通りに
> 決まってしまう。だから出力に関しては、出力を得るために 観測を何回か繰り返さないといけない。
> また、その出力状態の決まり方は確率的なので、
> 所望の状態に波を収束させるため(?)に Shorのアルゴリズムを使う。 ちょっと不便！

これは、どのような計算回路、計算方法(アルゴリズム)を採用するか、によります。
従来の計算機でできる全ての計算を行える量子コンピュータでは
欲しい解をえるために複数回の観測が必要かもしれません。

これでは量子コンピュータにメリットは小さいので、欲しい回がほぼ一回で得られる
計算方法が考えられる計算についてのみ計算する回路を組むことにするわけです。
素因数分解の例は、 一回の観測でほぼ100％の確率で欲しい結果を観測できるように、
複数回の計算を行います。その計算の手順がShorのアルゴリズムです。

> ●素因数分解は ２．のステップに時間がかかるので、量子計算を
　使うと劇的に早くなる。

>●量子計算でスピードが速くなるかどうかは問題に依存する。つまり、
　２．のステップが速い、というメリットが生かせないと
　量子計算を使う意味があまりない。

計算に時間がかかる、というよりは、計算対象が多数 (しらみつぶし的)というところが
量子計算アルゴリズム化すると従来のアルゴリズムより高速になる由縁です。
同じ理由で検索問題も高速に処理できる量子計算アルゴリズムが提案されています。

お礼

ありがとうございました。
おかげさまで、おおかまなところは分かったと思います。
興味が出てきたのでもう少し細かなところまで自分で勉強してみたいと思います。

回答No.4

774

Admin_07さんも書かれている通り、物理的な原理は、確率振幅(波動関数の確率解釈)と重ね合わせの原理、といことになります。

> しかし、具体的に計算結果を知りたいときは、
>(XX,YY)=(01,00)の場合と(XX,YY)=(00,10)の場合と、>２通りの「箱の空け方」があります。

正確には、一度開けてしまうと今までわからなかった中身が確定してしまいます。（「開け方によって変わる」、というのは、開けるまでは内容が不定ということの例えです。誤解を招く表現でごめんなさい。）

そのため、実際に計算することができる問題は限られるわけです。

>すると、 計算回数は半分でも、入力・結果の観測の回数が２倍になるので、結局トータルでかかる時間は一緒のような気がするのですが、どうなのでしょうか。

上述の通り、観測は一回だけです。入力回数は普通のコンピュータと同程度以下だと思います。また、仮に観測回数が二倍でも、入力より演算の方が時間がかかるのでやはり量子コンピュータの方が高速になります。

わかりやすい説明のページを見つけましたので
参考ＵＲＬに書いておきます。

参考URL：

http://pcweb.mycom.co.jp/news/2003/01/01/05.html

お礼

ありがとうございます。参考URLもがんばって読みました。なんか、私が下に書いた「k1 , k2 に情報を持たせる」というのはトンチンカンな解釈だったみたいですね。

教えていただいたことを、私なりにまとめてみました。
次のような理解で大丈夫でしょうか？

1.かせね合わせた状態の波を入力すればいいので、入力は一回ＯＫ。便利！

2.かせね合わせた状態で計算をするので、同種の計算は一回で行うことが
　できる。便利！

3.出力状態は、774さんがおっしゃるように観測したときに一通りに
　決まってしまう。だから出力に関しては、出力を得るために
　観測を何回か繰り返さないといけない。
　また、その出力状態の決まり方は確率的なので、
　所望の状態に波を収束させるため(?)に Shorのアルゴリズムを使う。
　ちょっと不便！

●素因数分解は ２．のステップに時間がかかるので、量子計算を
　使うと劇的に早くなる。

●量子計算でスピードが速くなるかどうかは問題に依存する。つまり、
　２．のステップが速い、というメリットが生かせないと
　量子計算を使う意味があまりない。

回答No.3

Admin_07

No1の人の回答には驚いたね，インド人もビックリだ．
何も知らないのに回答しちゃダメ．そんでもって嘘教えちゃ最悪だよ～．
よく反省してね．

量子コンピューターについてだけど，原理は重ね合わせ．線形結合とかね．
なんでもかんでも速くなるってわけじゃなくて，暗号解くのに必要な因数分解が速くなるだけ．
そのほかのなんかいい使い道だれか知らない？セールスマン問題とかさ．

お礼

ありがとうございます。「線形結合」ですか。なるほど。

つまり、たとえばベクトルをある基底ベクトルの線形結合と考えて、その基底ベクトルの係数にそれぞれ情報を持たせる、といった感じでしょうか？

たしかにこれなら、基底の次元の数だけビット数を増やすことができます。
（なにか勘違いしているでしょうか？）

補足

v (量子の状態?)を基底{e1, e2}を用いて、
　v = k1 e1 + k2 e2
と線形結合にする。
このときの k1 , k2 に情報を持たせる、ということなのかな、と予想してみました。

回答No.2

774

通常のビットは、0と決めれば0、1と決めれば1ですから、入力2ビットの計算機で、1*3の次に0*2を計算する場合、01,11,00,10の計8ビットを入力する必要があります。

一方、量子ビットは、計算に用いるまで 0でも1でもあります。ですから、01でも11でもある 2ビット XX と00でも10でもある2ビットYYの計4ビットを用いて一度だけXX*YYを計算すれば済むわけです。

　正確な理解には量子力学の知識が必要ですが、大雑把なイメージとしては、空け方によって中身が変わるびっくり箱ひとつを１量子ビットと考えればいいでしょう。中身がわからないままのびっくり箱同士をひとつのびっくり箱にすると、空け方によっていろんなものが出てくるが、その中身は計算前のそれぞれのびっくり箱のいろんな中身同士の計算結果というわけです。

ちなみに、#1 の kanetsu さんの方法は、1bitを多値化することによる情報量アップで、いわゆる量子コンピュータとは違うと思います。多値化に量子的性質を使っているという意味では量子コンピュータかも知れませんが。多値化自体は、量子的性質を使わなくても可能です（0V=0,1.5V=2,3V=2 等）。

お礼

>量子ビットは、計算に用いるまで 0でも1でもあります。ですから、
>01でも11でもある 2ビット XX と00でも10でもある2ビットYYの計
>4ビットを用いて一度だけXX*YYを計算すれば済むわけです。 空け
>方によって中身が変わるびっくり箱ひとつを１量子ビットと考え

だいぶん分かってきた気がします。ありがとうございます。一つ疑問があります。

01*11 と 00*10 と２回計算を行うのに比べて、量子ビットを使った XX*YY の計算回数は１回なので、確かに計算回数は半分です。

しかし、具体的に計算結果を知りたいときは、(XX,YY)=(01,00)の場合と(XX,YY)=(00,10)の場合と、２通りの「箱の空け方」があります。つまり、掛け算の結果を両方の場合について知るためには、箱を２回開ける必要があると思います。

すると、 計算回数は半分でも、入力・結果の観測の回数が２倍になるので、結局トータルでかかる時間は一緒のような気がするのですが、どうなのでしょうか。

回答No.1

kanetsu

アバウトな説明ですが、従来のコンピュータは、電圧の有無で状態を表したから、「有」、「無」の２状態しか表現できず２進数を用いていました。

量子にはスピンという属性もあるようなので（詳しくは知りませんが、スピンなし、右スピン、左スピンが表せたら３状態（３進数）が扱えます）、３進数以上の処理が出来るのでしょう。

同じ８桁でも、２進数なら２５６までしか扱えないのに、１０進数なら１００００００００まで扱えるように、ｎ進数のｎが増えると処理能力が向上するので、量子コンピュータが実現できれば、現在のコンピュータより能力は間違いなく向上すると思います。

お礼

ありがとうございます。
確かに量子コンピュータで飛躍的に計算能力が向上しそうですね。