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

arXiv:2507.03692

Modifications of Quantum Computation and Adaptive Queries to PP

David Miloschewsky, Supartha Podder

Published Jul 4, 2025• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2507.03692

Related papers

New Lower-Bounds for Quantum Computation with Non-Collapsing Measurements

David Miloschewsky, Supartha Podder

Aaronson, Bouland, Fitzsimons and Lee introduced the complexity class PDQP (which was original labeled naCQP), an alteration of BQP enhanced with the ability to obtain non-collapsing measurements, samples of quantum states without collapsing them. Although PDQP contains SZK, it still requires $Ω(N^{1/4})$ queries to solve unstructured search. We formulate an alternative equivalent definition of PDQP, which we use to prove the positive weighted adversary lower-bounding method, establishing multiple tighter bounds and a trade-off between queries and non-collapsing measurements. We utilize the technique in order to analyze the query complexity of the well-studied majority and element distinctness problems. Additionally, we prove a tight $Θ(N^{1/3})$ bound on search. Furthermore, we use the lower-bound to explore PDQP under query restrictions, finding that when combined with non-adaptive queries, we limit the speed-up in several cases.

arXiv:2411.04085•Leibniz international proceedings in informatics•Nov 6, 2024•0 citations

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

On exact counting and quasi-quantum complexity

Niel de Beaudrap

We present characterisations of "exact" gap-definable classes, in terms of indeterministic models of computation which slightly modify the standard model of quantum computation. This follows on work of Aaronson [arXiv:quant-ph/0412187], who shows that the counting class PP can be characterised in terms of bounded-error "quantum" algorithms which use invertible (and possibly non-unitary) transformations, or postselections on events of non-zero probability. Our work considers similar modifications of the quantum computational model, but in the setting of exact algorithms, and algorithms with zero error and constant success probability. We show that the gap-definable counting classes [J. Comput. Syst. Sci. 48 (1994), p.116] which bound exact and zero-error quantum algorithms can be characterised in terms of "quantum-like" algorithms involving nonunitary gates, and that postselection and nonunitarity have equivalent power for exact quantum computation only if these classes collapse.

arXiv:1509.07789•Sep 25, 2015•0 citations

Adaptivity vs. Postselection, and Hardness Amplification for Polynomial Approximation

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

Leibniz international proceedings in informatics•Jan 1, 2016•1 citation

Quantum Lower Bounds by Sample-to-Query Lifting

Qisheng Wang, Zhicheng Zhang

Abstract. The polynomial method by Beals, Buhrman, Cleve, Mosca, and de Wolf (FOCS 1998; [ J. ACM, 48 (2001), pp. 778–797]) and the adversary method by Ambainis (STOC 2000; [ J. Comput. System Sci., 64 (2002), pp. 750–767]) and the compressed oracle method by Zhandry [ Proceedings of the 39 th CRYPTO, 2019, pp. 239–268] have been shown to be powerful in proving quantum query lower bounds for a wide variety of problems. In this paper, we propose a new method for proving quantum query lower bounds by a quantum sample-to-query lifting theorem, which is from an information theory perspective. Using this method, we obtain the following new results: (1) A quadratic relation between quantum sample and query complexities regarding quantum property testing, which is optimal and saturated by quantum state discrimination. Here, the sample complexity is measured given sample access to the quantum state to be tested, while the query complexity is measured given query access to an oracle that block-encodes the quantum state. (2) A matching lower bound [Formula: see text] for quantum Gibbs sampling at inverse temperature [Formula: see text] ([Formula: see text] suppresses logarithmic factors), showing that the quantum Gibbs sampler by Gilyén, Su, Low, and Wiebe [ Proceedings of the 51 st STOC, 2019, pp. 193–204] is optimal. (3) A new lower bound [Formula: see text] for the entanglement entropy problem with gap [Formula: see text], which was recently studied by She and Yuen [ Proceedings of the 14 th ITCS, 2023, pp. 96:1–96:17]. (4) A series of quantum query lower bounds for matrix spectrum testing, based on the sample lower bounds for quantum state spectrum testing by O’Donnell and Wright (STOC 2015; [ Comm. Math. Phys., 387 (2021), pp. 1–95]). In addition, we provide unified proofs for some known lower bounds that have been proven previously via different techniques, including those for phase/amplitude estimation and Hamiltonian simulation.

arXiv:2308.01794•SIAM Journal on Computing•Oct 10, 2025•3 citations

Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks

Simon C. Marshall, Scott Aaronson, Vedran Dunjko

This paper furthers existing evidence that quantum computers are capable of computations beyond classical computers. Specifically, we strengthen the collapse of the polynomial hierarchy to the second level if: (i) Quantum computers with postselection are as powerful as classical computers with postselection ($\mathsf{PostBQP=PostBPP}$), (ii) any one of several quantum sampling experiments ($\mathsf{BosonSampling}$, $\mathsf{IQP}$, $\mathsf{DQC1}$) can be approximately performed by a classical computer (contingent on existing assumptions). This last result implies that if any of these experiment's hardness conjectures hold, then quantum computers can implement functions classical computers cannot ($\mathsf{FBQP\neq FBPP}$) unless the polynomial hierarchy collapses to its 2nd level. These results are an improvement over previous work which either achieved a collapse to the third level or were concerned with exact sampling, a physically impractical case. The workhorse of these results is a new technical complexity-theoretic result which we believe could have value beyond quantum computation. In particular, we prove that if there exists an equivalence between problems solvable with an exact counting oracle and problems solvable with an approximate counting oracle, then the polynomial hierarchy collapses to its second level, indeed to $\mathsf{ZPP^{NP}}$.

