BQP

計算複雑性理論において、有界誤差量子多項式時間（BQP ）は、量子コンピュータによって多項式時間で解ける決定問題のクラスであり、すべてのインスタンスでエラー確率が最大1/3である。^[¹^]これは、複雑性クラスBPPの量子版である。

決定問題が BQP （Billion Quod Problem：ビッグクオタク問題）に属するのは、その決定問題を高い確率で解決し、かつ多項式時間で実行することが保証された量子アルゴリズム（量子コンピュータ上で動作するアルゴリズム）が存在する場合である。このアルゴリズムを実行すれば、少なくとも2/3の確率で決定問題を正しく解決できる。

意味

BQPは、特定の有界誤差均一量子回路族に関連付けられた言語と見なすことができる。^[¹^]言語LがBQPに含まれるのは、多項式時間均一量子回路族が存在する場合に限る。 $\{Q_{n}\colon n\in \mathbb {N} \}$ 、したがって

すべての人にとって $n\in \mathbb {N}$ Q _{n は}n 個の量子ビットを入力として受け取り、1ビットを出力する。
Lのすべてのxに対して、 $\mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}$
Lに含まれないすべてのxについて、 $\mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}$

あるいは、量子チューリングマシンの観点からBQPを定義することもできる。言語LがBQPに含まれるのは、すべてのインスタンスに対してLをエラー確率が最大1/3で受理する多項式量子チューリングマシンが存在する場合に限る。 ^[²^]

他の「誤差が限定された」確率クラスと同様に、定義における 1/3 の選択は任意です。チェルノフ限界を使用して、アルゴリズムを一定回数実行し、多数決によって 1 未満の任意の正しい確率を達成できます。一方では1/2 − n ^{− c}まで高い誤差を許容し、他方では2 ^{− n ^c}まで小さい誤差を要求することによって、複雑性クラスは変わりません。ここでcは任意の正の定数、nは入力の長さです。^{[ 3 ]}

他の複雑性クラスとの関係

コンピュータサイエンスにおける未解決問題

関係は何ですか

{\mathsf {BQP}}

そして

{\mathsf {NP}}

？

コンピュータサイエンスにおける未解決問題

BQP は量子コンピュータ用に定義されています。古典コンピュータ (またはより正式には確率的チューリングマシン)に対応する複雑性クラスはBPPです。PやBPPと同様に、BQP はそれ自身に対して低次数であり、つまり $BQP BQP = BQP$ です。^{[ 2 ]}非公式には、これは多項式時間アルゴリズムが合成に関して閉じているために成り立ちます。多項式時間アルゴリズムがサブルーチンとして多項式時間アルゴリズムを呼び出す場合、結果として得られるアルゴリズムは依然として多項式時間です。

BQP はPとBPPを含み、 AWPP [ ⁴^] PP ^[⁵^]およびPSPACE ^[²^]に含まれています^。実際、PPではBQPは低レベルであり、PPマシンはBQP問題を瞬時に解くことができても何のメリットも得られないことを意味し、これらの類似したクラス間の能力の差を示唆しています。古典的な複雑性クラスとの既知の関係は次のとおりです。

{\mathsf {P\subseteq BPP\subseteq BQP\subseteq AWPP\subseteq PP\subseteq PSPACE\subseteq EXP}}

問題は⁠ ${\mathsf {P}}\ {\stackrel {?}{=}}\ {\mathsf {PSPACE}}$ は未解決であり、 BQPと上述のクラス間の不等式の証明は困難であると考えられている。^{[ 2 ]} BQPとNPの関係は不明である。2018年5月、プリンストン大学のコンピュータ科学者Ran Razとスタンフォード大学のAvishay Talは、オラクルに関してBQPがPHに含まれない論文^[⁶^]を発表した。オラクルAが存在し、 ${\mathsf {BQP}}^{\mathrm {A} }\nsubseteq {\mathsf {PH}}^{\mathrm {A} }$ [ ⁷^]極めて非公式な意味では、これは PH と BQP に同一だが追加の機能を与え、オラクル (BQP A ) を備えた BQP が PH A ではできないことを実行できることを検証するものと考えることが^でき^ます^。オラクルの分離は証明されていますが、BQP が PH に含まれていないという事実は証明されていません。オラクルの分離は、複雑性クラスが同じであるかどうかを証明するものではありません。オラクルの分離は、BQP が PH に含まれていない可能性があるという直感を与えます。

