Pith. sign in

REVIEW 4 major objections 4 minor 14 references

Non-Standard Oracles for Bounded-Error Complexity Classes

T0 review · 4 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves a bounded-error containment, QMA ⊆ polyQCPH, that holds for every classical oracle but fails for a specific quantum unitary oracle.

desk verdict Introduces polyQCPH and claims a bounded-error quantum oracle separation that would resolve an Aaronson open problem; the idea is good, but the write-up has fixable proof gaps. read the letter →

arxiv 2504.19470 v3 pith:D4OP5VOV submitted 2025-04-28 quant-ph cs.CC

Avantika Agarwal , Srijita Kundu This is my paper · ORCID
classification quant-phcs.CC MSC 68Q1568Q1281P68
keywords QMApolyQCPHquantum-classicalpolynomialhierarchyquantumoracledistributionalseparationbounded-errorcomplexityrelativization
topics P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes that the containment $\mathrm{QMA} \subseteq \mathrm{polyQCPH}$—quantum Merlin–Arthur inside the polynomial-time quantum-classical hierarchy with polynomially many alternating classical proofs—holds in the unrelativized model and relative to every classical oracle, yet there is a single quantum unitary oracle $U$ relative to which $\mathrm{QMA}^U$ is not contained in $\mathrm{polyQCPH}^U$. This is the first bounded-error example of a complexity-class containment that relativizes with respect to all classical oracles but fails with respect to a quantum oracle, resolving the open problem from [Aar09]. The proof works by defining $\mathrm{polyQCPH}$ as a bounded-error analogue of $\mathrm{PSPACE}$ in the quantum-oracle setting, then showing that the oracle of [AK07], already known to separate $\mathrm{QMA}$ from $\mathrm{QCMA}$, also separates $\mathrm{QMA}$ from $\mathrm{polyQCPH}$. The same separation is shown to hold relative to a distributional oracle, which the authors offer as a caution about the use of such non-standard oracle models.

What carries the argument

The central object is $\mathrm{polyQCPH}$, the quantum-classical polynomial hierarchy with a polynomial number of alternating classical proofs, defined so that it equals $\mathrm{PSPACE}$ relative to classical oracles but remains a bounded-error quantum class with a meaningful quantum-oracle relativization. The load-bearing mechanism is the geometric lemma for $p$-uniform measures: for a measure $\sigma$ obtained by conditioning Haar measure on an event of probability at least $p$, $E_{|\psi\rangle\sim\sigma}[\langle\psi|\rho|\psi\rangle] = O((1+\log(1/p))/N)$ for any density matrix $\rho$ on $N$ dimensions. Applied through the hybrid method, this bounds how well a $T$-query algorithm can distinguish the oracle $U_\psi$ from the identity when the good witness $w^*$ has a cell $S(w^*)$ of measure at least $2^{-m}$; the resulting small per-witness bias is what permits the diagonalization in Theorem 4.4 to make every $\mathrm{polyQCPH}$ verifier err on some input. The same bound extends to verifiers with query access to $U^*$, $U^T$, and $U^{-1}$.

What would settle it

Compute the expectation in Theorem 4.3, Eq. (1), for a small query algorithm (for example, a two-query circuit) on the [AK07] oracle with $n = 20$ qubits and witness length $m = 100$: the paper bounds the expected squared distance $E\bigl[\bigl\||\Phi_\psi\rangle - |\Phi_I\rangle\bigr\|^2\bigr]$ by $O\bigl(T\sqrt{(m+1)/2^n}\bigr)$, a quantity with the scaling of a distance. If the hybrid method actually accumulates $T^2(m+1)/2^n$ (squared-distance scaling), then the Markov step in Eq. (2) does not give $o(1)$ probability for polynomial $T$, and the diagonalization cannot force error. Evaluating the expectation exactly for one- and two-query algorithms would settle the exponent and hence whether $\mathrm{QMA}^U \not\subseteq \mathrm{polyQCPH}^U$ is established.

Watch

Extended reading notes

Core claim

