BQP
で計算複雑性理論、有界誤り量子多項式時間（BQPは）のクラスである意思決定の問題によって解ける量子コンピュータでは多項式時間のすべてのインスタンスの最大で1/3の誤り確率で、。これは複雑度クラス BPPの量子アナログです。
決定問題を高い確率で解決し、多項式時間で実行されることが保証されている量子アルゴリズム（量子コンピューターで実行されるアルゴリズム）が存在する場合、決定問題はBQPのメンバーです。アルゴリズムを実行すると、少なくとも2/3の確率で決定問題が正しく解決されます。
BQPアルゴリズム（1回実行） 答え 生産
正しい 答え
はい 番号
はい ≥2/ 3 ≤1/ 3
番号 ≤1/ 3 ≥2/ 3
BQPアルゴリズム（k回実行）
答え 生産
正しい 答え
はい 番号
はい > 1 − 2 − ck
番号 > 1 − 2 − ck
定数c > 0の場合
コンテンツ
1 意味
2 BQP-完全な問題
2.1 APPROX-QCIRCUIT-PROBの問題
3 他の複雑さのクラスとの関係
3.1 BQPとEXP 3.2 BQPとPSPACE
3.2.1 履歴の合計
3.3 BQPとPP 3.43.4 BQP、P、およびNP
4 も参照してください
5 参考文献
6 外部リンク
意味
BQPは、量子回路の特定の有界誤差均一ファミリに関連付けられた言語と見なすことができます。言語Lは、量子回路の多項式時間均一ファミリーが存在する場合にのみBQPに含まれます。
{{： ∈ }
{ {Q_ {n} Colon n in mathbb {N} }}
、 そのような
すべてのために ∈ {n in mathbb {N}}
、Q nはnキュービットを入力として受け取り、1ビットを出力します
すべてのためのxでL、（（ ||（（ ）。= 1 ）。 ≥2 3
{ mathrm {Pr}（Q _ {| x |}（x）= 1） geq { tfrac {2} {3}}}
Lにないすべてのxについて、（（ ||（（ ）。= 0 ）。 ≥2 3
{ mathrm {Pr}（Q _ {| x |}（x）= 0） geq { tfrac {2} {3}}}
あるいは、量子チューリングマシンの観点からBQPを定義することもできます。言語Lは、すべてのインスタンスで最大1/3のエラー確率でLを受け入れる多項式量子チューリングマシンが存在する場合にのみ、BQPに含まれます。
他の「制限付きエラー」確率クラスと同様に、定義での1/3の選択は任意です。アルゴリズムを一定の回数実行し、多数決を行って、チェルノフ境界を使用して、1未満の任意の望ましい正しさの確率を達成できます。複雑さのクラスは、一方では1/2 − n − cまでの誤差を許容するか、他方では2 − n cまでの誤差を要求することによって変更されません。ここで、cは任意の正の定数であり、nは長さです。入力の。
BQP-完全な問題
NP完全性やその他の完全問題の概念と同様に、BQP完全問題は、BQPにある問題として定義でき、BQPのすべての問題は多項式時間でそれに還元されます。
これは直感的なBQP完全問題であり、BQPの定義に直接起因します。
APPROX-QCIRCUIT-PROBの問題
量子回路の説明が与えられた {C}
に作用する {n}
キュービット {m}
ゲート、ここで {m}
の多項式です {n}
各ゲートは1つまたは2つのキュービットと2つの数値に作用します
α β ∈ [ 0 1
] α
>> β { alpha、 beta in 、 alpha> beta}
beta }””>
、次の2つのケースを区別します。
状態の最初のキュービットを測定する |
0 ⟩ ⊗ {C | 0 rangle ^ { otimes n}}
収量 | 1 ⟩ {| 1 rangle}
確率で≥ α
{ geq alpha}
状態の最初のキュービットを測定する |
0 ⟩ ⊗ {C | 0 rangle ^ { otimes n}}
収量 | 1 ⟩ {| 1 rangle}
確率で≤ β
{ leq beta}
インスタンスがこれらの2つのケースでカバーされていない場合、問題は動作を指定しないことに注意して
請求。BQPの問題はすべてAPPROX-QCIRCUIT-PROBになります。
証拠。アルゴリズムがあるとしましょう {A}
これはAPPROX-QCIRCUIT-PROBを解きます。つまり、与えられた量子回路です。 {C}
に作用する {n}
キュービット、および2つの数値
α β ∈ [ 0 1
] α
>> β { alpha、 beta in 、 alpha> beta}
beta }””>
、 {A}
上記の2つのケースを区別します。このオラクルを設定することで、BQPの問題を解決できます。α = 2 /
3 β= 1 / 3
{ alpha = 2/3、 beta = 1/3}
。
どんな場合でも L ∈{L in mathrm {BQP}}
、量子回路のファミリーが存在します
{{： ∈ }
{ {Q_ {n} Colon n in mathbb {N} }}
そのようなすべてのために ∈ {n in mathbb {N}}
、 状態
| ⟩
{| x rangle}
の {n}
キュービット、もし ∈ L 、 （（ NS（（ | ⟩
）。= 1
）。≥ 2 / 3
{x in L、Pr（Q_ {n}（| x rangle）= 1） geq 2/3}
; それ以外の場合 ∉ L 、 （（ NS（（ | ⟩
）。= 0
）。≥ 2 / 3
{x notin L、Pr（Q_ {n}（| x rangle）= 0） geq 2/3}
。入力を修正する
| ⟩
{| x rangle}
の {n}
キュービット、および対応する量子回路 {Q_ {n}}
。最初に回路を構築できます {C_ {x}}
そのような |0 ⟩
⊗=
| ⟩
{C_ {x} | 0 rangle ^ { otimes n} = | x rangle}
。これは、ハードワイヤリングによって簡単に行うことができます
| ⟩
{| x rangle}
一連のCNOTゲートを適用してキュービットを反転します。次に、2つの回路を組み合わせて取得できます ′={C ‘= C_ {x} Q_ {n}}
、 そしていま ′ 0 ⟩ ⊗= | ⟩
{C ‘| 0 rangle ^ { otimes n} = Q_ {n} | x rangle}
。そして最後に、必然的に {Q_ {n}}
は、いくつかのキュービットを測定し、それらにいくつかの（古典的な）論理ゲートを適用することによって得られます。いつでも測定を延期し 、回路の経路を変更して、の最初のキュービットを測定することができます。 ′ 0 ⟩ ⊗= | ⟩
{C ‘| 0 rangle ^ { otimes n} = Q_ {n} | x rangle}
、出力を取得します。これが私たちの回路になります {C}
、およびのメンバーシップを決定します {x}
の L {L}
実行することによって （（ ）。
{A（C）}
とα = 2 /
3 β= 1 / 3
{ alpha = 2/3、 beta = 1/3}
。BQPの定義により、最初のケース（受け入れ）または2番目のケース（拒否）のいずれかに分類されるため、 L ∈{L in mathrm {BQP}}
APPROX-QCIRCUIT-PROBになります。
APPROX-QCIRCUIT-PROBは、いくつかのよく知られた複雑さのクラスとBQPの間の関係を証明しようとするときに便利です。
他の複雑さのクラスとの関係
コンピュータサイエンスの未解決の問題：
の関係は何ですか{{ mathsf {BQP}}}
と {{ mathsf {NP}}}
？（コンピュータサイエンスにおける未解決の問題）
BQPと他の問題空間
との疑わしい関係
PSPACE内で
Pを一般化する他の確率的複雑度クラス（ZPP、 RP、co-RP、 BPP、 PP）
に関連するBQP
。これらの封じ込めのいずれかが厳格であるかどうかは不明です。
BQPは量子コンピューター用に定義されています。従来のコンピューター（またはより正式には確率的チューリングマシン）に対応する複雑さのクラスはBPPです。PやBPPと同様に、BQP自体は低く、つまりBQP BQP = BQPです。非公式には、多項式時間アルゴリズムは合成の下で閉じられるため、これは当てはまります。多項式時間アルゴリズムが多項式として多くの多項式時間アルゴリズムをサブルーチンとして呼び出す場合、結果のアルゴリズムは依然として多項式時間です。
BQPにはPとBPPが含まれ、AWPP、 PP 、およびPSPACEに含まれています。実際に、BQPは、ある低いためPPつまり、PPのマシンは解決することができることからの利益達成ないBQPの、瞬時にこれらの類似クラス間の電力の可能な差の指標を問題が。古典的な複雑さのクラスとの既知の関係は次のとおりです。 ⊆⊆⊆ W ⊆ ⊆NS E ⊆ E {{ mathsf {P subseteq BPP subseteq BQP subseteq AWPP subseteq PP subseteq PSPACE subseteq EXP}}}
P≟PSPACEの問題はまだ解決されていないため、BQPと上記のクラスとの間の不平等の証明は難しいと思われます。 BQPとNPの関係は不明です。2018年5月には、コンピュータ科学者は、ラズ蘭のプリンストン大学のとAvishayタルスタンフォード大学の論文発表され、に比べて、あることを示したオラクルは、BQPはに含まれていませんでしたPHを。
BQPに事後選択を追加すると、PPに等しい複雑度クラスPostBQPが生成されます。
これらの結果のいくつかを以下で証明または説明します。
BQPとEXP
より簡単な封じ込めから始めます。それを示すために NS⊆
E {{ mathsf {BQP}} subseteq { mathsf {EXP}}}
、APPROX-QCIRCUIT-PROBはBQP完了であるため、APPROX-QCIRCUIT-PROBがEXPにあることを示すだけで十分です。
主張 —
APPROX-QCIRCUIT-PROB ∈ E {{ text {APPROX-QCIRCUIT-PROB}} in { mathsf {EXP}}}
証明 —
アイデアは単純です。量子回路Cが与えられると、指数関数的なパワーがあるので、古典的なコンピューターを使用してCの各ゲートを刺激し、最終状態を得ることができます。
より正式には、Cをn個のキュービットとm個のゲート上の多項式サイズの量子回路とします。ここでmはnの多項式です。させて
| ψ 0⟩ = |
0 ⟩ ⊗ {| psi _ {0} rangle = | 0 rangle ^ { otimes n}}
と| ψ
I ⟩ {| psi _ {i} rangle}
回路のi番目のゲートが適用された後の状態になります
| ψ I− 1 ⟩
{| psi _ {i-1} rangle}
。各州
| ψ I ⟩ {| psi _ {i} rangle}
古典的なコンピュータでは、の単位ベクトルとして表すことができます。 2 { mathbb {C} ^ {2 ^ {n}}}
。さらに、各ゲートは次の行列で表すことができます。 2××
2 { mathbb {C} ^ {2 ^ {n} times 2 ^ {n}}}
。したがって、最終状態 | ψ ⟩
{| psi _ {m} rangle}
で計算することができます O （（ 2
2 ）。
{O（m2 ^ {2n}）}
時間、したがってすべて一緒に、私たちは2 O（（ ）。
{2 ^ {O（n）}}
最終状態を計算するための時間アルゴリズム、したがって最初のキュービットが1であると測定される確率。これは、
APPROX-QCIRCUIT-PROB ∈ E {{ text {APPROX-QCIRCUIT-PROB}} in { mathsf {EXP}}}
。
このアルゴリズムには次のものも必要であることに注意してください
2 O （（ ）。
{2 ^ {O（n）}}
ベクトルと行列を格納するスペース。次のセクションでは、スペースの複雑さを改善できることを示します。
BQPとPSPACE
証明する NS⊆NS E
{{ mathsf {BQP}} subseteq { mathsf {PSPACE}}}
、最初に履歴の合計と呼ばれる手法を紹介します。
履歴の合計
履歴の合計は、物理学者のリチャードファインマンが経路積分の定式化のために導入した手法です。この手法を量子コンピューティングに適用して、APPROX-QCIRCUIT-PROBを解決します。
履歴ツリーの合計
t個のゲートで構成される量子回路Cを考えてみましょう。 1
、 2 ⋯
、 {g_ {1}、g_ {2}、 cdots、g_ {m}}
、ここでそれぞれ {g_ {j}}
ユニバーサルゲートセットから来て、最大2キュービットに作用します。履歴の合計が何であるかを理解するために、量子回路がツリーとして与えられた場合の量子状態の進化を視覚化します。ルートは入力です| 0 ⟩
⊗ {| 0 rangle ^ { otimes n}}
、およびツリー内の各ノードには
2 {2 ^ {n}}
それぞれが州を表す子供たち { mathbb {C} ^ {n}}
。状態を表すj番目のレベルのノードからのツリーエッジの重み
| ⟩
{| x rangle}
のノードに + 1 {j + 1}
-状態を表す第レベル
|y ⟩
{| y rangle}
は⟨ y
| + 1 | ⟩
{ langle y | g_ {j + 1} | x rangle}
、の振幅
|y ⟩
{| y rangle}
適用後 + 1 {g_ {j + 1}}
オン
| ⟩
{| x rangle}
。ルートからリーフへのパスの遷移振幅は、パスに沿ったエッジのすべての重みの積です。最終状態が存在する確率を取得するには| ψ ⟩
{| psi rangle}
、を表すノードで終了するすべてのルートからリーブへのパスの振幅を合計します。
|ψ ⟩
{| psi rangle}
。
より正式には、量子回路Cの場合、履歴ツリー全体の合計は深さmのツリーであり、各ゲートに1つのレベルが 私
{g_ {i}}
ルートに加えて、分岐係数を使用
2 {2 ^ {n}}
。
定義 — 履歴は、履歴の合計ツリー内のパスです。履歴をシーケンスで示します（（ u0 = |
0⟩ u 1 ⋯
u − 1 u = ）。
{ displaystyle（u_ {0} = | 0 rangle ^ { otimes n} rightarrow u_ {1} rightarrow cdots rightarrow u_ {m-1} rightarrow u_ {m} = x）}
いくつかの最終状態xについて。
定義 — みましょうu v ∈
{{ 0 1 } {u、v in {0，1 } ^ {n}}
。エッジの振幅をしましょう（（ | u ⟩ |
v ⟩ ）。
{ displaystyle（| u rangle、| v rangle）}
でJ履歴木の上に和の番目のレベルに
α （（ u v ）。= ⟨ v
| |
u ⟩ { alpha _ {j}（u rightarrow v）= langle v | g_ {j} | u rangle}
。どんな歴史でも =（（ u0 u 1 ⋯
u − 1 u ）。
{h =（u_ {0} rightarrow u_ {1} rightarrow cdots rightarrow u_ {m-1} rightarrow u_ {m}）}
、履歴の遷移振幅は積です
α = α 1（（ |
0⟩ u 1
）。 α 2（（ u1 u 2
）。 ⋯ α （（ u − 1 ）。
{ 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）}
。
主張 — 歴史のために（（ u0 ⋯
u ）。
{ displaystyle（u_ {0} rightarrow cdots rightarrow u_ {m}）}
。履歴の遷移振幅は、多項式時間で計算できます。
証明 —
各ゲート {g_ {j}}
に分解することができます = I ⊗ 〜 {g_ {j} = I otimes { tilde {g}} _ {j}}
一部のユニタリ作用素 〜 {{ tilde {g}} _ {j}}
一般性を失うことなく最初の2つと見なすことができる2つのキュービットに作用します。したがって、⟨ v
| |
u⟩ = ⟨ v 1 v 2
| 〜 |u 1 u 2 ⟩ ⟨ v
3 ⋯ v | u 3 ⋯ u ⟩
{ 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の多項式であるため、履歴の遷移振幅は多項式時間で計算できます。
主張 — みましょう |
0 ⟩ ⊗ =
∑ ∈
{{ 0 1 } α | ⟩
{C | 0 rangle ^ { otimes n} = sum _ {x in {0，1 } ^ {n}} alpha _ {x} | x rangle}
量子回路の最終状態になります。いくつかのための ∈
{{ 0 1 } {x in {0，1 } ^ {n}}
、振幅
α { alpha _ {x}}
によって計算することができます α = ∑ =（（|0 ⊗ u 1 ⋯
u − 1 | ⟩ ）。 α { alpha _ {x} = sum _ {h =（| 0 rangle ^ { otimes n} rightarrow u_ {1} rightarrow cdots rightarrow u_ {t-1} rightarrow | x rangle）} alpha _ {h}}
。
証明 —
我々は持っています
α =
⟨ | |
0 ⟩ ⊗ =
⟨ |− 1 ⋯ 1
| |
0 ⟩ ⊗ { 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 =
∑ ∈
{{ 0 1 } | ⟩
⟨ |
{I = sum _ {x in {0，1 } ^ {n}} | x rangle langle x |}
の間に 1 、 2 {g_ {1}、g_ {2}}
、 と 2 、 3 {g_ {2}、g_ {3}}
、などのように、方程式を展開します。次に、各用語はに対応します
α { alpha _ {h}}
、 どこ =（（ |
0⟩ u 1 ⋯
u − 1 | ⟩ ）。 {h =（| 0 rangle ^ { otimes n} rightarrow u_ {1} rightarrow cdots rightarrow u_ {t-1} rightarrow | x rangle）}
主張 —
APPROX-QCIRCUIT-PROB
∈NS E
{{ text {APPROX-QCIRCUIT-PROB}} in { mathsf {PSPACE}}}
いくつかの振幅を計算するための履歴の合計アルゴリズムに注意してください
α { alpha _ {x}}
、計算の任意の時点で1つの履歴のみが保存されます。したがって、履歴の合計アルゴリズムは O （（）。
{O（nm）}
計算するスペース
α { alpha _ {x}}
以来の任意のx O （（）。
{O（nm）}
一部のワークスペース変数に加えて、履歴を格納するためにビットが必要です。
したがって、多項式空間では、次のように計算できます。
∑ || 2
{ sum _ {x} | alpha _ {x} | ^ {2}}
すべてのxにわたって、最初のキュービットは1、これは、回路の終わりまでに最初のキュービットが1であると測定される確率です。
その証明のために与えられたシミュレーションと比較して注意してください NS⊆
E {{ mathsf {BQP}} subseteq { mathsf {EXP}}}
、ここでのアルゴリズムは、はるかに少ないスペースで済みますが、代わりにはるかに長い時間がかかります。実際にはそれがかかります O （（ 2 NS）。
{O（m2 ^ {mn}）}
単一の振幅を計算する時間です！
BQPとPP
同様のsum-over-histories引数を使用して、次のことを示すことができます。 NS⊆ {{ mathsf {BQP}} subseteq { mathsf {PP}}}
。
BQP、P、およびNP
まず第一に、私たちは知っています⊆{{ mathsf {P}} subseteq { mathsf {BQP}}}
なぜなら、すべての古典的な回路は量子回路によってシミュレートできるからです。
BQPは、P以外の難しい問題、特にNPの問題を解決すると推測されます。P = NPかどうかわからないため、主張は不定です。したがって、これらの問題が実際にPにあるかどうかはわかりません。以下は、推測のいくつかの証拠です。
素因数分解（ショアのアルゴリズムを参照）
離散対数
量子システムのシミュレーション（ユニバーサル量子シミュレーターを参照）
単一性の特定の根でジョーンズ多項式を近似する
Harrow-Hassidim-Lloyd（HHL）アルゴリズム
しかし、私たちはまたの類似物を知っています⊈{{ mathsf {NP}} not subseteq { mathsf {BQP}}}
「ブラックボックス」の意味で。非構造化検索の問題を考えてみましょう。未知の関数へのOracleアクセスが与えられた場合 ：
{{0 1 }
{{0 1 }
{f： {0，1 } ^ {n} to {0，1 }}
、検索はxは、そのようなことを （（ ）。= 1
{f（x）= 1}
。この問題は明らかにNPに一方、この問題に最適な量子アルゴリズムは、グローバーのアルゴリズムです。 O （（ 2 ）。
{O（{ sqrt {2 ^ {n}}}）}
そのオラクルを介してfへのアクセスのみが許可されている場合。
も参照してください
隠されたサブグループの問題
多項式階層（PH）
量子複雑性理論
QMA、 NPと同等の量子。
参考文献
^ Michael Nielsen and Isaac Chuang（2000）。量子計算と量子情報。ケンブリッジ：ケンブリッジ大学出版局。ISBN 0-521-63503-9。
^ バーンスタイン、イーサン; ウメーシュ・ヴァジラーニ（1997年10月）。「量子複雑性理論」。SIAMジャーナルオンコンピューティング。26（5）：1411–1473。CiteSeerX 10.1.1.655.1186。土井：10.1137 / S0097539796300921。 ^ Barak、Sanjeev Arora、Boaz（2009）。計算の複雑さ：現代的なアプローチ/ SanjeevAroraとBoazBarak。ケンブリッジ。NS。122 。
^ マイケルA.ニールセン; アイザックL.チュアン「4.4測定」。量子計算と量子情報：10周年記念版。ケンブリッジ大学出版局。NS。186. ISBN 978-1-139-49548-6。
^ Odel A. Cross「5.2.2遅延測定」。量子コンピューティングのトピック。OAクロス。NS。348. ISBN 978-1-4800-2749-7。
^ フォートノフ、ランス; ロジャース、ジョン（1999）。「量子計算の複雑さの制限」（PDF）。J.計算。システム。科学。59（2）：240–252。arXiv：cs / 9811023。土井：10.1006 /jcss.1999.1651。ISSN 0022から0000まで。S2CID 42516312。
^ L. Adleman、J。DeMarrais、およびM.-D. 黄。量子計算可能性。SIAM J. Comput。、26（5）：1524–1540、1997。
^ ジョージ、マイケルゴダーバウアー、ステファン。「ECCC-TR18-107」。eccc.weizmann.ac.il 。
^ アーロンソン、スコット（2005）。「量子計算、事後選択、および確率的多項式時間」。英国王立協会Aの議事。461（2063）：3473–3482。arXiv：quant-ph / 0412187。Bibcode：2005RSPSA.461.3473A。土井：10.1098 /rspa.2005.1546。S2CID 1770389。 。で入手可能なプレプリント ^ アーロンソン、スコット（2004-01-11）。「今週の複雑さのクラス：PP」。計算の複雑さのウェブログ。
^ E。ベルンシュタインとU.ヴァジラーニ。量子複雑性理論、SIAM Journal on Computing、26（5）：1411-1473、1997。
^ L. Adleman、J。DeMarrais、およびM.Huang。量子計算可能性、SIAM Journal on Computing 26：1524-1540、1997。
^ ニールセン、マイケルA。; Chuang、Isaac L.（2000）、Quantum Computation and Quantum Information、Cambridge：Cambridge University Press、ISBN 0-521-63235-8、MR1796805。
^ arXiv：quant-ph / 9508027v2量子コンピューターでの素因数分解と離散対数のための多項式時間アルゴリズム、Peter W. Shor ^ ザルカ、クリストフ（1999-10-01）。「Groverの量子探索アルゴリズムが最適です」。フィジカルレビューA。60（4）：2746–2751。arXiv：quant-ph / 9711070。土井：10.1103 /PhysRevA.60.2746。
外部リンク
ウェイバックマシンで2013年6月3日にアーカイブされたBQPへの複雑性動物園のリンク”