フーリエサンプリングは、BQP に含まれるが多項式階層には含まれない問題であると長年疑われてきた。最近の予想では、同様の問題であるフーリエチェックも、多項式階層に含まれない BQP クラスに存在することが示唆されている。この予想は、BQP に存在する問題が NP 完全問題よりも難しいと分類される可能性があることを示唆しているため、特に注目に値する。多くの実用的な BQP 問題がPの外側に存在すると疑われているという事実と相まって( P ≠ NPの証明がないため、疑われているだけで検証されていない)、これは古典コンピューティングに対する量子コンピューティングの潜在的な力を示している。^{[ 7 ]}

BQPに後選択を追加すると、PPと等しい複雑性クラスPostBQPが得られます。^[⁸^]^[⁹^]

Promise-BQPにとって完全な問題

Promise-BQP は、量子回路の均一なファミリー (つまり、BQP 内) で解決できるプロミス問題のクラスです。 ^{[ 10 ]}完全性の証明は、このバージョンの BQP に焦点を当てています。NP完全性や他の完全問題の概念と同様に、完全問題を Promise-BQP に含まれる問題で、Promise-BQP 内の他のすべての問題が多項式時間でそれに還元される問題として定義できます。

近似回路プローブ

APPROX-QCIRCUIT-PROB問題は、効率的な量子計算に関しては完全な問題であり、以下に示すバージョンはPromise-BQP複雑性クラスに関しては完全な問題です（完全な問題が知られていないBQP複雑性クラス全体に関しては完全ではありません）。APPROX-QCIRCUIT-PROBの完全性は、他の複雑性クラスとBQPの関係を示す証明に役立ちます。

$n個の量子ビットに$ $m個の$ ゲートで作用する量子回路 $C$ の説明が与えられ、 $mは$ $n$ の多項式であり、各ゲートは1つまたは2つの量子ビットに作用し、2つの数値が与えられます。 $\alpha ,\beta \in [0,1],\alpha >\beta$ 以下の2つのケースを区別する。

状態の最初の量子ビットを測定する $C|0\rangle ^{\otimes n}$ 収量 $|1\rangle$ 確率で $\geq \alpha$
状態の最初の量子ビットを測定する $C|0\rangle ^{\otimes n}$ 収量 $|1\rangle$ 確率で $\leq \beta$

ここでは、入力値に関して不確実な点があります。なぜなら、この問題では、インスタンスがこれら2つのケースに該当しない場合の動作が規定されていないからです。

主張。あらゆる BQP 問題は APPROX-QCIRCUIT-PROB に帰着します。

証明。n $個の$ 量子ビットに作用する量子回路 $C$ と2つの数値が与えられたとき、 APPROX-QCIRCUIT-PROBを解くアルゴリズム $Aがあると仮定します。$ $\alpha ,\beta \in [0,1],\alpha >\beta$ $A$ は上記の2つのケースを区別します。このオラクルを使用してBQPのあらゆる問題を解決できます。 $\alpha =2/3,\beta =1/3$ 。

