01/02/21 23:04.net
>>素因数分解や離散対数問題を多項式時間で解く量子アルゴリズム
>まじですか。
んー、衝撃的な話題だったんで結構多くの人が知ってると
思ってたんだけど。
で、量子コンピュータの計算能力の秘密は、量子力学の重ね合わせの原理により、
n個の素子(キュービット)で2のn乗個の状態を表すことができ、
しかもその2のn乗個の状態に対する並列演算ができるってこと。
# この状態を表すのにテンソル積が使われている。
ただし、2のn乗個の重ね合わせ状態にある演算結果から
目的の解を取り出すのは結構難しいので、実際に多項式時間での解法が
見つかっているのは素因数分解や離散対数問題のような周期性のある問題だけ。
例えばNP完全問題について、いわゆる総当り的な解法では2のn乗の平方根の
オーダまでしか高速化できないことが示されてるんで、
量子コンピュータを使ってもNP完全問題は多項式時間では解けないんじゃ
ないかっていう意見が多い。
とりあえず日本語のサマリーとしては、
URLﾘﾝｸ(www.ipa.go.jp)
が良くまとまってると思う。
量子計算の詳しい原理については参考文献を当たってね。