量子計算量クラス（BQP）
量子コンピュータが「本当に速い」とはどの意味かが腑に落ちる。BQPの厳密な定義とP・NPとの包含関係、指数加速が成り立つ条件を、証明済みと未解決の境界まで正確に押さえられます。
- 1.BQPは、誤り確率を1/3以下に抑えた量子回路が多項式サイズで解ける判定問題のクラス。誤り1/3は多数決で指数的に潰せるため、しきい値の取り方に本質的な意味はない。
- 2.確実に言えるのは P ⊆ BPP ⊆ BQP ⊆ PSPACE の包含だけ。BQP と NP は包含関係が未証明で、BQP が NP完全問題を解けるという証拠は無く、素因数分解のような NP∩coNP 付近の問題が量子優位の主戦場になる。
- 3.指数加速が言えるのは、隠れた周期・群構造などの大域的性質を『問い』にできる限られた問題に対してのみ。ショアやサイモンはブラックボックスに対し証明可能な指数分離を持つが、一般の探索はグローバーの二次加速が限界。
「量子が速い」を計算量クラスで定義する
「量子コンピュータは指数的に速い」という言い回しは、正確には特定の問題クラスに対してしか成り立ちません。その線引きを与えるのが計算量クラス BQP（Bounded-error Quantum Polynomial time） です。BQP は「多項式サイズの量子回路が、誤り確率を一定以下に抑えて解ける判定問題の集合」を指し、古典の 計算量クラス P・NP の量子版に相当します。ここでは BQP の厳密な定義、他クラスとの包含関係、そして「どういう条件なら指数加速が正当化できるのか」を、証明済みの事実と未解決の予想を切り分けながら正確に整理します。
計算量の議論はすべて判定問題（答えが Yes/No）を対象にします。素因数分解や探索のような関数問題も、「N の d 桁目は 1 か」のような Yes/No 版に落として論じるのが約束です。
BQP の定義：多項式サイズ回路と誤り 1/3
BQP は、次の3条件をすべて満たす判定問題 L の集合として定義されます。
判定問題 L が BQP に属する ⇔ 次を満たす量子回路の族 {C_n} が存在する:
① 多項式サイズ : C_n のゲート数は入力長 n の多項式で抑えられる
② 一様性 : 回路 C_n の設計図を古典計算機が多項式時間で生成できる
③ 有界誤り : 入力 x に対し、C_|x| で計算し1量子ビットを測定した結果が
・x が Yes なら 確率 ≥ 2/3 で「1」
・x が No なら 確率 ≤ 1/3 で「1」
三つ目の「誤り確率 1/3」というしきい値は、一見すると恣意的に見えますが本質的な意味はありません。同じ回路を独立に何度も走らせて多数決を取れば、成功確率を指数的に 1 へ近づけられるからです。
成功確率が 2/3 の判定を独立に k 回繰り返し多数決すると、誤る確率はチェルノフ限界により k に対し指数的に減少します。したがって 1/2 + 1/poly(n) 程度のわずかな偏りさえあれば、多項式回の反復で誤りを 2^(-poly(n)) まで潰せます。BQP を 2/3 で定義しても 0.9 で定義しても、あるいは 1/2 + 1/n で定義しても、得られるクラスは同一です。これは古典の乱択クラス BPP と全く同じ事情で、両者の定義が構造的に対応していることを示します。
一様性（②）を要求するのは、これがないと「回路族の中に答えを埋め込む」不正ができてしまうためです。各入力長ごとに別々の回路を許す非一様な版は、より強力なクラス（BQP/poly）になり、区別が必要です。
確実に言える包含関係：P ⊆ BPP ⊆ BQP ⊆ PSPACE
BQP が他のクラスとどこに位置するかで、証明済みの事実は驚くほど少ないという点がまず重要です。厳密に証明されている包含は、次の一列だけです。
P ⊆ BPP ⊆ BQP ⊆ PSPACE （⊆ EXP）
P : 決定的多項式時間
BPP : 有界誤りの乱択多項式時間（古典の“実用的に解ける”）
BQP : 有界誤りの量子多項式時間
PSPACE: 多項式メモリで解ける（時間は問わない）
左端の P ⊆ BPP ⊆ BQP は素直です。量子回路は古典の可逆回路を部分に含められるので、古典で効率的に解けるものは量子でも解けます。難しいのは右端の BQP ⊆ PSPACE です。
量子回路の出力確率は、始状態から終状態までのすべての計算経路の振幅の総和（ファインマン経路和）で書けます。振幅は個々の経路ごとに古典計算で求まり、経路は指数個あるものの一度に1本ずつ足し込めば、必要なメモリは経路1本ぶんの多項式サイズで済みます。時間は指数的にかかりますが、空間は多項式に収まる——ゆえに BQP ⊆ PSPACE。この「振幅を足し上げる」構造は次の PP との関係にも直結します。
より精密には BQP ⊆ PP（多数決クラス）も証明されています。PP は「経路の重みつき和の符号」を判定するクラスで、量子の振幅干渉と相性がよく、P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE という鎖に収まります。
| 関係 | 状態 | 根拠・意味 |
|---|---|---|
| P ⊆ BPP ⊆ BQP | 証明済み | 量子は古典（決定的・乱択）回路を包含する |
| BQP ⊆ PSPACE | 証明済み | 経路和を1本ずつ評価すれば空間は多項式 |
| BQP ⊆ PP | 証明済み | 振幅の重みつき和の符号として判定できる |
| P ⊊ BQP | 未解決 | 厳密分離は未証明（P≠PSPACE すら未解決） |
| NP ⊆ BQP | 偽と予想 | 量子は NP完全を効率で解けないと信じられている |
決定的な分離 P ⊊ BQP（＝量子が古典より真に強い）は、実はまだ証明されていません。もし証明できれば P ⊊ PSPACE も従い、これは計算量理論の未解決大問題です。私たちが「量子が速い」と言うとき、その多くは証明ではなく、強く信じられている予想に基づいています。
BQP と NP：包含関係は未証明、NP完全は解けないと予想
最もよくある誤解が「量子コンピュータは NP完全問題を高速に解ける」というものです。これは現在の理解では誤りです。BQP と NP の間には、どちらの向きの包含も証明されていません。
BQP と NP の関係（いずれも未証明・予想）:
NP ⊆ BQP ? → 偽と広く信じられている（量子でも NP完全は指数時間）
BQP ⊆ NP ? → 偽と信じられている（BQP には NP 証明を持たない問題がありそう）
→ BQP と NP は「一方が他方を含む」関係ではなく、
互いにはみ出す（比較不能に近い）と予想されている
量子の高速化は「答えを総当たりで探す」タイプの問題には効きません。非構造的な探索に対しては グローバー探索 的な二次加速（N を √N に）が原理的な限界で、指数を多項式には落とせません（BBBV 下界）。SAT のような NP完全問題を BQP で解くには、この探索の壁を越える必要があり、それを可能にする構造が一般には存在しないと考えられています。つまり **BQP の強みは「探索の速さ」ではなく「特定の代数構造の抽出」**にあります。
では BQP はどこで NP と接するのか。素因数分解の判定版は NP ∩ coNP に属する（Yes も No も短い証拠で検証できる）と考えられており、NP完全ではありません。量子が真価を発揮するのは、この NP完全より「易しい」が古典では効率的に解けない中間帯——周期性や群構造など隠れた代数的性質を持つ問題です。
指数加速が成り立つ条件：隠れた構造と証明可能な分離
「どんな問題なら指数加速が言えるのか」を最も明確に語れるのは、ブラックボックス（オラクル）モデルです。入力の一部を「問い合わせ回数」で測るこの設定では、量子と古典の証明可能な指数分離が存在します。
オラクルに対する証明済みの分離:
サイモン問題 : 隠れた周期 s を持つ関数 f(x)=f(x⊕s) の s を求める
古典 : Ω(2^(n/2)) 回のクエリが必要（指数）
量子 : O(n) 回のクエリで解ける（多項式）
→ 証明可能な指数分離。ショアのアルゴリズムの原型
一般の非構造探索:
量子でも Ω(√N) 回必要 → 指数加速は起きない（二次のみ）
サイモン問題やショアが速いのは、答えが個々の値ではなく「全入力に共通する大域的パターン（周期・部分群）」だからです。量子並列性で全入力を一度に重ね合わせ、干渉によってこの大域構造だけを浮かび上がらせる——これが指数加速の唯一の一般的レシピといえます。
「量子は 2ⁿ 通りを同時に計算するから速い」という説明は不正確です。重ね合わせで 2ⁿ 個の振幅を保持できても、測定で取り出せるのはたった1つの結果にすぎません。指数加速の本質は並列数ではなく干渉——欲しい答えの振幅を強め合い、不要な答えの振幅を打ち消し合うよう回路を設計できたときにのみ加速が生じます。この干渉を大域構造に対して起こせない問題では、量子は古典に対して指数的な優位を持ちません。
一方で、現実の（オラクルでない）問題での指数分離は、P ⊊ BQP すら未証明である以上、厳密には一つも証明されていません。ショアの高速性は「古典の最良アルゴリズム（一般数体ふるいは準指数時間）よりずっと速い」という経験的事実であって、「古典では原理的に不可能」という証明ではない点に注意が必要です。指数加速が言える条件を、確実度の順に整理します。
| 条件・問題型 | 加速の度合い | 証明の強さ |
|---|---|---|
| 隠れ部分群（周期・群構造） | 指数（ショア・サイモン） | オラクルでは証明済み／実問題は経験則 |
| 非構造探索・総当たり | 二次のみ（√N） | 上下界とも証明済み（BBBV） |
| NP完全問題（SAT 等） | 汎用の指数加速は無いと予想 | 反証もされていないが強い予想 |
| 量子系のシミュレーション | 指数（自然な量子優位） | BQP完全性として位置づけ済み |
なお BQP には「最も難しい問題」＝ BQP完全な問題も定義でき、局所ハミルトニアンの時間発展の推定などがその代表です。量子系のシミュレーションこそ BQP が最も自然に力を発揮する領域で、これはファインマンが量子計算を構想した原点でもあります。
- BQP の定義：多項式サイズ・一様な量子回路族＋誤り
1/3以下。しきい値は確率増幅で任意に改善でき本質的でない。 - 証明済みの包含：
P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACEのみ。P ⊊ BQPは未証明（示せればP ≠ PSPACEも従う）。 - NP との関係：包含は両向きとも未証明。
NP ⊆ BQP（＝量子で NP完全が解ける）は偽と予想。 - 加速の条件：隠れ周期・群構造なら指数（ショア／サイモン、オラクルでは証明済み）。非構造探索は二次（
√N、BBBV 下界）が限界。 - 落とし穴：重ね合わせの並列数ではなく干渉が加速源。実問題での指数分離は厳密には未証明。
まとめ
BQP は「多項式サイズの量子回路が誤り 1/3 以下で解ける判定問題」であり、量子計算能力の正確な輪郭を与えるクラスです。要点は3つ。(1) 確実に証明されているのは P ⊆ BPP ⊆ BQP ⊆ PSPACE（さらに PP）だけで、量子が古典より真に強いという P ⊊ BQP すら未解決であること。(2) BQP と NP は包含関係が未証明で、NP完全問題を量子が効率的に解ける証拠は無い——強みは探索の速さではなく代数構造の抽出にあること。(3) 指数加速が言えるのは、周期や群構造という大域的パターンを干渉で抽出できる限られた問題に対してのみで、非構造探索は二次加速（√N）が原理的限界であること。この地図を持てば、計算量クラス P・NP の延長線上で「量子が本当に速い問題／速くない問題」を構造から見分けられるようになります。
量子コンピューティング Article
量子計算量クラス（BQP）を実務で読む
TL;DRは入口です。実際に選ぶ・使う段階では、何を解決するか、何と比較するか、導入後にどこで詰まるかまで見る必要があります。
解決すること
量子コンピュータ
比較で見る軸
難易度: advanced / カテゴリ: 量子コンピューティング / タグ数: 6
導入後に効く点
確実に言えるのは P ⊆ BPP ⊆ BQP ⊆ PSPACE の包含だけ。BQP と NP は包含関係が未証明で、BQP が NP完全問題を解けるという証拠は無く、素因数分解のような NP∩coNP 付近の問題が量子優位の主戦場になる。
先に潰すリスク
用語だけ覚えても、設計・実装・運用でどこに効くかを確認しないと判断を誤る。
- 難易度
- advanced
- カテゴリ
- 量子コンピューティング
- タグ数
- 6
判断チェックリスト
- 自社の用途が「量子コンピュータ / 計算量」に近いか確認する。
- 強みである「BQPは、誤り確率を1/3以下に抑えた量子回路が多項式サイズで解ける判定問題のクラス。誤り1/3は多数決で指数的に潰せるため、しきい値の取り方に本質的な意味はない。」が本当に評価軸になるか確認する。
- 注意点の「用語だけ覚えても、設計・実装・運用でどこに効くかを確認しないと判断を誤る。」を運用で吸収できるか確認する。
- 公開値や仕様値は、対象プラン・対象機種・対象リージョンまで確認する。
- 既存システム、ID、ネットワーク、監視、バックアップとの接続方法を先に洗い出す。
- 小さく試してから、本番移行、権限設計、障害時手順、コスト監視を決める。