いかなる場合でも $L\in {\mathsf {BQP}}$ 量子回路のファミリーが存在する $\{Q_{n}\colon n\in \mathbb {N} \}$ すべての $n\in \mathbb {N}$ 州 $|x\rangle$ の $n$ 量子ビット、もし $x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3$ ; そうでなければ $x\notin L,Pr(Q_{n}(|x\rangle )=0)\geq 2/3$ 入力を修正する $|x\rangle$ $n$ 個の量子ビットと、それに対応する量子回路 $Q_{n}$ まず回路を構築します $C_{x}$ そのため $C_{x}|0\rangle ^{\otimes n}=|x\rangle$ これはハードワイヤリングで簡単にできます $|x\rangle$ そして、一連のCNOTゲートを適用して量子ビットを反転させます。次に、2つの回路を組み合わせて、 $C'=Q_{n}C_{x}$ そして今 $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ そして最後に、必然的に $Q_{n}$ ^は、複数の量子ビットを測定し、それらにいくつかの（古典的な）論理ゲートを適用することによって得られます。測定を延期して^{回路を再配線する}^ことで^、^{最初の量子ビットを}測定することによって^、 $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ すると出力が得られます。これが回路 $C$ となり、メンバーシップを決定します。 $x\in L$ 実行することで $A(C)$ と $\alpha =2/3,\beta =1/3$ BQPの定義によれば、我々は最初のケース（受理）か2番目のケース（拒否）のどちらかに該当するので、 $L\in {\mathsf {BQP}}$ APPROX-QCIRCUIT-PROB に縮小します。

BQPとEXP

まず、より簡単な封じ込めから始めます。 ${\mathsf {BQP}}\subseteq {\mathsf {EXP}}$ APPROX-QCIRCUIT-PROB は BQP 完全であるため、APPROX-QCIRCUIT-PROB が EXP に含まれることを示すだけで十分です。

請求- ${\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}$

証拠

考え方は単純です。量子回路 $Cが与えられた場合、指数関数的なパワーを持つため、古典コンピュータを使用して$ $C$ 内の各ゲートを刺激することで最終状態を得ることができます。

より厳密には、 $C を$ $n$ 個の量子ビットと $m 個の$ ゲートを持つ多項式サイズの量子回路とする。ここで m は n の多項式である。 $|\psi _{0}\rangle =|0\rangle ^{\otimes n}$ そして $|\psi _{i}\rangle$ 回路内の $i$ 番目のゲートが適用された後の状態を $|\psi _{i-1}\rangle$ 各州 $|\psi _{i}\rangle$ は、古典的なコンピュータでは単位ベクトルとして表現できる。 $\mathbb {C} ^{2^{n}}$ さらに、各ゲートは行列で表すことができる。 $\displaystyle \mathbb {C} ^{2^{n}\times 2^{n}}}$ したがって、最終状態 $|\psi _{m}\rangle$ 計算可能 $O(m\cdot 2^{2n})$ 時間、そして全体として、 $2^O(n)$ 最終状態を計算するための時間アルゴリズム、したがって最初の量子ビットが1と測定される確率。これは、 ${\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}$ 。

このアルゴリズムには以下の要件も必要であることに注意してください。 $2^O(n)$ ベクトルと行列を格納するためのスペース。次のセクションでは、空間計算量を改善できることを示します。

BQPとPSPACE

履歴の合計は、物理学者リチャード・ファインマンが経路積分定式化のために導入した手法です。APPROX-QCIRCUIT-PROB は履歴の合計手法で定式化でき、次のことが示されます。 ${\mathsf {BQP}}\subseteq {\mathsf {PSPACE}}$ [ ¹³^]

$t$ 個のゲートからなる量子回路 $C$ を考えます。 $g_{1},g_{2},\cdots ,g_{m}$ それぞれ $g_{j}$ はユニバーサルゲートセットから生成され、最大で2つの量子ビットに作用します。履歴の合計が何であるかを理解するために、量子回路が与えられたときの量子状態の進化を木として視覚化します。ルートは入力です。 $|0\rangle ^{\otimes n}$ 、そしてツリーの各ノードには $2n$ 子供たち、それぞれが州を代表して $\mathbb {C} ^{n}$ $j$ 番目のレベルのノードからツリーエッジへの重みは、状態を表します。 $|x\rangle$ ノードへ $j+1$ 状態を表す第 1 レベル $|y\rangle$ は $\langle y|g_{j+1}|x\rangle$ 振幅 $|y\rangle$ 適用後 $g_{j+1}$ の上 $|x\rangle$ ルートからリーフへのパスの遷移振幅は、パスに沿ったエッジのすべての重みの積です。最終状態が $|\psi \rangle$ 、ノードで終わるすべてのルートから葉までのパスの振幅を合計します。 $|\psi \rangle$ 。

