ポストBQP

計算複雑性理論において、PostBQPは、事後選択と制限された誤差 (アルゴリズムがすべての入力に対して少なくとも 2/3 の時間正しいという意味) を 備えた量子チューリング マシンで多項式時間で解決可能なすべての計算問題で構成される複雑性クラスです。

事後選択は、現実的なコンピュータ（量子コンピュータであっても）が備えている機能とは考えられていませんが、それでも事後選択マシンは理論的な観点からは興味深いものです。

PostBQPから 2 つの主要な特徴 (量子性、事後選択) のいずれかを削除すると、次の 2 つの複雑性クラスが得られます。どちらもPostBQPのサブセットです。

• BQPはポスト選択がない点を除いてPostBQPと同じです
• BPP_パスはPostBQPと同じであるが、量子アルゴリズムの代わりに、アルゴリズムが古典的なランダム化アルゴリズム（事後選択付き）である点が異なる^[1]。

事後選択の追加により、量子チューリングマシンははるかに強力になるようです。スコット・アーロンソンは^{[2] [3]} ポストBQPはPPに等しいことを証明しました。これは比較的強力であると考えられているクラスですが、BQPには一見小さいクラスNPが含まれていることすら知られていません。同様の手法を使用して、アーロンソンは量子コンピューティングの法則に小さな変更を加えると、大きな影響が出ることも証明しました。具体的な例として、次の2つの変更のいずれかを行うと、 BQPの「新しい」バージョンはPPに等しくなります。

• 「量子ゲート」の定義を、ユニタリ演算だけでなく線形演算も含むように拡張すると、
• 基底状態を測定する確率が、任意の偶数p > 2に対して ではなくに比例する場合。${\displaystyle |x\rangle }$${\displaystyle |\alpha_{x}|^{p}}$${\displaystyle |\alpha _{x}|^{2}}$

PostBQPのいくつかの特性を説明するために、量子事後選択を説明する正式な方法を決めます。量子アルゴリズムを量子回路の族(具体的には、均一な回路族) として定義します。1 つの量子ビットを事後選択量子ビット P、もう 1 つを出力量子ビット Qと指定します。PostBQP は、事後選択量子ビットが であるイベントで事後選択することによって定義されます。明示的に、言語Lが PostBQP に属するとは、量子アルゴリズムAが存在し、入力xに対してAを実行し、2 つの量子ビットPとQ を測定した後、 ${\displaystyle |1\rangle }$

• P = 1 の確率はゼロではない
• 入力xがLに含まれる場合、Pr[ Q = 1| P = 1] ≥ 2/3
• 入力xがLにない場合はPr[ Q = 0| P = 1] ≥ 2/3です。

アルゴリズムの最後に単一のポスト選択ステップを許可すること（上記のように）と、アルゴリズムの途中で中間のポスト選択ステップを許可することは同等であることが示されます。^{[2] [4]}

以下はPostBQPの 3 つの基本的な特性です(同様の証明によりBQPにも当てはまります)。

1. PostBQPは補集合に関して閉じています。PostBQPの言語Lと対応する決定回路ファミリが与えられた場合、測定後に出力量子ビットを反転して新しい回路ファミリを作成し、新しい回路ファミリはLの補集合がPostBQPにあることを証明します。
2. PostBQPでは確率増幅を行うことができます。PostBQP の定義は、定義内の 2/3 の値を 1/2 から 1 までの間の他の定数に置き換えても変更されません。たとえば、成功確率が 2/3 のPostBQPアルゴリズムAがある場合、 Aの 3 つの独立したコピーを実行し、3 つの「内部」ビットの結合に等しいポスト選択ビットを出力し、3 つの「内部」ビットの過半数に等しい出力ビットを出力する別のアルゴリズムを構築できます。新しいアルゴリズムは、元の 2/3 よりも大きい条件付き確率で正しく動作します。${\displaystyle (2/3)^{3}+3(1/3)(2/3)^{2}=20/27}$
3. PostBQP は、交差に関して閉じています。2つの言語⁠ ⁠と⁠ ⁠のPostBQP回路ファミリがあり、それぞれに後選択量子ビットと出力量子ビット⁠ ⁠があるとします。確率増幅により、両方の回路ファミリの成功確率が少なくとも 5/6 であると想定できます。次に、 ⁠ ⁠と⁠ ⁠の回路が独立して実行される複合アルゴリズムを作成し、P を⁠ ⁠と⁠ ⁠の論理積に設定し、Q を⁠ ⁠ ⁠と⁠ ⁠の論理積に設定します。この複合アルゴリズムが(条件付き) 確率少なくとも 2/3 でへのメンバーシップを正しく決定することは、和集合によって簡単にわかります。${\displaystyle L_{1}}$${\displaystyle L_{2}}$${\displaystyle P_{1},P_{2},Q_{1},Q_{2}}$${\displaystyle L_{1}}$${\displaystyle L_{2}}$${\displaystyle P_{1}}$${\displaystyle P_{2}}$${\displaystyle Q_{1}}$${\displaystyle Q_{2}}$${\displaystyle L_{1}\cap L_{2}}$

