量子コンピュータとNP完全問題 - 最適化問題に対する超高速＆安定計算今月の日経サイエンスに”量子コンピュータも苦手な問題”という特集がある。既存のコンピュータでもクラス P の問題は効率良く（多項式時間で）解くことができる。多項式時間でというところが曲者で O(n^100) でも n の多項式なので効率が良いという話になる。現在のコンピュータが出来ることは以下のようになる。 １：クラス P の問題を多項式時間で解くことが可能 ２：クラス NP の問題の解の検証が多項式時間で可能 ３：ある NP 完全問題から別の NP 完全問題への変換が多項式時間で可能 というわけで、現実問題から考えると最適に解くという意味ではあまり大したことができるわけではない。そこで量子コンピュータに期待が集まっているのだが、量子コンピュータで効率良く解くことができる問題のクラスは BQP (bounded-error, quantum, polynomial time)と呼ばれていて
