うーん

ツッコミに対する反応を見て余計分からなくなった.

mixi日記で、突っ込まれた点について。
量子コンピュータはチューリングマシンでできることは全てできることが証明されているので、かけ算も当然できます。量子力学的重ね合わせを使わなければ、全ての量子ビットが古典ビットになり、状態の読み書きが自由にできるので、古典コンピュータと同じになります。しかし、問題は、高速にできるかどうかです。n量子ビットあれば、2^n個のかけ算を並列にO(1)で処理して欲しく、それがないと、量子コンピュータの価値が出ないのですが、それが、僕には無理そうに見えるという意味です。

O(1)は無理だが, O(n^2)とかO(n log n log log n)なら出来る.
重ね合わせておいてもbをnビット列として,

という演算はO(n)個の量子ゲートで出来る*1. なのでXORとNOT使って掛算回路組めば十分で, 重ね合わせておこうが掛算も出来る.

現実的に10000量子ビット用意して計算するの無理じゃない?という話なら納得出来るんだけど, 何を問題にしたいのかよく分からない.

*1:制御NOTをn個で出来る