より厳密に言うと、量子回路 $Cの場合、履歴の合計ツリーは深さ$ $m$ のツリーであり、各ゲートに対して 1 つのレベルが存在する。 $g_{i}$ 根に加えて、分岐係数も $2n$ 。

定義—履歴とは、履歴の総和ツリーにおけるパスのことです。履歴はシーケンスで表します。 $(u_{0}=|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m}=x)$ ある最終状態 $x$ に対して。

定義する— $u,v\in \{0,1\}^{n}$ エッジの振幅を $(|u\rangle ,|v\rangle )$ 履歴ツリーの $j$ 番目のレベルでは $\alpha _{j}(u\rightarrow v)=\langle v|g_{j}|u\rangle$ 履歴については $h=(u_{0}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m})$ 履歴の遷移振幅は積である $\alpha _{h}=\alpha _{1}(|0\rangle ^{\otimes n}\rightarrow u_{1})\alpha _{2}(u_{1}\rightarrow u_{2})\cdots \alpha _{m}(u_{m-1}\rightarrow x)$ 。

主張—履歴について $(u_{0}\rightarrow \cdots \rightarrow u_{m})$ 履歴の遷移振幅は多項式時間で計算可能である。

証拠

各ゲート $g_{j}$ 分解すると $g_{j}=I\otimes {\tilde {g}}_{j}$ あるユニタリ演算子に対して ${\tilde {g}}_{j}$ 2つの量子ビットに作用する。一般性を失うことなく、これらは最初の2つとすることができる。したがって、 $\langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle$ $これはn$ の多項式時間で計算できます。mはnの多項式なので $、$ $履歴$ の遷移振幅は多項式時間で計算できます。

クレーム—許可する $C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle$ 量子回路の最終状態となる。 $x\in \{0,1\}^{n}$ 振幅 $\alpha _{x}$ 計算方法 $\alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}$ 。

証拠

我々は持っています $\alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}$ 結果は、挿入することで直接得られます。 $I=\sum _{x\in \{0,1\}^{n}}|x\rangle \langle x|$ 間 $g_{1},g_{2}$ 、そして $g_{2},g_{3}$ などと続けて、方程式を展開します。すると、各項は $\alpha _{h}$ 、どこ $h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )$

請求- ${\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {PSPACE}}$

履歴の合計アルゴリズムで振幅を計算することに注目してください $\alpha _{x}$ 計算のどの時点でも、履歴は 1 つだけ保存されます。したがって、履歴の合計アルゴリズムは、 $O(nm)$ 計算するためのスペース $\alpha _{x}$ 任意の $x$ に対して、 $O(nm)$ 履歴を保存するには、ワークスペース変数に加えてビットが必要です。

したがって、多項式空間では、 $\sum _{x}|\alpha _{x}|^{2}$ 最初の量子ビットがすべての $xに対して$ 1は、回路の終了時に最初の量子ビットが1と測定される確率です。

証明のために与えられたシミュレーションと比較すると、 ${\mathsf {BQP}}\subseteq {\mathsf {EXP}}$ 我々のアルゴリズムは、スペースははるかに少なくて済むが、時間ははるかに多くかかる。実際には、 $O(m\cdot 2^{mn})$ さあ、単一の振幅を計算する時間だ！

BQPとPP

同様の履歴の総和論法を用いて、 ${\mathsf {BQP}}\subseteq {\mathsf {PP}}$ [ ¹⁴^]

PとBQP

私たちは知っています ${\mathsf {P}}\subseteq {\mathsf {BQP}}$ なぜなら、すべての古典回路は量子回路によってシミュレートできるからである。^{[ 15 ]}

BQPはP以外の難問、具体的にはNPの難問を解決すると推測されている。しかし、P=NPかどうかが不明であるため、これらの問題が実際にPに含まれるかどうかは不明であり、この主張は不確定である。以下に、この推測を裏付けるいくつかの証拠を示す。

参考文献

