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

Leibniz international proceedings in informatics

Adaptivity vs. Postselection, and Hardness Amplification for Polynomial Approximation

Lijie Chen

Published Jan 1, 2016• 1 citation
Publisher

Abstract

We study the following problem: with the power of postselection (classically or quantumly), what is your ability to answer adaptive queries to certain languages? More specifically, for what kind of computational classes C, we have P^C belongs to PostBPP or PostBQP? While a complete answer to the above question seems impossible given the development of present computational complexity theory. We study the analogous question in query complexity, which sheds light on the limitation of relativized methods (the relativization barrier) to the above question. Informally, we show that, for a partial function f, if there is no efficient small bounded-error algorithm for f classically or quantumly, then there is no efficient postselection bounded-error algorithm to answer adaptive queries to f classically or quantumly. Our results imply a new proof for the classical oracle separation P^{NP^O} notsubset PP^O, which is arguably more elegant. They also lead to a new oracle separation P^{SZK^O} notsubset PP^O, which is close to an oracle separation between SZK and PP - an open problem in the field of oracle separations. Our result also implies a hardness amplification construction for polynomial approximation: given a function f on n bits, we construct an adaptive-version of f, denoted by F, on O(m·n) bits, such that if f requires large degree to approximate to error 2/3 in a certain one-sided sense, then F requires large degree to approximate even to error 1/2 - 2^{-m}. Our construction achieves the same amplification in the work of Thaler (ICALP, 2016), by composing a function with O(log n) deterministic query complexity, which is in sharp contrast to all the previous results where the composing amplifiers are all hard functions in a certain sense.

DOI
10.4230/lipics.isaac.2016.26

Related papers

Adaptivity vs Postselection

Lijie Chen

We study the following problem: with the power of postselection (classically or quantumly), what is your ability to answer adaptive queries to certain languages? More specifically, for what kind of computational classes $\mathcal{C}$, we have $\mathsf{P}^{\mathcal{C}}$ belongs to $\mathsf{PostBPP}$ and $\mathsf{PostBQP}$? While a complete answer to the above question seems impossible given the development of present computational complexity theory. We study the analogous question in query complexity, which sheds light on the limitation of {\em relativized} methods (the relativization barrier) to the above question. Informally, we show that, for a partial function $f$, if there is no efficient (In the world of query complexity, being efficient means using $O(\operatorname*{polylog}(n))$ time.) {\em small bounded-error} algorithm for $f$ classically or quantumly, then there is no efficient postselection bounded-error algorithm to answer adaptive queries to $f$ classically or quantumly. Our results imply a new proof for the classical oracle separation $\mathsf{P}^{\mathsf{NP}^{\mathcal{O}}} \not\subset \mathsf{PP}^{\mathcal{O}}$. They also lead to a new oracle separation $\mathsf{P}^{\mathsf{SZK}^{\mathcal{O}}} \not\subset \mathsf{PP}^{\mathcal{O}}$. Our result also implies a hardness amplification construction for polynomial approximation: given a function $f$ on $n$ bits, we construct an adaptive-version of $f$, denoted by $F$, on $O(m \cdot n)$ bits, such that if $f$ requires large degree to approximate to error $2/3$ in a certain one-sided sense, then $F$ requires large degree to approximate even to error $1/2 - 2^{-m}$. Our construction achieves the same amplification in the work of Thaler (ICALP, 2016), by composing a function with $O(\log n)$ {\em deterministic query complexity}.

arXiv:1606.04016•Jun 13, 2016•2 citations

Modifications of Quantum Computation and Adaptive Queries to PP

David Miloschewsky, Supartha Podder

In 2004, Aaronson introduced the complexity class $\mathsf{PostBQP}$ ($\mathsf{BQP}$ with postselection) and showed that it is equal to $\mathsf{PP}$. Following their line of work, we introduce two new complexity classes. The first, $\mathsf{CorrBQP}$, is a modification of $\mathsf{BQP}$ which has the power to perform correlated measurements, i.e. measurements that output the same value across a partition of registers. The second, $\mathsf{MajBQP}$, augments $\mathsf{BQP}$ with the ability to collapse a register to its most likely measurement outcome. Specifically, we consider two variants, $\mathsf{MajBQP}$ and $\mathsf{AdMajBQP}$, where the latter may perform intermediate measurements. We exactly characterize the computational power of the models, $\mathsf{CorrBQP} = \mathsf{AdMajBQP} = \mathsf{BPP}^{\mathsf{PP}}$ and $\mathsf{MajBQP} = \mathsf{P}^{\mathsf{PP}}$. In fact, we show that other metaphysical modifications of $\mathsf{BQP}$, such as $\mathsf{CBQP}$ (i.e. $\mathsf{BQP}$ with the ability to clone arbitrary quantum states), are also equal to $\mathsf{BPP}^{\mathsf{PP}}$. We show that $\mathsf{CorrBQP}$ and $\mathsf{MajBQP}$ are self-low with respect to classically-accessible queries. In contrast, if they were self-low under quantumly-accessible queries, the counting hierarchy would collapse. Furthermore, we introduce a variant of rational degree that lower-bounds the query complexity of $\mathsf{BPP}^{\mathsf{PP}}$. Lastly, we extend the adversary lower-bounding technique to $\mathsf{AdPDQP}$, $\mathsf{BQP}$ with the ability to sample the current state of an algorithm with collapsing it and adapt the computation based on the samples.