arXiv:2410.20935•Leibniz international proceedings in informatics•Oct 28, 2024•0 citations
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.
Aaronson, Bouland, Fitzsimons and Lee introduced the complexity class PDQP (which was original labeled naCQP), an alteration of BQP enhanced with the ability to obtain non-collapsing measurements, samples of quantum states without collapsing them. Although PDQP contains SZK, it still requires Ω(N1/4)Ω(N^{1/4})Ω(N1/4) queries to solve unstructured search. We formulate an alternative equivalent definition of PDQP, which we use to prove the positive weighted adversary lower-bounding method, establishing multiple tighter bounds and a trade-off between queries and non-collapsing measurements. We utilize the technique in order to analyze the query complexity of the well-studied majority and element distinctness problems. Additionally, we prove a tight Θ(N1/3)Θ(N^{1/3})Θ(N1/3) bound on search. Furthermore, we use the lower-bound to explore PDQP under query restrictions, finding that when combined with non-adaptive queries, we limit the speed-up in several cases.
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}.
We present characterisations of "exact" gap-definable classes, in terms of indeterministic models of computation which slightly modify the standard model of quantum computation. This follows on work of Aaronson [arXiv:quant-ph/0412187], who shows that the counting class PP can be characterised in terms of bounded-error "quantum" algorithms which use invertible (and possibly non-unitary) transformations, or postselections on events of non-zero probability. Our work considers similar modifications of the quantum computational model, but in the setting of exact algorithms, and algorithms with zero error and constant success probability. We show that the gap-definable counting classes [J. Comput. Syst. Sci. 48 (1994), p.116] which bound exact and zero-error quantum algorithms can be characterised in terms of "quantum-like" algorithms involving nonunitary gates, and that postselection and nonunitarity have equivalent power for exact quantum computation only if these classes collapse.
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.
Abstract. The polynomial method by Beals, Buhrman, Cleve, Mosca, and de Wolf (FOCS 1998; [ J. ACM, 48 (2001), pp. 778–797]) and the adversary method by Ambainis (STOC 2000; [ J. Comput. System Sci., 64 (2002), pp. 750–767]) and the compressed oracle method by Zhandry [ Proceedings of the 39 th CRYPTO, 2019, pp. 239–268] have been shown to be powerful in proving quantum query lower bounds for a wide variety of problems. In this paper, we propose a new method for proving quantum query lower bounds by a quantum sample-to-query lifting theorem, which is from an information theory perspective. Using this method, we obtain the following new results: (1) A quadratic relation between quantum sample and query complexities regarding quantum property testing, which is optimal and saturated by quantum state discrimination. Here, the sample complexity is measured given sample access to the quantum state to be tested, while the query complexity is measured given query access to an oracle that block-encodes the quantum state. (2) A matching lower bound [Formula: see text] for quantum Gibbs sampling at inverse temperature [Formula: see text] ([Formula: see text] suppresses logarithmic factors), showing that the quantum Gibbs sampler by Gilyén, Su, Low, and Wiebe [ Proceedings of the 51 st STOC, 2019, pp. 193–204] is optimal. (3) A new lower bound [Formula: see text] for the entanglement entropy problem with gap [Formula: see text], which was recently studied by She and Yuen [ Proceedings of the 14 th ITCS, 2023, pp. 96:1–96:17]. (4) A series of quantum query lower bounds for matrix spectrum testing, based on the sample lower bounds for quantum state spectrum testing by O’Donnell and Wright (STOC 2015; [ Comm. Math. Phys., 387 (2021), pp. 1–95]). In addition, we provide unified proofs for some known lower bounds that have been proven previously via different techniques, including those for phase/amplitude estimation and Hamiltonian simulation.
This paper furthers existing evidence that quantum computers are capable of computations beyond classical computers. Specifically, we strengthen the collapse of the polynomial hierarchy to the second level if: (i) Quantum computers with postselection are as powerful as classical computers with postselection (PostBQP=PostBPP\mathsf{PostBQP=PostBPP}PostBQP=PostBPP), (ii) any one of several quantum sampling experiments (BosonSampling\mathsf{BosonSampling}BosonSampling, IQP\mathsf{IQP}IQP, DQC1\mathsf{DQC1}DQC1) can be approximately performed by a classical computer (contingent on existing assumptions). This last result implies that if any of these experiment's hardness conjectures hold, then quantum computers can implement functions classical computers cannot (FBQP≠FBPP\mathsf{FBQP\neq FBPP}FBQP=FBPP) unless the polynomial hierarchy collapses to its 2nd level. These results are an improvement over previous work which either achieved a collapse to the third level or were concerned with exact sampling, a physically impractical case. The workhorse of these results is a new technical complexity-theoretic result which we believe could have value beyond quantum computation. In particular, we prove that if there exists an equivalence between problems solvable with an exact counting oracle and problems solvable with an approximate counting oracle, then the polynomial hierarchy collapses to its second level, indeed to ZPPNP\mathsf{ZPP^{NP}}ZPPNP.