The paper introduces the bounded-error quantum class $\mathrm{polyQCPH}$, in which a polynomial-time quantum verifier receives polynomially many alternating classical proofs and must accept true instances with probability at least $2/3$ and reject false instances with probability at most $1/3$. It proves that $\mathrm{QMA} \subseteq \mathrm{polyQCPH}$, that $\mathrm{QMA}^O \subseteq \mathrm{polyQCPH}^O$ for every classical oracle $O$—because $\mathrm{polyQCPH}^O = \mathrm{PSPACE}^O$—and that there exists a quantum unitary oracle $U$ such that $\mathrm{QMA}^U \not\subseteq \mathrm{polyQCPH}^U$. The separating $U$ is the reflection oracle $U_\psi = I - 2|\psi\rangle\langle\psi|$ for a Haar-random state $|\psi\rangle$ versus the identity $I$, the same oracle used in [AK07] to separate $\mathrm{QMA}$ from $\mathrm{QCMA}$. The argument adapts the geometric bound on $p$-uniform measures from [AK07] to show that a witness $w^*$ whose cell $S(w^*)$ has large measure forces every classical witness to have small distinguishing bias between $U_\psi$ and $I$; a diagonalization over $\mathrm{polyQCPH}$ verifiers then constructs $U$ with a verifier that errs on a chosen input. The same construction is carried out for the distributional oracle model using the oracle of [LLPY24], yielding $\mathrm{QMA}^D \not\subseteq \mathrm{polyQCPH}^D$ for a distributional oracle $D$.

Load-bearing premise

The separation stands or falls on the geometric bound from [AK07]: a witness cell of large $p$-uniform measure must force every classical proof to have small distinguishing bias between $U_\psi$ and the identity, in the exact quantitative form used in Theorem 4.3; if that bound, or its stated exponent, fails, the diagonalization in Theorem 4.4 cannot force a $\mathrm{polyQCPH}$ verifier to err on the selected state.

Editorial extensions

If this is right

  • It resolves the open problem from [Aar09] for bounded-error classes: $\mathrm{QMA} \subseteq \mathrm{polyQCPH}$ is a containment that relativizes for every classical oracle but not for a quantum unitary oracle, so relativizing proof techniques cannot settle it in both settings at once.
  • The [AK07] reflection oracle separates $\mathrm{QMA}$ not only from $\mathrm{QCMA}$, but from the entire polynomial quantum-classical hierarchy, and from $\mathrm{PQP}$ as well, since $\mathrm{QMA}^U \subseteq \mathrm{PQP}^U$ (Lemma 4.1).
  • The separation persists even when the $\mathrm{polyQCPH}$ verifier is allowed queries to $U^*$, $U^T$, and $U^{-1}$, so it does not rely on restricted query access.
  • For distributional oracles, the equality $\mathrm{polyQCPH}^D = \mathrm{PSPACE}^D$ that holds for classical oracles breaks: there is a distributional oracle $D$ with $\mathrm{QMA}^D \not\subseteq \mathrm{polyQCPH}^D$.
  • The results support the abstract's caution: quantum unitary oracles and distributional oracles must be used carefully, because separations in these models do not automatically translate into relativization barriers for classical proof techniques.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A direct corollary the paper leaves implicit: since $\mathrm{QMA}^U \subseteq \mathrm{PQP}^U$ and $\mathrm{PQP}^U \not\subseteq \mathrm{polyQCPH}^U$, the $\mathrm{PQP}$/$\mathrm{PSPACE}$ analogue also fails to relativize quantumly, so the phenomenon is not an artifact of quantum proofs.
  • The geometric-bound mechanism suggests a recipe: any quantum oracle problem with a single NO oracle and a good-witness partition into cells of measure at least $2^{-m}$ should yield a $\mathrm{QMA}$-vs-$\mathrm{polyQCPH}$ separation; testing this on other single-NO oracles from quantum cryptography could show whether the partition structure is the key driver.
  • If the geometric bound's exponent were corrected to a different $T$-dependence, the separation might shift from $\mathrm{polyQCPH}$ to a class with fewer alternation rounds; a natural stress test is whether the [AK07] oracle still separates $\mathrm{QMA}$ from $\mathrm{QCPH}$ (constant alternations).
  • The distributional separation is driven by the prover's ignorance of the sampled $r_n$: the noise-robust witness bound of [LLPY24] (Lemma 5.2) holds only when proofs avoid $r_n$. One could test whether allowing classical proofs to depend on $r_n$ either restores the containment or requires a different oracle construction.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper introduces a bounded-error quantum-classical polynomial hierarchy polyQCPH, proves that QMA is contained in polyQCPH both unrelativized and relative to every classical oracle, and claims to construct a quantum unitary oracle U such that QMA^U is not contained in polyQCPH^U. It also claims an analogous separation relative to a distributional oracle. The main conceptual contribution is to exhibit a complexity-class containment that relativizes classically but fails quantumly, thereby resolving an open problem of Aaronson for bounded-error classes. The proofs reuse the Aaronson-Kuperberg quantum oracle and the Li-Liu-Pelecanos-Yamakawa distributional oracle, and introduce polyQCPH as the bounded-error analogue of PSPACE that admits a quantum-oracle interpretation.