arXiv:2507.03692•Jul 4, 2025•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

Post-selected Classical Query Complexity

Chris Cade

We study classical query algorithms with post-selection, and find that they are closely connected to rational functions with nonnegative coefficients. We show that the post-selected classical query complexity of a Boolean function is equal to the minimal degree of a rational function with nonnegative coefficients that approximates it (up to a factor of two). For post-selected quantum query algorithms, a similar relationship was shown by Mahadev and de Wolf, where the rational approximations are allowed to have negative coefficients. Using our characterisation, we find an exponentially large separation between post-selected classical query complexity and post-selected quantum query complexity, by proving a lower bound on the degree of rational approximations (with nonnegative coefficients) to the Majority function. This lower bound can be generalised to arbitrary symmetric functions, and allows us to find an unbounded separation between non-deterministic quantum and post-selected classical query complexity. All lower bounds carry over into the communication complexity setting. We show that the zero-error variants of post-selected query algorithms are equivalent to non-deterministic classical query algorithms, which in turn are characterised by nonnegative polynomials, and for some problems require exponentially more queries to the input than their bounded-error counterparts. Finally, we describe a post-selected query algorithm for approximating the Majority function, and an efficient query algorithm for approximate counting.

arXiv:1804.10010•Apr 26, 2018•1 citation

A Relativizing MIP for BQP

Scott Aaronson, Anand Natarajan, Avishay Tal +1 more

Complexity class containments involving interactive proof classes are famously nonrelativizing: although $\mathsf{IP} = \mathsf{PSPACE}$, Fortnow and Sipser showed that that there exists an oracle relative to which $\mathsf{coNP} \not\subseteq \mathsf{IP}$. In contrast, the question of whether the containment $\mathsf{BQP} \subseteq \mathsf{IP}$ is relativizing remains wide open. In this work we make progress towards resolving this question by showing that the containment $\mathsf{BQP} \subseteq \mathsf{MIP}$ holds with respect to any classical oracle. We obtain this result by constructing, for any classical oracle $O$, a $\mathsf{PCP}$ proof system for $\mathsf{BQP}^{O}$ where the verifier makes polynomially many classical queries to an exponentially-long proof, and to the oracle $O$. Our construction is inspired by the state synthesis algorithm of Grover and Rudolph, and serves as a complement to the "exponential PCP" constructed by Aharonov, Arad, and Vidick, which achieves similar parameters but which is based on different ideas and does not relativize. We propose relativization as a proxy for prover efficiency, and hope that progress towards an $\mathsf{IP}$ for $\mathsf{BQP}$ in the oracle world will lead to a non-cryptographic interactive protocol for proving any quantum computation to a classical skeptic in the unrelativized world, which is a longstanding open problem in quantum complexity theory.

quant-pharXiv:2604.11952•Apr 15, 2026•0 citations

Approximate Degree in Classical and Quantum Computing

Mark Bun, Justin Thaler

The ability (or inability) to represent or approximate Boolean functions by polynomials is a central concept in complexity theory, underlying interactive and probabilistically checkable proof systems, circuit lower bounds, quantum complexity theory, and more. In this book, the authors survey what is known about a particularly natural notion of approximation by polynomials, capturing pointwise approximation over This book covers recent progress on proving approximate degree lower and upper bounds and describes some applications of the new bounds to oracle separations, quantum query and communication complexity, and circuit complexity. The authors explain how several of these advances have been unlocked by a particularly simple and elegant technique, called dual block composition, for constructing solutions to this dual linear program. They also provide concise coverage of even more recent lower bound techniques based on a new complexity measure called spectral sensitivity. Finally, they show how explicit constructions of approximating polynomials have been inspired by quantum query algorithms. This book provides a comprehensive review of the foundational and recent developments of an important topic in both classical and quantum computing. The reader has a considerable body of knowledge condensed in an accessible form to quickly understand the principles and further their own research.

