量子コンピュータとNP完全問題

今月の日経サイエンスに”量子コンピュータも苦手な問題”という特集がある。既存のコンピュータでもクラス P の問題は効率良く（多項式時間で）解くことができる。多項式時間でというところが曲者で O(n^100) でも n の多項式なので効率が良いという話になる。現在のコンピュータが出来ることは以下のようになる。
１：クラス P の問題を多項式時間で解くことが可能
２：クラス NP の問題の解の検証が多項式時間で可能
３：ある NP 完全問題から別の NP 完全問題への変換が多項式時間で可能
というわけで、現実問題から考えると最適に解くという意味ではあまり大したことができるわけではない。そこで量子コンピュータに期待が集まっているのだが、量子コンピュータで効率良く解くことができる問題のクラスは BQP (bounded-error, quantum, polynomial time)と呼ばれていて、因数分解などが含まれている。クラス BQP にクラス P が含まれることは明らかだが、NP 完全問題は クラス BQP に含まれないと予想されている（証明されたわけではないが）。というわけで量子コンピュータで NP 完全問題を解いても、やはり指数時間かかってしまうという可能性も高い。ちなみに n × n の囲碁やチェスなどは、PSPACE 問題というクラスに含まれていて、PSPACE問題は通常のコンピュータでは記憶領域は多項式サイズで足りるが、実行時間（あるいはステップ数）が指数時間的に増大する可能性がある問題のクラスで、全ての NP 問題を含んでいる。BQP は PSPACE よりも大きくなることは有り得ないと考えられている。