Significance. If the main theorem were fully established, it would resolve a question that has been open since 2009 and would provide a concrete cautionary example about the use of quantum and distributional oracle models. The paper is also notable for introducing a natural bounded-error class, polyQCPH, that generalizes QCMA and collapses to PSPACE under classical oracles. The central separation is plausible and the reuse of the AK07 and LLPY24 oracles gives the argument a solid external foundation. However, the manuscript as written contains several load-bearing gaps: the formal definition of polyQCPH does not match the intended polynomial number of alternations, the key geometric bound in Theorem 4.3 is asserted without a supporting derivation, and the proof of Lemma 4.1 is incorrect. These issues prevent acceptance in the current form.

major comments (4)
  1. [Definitions 2.9–2.11] The formal definition of polyQCPH is inconsistent with the intended meaning. Definition 2.9 states that V_n takes proofs y_1,...,y_{n_i}, and Definition 2.11 defines polyQCPH as the union over i∈N of polyQCΣ_i. If the number of proofs is the fixed constant i, the union does not allow the number of alternations to grow with the input length, contradicting the introduction and the use in Theorem 4.4 of q(n_i) alternations. The definitions should be rewritten so that the number of proofs is a polynomial function i(n), and polyQCPH is the union over all polynomial functions i(n). Without this correction, the statement of the main theorem is ambiguous.
  2. [Theorem 4.3, Eq. (1)] The bound E_{|ψ>∼S(w*)}[|| |Φψ> − |ΦI> ||^2] ≤ O(T sqrt((m+1)/2^n)) is the pivotal estimate for the quantum oracle separation, but it is asserted without proof. The paper says this follows from Lemma 2.13, yet Lemma 2.13 applies to a density matrix ρ that is independent of ψ, whereas in the hybrid expansion the state before each query depends on ψ through earlier queries. The printed second-moment form is not directly a consequence of the stated lemma. Since Eq. (2) and Theorem 4.4 rest entirely on this bound, the authors must either provide a complete derivation or cite the exact theorem in [AK07] that yields this estimate, explaining how the adaptive dependence of the query algorithm is handled.
  3. [Lemma 4.1] The proof of QMA^U⊆PQP^U is incorrect. For a YES instance, feeding the maximally mixed state to a QMA verifier gives the average acceptance probability over all proof states, and the existence of one good proof does not imply a lower bound of 2^{-p(n)}(1−2^{-r(n)}). The average can be arbitrarily small, for example if the verifier accepts only a single computational basis state. The lemma may be true, but this proof does not establish it. The lemma is not needed for the main separation, but as written it is a substantial error in a stated result and should be fixed or removed.
  4. [Theorem 5.3] The claim that L∈QMA^O with probability 1 over the choice of {(b_n,H_n,r_n)} is not justified by Lemma 5.2 item 1. That lemma provides a witness |z_H> that succeeds with probability 1−negl(n) over (H_n,r_n,b_n), but a negligible failure probability for each n does not imply that all n succeed with probability 1, because the failure probabilities may not be summable. The authors should either prove a stronger statement, such as the existence of a witness that works for every r_n up to a measure-zero set, or give the precise theorem in [LLPY24] that establishes L∈QMA^O with probability 1. This is load-bearing for the completeness side of the distributional separation.
