量子コンピュータ (りょうしコンピュータ) は、量子力学的な重ね合わせを用いて並列性を
実現する次世代のコンピュータ。
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
ヴァジラーニらは、量子チューリングマシンと古典チューリングマシンの計算可能性が等価で
あることを示した。したがって、古典チューリングマシンで原理的に解くことができない問題は
量子チューリングマシンにも解くことはできない。