Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

P(APP) = P(prBPP)

Philippe Moser

Published Jan 1, 2002• 0 citations
OpenAlex

Abstract

We show that for deterministic polynomial time computations, oracle access to APP, the class of real functions approximable by probabilistic Turing machines, is the same as having oracle access to promise-BPP. First, we construct a mapping that maps every function in APP to a promise problem in prBPP, and that preserves completeness, i.e. maps complete functions to complete promise problems. Next, we construct a mapping from prBPP into APP, that maps every promise problem to a function in APP, and which preserves completeness. Then, we prove that PAPP=PprBPP. Finally, we use our results to simplify proofs of important results on APP, such as the APP-completeness of the function fCAPP, which approximates the acceptance probability of a Boolean circuit, the error probability reduction Theorem for APP functions, and the conditional derandomization result APP=AP iff prBPP is easy.

Related papers

Promises should be taken seriously: On relativization with promise problems

David Miloschewsky, Supartha Podder, Dorian Rudolph

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}$.

cs.CCCross-listedarXiv:2609.07945•Sep 9, 2026•0 citations

Efficient Reductions from NP to Parity using Error-Correcting Codes

Kenneth W. Regan

This paper proves that every language in NP is recognized by an RP[ \\Phi P] machine whose time complexity is quasilinear, apart from the time to verify witnesses. The results significantly improve the number of random bits, success probability, and running time of Valiant and Vazirani's original construction [VV86], and beat both the 2n random bits and time/success tradeoff in subsequent methods based on universal hashing. Questions of further improvements are connected to open problems in the theory of error-correcting codes. 1. Introduction Valiant and Vazirani [VV86] proved that every language L 2 NP is accepted by a polynomial-time bounded probabilistic oracle Turing machine M o which, on any input x, computes a Boolean formula OE x as an oracle query, and accepts if the answer is `1'. The oracle of M o has the "promise property" that whenever OE x has a unique satisfying assignment, it always answers `1', and whenever OE x has no satisfying assignments, it answers `0'. An ...

•Jan 1, 1993•1 citation

BQP, Meet NP: Search-To-Decision Reductions and Approximate Counting

Sevag Gharibian, Jonas Kamminga

What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires $Θ(n)$ queries to an NP oracle to compute a witness to a given SAT formula, quantumly $Θ(\log n)$ queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires $Ω(\log n)$ queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires $Ω(\log n)$ queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making $o(log n)$ NP queries, then $\text{BPP}^{\text{NP}[o(n)]}$ contains a $\text{P}^{\text{NP}}$-complete problem if the algorithm is classical and $\text{FBQP}^{\text{NP}[o(n)]}$ contains an $\text{FP}^{\text{NP}}$-complete problem if the algorithm is quantum.

arXiv:2401.03943•Leibniz international proceedings in informatics•Jan 1, 2024•0 citations

Constructive derandomization of query algorithms

Guy Blanc, Jane Lange, Li-Yang Tan

We give efficient deterministic algorithms for converting randomized query algorithms into deterministic ones. We first give an algorithm that takes as input a randomized $q$-query algorithm $R$ with description length $N$ and a parameter $\varepsilon$, runs in time $\mathrm{poly}(N) \cdot 2^{O(q/\varepsilon)}$, and returns a deterministic $O(q/\varepsilon)$-query algorithm $D$ that $\varepsilon$-approximates the acceptance probabilities of $R$. These parameters are near-optimal: runtime $N + 2^{Ω(q/\varepsilon)}$ and query complexity $Ω(q/\varepsilon)$ are necessary. Next, we give algorithms for instance-optimal and online versions of the problem: $\circ$ Instance optimal: Construct a deterministic $q^\star_R$-query algorithm $D$, where $q^\star_R$ is minimum query complexity of any deterministic algorithm that $\varepsilon$-approximates $R$. $\circ$ Online: Deterministically approximate the acceptance probability of $R$ for a specific input $\underline{x}$ in time $\mathrm{poly}(N,q,1/\varepsilon)$, without constructing $D$ in its entirety. Applying the techniques we develop for these extensions, we constructivize classic results that relate the deterministic, randomized, and quantum query complexities of boolean functions (Nisan, STOC 1989; Beals et al., FOCS 1998). This has direct implications for the Turing machine model of computation: sublinear-time algorithms for total decision problems can be efficiently derandomized and dequantized with a subexponential-time preprocessing step.

