計算複雑性理論において、BQPとは、量子コンピュータによって誤り確率が高々1/3で多項式時間で解ける決定問題の複雑性クラスである。Bounded-error Quantum Polynomial time の頭文字をとったものである。ある問題がBQPに属すなら、高い確率で正答を返し、多項式時間で実行可能な、量子コンピュータのためのアルゴリズムが存在する。そのアルゴリズムは解がYESのときもNOのときも最大で1/3の確率で間違った答えを返す。
BPPと同じように、定義の1/3というのは0以上1/2未満の任意の定数である。その定数が変化してもBQPは変化しない。
他の計算量クラスとの関係
このクラスは量子コンピュータのために定義されたもので、古典コンピュータ(または、ランダムな挙動を許したチューリングマシン)に自然な対応をするクラスはBPPである。
BQPはPとBPPを含み、PPとPSPACEに含まれる。 まとめると以下のような関係がある。
![{\displaystyle {\mbox{P}}\subseteq {\mbox{BPP}}\subseteq {\mbox{BQP}}\subseteq {\mbox{PP}}\subseteq {\mbox{PSPACE}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8232a2b094e77a90524991c969958dc1353993ac)
BQPとNPの関係については、2010年代ころより、NPを含むPHにBQPが含まれない、ということを示唆する結果がいくつか示されてきている。
|
---|
実用的な時間で解けるクラス | - DLOGTIME
- AC0
- ACC0
- TC0
- L
- SL
- RL
- NL
- NC
- SC
- CC
- P
- ZPP
- RP
- BPP
- BQP
- APX
|
---|
実用的な時間で解けないと疑われているクラス | |
---|
実用的な時間では解けないクラス | |
---|
クラス階層 | |
---|
クラスの族 | |
---|
一覧・ カテゴリ |
|
---|
全般 | |
---|
定理 | - ベル
- Eastin–Knill
- Gleason's
- Gottesman–Knill
- Holevo's
- No-broadcasting
- 複製不可能
- No-communication
- 削除不可能
- No-hiding
- No-teleportation
- PBR
- マーゴラス=レヴィンチン
- Threshold
- Solovay–Kitaev
- Purification
|
---|
量子通信 | - en:Classical capacity
- entanglement-assisted
- en:quantum capacity
- en:Entanglement distillation
- en:Monogamy of entanglement
- en:LOCC
- en:Quantum channel
- 量子テレポーテーション
- en:Superdense coding
量子暗号 | - en:Post-quantum cryptography
- en:Quantum coin flipping
- en:Quantum money
- 量子鍵配送
- BB84
- en:SARG04
- other protocols
- en:Quantum secret sharing
|
---|
|
---|
量子アルゴリズム(英語版) | - en:Amplitude amplification
- Bernstein–Vazirani
- en:Boson sampling
- ドイッチュ・ジョサ
- グローバー
- HHL
- Hidden subgroup
- 量子焼きなまし法
- Quantum counting
- 量子フーリエ変換(英語版)
- 量子最適化(英語版)
- 量子位相推定(英語版)
- ショア(英語版)
- サイモン(英語版)
- VQE
|
---|
量子複雑性理論(英語版) | - BQP
- EQP
- QIP
- en:QMA
- en:PostBQP
|
---|
量子プロセッサベンチマーク | - 量子超越性
- en:Quantum volume
- en:Randomized benchmarking
- 緩和時間
|
---|
量子計算モデル | - en:Adiabatic quantum computation
- en:Continuous-variable quantum information
- en:One-way quantum computer
- 量子回路
- 量子機械学習(英語版)
- 量子チューリングマシン(英語版)
- トポロジカル量子コンピュータ(英語版)
|
---|
量子誤り訂正(英語版) | - Codes
- CSS
- quantum convolutional
- stabilizer
- Shor
- Bacon–Shor
- Steane
- Toric
- gnu
- Entanglement-assisted
|
---|
物理的実装 | 量子光学 | - Cavity QED
- Circuit QED
- Linear optical QC
- en:KLM protocol
|
---|
冷却原子気体 | |
---|
スピンに基づく | |
---|
超伝導(英語版) | - 電荷量子ビット(英語版)
- 磁束量子ビット(英語版)
- 位相量子ビット(英語版)
- en:Transmon
|
---|
|
---|
量子プログラミング言語 | - en:OpenQASM–Qiskit–IBM QX
- Quil–Forest/Rigetti QCS
- en:Cirq
- Q#
- en:libquantum
|
---|
量子情報科学
|