⚛️ quantum physics

Promises should be taken seriously: On relativization with promise problems

This paper investigates the non-canonical nature of relativization for promise problems by introducing robust and loose query semantics to demonstrate that language-level complexity results do not necessarily transfer to promise settings, while simultaneously strengthening upper bounds on the Quantum-Classical Polynomial Hierarchy and establishing the self-lowness of PromiseBQP under robust queries.

Original authors: David Miloschewsky, Supartha Podder, Dorian Rudolph

Published 2026-09-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: David Miloschewsky, Supartha Podder, Dorian Rudolph

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of computer science, researchers often try to understand the limits of what machines can solve by imagining them with a special tool: a black box that instantly answers specific questions. This tool, called an oracle, allows scientists to test how powerful a computer becomes when it can ask for help on difficult problems without having to solve them itself. For decades, this method has been used to compare different types of computing, from the classical machines we use today to the theoretical quantum computers of the future. However, a subtle complication arises when the questions asked of the black box are not always clear-cut. Sometimes, the box is only designed to give correct answers to a specific set of questions, while remaining silent or arbitrary about everything else. This is known as a promise problem, where the machine is promised that its inputs will fall into a certain category, but the rules for what happens outside that category are undefined. The question of how a computer should behave when it accidentally asks a question outside this promise has long been a point of confusion, with different researchers assuming different rules for the same scenario.

A team of researchers has now taken a close look at this ambiguity, demonstrating that the way we handle these undefined questions fundamentally changes the power of the computer. They explored two distinct ways a machine might interact with such a black box. In one approach, the machine must be robust, meaning it has to give the right answer no matter how the undefined questions are eventually filled in. In the other, the machine is allowed to be looser, provided that its internal choices, like the random numbers it generates, do not change just because it asked a question that fell outside the promise. By carefully testing these two approaches, the team discovered that results which seem to hold true for standard problems often break down when applied to promise problems. They constructed a specific mathematical world where classical and quantum computers appear to have the exact same power when solving standard problems, yet the quantum computer remains strictly more powerful when faced with promise problems. This finding proves that we cannot simply assume that the rules for standard problems apply automatically to promise problems; the treatment of off-promise queries is essential and must be defined explicitly.

The researchers also used this new understanding to improve our knowledge of a complex hierarchy of computational difficulty known as the quantum-classical polynomial hierarchy. This hierarchy represents a ladder of problems that get progressively harder to solve, involving layers of questions and answers. For some time, the best known estimate for how high this ladder could reach was quite high, but the team managed to lower that ceiling significantly. By using the "loose" access method, they showed that this entire hierarchy can be contained within a much smaller, more manageable class of problems. This was achieved not by inventing a new type of computer, but by adapting a famous mathematical proof to work directly with the messy reality of promise problems, showing that the structure of these problems is more constrained than previously thought.

Furthermore, the study addressed a deep question about whether quantum computers can be their own best helpers. In the world of standard problems, a quantum computer can simulate itself without losing any power, a property known as being "self-low." The team proved that this is also true for promise problems, but only if the machine is forced to be robust in its answers. They showed that even when a quantum computer is given extra help in the form of a pre-prepared quantum state, it can still simulate itself efficiently without collapsing the complexity of the task. This result relies on a clever technique where the machine randomly shifts the threshold it uses to decide if a question is "yes" or "no," effectively averaging out the confusion caused by undefined inputs.

Finally, the researchers uncovered a significant barrier to transferring certain counting results from standard problems to promise problems. They found that if we tried to apply a specific counting rule to promise problems in the same way we do for standard ones, it would cause a massive collapse in the hierarchy of computational difficulty, implying that many distinct levels of complexity are actually the same. This suggests that the two types of problems are fundamentally different in how they handle counting. To resolve this, they introduced a new, restricted version of a powerful quantum model that only allows for input-independent choices. They proved that this restricted model behaves well and does not cause the collapse, offering a clearer path forward for understanding these complex classes. The work serves as a reminder that in the intricate world of computational theory, the smallest details in how we define a machine's behavior can lead to vastly different conclusions about its capabilities.

Technical Summary: Promises should be taken seriously: On relativization with promise problems

Problem Statement
The paper investigates the behavior of computational complexity classes when relativized with access to promise problems rather than standard languages. In standard relativization, an oracle provides a definitive answer (0 or 1) to every query. In contrast, a promise problem $\Pi = (\Pi_{yes}, \Pi_{no})$ only constrains inputs within the promise set $\Pi_{yes} \cup \Pi_{no}$ ; inputs outside this set (off-promise) are unconstrained.

The central difficulty arises because the standard definition of oracle access assumes a total function. For promise problems, one must define how a machine behaves when it queries off-promise inputs. The authors analyze two distinct semantics for this access:

Robust Queries: The machine must solve the problem correctly regardless of how the off-promise inputs are completed (i.e., for every completion $A$ of the promise, the machine succeeds).
Loose Queries: The machine's internal choices (e.g., random strings or witnesses) are fixed before the completion is chosen. The machine must succeed for all completions using the same internal choice.