1 2 3マイケル・ニールセン、アイザック・チュアン（2000）。量子計算と量子情報。ケンブリッジ：ケンブリッジ大学出版局。ISBN 0-521-63503-9。
1 2 3 4バーンスタイン、イーサン。ヴァジラニ、ウメッシュ (1997 年 10 月)。「量子複雑性理論」。SIAM ジャーナルオンコンピューティング。26 ( 5 ) : 1411–1473。CiteSeerX 10.1.1.655.1186 。土井：10.1137/S0097539796300921。
↑ Barak, Sanjeev Arora, Boaz (2009). Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak . Cambridge. p. 122. 2018年7月24日取得。 {{cite book}}: CS1 maint: 発行元が見つかりません (リンク) CS1 maint: 複数の名前: 著者リスト (リンク)
↑ Fortnow, Lance; Rogers, John (1999). "量子計算の複雑性制限" (PDF) . J. Comput. Syst. Sci . 59 (2): 240– 252. arXiv : cs/9811023 . doi : 10.1006/jcss.1999.1651 . ISSN 0022-0000 . S2CID 42516312 . 2022年10月9日にオリジナルからアーカイブ(PDF) 。
↑ L. アドルマン、J. デマレ、医学博士。黄さん。量子計算能力。 SIAM J. Comput.、26(5):1524–1540、1997。
↑ジョージ、マイケル・ゴダーバウアー、ステファン。「ECCC-TR18-107」。eccc.weizmann.ac.il 。2018-08-03に取得。{{cite web}}: CS1 maint: 複数の名前: 著者リスト (リンク)
1 2 Aaronson, Scott (2010). "BQP と多項式階層" (PDF) . ACM STOC 2010 論文集. 2022-10-09 のオリジナルからアーカイブ(PDF) 。
↑ Aaronson, Scott (2005). "Quantum computing, postselection, and probabilistic polynomial-time". Proceedings of the Royal Society A. 461 ( 2063): 3473–3482 . arXiv : quant-ph/0412187 . Bibcode : 2005RSPSA.461.3473A . doi : 10.1098/rspa.2005.1546 . S2CID 1770389 . プレプリントは以下から入手可能です。
↑アーロンソン、スコット (2004-01-11). 「今週の複雑性クラス: PP」 .計算複雑性ウェブログ. 2008-05-02取得.
↑ Janzing, Dominik; Wocjan, Pawel (2007-03-30). "A Simple PromiseBQP-complete Matrix Problem" (PDF) . Theory of Computing . 3 (4): 61– 79. doi : 10.4086/toc.2007.v003a004 . 2024-04-18に取得.
↑マイケル・A・ニールセン、アイザック・L・チュアン（2010年12月9日）「4.4 測定」『量子計算と量子情報：10周年記念版』ケンブリッジ大学出版局、186ページ。ISBN 978-1-139-49548-6。
↑ Odel A. Cross (2012年11月5日)「5.2.2 遅延測定」量子コンピューティングのトピックス。OA Cross。348ページ。ISBN 978-1-4800-2749-7。
↑ E. Bernstein および U. Vazirani. 量子複雑性理論、SIAM Journal on Computing、26(5):1411-1473、1997 年。
↑ L. Adleman、J. DeMarrais、M. Huang。「量子計算可能性」、SIAM Journal on Computing 26:1524-1540、1997年。
↑ Nielsen, Michael A.; Chuang, Isaac L. (2000), Quantum Computation and Quantum Information, Cambridge: Cambridge University Press, ISBN 0-521-63235-8, MR 1796805.
1 2 arXiv:quant-ph/9508027v2量子コンピュータ上での素因数分解と離散対数のための多項式時間アルゴリズム、Peter W. Shor

外部リンク

Complexity Zoo の BQP へのリンク(2013 年 6 月 3 日時点のWayback Machineにアーカイブ)

[Chuang2000-1] 1 2 3マイケル・ニールセン、アイザック・チュアン（2000）。量子計算と量子情報。ケンブリッジ：ケンブリッジ大学出版局。ISBN 0-521-63503-9。

