量子コンピュータはチューリングマシンを越えない
相当古いエントリーですが、池田信夫氏が
http://blog.goo.ne.jp/ikedanobuo/e/17719a64e3e6e062ef6b37b82d59bad5
コンピュータ素子の微細化は急速に進んでいるが、その極致が電子のスピンを使った量子コンピュータだ。普通のコンピュータが0か1かというbitの情報しか持たないのに対して、シュレーディンガーの波動関数であらわされる「純粋状態」の電子ではupと downのスピンが一定の確率で重ねあわされている。この2値の状態ベクトルをqubit(quantum bit)とよび、これを利用して多くの計算過程を重ね合わせる超並列の高速コンピュータをつくろうというのである。
（中略）
しかし確率的な波動が本質的な状態だとすると、観測によってそれが消えるのはなぜか。これについて現在の標準的な解釈では、電子が外界と相互作用することによってdecoherence（非干渉化）が生じ、混合状態以外の波（合成された密度行列の非対角成分）が極小化して見えなくなると考える。したがって非干渉化が起こらないように純粋状態を持続することができれば、チューリング・マシンを超える強力なコンピュータができるとともに、非干渉化理論が実証され、観測問題も解決するわけだ。
小生もこの道の専門ではないので、あまり強いことは言えないのですが
少なくとも
ということだけは確かなわけで、池田信夫氏のエントリーは明らかに誤解を生むこと必至ですよね
（池田氏が実際にどういう理解をしているのかはわかりませんが）。
まず、前者についてですが
http://ja.wikipedia.org/wiki/%E9%87%8F%E5%AD%90%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF
A. D. バーンスタインとU. ヴァジラニは、量子チューリングマシンと古典チューリングマシンの計算可能性が等価であることを示した。したがって、古典コンピュータで原理的に解くことができない問題は量子コンピュータにも解くことはできない。
量子コンピュータは古典コンピュータを容易にシミュレートすることが可能であるため、古典的なコンピュータで速く解ける問題は、量子コンピュータにも速く解くことができる。よって、量子コンピュータは古典コンピュータ「以上」に強力な計算速度を持つ。ただし、「より大きい」計算速度を持つのかどうか（量子コンピュータにしか速く解けない問題が存在するのかどうか）は、現在のところ証明されていない。 Shorのアルゴリズムにより、NP問題（検算はすぐにできるが、解くのに時間がかかる問題）である素因数分解を素早く解くことができるため、例えば素因数分解問題が古典コンピュータで解けないということを示せば量子コンピュータは古典コンピュータより強力であることになる。
「チューリング・マシン」と「古典コンピュータ」は当然、同一の概念ではないので、池田氏の説明はミスリードですね。
チューリングマシンの定義は以下です。
http://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3
「古典コンピュータ」とは、今、我々が使っているコンピュータなわけですが
古典コンピュータを概念化したらチューリングマシンだが、量子コンピュータを概念化したらチューリングマシンではない
というものでは断じてありません。
池田氏の文章の「チューリング・マシン」を「古典コンピュータ」に置き換えれば問題はないです。
ちなみに、ペギオ氏の粘菌コンピュータは、チューリングマシンを越えることを意図しているといっても差し支えないかと。
この場合、チューリングマシンを越えたいという意図とは、生物と無生物との境界を越えたいということに繋がってくるわけで
粘菌コンピュータと量子コンピュータは問題意識が根本から違います。
次に、観測問題ですが、現在の量子力学における観測問題に関する関心は分からないのですが
何の文脈もなく観測問題っていったらシュレーディンガーの猫の話だと思うんですよね。
http://ja.wikipedia.org/wiki/%E3%82%B7%E3%83%A5%E3%83%AC%E3%83%BC%E3%83%87%E3%82%A3%E3%83%B3%E3%82%AC%E3%83%BC%E3%81%AE%E7%8C%AB
これって、純粋状態が維持できれば解決できるとか、そんなレベルの問題ではないんじゃないかと。
量子の位置を確率的にしか表現できないという問題は解決しようがないわけですから。
２年前のエントリーにいまさらの突っ込み。
とはいえ、なんだかんだ言いながらも、小生は池田信夫氏を応援しています。