minor comments (4)
  1. [Definition 2.9] The notation y_{n_i} appears to be a typo; the intended number of proofs should be a polynomial function of n, and the definition should use i(n) rather than the ambiguous subscript n_i.
  2. [Lemma 3.2] The proof of PSPACE^O⊆polyPH^O is very terse; it should state explicitly that the TQBF formula constructed in Lemma 3.1 can include oracle predicates O so that the quantified formula is decidable by polyPH^O.
  3. [Theorem 4.3] The theorem statement says 'with high probability' but does not quantify the probability or the exact measure over S(w*); the proof later uses 2/3, so this should be stated as a specific parameter in the theorem.
  4. [Theorem 4.4] The diagonalization should specify that n_i is chosen sufficiently large so that no previously handled verifier can query U_{n_i} on its own input length; otherwise fixing U_{n_i} could disturb earlier diagonalization steps. This is fixable by a standard size argument but should be stated.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; the central claims rest on external prior oracle results and standard PSPACE facts, with only non-load-bearing self-citations.

full rationale

The paper's derivation chain is not circular in the sense targeted by this pass. The unrelativized and classical-oracle containments QMA⊆polyQCPH and QMA^O⊆polyQCPH^O are obtained by composing standard external facts: QMA⊆PSPACE from Marriott-Watrous and PSPACE^O=polyPH^O=polyQCPH^O from the classical TQBF-completeness theorem. These are not fitted parameters, renamed predictions, or definitions of one class in terms of the other. The quantum and distributional separations are imported from external, independently published constructions: the AK07 unitary oracle problem and its geometric Lemma 2.13, and the LLPY24 distributional oracle Lemma 5.2. The paper does not tune a parameter to a data subset and then relabel it as a prediction; the diagonalization in Theorem 4.4 uses the AK07 oracle in essentially the way AK07 used it. The only author self-citations, [AGKR24] and [AB24], are pointers for additional properties of QCPH and are not load-bearing for any theorem. The reviewer-flagged concern about Theorem 4.3 Eq. (1), where a second-moment bound is asserted with a first-moment-looking right-hand side and cited to AK07, is a missing-derivation and possible mathematical-correctness risk rather than a circular dependency, because the cited bound is external, not derived from the conclusion being proved. Similarly, the apparent quantitative issue in Lemma 4.1's maximally-mixed-state padding is a correctness concern, not an equivalence-by-construction. Accordingly, the central derivation is self-contained against external benchmarks and no significant circularity is present.

Assumptions & free parameters 0 free parameters · 5 assumptions · 1 invented entities

No free parameters are fitted. The main mathematical inputs are standard results in quantum complexity (strong error reduction, PSPACE = BQPSPACE, PQP = PP) and two external oracle lemmas, AK07's geometric lemma and LLPY24's distributional indistinguishability lemma. The proof of Theorem 5.3 requires a stronger version of the LLPY24 lemma than the paper states.

assumptions (5)
  • standard math QMA has strong error reduction: for any polynomial r, completeness 1 - 2^{-r} and soundness 2^{-r} are achievable (Marriott-Watrous).
    Used in Lemma 4.1 to make the maximally mixed state verifier's YES and NO acceptance probabilities well separated.
  • standard math TQBF is complete for PSPACE, and this relativizes with respect to every classical oracle.
    Invoked in Lemma 3.1 and used to prove PSPACE = polyQCPH for classical oracles.
  • standard math PSPACE equals BQPSPACE (Watrous 2003).
    Used in Section 1.1 to argue that BQPSPACE is not the right quantum analogue of PSPACE for the separation.
  • domain assumption Lemma 5.2, quoted as Lemma 6.1 of LLPY24, holds as stated, including the unstated properties of the code C from YZ24.
    The distributional oracle separation in Theorem 5.3 relies entirely on this external lemma; its proof is not included and depends on code properties not described in this paper.
  • standard math PP equals PQP, and this identity relativizes with respect to classical and distributional oracles.
    Used in Figure 1 and in the proof that PQP^D is contained in PSPACE^D for distributional oracles.
