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 PO = BQPO = AWPPO, but PromiseBQPOnot⊆PromisePO/poly. In particular, BPPO = BQPO, but PromiseBQPO ≠ PromiseBPPO, 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 PPPPP to QCPH ⊆ BP· PP ⊆ PromiseBPPPP. The same proof also shows PPPromiseBQP = PP. Additionally, we show that 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 AWPP and APP are low for PP, a corresponding promise analogue would collapse the counting hierarchy as GapP ⊆ FPPromiseAWPP. This motivates the introduction of PromisePostBQP*, which restricts PostBQP to input-indepencent postselection. By showing that it is low for \PP, we obtain PPPromiseYQP* = PP.
Related
BibTeX
@misc{miloschewsky2026promises,
title = {{Promises should be taken seriously: On relativization with promise problems}},
author = {David Miloschewsky and Supartha Podder and Dorian Rudolph},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.07945},
eprint = {2609.07945},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.07945},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Promises should be taken seriously: On relativization with promise problems
AU - David Miloschewsky
AU - Supartha Podder
AU - Dorian Rudolph
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.07945
UR - https://arxiv.org/abs/2609.07945
AB - 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 P^O = BQP^O = AWPP^O, but PromiseBQP^Onot⊆PromiseP^O_/poly. In particular, BPP^O = BQP^O, but PromiseBQP^O ≠ 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 P^PP^PP to QCPH ⊆ BP· PP ⊆ PromiseBPP^PP. The same proof also shows PP^PromiseBQP = PP. Additionally, we show that 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 AWPP and APP are low for PP, a corresponding promise analogue would collapse the counting hierarchy as GapP ⊆ FP^PromiseAWPP. This motivates the introduction of PromisePostBQP^*, which restricts PostBQP to input-indepencent postselection. By showing that it is low for \PP, we obtain PP^PromiseYQP^* = PP.
ER -