Promises should be taken seriously: On relativization with promise problems

技術要約：プロミス問題における相対化において、プロミスは真剣に受け止められるべきである

問題提起
本論文は、標準的な言語ではなく「プロミス問題（promise problems）」へのアクセスを伴う相対化において、計算複雑性クラスがどのように振る舞うかを調査している。標準的な相対化では、オラクルは決定的な回答（0または1）をすべてのクエリに対して提供する。対照的に、プロミス問題 $\Pi = (\Pi_{yes}, \Pi_{no})$ は、プロミス集合 $\Pi_{yes} \cup \Pi_{no}$ 内の入力のみを制約し、それ以外の入力（オフ・プロミス）については制約を設けない。

中心となる困難は、標準的なオラクルアクセスの定義が全関数を仮定している点にある。プロミス問題の場合、マシンがオフ・プロミスの入力をクエリした際にどのように振る舞うべきかを定義しなければならない。著者らは、このアクセスに関する2つの異なるセマンティクスを分析している：

1. ロバスト・クエリ（Robust Queries）: マシンは、プロミスのあらゆる補完（すなわち、プロミスのすべての補完 $A$ に対して）に関して、正しく問題を解かなければならない。
2. ルース・クエリ（Loose Queries）: マシンの内部的な選択（例：乱数文字列や証拠）は、補完が選択される前に固定される。マシンは、同じ内部的選択を用いて、すべての補完に対して成功しなければならない。

本論文は、言語に関して既知の相対化結果（例：$BPP \subseteq P/poly$、Todaの定理）が、これらのセマンティクスの下でプロミス問題へと転移するかどうかを問い、また、選択されたセマンティクスが結果として得られる複雑性階層にどのように影響するかを検討している。

手法
著者らは、オラクル構成法と算術化手法を組み合わせた手法を用いている：

• オラクル構成: 言語ベースの結果とプロミスベースの結果を分離するために、著者らは、PSPACE完全な言語と、PSPACEに対するコーエン・ジェネリック集合を組み合わせた特定のオラクル $O$ を構築する。そこでは、ジェネリック集合の中にサイモン問題（Simon's problem）の独立したインスタンスをエンコードしている。
• 直接積境界（Direct-Product Bounds）: 著者らは、直接積境界（Dru12）を利用して、アドバイスを持つマシンは、オラクルにエンコードされたサイモン問題のすべての独立したインスタンスを同時に解くことはできないことを論じ、この相対化された世界において $PromiseBQP$と$PromiseP/poly$ を分離する。
• ルース・アクセスと算術化: 量子古典多項式階層（$QCPH$）の上界を改善するために、著者らはTodaの定理を適応させる。彼らは「ルース・アクセス非決定論的階層（loose-access unambiguous hierarchy）」を導入し、正確な算術化（受理確率をGapP関数で表現すること）を用いて、ランダムなシードを単一のクエリへと圧縮する。これにより、$PromiseBQP$が$BQP$ における任意の補完によって単純に置き換えられないという問題を回避できる。
• 自己低位性（Self-Lowness）によるランダム閾値: $PromiseBQP$の自己低位性の結果を証明するために、著者らは、オフ・プロミスのクエリの受理確率が$1/2$ に極めて近くなる可能性に対処する。彼らはオフ・プロミスの区間をサブ区間に分割し、各クエリにランダムな閾値を割り当てることで、シミュレーション誤差が多項式レベルに小さくなるように保証する。
• ポストセレクションの変種: カウンティングの結果を扱うために、著者らは $PromisePostBQP^*$ を導入する。これは、$PostBQP$の変種であり、ポストセレクション回路が入力自体ではなく、入力長のみに依存するように設計されている。これにより、$PromiseYQP^*$と$PP$ の間の溝を埋めることが可能になる。

主要な貢献と結果

1. 言語設定とプロミス設定の分離:
   著者らは以下の性質を持つオラクル $O$ を構築する：
   $$P^O = BPP^O = BQP^O = AWPP^O$$
   しかし、
   $$PromiseBQP^O \not\subseteq PromiseP^O/poly$$
   これは、言語に関する結果（$BPP \subseteq P/poly$ など）が、必ずしもプロミス問題へと転移しないことを示している。具体的には、Nisanによる、「$BPP = BQP$ だが $PromiseBQP \neq PromiseBPP$ となるようなオラクルが存在するか」という問いに答えている。これは、「補完」が対応する言語クラスに含まれるとは限らないことを強調している。

2. $QCPH$ の上界の改善:
   ルース・オラクルアクセスを用いることで、著者らは量子古典多項式階層（$QCPH$）の上界を改善する。彼らは以下を証明する：
   $$QCPH \subseteq BP \cdot PP \subseteq PromiseBPP^{PP}$$
   これは、クラスの導入以来変わっていなかった従来の最良の上界 $PP^{PP}$ を改善するものである。証明では、ルース・アクセス非決定論的階層とGapP算術化を利用して、プロミス問題で直接動作するようにTodaの定理を適応させている。その系として、$PP^{PromiseBQP} = PP$ であることを示している。

3. $PromiseBQP$ の自己低位性:
   著者らは、$PromiseBQP$ がロバスト・クエリの下で、量子アドバイスを伴う場合でも自己低位であることを確立する：
   $$PromiseBQP^{PromiseBQP} = PromiseBQP$$
   $$PromiseBQP^{PromiseBQP/qpoly} = PromiseBQP/qpoly$$
   これは、オフ・プロミスの確率が $1/2$ に近い場合でもシミュレーション誤差が無視可能になるよう、クエリをシミュレートするために使用される閾値をランダム化することによって達成される。

4. カウンティング階層の崩壊に対する障害:
   本論文は、$GapP \subseteq FP^{PromiseAWPP}$ であることを示している。したがって、もし $PromiseAWPP \subseteq PromiseBQP/qpoly$ であれば、カウンティング階層（$CH$）は $YQP^*$ へと崩壊する。これは、$PromiseAWPP$と$PromiseBQP$ がおそらく異なることを示唆している。
   さらに、言語の設定では $AWPP$ は $PP$ に対して低位であるが（$PP^{AWPP} = PP$）、著者らは、プロミスクラスに対して直接的な類似物を適用するとカウンティング階層の崩壊を招くことを示している。これを解決するために、彼らは $PromisePostBQP^*$ を導入し、以下を証明する：
   $$PP^{PromisePostBQP^*} = PP \implies PP^{PromiseYQP^*} = PP$$

意義
本論文は、意味論的複雑性クラス（構文的制約ではなく受理確率によって定義されるクラス）にとって、オフ・プロミスのクエリの扱いは不可欠であり、無視できないものであると主張している。その結果は以下のことを示している：

• 言語に関する相対化結果は、自動的にはプロミス問題へと転移しない。
• 「ロバスト」と「ルース」のクエリ・セマンティクスの選択は、結果として得られる複雑性クラスの能力を著しく変化させる。
• 算術化や自己低位性の証明といった標準的な手法は、カウンティング階層の崩壊や誤った結論を避けるために（ランダムな閾値の設定やポストセレクションの制限など）、注意深い適応を必要とする。

本研究は、相対化された世界におけるプロミス問題の分析のための厳密な枠組みを提供し、言語ベースの複雑性結果をプロミス設定へと拡張することの限界を明らかにしている。