invented entities (1)
  • polyQCPH (polynomial-alternation quantum-classical polynomial hierarchy)
    purpose: Bounded-error quantum analogue of PSPACE that equals PSPACE under classical oracles but separates from QMA under a quantum oracle; used to resolve Aaronson's open problem.
    Defined in Definition 2.11. Its usefulness depends on its identity with PSPACE classically, which the paper proves, and on its behavior under quantum oracles, which is the paper's central result. It is a mathematical definition rather than a physical entity with external falsifiable consequences.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Non-Standard Oracles for Bounded-Error Complexity Classes." pith.science (2026). https://pith.science/paper/D4OP5VOV

@misc{pith2026250419470,
  author       = {Pith},
  title        = {Pith review of: Non-Standard Oracles for Bounded-Error Complexity Classes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/D4OP5VOV}},
  note         = {Machine review of arXiv:2504.19470}
}
read the original abstract

In recent years, the quantum oracle model introduced by Aaronson and Kuperberg (2007) has found a lot of use in showing oracle separations between complexity classes and cryptographic primitives. It is generally assumed that proof techniques that do not relativize with respect to quantum oracles will also not relativize with respect to classical oracles. Aaronson (2009) showed that this is not the case by showing a complexity class containment that relativizes with respect to classical oracles but not with quantum oracles. However, their result only works for zero-error quantum complexity classes and they leave open the problem for bounded-error complexity classes. We show that there is a quantum oracle problem that is contained in the class QMA, but not in a class we call polyQCPH. However, with respect to classical oracles, QMA is contained in polyQCPH, because polyQCPH is equal to PSPACE with respect to classical oracles. Our result works for polyQCPH, which is a bounded-error complexity class, thus it resolves the open problem from Aaronson (2009). We also show that the same separation holds relative to a distributional oracle, which is a model introduced by Natarajan and Nirkhe (2024). We believe our findings show the need for some caution when using these non-standard oracle models, particularly when showing separations between quantum and classical resources.

Figures

Figures reproduced from arXiv: 2504.19470 by the authors.

