量子超越性
これらの包含関係が厳密かどうか(等号が成立しないかどうか)はどれも未解決の問題である。
古典的なコンピューティングでは計算できないことを証明する難しさは、量子優越性を示す上での一般的な課題である。 白黒をはっきりつける決定問題とは異なり、サンプリング問題は、ある確率分布からのサンプルを求める。 任意の量子回路の出力から効率的にサンプリングできる古典的なアルゴリズムがある場合、 多項式階層は第3レベルに折りたたまれるが、これはほとんどあり得ないと考えられてる。 ボソンサンプリングは、より具体的な提案であり、その古典的な難しさは、複雑なエントリを持つ大きな行列のパーマネントを計算する難しさに依存する。これは、#P完全な問題である。この結論に到達するために使用された議論は、IQPサンプリングにも拡張され、そこでは問題の平均と最悪のケースの複雑さは同じであるという推測のみが必要となる。
量子コンピュータは、 デコヒーレンスとノイズにより、従来のコンピュータよりもはるかにエラーの影響を受けやすい。量子しきい値定理は、ノイズの多い量子コンピューターは量子エラー修正コードを使用して、各コンピューターサイクルで発生するエラーがある値よりも小さいことを前提にして、ノイズのない量子コンピューターをシミュレートできることを示している。数値シミュレーションによると、許容されるエラー率は3%に達する。ただし、量子エラー訂正に必要なリソースが量子ビットの数に応じてどのように増えるのかはわかっていない。懐疑論者は、量子計算を成功させ量子優位性を実証するためには、大規模化した量子システムにおける未知のノイズの振る舞いが障害になると指摘している。
量子計算の研究の成果として、古典計算におけるアルゴリズムの進歩があり、その結果として古典コンピュータと性能が同等になると言う事も起きてきた。 これは、あるレベルでは、量子優位性は、量子計算と同等のパフォーマンスを持つ古典アルゴリズムが存在しないと言う、否定の証明をしようとしていることになる。