The paper asks whether relativization results known for languages (e.g., $BPP \subseteq P/poly$ , Toda's Theorem) transfer to promise problems under these semantics, and how the choice of semantics affects the resulting complexity hierarchies.

Methodology
The authors employ a combination of relativization techniques, oracle constructions, and arithmetization methods:

Oracle Constructions: To separate language-based results from promise-based results, the authors construct a specific oracle $O$ by combining a PSPACE-complete language with a Cohen-generic set relative to PSPACE. They encode independent instances of Simon's problem into the generic set.
Direct-Product Bounds: They utilize the direct-product bound (Dru12) to argue that machines with advice cannot simultaneously solve all independent instances of Simon's problem encoded in the oracle, thereby separating $PromiseBQP$ from $PromiseP/poly$ in this relativized world.
Loose Access and Arithmetization: To improve upper bounds on the Quantum-Classical Polynomial Hierarchy ( $QCPH$ ), the authors adapt Toda's theorem. They introduce a "loose-access unambiguous hierarchy" and use exact arithmetization (representing acceptance probabilities via GapP functions) to compress random seeds into single queries. This allows them to bypass the issue that $PromiseBQP$ cannot simply be replaced by an arbitrary completion in $BQP$ .
Self-Lowness via Randomized Thresholds: To prove self-lowness results for $PromiseBQP$, the authors address the issue that off-promise queries might have acceptance probabilities arbitrarily close to $1/2$ . They partition the off-promise interval into sub-intervals and assign a random threshold to each query, ensuring that the simulation error remains polynomially small.
Postselection Variants: To handle counting results, they introduce $PromisePostBQP^*$ , a variant of $PostBQP$ where the postselection circuit depends only on the input length, not the input itself. This allows them to bridge the gap between $PromiseYQP^*$ and $PP$ .

Key Contributions and Results

Separation of Language and Promise Settings:
The authors construct an oracle $O$ such that:
$P^O = BPP^O = BQP^O = AWPP^O$
However,
$PromiseBQP^O \not\subseteq PromiseP^O/poly$
This demonstrates that results holding for languages (like $BPP \subseteq P/poly$ ) do not necessarily transfer to promise problems. Specifically, it answers a question by Nisan regarding whether an oracle exists where $BPP = BQP$ but $PromiseBQP \neq PromiseBPP$ . This highlights that the "completion" of a promise problem cannot be assumed to lie in the corresponding language class.
Improved Upper Bound for $QCPH$ :
Using loose oracle access, the authors improve the upper bound for the Quantum-Classical Polynomial Hierarchy ( $QCPH$ ). They prove:
$QCPH \subseteq BP \cdot PP \subseteq PromiseBPP^{PP}$
This improves upon the previous best bound of $PP^{PP}$ , which had not changed since the class was introduced. The proof adapts Toda's theorem to work directly with promise problems, utilizing a loose-access unambiguous hierarchy and GapP arithmetization. As a corollary, they show $PP^{PromiseBQP} = PP$ .
Self-Lowness of $PromiseBQP$:
The authors establish that $PromiseBQP$ is self-low under robust queries, even with quantum advice:
$PromiseBQP^{PromiseBQP} = PromiseBQP$
$PromiseBQP^{PromiseBQP/qpoly} = PromiseBQP/qpoly$
This is achieved by randomizing the threshold used to simulate queries, ensuring that the simulation error is negligible even when off-promise probabilities are close to $1/2$ .
Obstruction to Counting Hierarchy Collapse:
The paper shows that $GapP \subseteq FP^{PromiseAWPP}$ . Consequently, if $PromiseAWPP \subseteq PromiseBQP/qpoly$ , the Counting Hierarchy ( $CH$ ) would collapse to $YQP^*$ . This suggests that $PromiseAWPP$ and $PromiseBQP$ are likely distinct.
Furthermore, while $AWPP$ is low for $PP$ in the language setting ( $PP^{AWPP} = PP$ ), the authors show that a direct analogue for promise classes would collapse the counting hierarchy. To resolve this, they introduce $PromisePostBQP^*$ and prove:
$PP^{PromisePostBQP^*} = PP \implies PP^{PromiseYQP^*} = PP$

Significance
The paper argues that for semantic complexity classes (classes defined by acceptance probabilities rather than syntactic constraints), the treatment of off-promise queries is essential and cannot be ignored. The results demonstrate that:

Relativized results for languages do not automatically transfer to promise problems.
The choice between "robust" and "loose" query semantics significantly alters the power of the resulting complexity classes.
Standard techniques like arithmetization and self-lowness proofs require careful adaptation (e.g., randomizing thresholds or restricting postselection) when applied to promise problems to avoid incorrect conclusions or collapses of the counting hierarchy.

The work provides a rigorous framework for analyzing promise problems in relativized worlds, clarifying the limitations of extending language-based complexity results to the promise setting.

More like this