より一般的には、これらのアイデアの組み合わせは、PostBQPが和集合および BQP 真理値表還元の下で閉じていることを示します。

スコット・アーロンソンは、複雑性クラス(事後選択限界誤差量子多項式時間) とPP (確率多項式時間)が等しいことを示しました^{[5] 。この}量子計算の再定式化により、の特性に対する新たな洞察とより簡単な証明が得られたことから、 この結果は重要でした。${\displaystyle {\mathsf {PostBQP}}}$${\displaystyle {\mathsf {PP}}}$${\displaystyle {\mathsf {PP}}}$

⁠ ⁠${\displaystyle {\mathsf {PostBQP}}}$回路ファミリの通常の定義は、2 つのアウトビット キュービットP (事後選択) とQ (出力) を持ち、最後にPとQ を1 回測定して、 P = 1を測定する確率が非ゼロの確率、入力 x が言語内にある場合は条件付き確率Pr[ Q = 1| P = 1] ≥ 2/3 、入力x が言語内にない場合はPr[ Q = 0| P = 1] ≥ 2/3 となるようなものです。技術的な理由から、 ⁠ ⁠の定義を次のように調整します。回路ファミリに応じて、ある定数cに対してPr[ P = 1] ≥ 2 ^{− n c}を要求します。この選択は ⁠ P o s t B Q P {\displaystyle {\mathsf {PostBQP}}} ⁠ の基本的な特性には影響しないことに注意してください。また、典型的なゲート（例：Hadamard、Toffoli）で構成される計算は、Pr[ P = 1] > 0の場合は常にこの特性を持つことが示されています。 ${\displaystyle {\mathsf {PostBQP}}}$

言語L を決定するための回路の⁠ ⁠${\displaystyle {\mathsf {PostBQP}}}$族が与えられたとします。一般性を失うことなく (たとえば、量子コンピュータの非本質的特性を参照)、すべてのゲートには実数で表される遷移行列があり、そのために 1 つの量子ビットが追加されると仮定します。

ポスト選択測定が行われる前の回路の最終的な量子状態をΨで表します。証明の全体的な目標は、 L を決定するアルゴリズムを構築することです。より具体的には、L がQ ${\displaystyle {\mathsf {PP}}}$= 1、P = 1の状態におけるΨの振幅の二乗と Q = 0、P = 1 の状態における Ψ の振幅の二乗を正しく比較して、どちらが大きいかを判断すれば十分です。重要な洞察は、これらの振幅の比較が、 ⁠ ⁠マシンの受け入れ確率を 1/2 と比較することに変換できるということです。 ${\displaystyle {\mathsf {PP}}}$

nは入力サイズ、B = B ( n )は回路内の量子ビットの総数 (入力、補助量子ビット、出力量子ビット、および選択後量子ビット)、G = G ( n )はゲートの総数を表します。i 番目のゲートを遷移行列 A i (実数ユニタリ行列) で表し、初期状態^を(ゼロで埋める) とします。次に、 S ₁ (またはS _{0 ) を}P = 1、Q = 1 (またはP = 1、Q = 0 )に対応する基底状態の集合として定義し、確率を定義します。 ${\displaystyle 2^{B}\times 2^{B}}$${\displaystyle |x\rangle }$${\displaystyle \Psi =A^{G}A^{G-1}\dotsb A^{2}A^{1}|x\rangle }$

${\displaystyle \pi _{1}:={\text{Pr}}[P=1,Q=1]=\sum _{\omega \in S_{1}}\Psi _{\omega }^{2}}$

${\displaystyle \pi _{0}:={\text{Pr}}[P=1,Q=0]=\sum _{\omega \in S_{0}}\Psi _{\omega }^{2}.}$