•Jan 1, 2022•0 citations
We study the following problem: with the power of postselection (classically or quantumly), what is your ability to answer adaptive queries to certain languages? More specifically, for what kind of computational classes C, we have P^C belongs to PostBPP or PostBQP? While a complete answer to the above question seems impossible given the development of present computational complexity theory. We study the analogous question in query complexity, which sheds light on the limitation of relativized methods (the relativization barrier) to the above question. Informally, we show that, for a partial function f, if there is no efficient small bounded-error algorithm for f classically or quantumly, then there is no efficient postselection bounded-error algorithm to answer adaptive queries to f classically or quantumly. Our results imply a new proof for the classical oracle separation P^{NP^O} notsubset PP^O, which is arguably more elegant. They also lead to a new oracle separation P^{SZK^O} notsubset PP^O, which is close to an oracle separation between SZK and PP - an open problem in the field of oracle separations. Our result also implies a hardness amplification construction for polynomial approximation: given a function f on n bits, we construct an adaptive-version of f, denoted by F, on O(m·n) bits, such that if f requires large degree to approximate to error 2/3 in a certain one-sided sense, then F requires large degree to approximate even to error 1/2 - 2^{-m}. Our construction achieves the same amplification in the work of Thaler (ICALP, 2016), by composing a function with O(log n) deterministic query complexity, which is in sharp contrast to all the previous results where the composing amplifiers are all hard functions in a certain sense.
We study the following problem: with the power of postselection (classically or quantumly), what is your ability to answer adaptive queries to certain languages? More specifically, for what kind of computational classes C\mathcal{C}C, we have PC\mathsf{P}^{\mathcal{C}}PC belongs to PostBPP\mathsf{PostBPP}PostBPP and PostBQP\mathsf{PostBQP}PostBQP? While a complete answer to the above question seems impossible given the development of present computational complexity theory. We study the analogous question in query complexity, which sheds light on the limitation of {\em relativized} methods (the relativization barrier) to the above question. Informally, we show that, for a partial function fff, if there is no efficient (In the world of query complexity, being efficient means using O(polylog⁡(n))O(\operatorname*{polylog}(n))O(polylog(n)) time.) {\em small bounded-error} algorithm for fff classically or quantumly, then there is no efficient postselection bounded-error algorithm to answer adaptive queries to fff classically or quantumly. Our results imply a new proof for the classical oracle separation PNPO⊄PPO\mathsf{P}^{\mathsf{NP}^{\mathcal{O}}} \not\subset \mathsf{PP}^{\mathcal{O}}PNPO⊂PPO. They also lead to a new oracle separation PSZKO⊄PPO\mathsf{P}^{\mathsf{SZK}^{\mathcal{O}}} \not\subset \mathsf{PP}^{\mathcal{O}}PSZKO⊂PPO. Our result also implies a hardness amplification construction for polynomial approximation: given a function fff on nnn bits, we construct an adaptive-version of fff, denoted by FFF, on O(m⋅n)O(m \cdot n)O(m⋅n) bits, such that if fff requires large degree to approximate to error 2/32/32/3 in a certain one-sided sense, then FFF requires large degree to approximate even to error 1/2−2−m1/2 - 2^{-m}1/2−2−m. Our construction achieves the same amplification in the work of Thaler (ICALP, 2016), by composing a function with O(log⁡n)O(\log n)O(logn) {\em deterministic query complexity}.
In 2004, Aaronson introduced the complexity class PostBQP\mathsf{PostBQP}PostBQP (BQP\mathsf{BQP}BQP with postselection) and showed that it is equal to PP\mathsf{PP}PP. Following their line of work, we introduce two new complexity classes. The first, CorrBQP\mathsf{CorrBQP}CorrBQP, is a modification of BQP\mathsf{BQP}BQP which has the power to perform correlated measurements, i.e. measurements that output the same value across a partition of registers. The second, MajBQP\mathsf{MajBQP}MajBQP, augments BQP\mathsf{BQP}BQP with the ability to collapse a register to its most likely measurement outcome. Specifically, we consider two variants, MajBQP\mathsf{MajBQP}MajBQP and AdMajBQP\mathsf{AdMajBQP}AdMajBQP, where the latter may perform intermediate measurements. We exactly characterize the computational power of the models, CorrBQP=AdMajBQP=BPPPP\mathsf{CorrBQP} = \mathsf{AdMajBQP} = \mathsf{BPP}^{\mathsf{PP}}CorrBQP=AdMajBQP=BPPPP and MajBQP=PPP\mathsf{MajBQP} = \mathsf{P}^{\mathsf{PP}}MajBQP=PPP. In fact, we show that other metaphysical modifications of BQP\mathsf{BQP}BQP, such as CBQP\mathsf{CBQP}CBQP (i.e. BQP\mathsf{BQP}BQP with the ability to clone arbitrary quantum states), are also equal to BPPPP\mathsf{BPP}^{\mathsf{PP}}BPPPP. We show that CorrBQP\mathsf{CorrBQP}CorrBQP and MajBQP\mathsf{MajBQP}MajBQP are self-low with respect to classically-accessible queries. In contrast, if they were self-low under quantumly-accessible queries, the counting hierarchy would collapse. Furthermore, we introduce a variant of rational degree that lower-bounds the query complexity of BPPPP\mathsf{BPP}^{\mathsf{PP}}BPPPP. Lastly, we extend the adversary lower-bounding technique to AdPDQP\mathsf{AdPDQP}AdPDQP, BQP\mathsf{BQP}BQP with the ability to sample the current state of an algorithm with collapsing it and adapt the computation based on the samples.
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.
We study classical query algorithms with post-selection, and find that they are closely connected to rational functions with nonnegative coefficients. We show that the post-selected classical query complexity of a Boolean function is equal to the minimal degree of a rational function with nonnegative coefficients that approximates it (up to a factor of two). For post-selected quantum query algorithms, a similar relationship was shown by Mahadev and de Wolf, where the rational approximations are allowed to have negative coefficients. Using our characterisation, we find an exponentially large separation between post-selected classical query complexity and post-selected quantum query complexity, by proving a lower bound on the degree of rational approximations (with nonnegative coefficients) to the Majority function. This lower bound can be generalised to arbitrary symmetric functions, and allows us to find an unbounded separation between non-deterministic quantum and post-selected classical query complexity. All lower bounds carry over into the communication complexity setting. We show that the zero-error variants of post-selected query algorithms are equivalent to non-deterministic classical query algorithms, which in turn are characterised by nonnegative polynomials, and for some problems require exponentially more queries to the input than their bounded-error counterparts. Finally, we describe a post-selected query algorithm for approximating the Majority function, and an efficient query algorithm for approximate counting.
Complexity class containments involving interactive proof classes are famously nonrelativizing: although IP=PSPACE\mathsf{IP} = \mathsf{PSPACE}IP=PSPACE, Fortnow and Sipser showed that that there exists an oracle relative to which coNP⊈IP\mathsf{coNP} \not\subseteq \mathsf{IP}coNP⊆IP. In contrast, the question of whether the containment BQP⊆IP\mathsf{BQP} \subseteq \mathsf{IP}BQP⊆IP is relativizing remains wide open. In this work we make progress towards resolving this question by showing that the containment BQP⊆MIP\mathsf{BQP} \subseteq \mathsf{MIP}BQP⊆MIP holds with respect to any classical oracle. We obtain this result by constructing, for any classical oracle OOO, a PCP\mathsf{PCP}PCP proof system for BQPO\mathsf{BQP}^{O}BQPO where the verifier makes polynomially many classical queries to an exponentially-long proof, and to the oracle OOO. Our construction is inspired by the state synthesis algorithm of Grover and Rudolph, and serves as a complement to the "exponential PCP" constructed by Aharonov, Arad, and Vidick, which achieves similar parameters but which is based on different ideas and does not relativize. We propose relativization as a proxy for prover efficiency, and hope that progress towards an IP\mathsf{IP}IP for BQP\mathsf{BQP}BQP in the oracle world will lead to a non-cryptographic interactive protocol for proving any quantum computation to a classical skeptic in the unrelativized world, which is a longstanding open problem in quantum complexity theory.
The ability (or inability) to represent or approximate Boolean functions by polynomials is a central concept in complexity theory, underlying interactive and probabilistically checkable proof systems, circuit lower bounds, quantum complexity theory, and more. In this book, the authors survey what is known about a particularly natural notion of approximation by polynomials, capturing pointwise approximation over This book covers recent progress on proving approximate degree lower and upper bounds and describes some applications of the new bounds to oracle separations, quantum query and communication complexity, and circuit complexity. The authors explain how several of these advances have been unlocked by a particularly simple and elegant technique, called dual block composition, for constructing solutions to this dual linear program. They also provide concise coverage of even more recent lower bound techniques based on a new complexity measure called spectral sensitivity. Finally, they show how explicit constructions of approximating polynomials have been inspired by quantum query algorithms. This book provides a comprehensive review of the foundational and recent developments of an important topic in both classical and quantum computing. The reader has a considerable body of knowledge condensed in an accessible form to quickly understand the principles and further their own research.