arXiv:1912.03042•Dec 6, 2019•0 citations

On Polynomially Many Queries to NP or QMA Oracles

Sevag Gharibian, Dorian Rudolph

We study the complexity of problems solvable in deterministic polynomial time with access to an NP or Quantum Merlin-Arthur (QMA)-oracle, such as $P^{NP}$ and $P^{QMA}$, respectively. The former allows one to classify problems more finely than the Polynomial-Time Hierarchy (PH), whereas the latter characterizes physically motivated problems such as Approximate Simulation (APX-SIM) [Ambainis, CCC 2014]. In this area, a central role has been played by the classes $P^{NP[\log]}$ and $P^{QMA[\log]}$, defined identically to $P^{NP}$ and $P^{QMA}$, except that only logarithmically many oracle queries are allowed. Here, [Gottlob, FOCS 1993] showed that if the adaptive queries made by a $P^{NP}$ machine have a "query graph" which is a tree, then this computation can be simulated in $P^{NP[\log]}$. In this work, we first show that for any verification class $C\in\{NP,MA,QCMA,QMA,QMA(2),NEXP,QMA_{\exp}\}$, any $P^C$ machine with a query graph of "separator number" $s$ can be simulated using deterministic time $\exp(s\log n)$ and $s\log n$ queries to a $C$-oracle. When $s\in O(1)$ (which includes the case of $O(1)$-treewidth, and thus also of trees), this gives an upper bound of $P^{C[\log]}$, and when $s\in O(\log^k(n))$, this yields bound $QP^{C[\log^{k+1}]}$ (QP meaning quasi-polynomial time). We next show how to combine Gottlob's "admissible-weighting function" framework with the "flag-qubit" framework of [Watson, Bausch, Gharibian, 2020], obtaining a unified approach for embedding $P^C$ computations directly into APX-SIM instances in a black-box fashion. Finally, we formalize a simple no-go statement about polynomials (c.f. [Krentel, STOC 1986]): Given a multi-linear polynomial $p$ specified via an arithmetic circuit, if one can "weakly compress" $p$ so that its optimal value requires $m$ bits to represent, then $P^{NP}$ can be decided with only $m$ queries to an NP-oracle.

arXiv:2111.02296•Leibniz international proceedings in informatics•Nov 3, 2021•0 citations

On the power of quantum computation

D.R. Simon

The quantum model of computation is a probabilistic model, similar to the probabilistic Turing Machine, in which the laws of chance are those obeyed by particles on a quantum mechanical scale, rather than the rules familiar to us from the macroscopic world. We present here a problem of distinguishing between two fairly natural classes of function, which can provably be solved exponentially faster in the quantum model than in the classical probabilistic one, when the function is given as an oracle drawn equiprobably from the uniform distribution on either class. We thus offer compelling evidence that the quantum model may have significantly more complexity theoretic power than the probabilistic Turing Machine. In fact, drawing on this work, Shor (1994) has recently developed remarkable new quantum polynomial-time algorithms for the discrete logarithm and integer factoring problems.>