[BernVazi-2] 1 2 3 4バーンスタイン、イーサン。ヴァジラニ、ウメッシュ (1997 年 10 月)。「量子複雑性理論」。SIAM ジャーナルオンコンピューティング。26 ( 5 ) : 1411–1473。CiteSeerX 10.1.1.655.1186 。土井：10.1137/S0097539796300921。

[3] Barak, Sanjeev Arora, Boaz (2009). Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak . Cambridge. p. 122. 2018年7月24日取得。 {{cite book}}: CS1 maint: 発行元が見つかりません (リンク) CS1 maint: 複数の名前: 著者リスト (リンク)

[4] Fortnow, Lance; Rogers, John (1999). "量子計算の複雑性制限" (PDF) . J. Comput. Syst. Sci . 59 (2): 240– 252. arXiv : cs/9811023 . doi : 10.1006/jcss.1999.1651 . ISSN 0022-0000 . S2CID 42516312 . 2022年10月9日にオリジナルからアーカイブ(PDF) 。

[5] L. アドルマン、J. デマレ、医学博士。黄さん。量子計算能力。 SIAM J. Comput.、26(5):1524–1540、1997。

[6] ジョージ、マイケル・ゴダーバウアー、ステファン。「ECCC-TR18-107」。eccc.weizmann.ac.il 。2018-08-03に取得。{{cite web}}: CS1 maint: 複数の名前: 著者リスト (リンク)

[:0-7] 1 2 Aaronson, Scott (2010). "BQP と多項式階層" (PDF) . ACM STOC 2010 論文集. 2022-10-09 のオリジナルからアーカイブ(PDF) 。

[PostBQP=PP-8] Aaronson, Scott (2005). "Quantum computing, postselection, and probabilistic polynomial-time". Proceedings of the Royal Society A. 461 ( 2063): 3473–3482 . arXiv : quant-ph/0412187 . Bibcode : 2005RSPSA.461.3473A . doi : 10.1098/rspa.2005.1546 . S2CID 1770389 . プレプリントは以下から入手可能です。

[9] アーロンソン、スコット (2004-01-11). 「今週の複雑性クラス: PP」 .計算複雑性ウェブログ. 2008-05-02取得.

[janzing-wocjan-10] Janzing, Dominik; Wocjan, Pawel (2007-03-30). "A Simple PromiseBQP-complete Matrix Problem" (PDF) . Theory of Computing . 3 (4): 61– 79. doi : 10.4086/toc.2007.v003a004 . 2024-04-18に取得.

[NielsenChuang2010-11] マイケル・A・ニールセン、アイザック・L・チュアン（2010年12月9日）「4.4 測定」『量子計算と量子情報：10周年記念版』ケンブリッジ大学出版局、186ページ。ISBN 978-1-139-49548-6。

[Cross2012-12] Odel A. Cross (2012年11月5日)「5.2.2 遅延測定」量子コンピューティングのトピックス。OA Cross。348ページ。ISBN 978-1-4800-2749-7。

[13] E. Bernstein および U. Vazirani. 量子複雑性理論、SIAM Journal on Computing、26(5):1411-1473、1997 年。

[14] L. Adleman、J. DeMarrais、M. Huang。「量子計算可能性」、SIAM Journal on Computing 26:1524-1540、1997年。

[15] Nielsen, Michael A.; Chuang, Isaac L. (2000), Quantum Computation and Quantum Information, Cambridge: Cambridge University Press, ISBN 0-521-63235-8, MR 1796805.

[Shor-16] 1 2 arXiv:quant-ph/9508027v2量子コンピュータ上での素因数分解と離散対数のための多項式時間アルゴリズム、Peter W. Shor

[

[

[ 3 ]

4

5

[

[

[

[ 10 ]

は、

ことで

13

14

[ 15 ]

[ 16 ]

BQP

意味

他の複雑性クラスとの関係

Promise-BQPにとって完全な問題

近似回路プローブ

BQPとEXP

BQPとPSPACE

BQPとPP

PとBQP

関連項目

参考文献

外部リンク

関連するトピック

BQPは、 PSPACE

Pを一般化した他の確率的複雑性クラス（

ZPP

RP