Fugu-MT 論文翻訳(概要): Promises should be taken seriously: On relativization with promise problems

論文の概要: Promises should be taken seriously: On relativization with promise problems

arxiv url: http://arxiv.org/abs/2609.07945v1
Date: Mon, 07 Sep 2026 19:56:41 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-11 19:59:50.911672
Title: Promises should be taken seriously: On relativization with promise problems
Title（参考訳）: 約束は真剣に考えるべきである:約束問題との相対性について
Authors: David Miloschewsky, Supartha Podder, Dorian Rudolph,
Abstract要約: 我々は、計算モデルと、オラクルへのブラックボックスアクセスを比較した。約束の問題に対して、ブラックボックスアクセスは、約束外の入力が制限されないため、標準的ではない。言語の結果がpromiseに転送される必要はないことを示す。
参考スコア（独自算出の注目度）: 0.25489046505746704
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Relativization is concerned with comparing computational models with black-box access to an oracle. For promise problems, black-box access is not canonical due to inputs outside of the promise being unconstrained. We study two semantics for such access. Under robust queries, a machine must correctly answer regardless of the completion of the problem,, while loose access requires that the internal choices of a machine do not change based on off-promise queries. Our first result separates the language and promise settings. Namely, we construct an oracle $O$ such that $\mathsf{P}^O = \mathsf{BQP}^O = \mathsf{AWPP}^O$, but $\mathsf{PromiseBQP}^O\not\subseteq\mathsf{PromiseP}^O_{\mathsf{/poly}}$. In particular, $\mathsf{BPP}^O = \mathsf{BQP}^O$, but $\mathsf{PromiseBQP}^O \neq \mathsf{PromiseBPP}^O$, showing that results for languages need not transfer to promises. Next, we use loose queries to strengthen the upper bound on the Quantum-Classical Polynomial Hierarchy from $\mathsf{P}^{\mathsf{PP}^{\mathsf{PP}}}$ to $\mathsf{QCPH} \subseteq \mathsf{BP\cdot PP} \subseteq \mathsf{PromiseBPP}^{\mathsf{PP}}$. The same proof also shows $\mathsf{PP}^\mathsf{PromiseBQP} = \mathsf{PP}$. Additionally, we show that $\mathsf{PromiseBQP}$, even when given quantum advice, is self-low under robust queries. Finally, we exhibit an obstruction to transferring language-level counting results to promise classes. Although $\mathsf{AWPP}$ and $\mathsf{APP}$ are low for $\mathsf{PP}$, a corresponding promise analogue would collapse the counting hierarchy as $\mathsf{GapP} \subseteq \mathsf{FP}^{\mathsf{PromiseAWPP}}$. This motivates the introduction of $\mathsf{PromisePostBQP^*}$, which restricts $\mathsf{PostBQP}$ to input-indepencent postselection. By showing that it is low for \PP, we obtain $\mathsf{PP}^{\mathsf{PromiseYQP^*}} = \mathsf{PP}$.
Abstract（参考訳）: 相対化は、計算モデルとオラクルへのブラックボックスアクセスの比較に関係している。約束の問題に対して、ブラックボックスアクセスは、約束外の入力が制限されないため、標準的ではない。このようなアクセスのための2つの意味論を研究する。堅牢なクエリでは、マシンは問題の完了にかかわらず正しく答える必要があり、一方、緩いアクセスでは、マシンの内部選択はオフプロミズクエリに基づいて変更されない必要がある。最初の結果は言語を分離し、設定を約束します。すなわち、オラクル$O$を$\mathsf{P}^O = \mathsf{BQP}^O = \mathsf{AWPP}^O$, but $\mathsf{PromiseBQP}^O\not\subseteq\mathsf{PromiseP}^O_{\mathsf{/poly}}$とする。特に、$\mathsf{BPP}^O = \mathsf{BQP}^O$, but $\mathsf{PromiseBQP}^O \neq \mathsf{PromiseBPP}^O$は、言語の結果をpromiseに転送する必要はないことを示している。次に、ゆるいクエリを用いて、$\mathsf{P}^{\mathsf{PP}^{\mathsf{PP}}}$ to $\mathsf{QCPH} \subseteq \mathsf{BP\cdot PP} \subseteq \mathsf{PromiseBPP}^{\mathsf{PP}}$から量子古典多項式階層上の上限を強化する。同じ証明は、$\mathsf{PP}^\mathsf{PromiseBQP} = \mathsf{PP}$を示す。さらに、量子アドバイスが与えられたとしても、$\mathsf{PromiseBQP}$はロバストなクエリの下で自己低下していることを示す。最後に,言語レベルカウントの結果を約束クラスに転送する際の障害を示す。 $\mathsf{AWPP}$と$\mathsf{APP}$は、$\mathsf{PP}$に対して低いが、対応する約束アナログはカウント階層を$\mathsf{GapP} \subseteq \mathsf{FP}^{\mathsf{PromiseAWPP}}$に分解する。これは$\mathsf{PromisePostBQP^*}$の導入を動機付け、$\mathsf{PostBQP}$を入出力ポストセレクションに制限する。 PP が低いことを示すことにより、$\mathsf{PP}^{\mathsf{PromiseYQP^*}} = \mathsf{PP}$ が得られる。

論文の概要: Promises should be taken seriously: On relativization with promise problems

関連論文リスト