量子コンピューターも苦手な問題

　量子コンピューターが実現すると，情報の検索が格段に速くできるようになり，インターネット上の金銭取引に利用されている暗号が簡単に解読できてしまう。夢の高速コンピューターが，注目を集めている。

　通常のビットは「０」か「１」のどちらかの値を取るが，量子コンピューターが扱う量子ビット（キュービット）では，それらが同時に存在する重ね合わせ状態も可能だ。このことを利用すると，少数の量子ビットでも大量の情報を扱える。量子コンピューターはそれらすべてをいわば並列処理し，既存のコンピューターでは効率よく解けない問題のうち，特定のものを高速に解くことを可能にする。

　だが，そうした量子アルゴリズムはほんの数例見つかっているにすぎない。例えば，橋で結ばれた島々をそれぞれ1度ずつ巡るルートを見つけるという問題。島が３つ，４つと少なければしらみつぶしに調べてもたいしたことはない。しかし，島が数十個，数百個と増えてくるとお手上げだ。これは，既存のどのコンピューターでも効率よく解くことができない難しい問題として知られているが，今では，量子コンピューターでもやはり解けないだろうと考えられている。

　既知の物理法則に奇抜な変更が加えられれば，そうした困難な問題を解くコンピューターを作れるかもしれない。しかしながら，こうした変更は非現実的に思える。これらの問題を効率よく解くことが不可能であることを物理学の基本原理に据える日が来るかもしれない。