理論的には解けるが現実的な時間では解けない問題
https://motojapan.hateblo.jp/entry/2017/11/15/082738
https://daigakudenki.com/np-hard/
量子コンピュータで効率良く解くことができる問題のクラスは BQP (bounded-error, quantum, polynomial time)と呼ばれていて、因数分解などが含まれている。クラス BQP にクラス P が含まれることは明らかだが、NP完全問題は クラス BQP に含まれないと予想されている（証明されたわけではないが）。というわけで量子コンピュータで NP 完全問題を解いても、やはり指数時間かかってしまうという可能性も高い。ちなみに n × n の囲碁やチェスなどは、PSPACE 問題というクラスに含まれていて、PSPACE問題は通常のコンピュータでは記憶領域は多項式サイズで足りるが、実行時間（あるいはステップ数）が指数時間的に増大する可能性がある問題のクラスで、全ての NP 問題を含んでいる。BQP は PSPACE よりも大きくなることは有り得ないと考えられている。