Figure 1
Figure 1. Complexity class containments in the unrelatized setting, and with respect to classical, [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 10 canonical work pages

  1. [1]

    On perfect completeness for QMA

    [Aar09] S. Aaronson. “On perfect completeness for QMA.” In:Quantum Inf. Comput.9.1&2 (2009), pp. 81–89.doi:10.26421/QIC9.1-2-5. [AB09] S. Arora and B. Barak.Computational Complexity - A Modern Approach. Cam- bridge University Press, 2009.isbn: 978-0-521-42426-4. [AB24] A. Agarwal and S. Ben-David. “Oracle Separations for the Quantum-Classical Poly- nomial...

    work page doi:10.48550/arxiv.2410.19062 2009

  2. [5]

    The Power of a Single Haar Random State: Constructing and Separating Quantum Pseudorandomness

    arXiv:2510 .05055 [quant-ph]. [CCS25] B. Chen, A. Coladangelo, and O. Sattath. “The Power of a Single Haar Random State: Constructing and Separating Quantum Pseudorandomness.” In:Advances in Cryptology – EUROCRYPT 2025: 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4–8, 2025, Proceeding...

    work page doi:10.1007/978-3-031-91098-2_5 2025

  3. [6]

    On Central Primitives for Quantum Cryptography with Classical Communication

    arXiv:2402.17715 [cs.CR]. [CKP24] R. Chatterjee, S. Kundu, and S. Podder.Are uncloneable proof and advice states strictly necessary?2024. arXiv:2410.11827 [quant-ph]. 19 [CM24] A. Coladangelo and S. Mutreja. “On Black-Box Separations of Quantum Digital Signatures from Pseudorandom States.” In:Theory of Cryptography - 22nd Interna- tional Conference, TCC 2...

    work page Pith review arXiv 2024

  4. [7]

    Translating Between the Common Haar Random State Model and the Unitary Model

    arXiv:2503.11634 [quant-ph]. [H˚ as86] J. H˚ astad. “Almost Optimal Lower Bounds for Small Depth Circuits.” In:Proceed- ings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA. Ed. by J. Hartmanis. ACM, 1986, pp. 6–20.doi: 10.1145/12130.12132. [HRST17] J. H˚ astad, B. Rossman, R. A. Servedio, and L. Tan. “A...

    work page Pith review arXiv 2017

  5. [12]

    Oracle Separation of BQP and PH

    LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2024, 82:1–82:23.doi:10.4230/LIPICS.ITCS.2024.82. [RT19] R. Raz and A. Tal. “Oracle Separation of BQP and PH.” In:Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. STOC

    doi:10.4230/lipics.itcs.2024.82 2024

  6. [197]

    Classical vs Quantum Advice and Proofs Under Classically-Accessible Oracle

    LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2021, 2:1–2:20.doi: 10.4230/LIPICS.TQC.2021.2. [LLPY24] X. Li, Q. Liu, A. Pelecanos, and T. Yamakawa. “Classical vs Quantum Advice and Proofs Under Classically-Accessible Oracle.” In:15th Innovations in Theoret- ical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkele...

    doi:10.4230/lipics.tqc.2021.2 2021

  7. [234]

    Quantum Pseudorandomness and Classical Complexity

    LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2022, 5:1–5:19.doi:10.4230/LIPICS.CCC.2022.5. [Kre21] W. Kretschmer. “Quantum Pseudorandomness and Classical Complexity.” In:16th Conference on the Theory of Quantum Computation, Communication and Cryptog- raphy, TQC 2021, July 5-8, 2021, Virtual Conference. Ed. by M. Hsieh. Vol

    doi:10.4230/lipics.ccc.2022.5 2022

  8. [287]

    QMA vs. QCMA and Pseudorandomness

    LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2024, 72:1–72:19.doi:10.4230/LIPICS.ITCS.20 24.72. [LMY24] J. Liu, S. Mutreja, and H. Yuen. “QMA vs. QCMA and Pseudorandomness.” In: CoRRabs/2411.14416 (2024).doi:10.48550/ARXIV.2411.14416. arXiv:2411.14

    work page Pith review arXiv doi:10.48550/arxiv.2411.14416 2024

Show all 14 references
  1. [297]

    A New World in the Depths of Microcrypt: Separating OWSGs and Quantum Money from QE- FID

    LIPIcs. Schloss Dagstuhl - Leibniz- Zentrum f¨ ur Informatik, 2024, 21:1–21:18.doi:10.4230/LIPICS.ICALP.2024.21. [BMMMY25] A. Behera, G. Malavolta, T. Morimae, T. Mour, and T. Yamakawa. “A New World in the Depths of Microcrypt: Separating OWSGs and Quantum Money from QE- FID.”...

    2024 doi

  2. [325]

    Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2025, 95:1–95:19.doi: 10.4230/LIPICS.ITCS.2025.95

    LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2025, 95:1–95:19.doi: 10.4230/LIPICS.ITCS.2025.95. 21

    2025 doi

  3. [416]

    Quantum Arthur-Merlin games

    20 [MW05] C. Marriott and J. Watrous. “Quantum Arthur-Merlin games.” In:Comput. Com- plex.14.2 (2005), pp. 122–152. [NC16] M. A. Nielsen and I. L. Chuang.Quantum Computation and Quantum Informa- tion (10th Anniversary edition). Cambridge University Press, 2016.isbn: 978-1-10- ...

    2005 doi

  4. [2019]

    The complexity of approximate counting

    New York, NY, USA: Association for Computing Machinery, 2019, pp. 13–23.isbn: 978-1-4503-6705-9.doi:10.1145/3313276.3316315. [Sto83] L. Stockmeyer. “The complexity of approximate counting.” In:Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. STOC ’83. ...

    2003

  5. [2024]

    Cryptography in the Common Haar State Model: Feasibility Results and Separations

    arXiv:2404.05227 [quant-ph]. [AGL24b] P. Ananth, A. Gulati, and Y.-T. Lin. “Cryptography in the Common Haar State Model: Feasibility Results and Separations.” In:Theory of Cryptography: 22nd In- ternational Conference, TCC 2024, Milan, Italy, December 2–6, 2024, Proceedings, P...

    2024 arXiv

  6. [2025]

    Oracle Separation of QMA and QCMA with Bounded Adaptivity

    arXiv:2511.09551 [quant-ph]. [BK24] S. Ben-David and S. Kundu. “Oracle Separation of QMA and QCMA with Bounded Adaptivity.” In:51st International Colloquium on Automata, Languages, and Pro- gramming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia. Ed. by K. Bringmann, M. Grohe,...

    2024

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.