⁠ ⁠${\displaystyle {\mathsf {PostBQP}}}$の定義は、xがLに含まれるかどうかに応じて、またはのいずれかになることを保証します。 ${\displaystyle \pi _{1}\geq 2\pi _{0}}$${\displaystyle \pi _{0}\geq 2\pi _{1}}$

私たちのマシン${\displaystyle {\mathsf {PP}}}$はと を比較します。これを行うには、行列の乗算の定義を拡張します。 ${\displaystyle \pi_{1}}$${\displaystyle \pi_{0}}$

${\displaystyle \Psi _{\omega }=\sum _{\alpha _{1},\ldots ,\alpha _{G}}A_{\omega ,\alpha _{G}}^{G}A_{\alpha _{G},\alpha _{G-1}}^{G-1}\dotsb A_{\alpha _{3},\alpha _{2}}^{2}A_{\alpha _{2},\alpha _{1}}^{1}x_{\alpha _{1}}}$

ここで、和はG基底ベクトルのすべてのリストに対して取られます。ここで、 と は、これらの項のペアごとの積の和として表すことができます。直感的には、受理確率が のようなマシンを設計したいと考えます。なぜなら、 の場合、受理確率は となり、 の場合、受理確率は となるからです。 ${\displaystyle \alpha_{i}}$${\displaystyle \pi_{1}}$${\displaystyle \pi_{0}}$${\displaystyle {\tfrac {1}{2}}(1+\pi _{1}-\pi _{0})}$${\displaystyle x\in L}$${\displaystyle {\tfrac {1}{2}}(1+\pi _{1}-\pi _{0})>{\tfrac {1}{2}}}$${\displaystyle x\not \in L}$${\displaystyle {\tfrac {1}{2}}(1+\pi _{1}-\pi _{0})<{\tfrac {1}{2}}}$

⁠ ⁠${\displaystyle {\mathsf {PostBQP}}}$の定義は、x がL内にある場合は、そうでない場合は であることを示しています。ここで説明する大きな多項式 ⁠ ⁠ の分母に最も近い分数でAのすべての要素を置き換えてみましょう。後で使用するのは、x がL内にある場合、およびx がL内にない場合は、新しいπ値が満たすというものです。以前の技術的仮定を使用し、計算状態の 1 ノルムがどのように変化するかを分析することにより、これが満たされることがわかります。したがって、明らかにnの多項式である十分に大きいfが存在することになります。 ${\displaystyle \pi _{1}\geq {\tfrac {2}{3}}(\pi _{0}+\pi _{1})}$${\displaystyle \pi _{0}\geq {\tfrac {2}{3}}(\pi _{0}+\pi _{1})}$${\displaystyle 2^{f(n)}}$${\displaystyle f(n)}$ ${\displaystyle \pi _{1}>{\tfrac {1}{2}}(\pi _{0}+\pi _{1})}$${\displaystyle \pi _{0}>{\tfrac {1}{2}}(\pi _{0}+\pi _{1})}$${\displaystyle (1+2^{-f(n)}2^{B})^{G}-1<{\tfrac {1}{6}}2^{-n^{c}},}$

ここで、我々のマシン${\displaystyle {\mathsf {PP}}}$の詳細な実装を示す。αをシーケンスとして表し、略記法を定義する。 ${\displaystyle \{\alpha _{i}\}_{i=1}^{G}}$

${\displaystyle \Pi (A,\omega ,\alpha ,x):=A_{\omega ,\alpha _{G}}^{G}A_{\alpha _{G},\alpha _{G-1}}^{G-1}\dotsb A_{\alpha _{3},\alpha _{2}}^{2}A_{\alpha _{2},\alpha _{1}}^{1}x_{\alpha _{1}}}$、

それから

${\displaystyle \pi _{1}-\pi _{0}=\sum _{\omega \in S_{1}}\sum _{\alpha ,\alpha '}\Pi (A,\omega ,\alpha ,x)\Pi (A,\omega ,\alpha ',x)-\sum _{\omega \in S_{0}}\sum _{\alpha ,\alpha '}\Pi (A,\omega ,\alpha ,x)\Pi (A,\omega ,\alpha ',x).}$

私たちは、⁠ ⁠${\displaystyle {\mathsf {PP}}}$マシンを次のように 定義します