Annual Symposium on Foundations of Computer Science•Dec 17, 2002•491 citations
We show that for deterministic polynomial time computations, oracle access to
APP, the class of real functions
approximable by probabilistic Turing machines, is the same as having oracle access to
promise-BPP. First,
we construct a mapping that maps every function in APP to a promise problem
in prBPP, and that preserves completeness, i.e. maps complete functions to complete promise problems.
Next, we construct
a mapping from
prBPP into APP, that maps every promise problem to a function
in APP, and which preserves completeness.
Then, we prove that PAPP=PprBPP.
Finally, we use our results to simplify proofs of important results on APP, such as
the APP-completeness of the function fCAPP,
which approximates the acceptance
probability of a Boolean circuit, the error probability reduction Theorem
for APP functions, and the conditional derandomization result
APP=AP iff prBPP is easy.
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 OOO such that PO=BQPO=AWPPO\mathsf{P}^O = \mathsf{BQP}^O = \mathsf{AWPP}^OPO=BQPO=AWPPO, but PromiseBQPO⊈PromiseP/polyO\mathsf{PromiseBQP}^O\not\subseteq\mathsf{PromiseP}^O_{\mathsf{/poly}}PromiseBQPO⊆PromiseP/polyO​. In particular, BPPO=BQPO\mathsf{BPP}^O = \mathsf{BQP}^OBPPO=BQPO, but PromiseBQPO≠PromiseBPPO\mathsf{PromiseBQP}^O \neq \mathsf{PromiseBPP}^OPromiseBQPO=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\mathsf{P}^{\mathsf{PP}^{\mathsf{PP}}}PPPPP to QCPH⊆BP⋅PP⊆PromiseBPPPP\mathsf{QCPH} \subseteq \mathsf{BP\cdot PP} \subseteq \mathsf{PromiseBPP}^{\mathsf{PP}}QCPH⊆BP⋅PP⊆PromiseBPPPP. The same proof also shows PPPromiseBQP=PP\mathsf{PP}^\mathsf{PromiseBQP} = \mathsf{PP}PPPromiseBQP=PP. Additionally, we show that PromiseBQP\mathsf{PromiseBQP}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\mathsf{AWPP}AWPP and APP\mathsf{APP}APP are low for PP\mathsf{PP}PP, a corresponding promise analogue would collapse the counting hierarchy as GapP⊆FPPromiseAWPP\mathsf{GapP} \subseteq \mathsf{FP}^{\mathsf{PromiseAWPP}}GapP⊆FPPromiseAWPP. This motivates the introduction of PromisePostBQP∗\mathsf{PromisePostBQP^*}PromisePostBQP∗, which restricts PostBQP\mathsf{PostBQP}PostBQP to input-indepencent postselection. By showing that it is low for \PP, we obtain PPPromiseYQP∗=PP\mathsf{PP}^{\mathsf{PromiseYQP^*}} = \mathsf{PP}PPPromiseYQP∗=PP.
This paper proves that every language in NP is recognized by an RP[ \\Phi P] machine whose time complexity is quasilinear, apart from the time to verify witnesses. The results significantly improve the number of random bits, success probability, and running time of Valiant and Vazirani's original construction [VV86], and beat both the 2n random bits and time/success tradeoff in subsequent methods based on universal hashing. Questions of further improvements are connected to open problems in the theory of error-correcting codes. 1. Introduction Valiant and Vazirani [VV86] proved that every language L 2 NP is accepted by a polynomial-time bounded probabilistic oracle Turing machine M o which, on any input x, computes a Boolean formula OE x as an oracle query, and accepts if the answer is `1'. The oracle of M o has the "promise property" that whenever OE x has a unique satisfying assignment, it always answers `1', and whenever OE x has no satisfying assignments, it answers `0'. An ...
What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires Θ(n)Θ(n)Θ(n) queries to an NP oracle to compute a witness to a given SAT formula, quantumly Θ(log⁡n)Θ(\log n)Θ(logn) queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires Ω(log⁡n)Ω(\log n)Ω(logn) queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires Ω(log⁡n)Ω(\log n)Ω(logn) queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making o(logn)o(log n)o(logn) NP queries, then BPPNP[o(n)]\text{BPP}^{\text{NP}[o(n)]}BPPNP[o(n)] contains a PNP\text{P}^{\text{NP}}PNP-complete problem if the algorithm is classical and FBQPNP[o(n)]\text{FBQP}^{\text{NP}[o(n)]}FBQPNP[o(n)] contains an FPNP\text{FP}^{\text{NP}}FPNP-complete problem if the algorithm is quantum.
We give efficient deterministic algorithms for converting randomized query algorithms into deterministic ones. We first give an algorithm that takes as input a randomized qqq-query algorithm RRR with description length NNN and a parameter ε\varepsilonε, runs in time poly(N)⋅2O(q/ε)\mathrm{poly}(N) \cdot 2^{O(q/\varepsilon)}poly(N)⋅2O(q/ε), and returns a deterministic O(q/ε)O(q/\varepsilon)O(q/ε)-query algorithm DDD that ε\varepsilonε-approximates the acceptance probabilities of RRR. These parameters are near-optimal: runtime N+2Ω(q/ε)N + 2^{Ω(q/\varepsilon)}N+2Ω(q/ε) and query complexity Ω(q/ε)Ω(q/\varepsilon)Ω(q/ε) are necessary. Next, we give algorithms for instance-optimal and online versions of the problem: ∘\circ∘ Instance optimal: Construct a deterministic qR⋆q^\star_RqR⋆​-query algorithm DDD, where qR⋆q^\star_RqR⋆​ is minimum query complexity of any deterministic algorithm that ε\varepsilonε-approximates RRR. ∘\circ∘ Online: Deterministically approximate the acceptance probability of RRR for a specific input x‾\underline{x}x​ in time poly(N,q,1/ε)\mathrm{poly}(N,q,1/\varepsilon)poly(N,q,1/ε), without constructing DDD in its entirety. Applying the techniques we develop for these extensions, we constructivize classic results that relate the deterministic, randomized, and quantum query complexities of boolean functions (Nisan, STOC 1989; Beals et al., FOCS 1998). This has direct implications for the Turing machine model of computation: sublinear-time algorithms for total decision problems can be efficiently derandomized and dequantized with a subexponential-time preprocessing step.
We study the complexity of problems solvable in deterministic polynomial time with access to an NP or Quantum Merlin-Arthur (QMA)-oracle, such as PNPP^{NP}PNP and PQMAP^{QMA}PQMA, respectively. The former allows one to classify problems more finely than the Polynomial-Time Hierarchy (PH), whereas the latter characterizes physically motivated problems such as Approximate Simulation (APX-SIM) [Ambainis, CCC 2014]. In this area, a central role has been played by the classes PNP[log⁡]P^{NP[\log]}PNP[log] and PQMA[log⁡]P^{QMA[\log]}PQMA[log], defined identically to PNPP^{NP}PNP and PQMAP^{QMA}PQMA, except that only logarithmically many oracle queries are allowed. Here, [Gottlob, FOCS 1993] showed that if the adaptive queries made by a PNPP^{NP}PNP machine have a "query graph" which is a tree, then this computation can be simulated in PNP[log⁡]P^{NP[\log]}PNP[log]. In this work, we first show that for any verification class C∈{NP,MA,QCMA,QMA,QMA(2),NEXP,QMAexp⁡}C\in\{NP,MA,QCMA,QMA,QMA(2),NEXP,QMA_{\exp}\}C∈{NP,MA,QCMA,QMA,QMA(2),NEXP,QMAexp​}, any PCP^CPC machine with a query graph of "separator number" sss can be simulated using deterministic time exp⁡(slog⁡n)\exp(s\log n)exp(slogn) and slog⁡ns\log nslogn queries to a CCC-oracle. When s∈O(1)s\in O(1)s∈O(1) (which includes the case of O(1)O(1)O(1)-treewidth, and thus also of trees), this gives an upper bound of PC[log⁡]P^{C[\log]}PC[log], and when s∈O(log⁡k(n))s\in O(\log^k(n))s∈O(logk(n)), this yields bound QPC[log⁡k+1]QP^{C[\log^{k+1}]}QPC[logk+1] (QP meaning quasi-polynomial time). We next show how to combine Gottlob's "admissible-weighting function" framework with the "flag-qubit" framework of [Watson, Bausch, Gharibian, 2020], obtaining a unified approach for embedding PCP^CPC computations directly into APX-SIM instances in a black-box fashion. Finally, we formalize a simple no-go statement about polynomials (c.f. [Krentel, STOC 1986]): Given a multi-linear polynomial ppp specified via an arithmetic circuit, if one can "weakly compress" ppp so that its optimal value requires mmm bits to represent, then PNPP^{NP}PNP can be decided with only mmm queries to an NP-oracle.
The quantum model of computation is a probabilistic model, similar to the probabilistic Turing Machine, in which the laws of chance are those obeyed by particles on a quantum mechanical scale, rather than the rules familiar to us from the macroscopic world. We present here a problem of distinguishing between two fairly natural classes of function, which can provably be solved exponentially faster in the quantum model than in the classical probabilistic one, when the function is given as an oracle drawn equiprobably from the uniform distribution on either class. We thus offer compelling evidence that the quantum model may have significantly more complexity theoretic power than the probabilistic Turing Machine. In fact, drawing on this work, Shor (1994) has recently developed remarkable new quantum polynomial-time algorithms for the discrete logarithm and integer factoring problems.>