BQP:Bounded-error Quantum Polynomial time：誤り許容の量子多項式時間

Bounded-error Quantum Polynomial time(BQP)という複雑性クラスが定義され、その性質が研究されるようになったことで、計算理論における効率性（Efficiency）の定義そのものが再考を迫られました。

1. 「チャーチ＝チューリングのテーゼ」の拡張

BQPの登場により、計算理論の根本である「拡張チャーチ＝チューリングのテーゼ」が修正されました。

以前の認識: 「物理的に実現可能なあらゆる計算機は、確率的チューリングマシン（BPP）によって多項式時間でシミュレートできる」。
証明されたこと: 量子力学的なプロセス（BQP）を用いることで、古典的なマシンでは指数関数的な時間を要すると考えられる問題を、多項式時間で解けることが示されました（ショアのアルゴリズムなど）。
意義: これにより、「物理法則の違いが、計算量の階層（複雑性クラス）の構造を変える」ことが決定的に証明されました。

P vs NP(Pと NP は違うのか？)という問いに対し、P≠NPやP=NPを判断する根拠にはなり得ないものの量子計算の文脈から一つの進展が提示されました。

証明されたこと: 特定の「オラクル（ブラックボックス関数）」を仮定した世界において、BQP が PH（多項式階層）の外側に位置することが証明されています（2018年のRazとTalによる成果など）。
意義: これは、量子コンピュータが「NP完全問題を解かなくても、古典コンピュータには到底不可能なタスクをこなせる」独自の計算領域を持っていることを論理的に裏付けました。

証明複雑性の観点では、BQPと関連する量子プロトコルが、証明の「検証」における劇的な飛躍をもたらしました。

証明されたこと (MIP*= RE):量子もつれを共有する複数の証明者がいる場合、BQP的な検証能力を持つ人間は、「停止性問題（計算不可能とされる問題）」ですら、その正しさを検証できることが2020年に証明されました。
意義: これは証明複雑性における大きな進展です。古典的な証明体系（MIP:Multi-Prover Interactive Proofs）では NEXP（P ⊆ NP ⊆ EXPTIME ⊆ NEXPTIME 指数関数時間）までの問題しか扱えませんでしたが、量子リソースの介入により、検証可能な地平が「計算可能な領域」を超えて無限まで広がったことを意味します。

BQPの存在は情報の重ね合わせと干渉（エンタングルメント）は、時間や空間といった計算リソースと交換可能な、独立した『計算資源』であるという事実を証明しました。