Promises should be taken seriously: On relativization with promise problems

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⊈{\mathsf{PromiseP}}_{/poly}^O$. In particular, ${\mathsf{BPP}}^O={\mathsf{BQP}}^O$, but ${\mathsf{PromiseBQP}}^O\ne {\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 \mathsf{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{PromisePostBQ}{\mathsf{P}}^{\ast }$, which restricts $\mathsf{PostBQP}$ to input-indepencent postselection. By showing that it is low for \PP, we obtain ${\mathsf{PP}}^{\mathsf{PromiseYQ}{\mathsf{P}}^{\ast }}=\mathsf{PP}$.

21 pages, 1 figure