• 基底状態ωを一様にランダムに選ぶ
• もしそうなら停止し、確率1/2で受け入れ、確率1/2で拒否する${\displaystyle \omega \not \in S_{0}\cup S_{1}}$
• G基底状態の2つのシーケンスを一様にランダムに選択する${\displaystyle \alpha ,\alpha '}$
• 計算します（分母が となる分数です）${\displaystyle X=\Pi (A,\omega ,\alpha ,x)\Pi (A,\omega ,\alpha ',x)}$${\displaystyle 2^{2f(n)G(n)}}$${\displaystyle -1\leq X\leq 1}$
• 確率で受け入れ、確率で拒否する場合（最大でコイン投げ回数分）${\displaystyle \omega \in S_{1}}$${\displaystyle {\tfrac {1+X}{2}}}$${\displaystyle {\tfrac {1-X}{2}}}$${\displaystyle 2f(n)G(n)+1}$
• それ以外の場合（）確率で受け入れ、確率で拒否する（これも最大で⁠ ⁠コイントス）${\displaystyle \omega \in S_{0}}$${\displaystyle {\tfrac {1-X}{2}}}$${\displaystyle {\tfrac {1+X}{2}}}$${\displaystyle 2f(n)G(n)+1}$

すると、このマシンが確率で受け入れることを計算するのは簡単な ので、必要に応じて 、これは言語Lの⁠ ⁠マシンになります。 ${\displaystyle {\frac {1}{2}}+{\frac {\pi _{1}-\pi _{0}}{2^{1+B(n)+2B(n)G(n)}}},}$${\displaystyle {\mathsf {PP}}}$

長さ の入力xに対して時間計算量が ⁠ ⁠ のマシンがあるとし${\displaystyle {\mathsf {PP}}}$ます。マシンは計算中にコインを投げる回数は最大T回です。したがって、マシンは 2 つの入力 ( x, r )を受け取る決定論的関数f (たとえば、古典的な回路によって実装)と見なすことができます。ここで、 rは長さTのバイナリ文字列で、計算によって実行されるランダムなコイン投げの結果を表し、 fの出力は1 (承認) または 0 (拒否) です。 ⁠ ⁠の定義から、次のことがわかります。 ${\displaystyle T:=T(n)}$${\displaystyle n:=|x|}$${\displaystyle {\mathsf {PP}}}$

${\displaystyle x\in L\Leftrightarrow \#\{r\in \{0,1\}^{T}\mid f(x,r)=1\}>2^{T-1}}$

したがって、上記のステートメントが真かどうかを判断できるアルゴリズムが 必要です。${\displaystyle {\mathsf {PostBQP}}}$

sを受理につながるランダムな文字列の数と 定義する。

${\displaystyle s:=\#\{r\in \{0,1\}^{T}\mid f(x,r)=1\}}$

拒否される文字列の数も同様です。一般性を失うことなく、 を論じることは簡単です。詳細については、 ⁠ ⁠が補集合 に関して閉じていることの証明における、一般性を失うことなく同様の仮定を参照してください。 ${\displaystyle 2^{T}-s}$${\displaystyle s\not \in \{0,2^{T}/2,2^{T}\}}$${\displaystyle {\mathsf {PP}}}$

この問題を解くアーロンソンのアルゴリズムは以下のとおりです。簡単にするために、すべての量子状態を非正規化として記述します。まず、状態を準備します。次に、2番目のレジスタ（最初のT量子ビットのそれぞれ）にアダマールゲートを適用し、2番目のレジスタを測定して、それがすべてゼロの文字列であることを事後選択します。これにより、最後のレジスタ（最後の量子ビット）が残差状態のままになることは簡単に確認できます。 ${\displaystyle |x\rangle \otimes \sum _{r\in \{0,1\}^{T}}|r\rangle |f(x,r)\rangle }$

${\displaystyle |\psi \rangle :=(2^{T}-s)|0\rangle +s|1\rangle .}$

ここでHはアダマールゲートを表し、状態を計算する。

${\displaystyle H|\psi \rangle =(2^{T}|0\rangle +(2^{T}-2s)|1\rangle )/{\sqrt {2}}}$。

ここで、は正の実数で、 は後で選択される。状態を計算し、2番目の量子ビットを測定し、その値が1に等しいかどうかで事後選択する。これ により、最初の量子ビットは、${\displaystyle \alpha ,\beta }$${\displaystyle \alpha ^{2}+\beta ^{2}=1}$${\displaystyle \alpha |0\rangle |\psi \rangle +\beta |1\rangle |H\psi \rangle }$${\displaystyle \beta /\alpha }$

${\displaystyle |\phi _{\beta /\alpha }\rangle :=\alpha s|0\rangle +{\frac {\beta }{\sqrt {2}}}(2^{T}-2s)|1\rangle }$。

量子ビットの可能な状態を円として視覚化すると、 の場合(つまり の場合) は開いた象限にあり、の場合(つまり の場合)は開いた象限にあることがわかります。実際、任意の固定されたx (およびそれに対応するs ) に対して、の比率を変化させると、 の像がまさに対応する開いた象限になることに注意してください。証明の残りの部分では、これら 2 つの象限を区別できるという考えを明確にします。 ${\displaystyle s>2^{T-1}}$${\displaystyle x\in L}$${\displaystyle \phi _{\beta /\alpha }}$${\displaystyle Q_{acc}:=(-|1\rangle ,|0\rangle )}$${\displaystyle s<2^{T-1}}$${\displaystyle x\not \in L}$${\displaystyle \phi _{\beta /\alpha }}$${\displaystyle Q_{rej}:=(|0\rangle ,|1\rangle )}$${\displaystyle \beta /\alpha }$${\displaystyle (0,\infty )}$${\displaystyle |\phi _{\beta /\alpha }\rangle }$

の中心である とし、が に直交するとします。 内のどの量子ビットも、基底 で測定すると、 の 1/2 未満の値を返します。一方、および を選択した場合、基底で測定すると常に の値が得られます。がわからないため、 r*の正確な値もわかりませんが、 の複数の (多項式に多い) 異なる値を試して、r*に「近い」値が得られることを期待できます。 ${\displaystyle |+\rangle =(|1\rangle +|0\rangle )/{\sqrt {2}}}$${\displaystyle Q_{rej}}$${\displaystyle |-\rangle }$${\displaystyle |+\rangle }$${\displaystyle Q_{acc}}$${\displaystyle \{|+\rangle ,|-\rangle \}}$${\displaystyle |+\rangle }$${\displaystyle x\not \in L}$${\displaystyle \beta /\alpha =r^{*}:={\sqrt {2}}s/(2^{T}-2s)}$${\displaystyle |\phi _{\beta /\alpha }\rangle }$${\displaystyle \{|+\rangle ,|-\rangle \}}$${\displaystyle |+\rangle }$${\displaystyle \beta /\alpha }$

具体的には、について の形のあらゆる値を に順次設定することに留意してください。すると、基本的な計算により、 iのこれらの値の1つに対して、 を基底で測定すると少なくとも次の値になる確率が示されます。${\displaystyle 2^{-T}<r*<2^{T}}$${\displaystyle \beta /\alpha }$${\displaystyle 2^{i}}$${\displaystyle -T\leq i\leq T}$${\displaystyle |\phi _{2^{i}}\rangle }$${\displaystyle \{|+\rangle ,|-\rangle \}}$${\displaystyle |+\rangle }$${\displaystyle (3+2{\sqrt {2}})/6\approx 0.971.}$

全体として、⁠ ⁠${\displaystyle {\mathsf {PostBQP}}}$アルゴリズムは次のようになります。k を1/2 から までの間の任意の定数とします。各 に対して次の実験を行います。基底で を構築し、合計 回測定します。ここで、C は定数です。測定値の割合がkより大きい場合は、拒否します。どのiに対しても拒否しない場合は、受け入れます。チェルノフ境界により、十分に大きい普遍定数Cに対して、少なくとも 2/3 の確率で x を正しく分類できることが示されます。${\displaystyle (3+2{\sqrt {2}})/6}$${\displaystyle -T\leq i\leq T}$${\displaystyle |\phi _{2^{i}}\rangle }$${\displaystyle \{|+\rangle ,|-\rangle \}}$${\displaystyle C\log T}$${\displaystyle |+\rangle }$

このアルゴリズムは、全体の選択後確率が小さすぎないという技術的な仮定を満たしていることに注意してください。 の各個別の測定値には選択後確率があり、したがって全体の確率は です。 ${\displaystyle |\phi _{2^{i}}\rangle }$${\displaystyle 1/2^{O(T)}}$${\displaystyle 1/2^{O(T^{2}\log T)}}$

• PPの量子計算の再定式化を参照