Pith. sign in

REVIEW 2 major objections 4 minor 13 references

QMA vs. QCMA and Pseudorandomness

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

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

Pith's one-line read Assuming a quantum pseudorandomness conjecture for dense permutations, this paper proves a classical oracle separates QMA from QCMA, resolving the long-standing question under that assumption.

desk verdict A conditional QMA/QCMA classical-oracle separation with a solid main proof, but the paper's unconditional interactive-game section has a real independence gap. read the letter →

arxiv 2411.14416 v4 pith:VEZ6SHRF submitted 2024-11-21 quant-ph cs.CC

Jiahui Liu , Saachi Mutreja , Henry Yuen This is my paper · ORCID
classification quant-phcs.CC MSC 68Q1268Q17 PACS 03.67.Lx
keywords QMAvsQCMAclassicaloracleseparationquantumpseudorandomnessdenserandompermutationsmin-entropydecompositionqueryalgorithmsgraphinteractivegames
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

This paper is trying to establish that the gap between quantum and classical proofs can be witnessed by an ordinary classical oracle, provided a plausible but unproved pseudorandomness statement holds. The statement, Conjecture 1.5, says that a quantum algorithm making few queries cannot distinguish a uniform random permutation from one sampled from any distribution whose forward and inverse permutations are both dense in min-entropy. If the conjecture is right, the paper's Components oracle problem—distinguishing a two-component graph from an expander—separates QMA from QCMA. The result also sets up a win-win: either the separation exists, or quantum algorithms gain an advantage at distinguishing dense permutation distributions from uniform, an outcome with cryptographic consequences.

What carries the argument

The load-bearing object is Conjecture 1.5, the quantum pseudorandomness conjecture for random permutations: for any quantum query algorithm making T queries to a tuple of permutations, if both the permutation distribution and its inverse are δ-dense, then the acceptance probability is within poly(T, log N_i)·poly(δ) of that under uniform permutations. Carrying the argument is a min-entropy decomposition lemma (Lemma 3.3) that expresses any high-min-entropy distribution over permutations as a convex combination of (k,δ)-dense distributions with the inverses also dense; this lemma turns the existence of a large set of accepted instances into a pseudorandomness statement. The Components oracle problem—graph oracles given by R=3 perfect matchings, Yes instances having two components and No instances being expanders—provides the concrete separation problem, and the raw-permutation model connects it to permutation queries.

What would settle it

To refute the conjecture it suffices to exhibit a family of permutations whose forward and inverse distributions are δ_N-dense with δ_N·poly(T_N, log N) tending to 0, along with a T_N-query quantum algorithm whose distinguishing bias from uniform is bounded away from 0; no such pair is known, and finding one would collapse the proof of the conditional separation.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is a conditional separation via reduction. Assuming Conjecture 1.5, any efficient QCMA verifier for the Components problem would imply an efficient quantum query algorithm that distinguishes a uniform two-component graph oracle from a uniform expander graph oracle, contradicting a known query lower bound. The reduction works through a min-entropy decomposition lemma for permutations: a high-min-entropy distribution over raw permutations can be split into convex combinations of (k,δ)-dense distributions, and Conjecture 1.5 makes each dense piece look like a bit-fixed source to a few-query algorithm. The fixed coordinates translate to small graph-fixing data, and a random-walk planting procedure shows that such fixed data cannot help, completing the contradiction.

Load-bearing premise

The whole conditional separation rests on Conjecture 1.5—that few-query quantum algorithms cannot distinguish uniform permutations from any distribution whose forward and inverse permutations are both dense in min-entropy—which the paper does not prove.

Editorial extensions

If this is right

  • If Conjecture 1.5 is true, QMA^F differs from QCMA^F for a standard classical oracle F, with no restrictions on the verifier.
  • A proof of the conjecture would settle the long-standing question unconditionally; a refutation would demonstrate quantum advantage in distinguishing dense permutation distributions from uniform.
  • The unconditional interactive-game result yields a simplified proof of a QMA/QCMA separation relative to a distributional oracle.
  • A special case of the simpler boolean-function pseudorandomness conjecture is proved with exponential dependence on query count, giving partial evidence for the family of conjectures.
  • The lower bound for the Components problem holds against all QCMA verifiers with N^{o(1)} queries and witness length, conditional on the conjecture.

Reading between the lines

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

  • An implicit consequence of the win-win framing: if Conjecture 1.5 is eventually disproved, the byproduct is a concrete quantum advantage in the random-permutation model, potentially relevant to post-quantum security of symmetric-key constructions.
  • The decomposition argument suggests a route to an unconditional separation: prove a permutation analogue of the weak pseudorandomness lemma with only exponential dependence on T, possibly using hypercontractivity on the symmetric group.
  • The reliance on 'the witness fixes few coordinates' might be replaced by a direct argument for the Components problem, avoiding the need to resolve the full Aaronson-Ambainis conjecture.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper studies the longstanding question of whether there exists a classical oracle separating QMA from QCMA. Its main contribution is a conditional separation: assuming Conjecture 1.5, a quantum pseudorandomness conjecture for dense distributions over permutations, there is a classical oracle F such that QMA^F differs from QCMA^F. The proof introduces the Components problem, translates graph oracles into a raw-permutation model, applies a min-entropy decomposition to the high-min-entropy distribution induced by a maximizing classical witness, invokes Conjecture 1.5 via Lemma 4.5 to pass from dense sources to bit-fixing sources, and then uses a planting reduction (Lemma 6.4) to reduce distinguishability of the fixed-data instances to the Ambainis-Childs-Liu expansion-testing lower bound. The paper also presents an unconditional separation for an interactive oracle-distinguishing game and claims this yields a simplified proof of distributional oracle separations of Natarajan-Nirkhe and Li-Liu-Pelecanos-Yamakawa.

Significance. If Conjecture 1.5 is true, Theorem 1.1 resolves the Aaronson-Kuperberg question in the standard classical oracle model with an unrestricted verifier, which would be a major advance in quantum complexity theory. The conditional proof is substantial and largely self-contained: the raw-permutation equivalence (Claim 2), the min-entropy decomposition for permutations (Lemma 3.3), the reduction from (k,delta)-dense to delta-dense permutation tuples (Lemma 4.5), and the reconnect/uniformity argument (Lemma 6.6) are nontrivial and clearly presented. The paper is also honest about the status of Conjecture 1.5, which is an unproved mathematical statement rather than a restatement of the conclusion. However, the claimed unconditional interactive-game separation in Section 7 contains a load-bearing gap that currently undermines that part of the paper.

major comments (2)
  1. [Section 7.4, Claim 8] The independence argument for the sequential repetition is not valid as stated. The claim asserts that for a fresh challenge r_i, the oracle F(r_i,.) is independent of all previous oracles F(r_j,.) and hence of the adversary's prior state. This is only true marginally: all proper sub-oracles share the same hidden partition S (and the same set Z), and the adversary's state after previous rounds can encode information about S through its queries and measurements. Conditioned on an outcome X=x of previous rounds, the distribution of F(r_i,.) can differ from the unconditional distribution used in the single-instance lower bound. Therefore the bound Pr[B_i=1|X=x] <= 1/2 + 1/sqrt(N) + O(K/N) is not established, the application of Lemma 7.1 is unsupported, and the claimed unconditional interactive-game separation and the distributional-oracle corollary in Section 7 do not currently follow. The argument would need either fresh independent partitions per round or a single-instance lower bound that holds against a distinguisher holding side information about S.
  2. [Section 7.4, Theorem 7.5] The stated lower bound Omega(eta N) for success probability 1/2 + eta is asserted without derivation of the dependence on eta. The adversary-method calculation in the proof appears to establish a constant-error lower bound of Omega(N); the linear scaling in eta is needed later when eta is set to 1/sqrt(N) to obtain a negligible advantage. This scaling should be justified explicitly, for example by invoking the standard error-probability form of the adversary method, otherwise the subsequent parameter choices in the multi-instance analysis are not supported.
minor comments (4)
  1. [Abstract and Introduction] There are several typos in the abstract and introduction, e.g., 'wh ether' and 'd rawn' in the abstract, and 'P1,...' in the abstract sentence about raw permutations. A careful proofreading pass is needed.
  2. [Section 2.3, Lemma 2.5] The proof of Lemma 2.5 would benefit from spelling out the final application of Theorem 2.4: the norm bound T/N^{1/20} follows from sqrt(T * T/N^{1/10}), but the intermediate expression in the text is easy to misread as a direct bound on the query-weight sum.
  3. [Section 7.2] The notation R is used differently here than in the main body: earlier R is a fixed constant, while in the interactive game the authors set |R| = N. This change of regime should be stated clearly to avoid confusion.
  4. [Section 7.5] The reduction from the distributional oracle model to the interactive game assumes that the interactive prover can identify the set Z of proper challenges by unbounded access to F. This is plausible since the prover is unbounded, but the recognition test should be described explicitly, especially because non-proper oracles may behave arbitrarily.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the conditional separation is a genuine implication from a stated conjecture.

full rationale

The paper's central claim, Theorem 1.1, is an explicitly conditional implication: assuming Conjecture 1.5 (the quantum pseudorandomness conjecture for dense permutation tuples), there exists a classical oracle F with QMA^F != QCMA^F. The conjecture is stated independently in Section 1.1 as a statement about quantum query algorithms distinguishing dense permutation distributions from uniform ones; it does not mention QMA or QCMA and does not presuppose the separation. The derivation chain in Sections 3-6 uses standard min-entropy decomposition (Lemma 3.3), derives a bit-fixing variant of the conjecture (Lemma 4.5), and ultimately reduces to the external query lower bound of Ambainis-Childs-Liu (Lemma 2.5). No parameter is fitted, no 'prediction' is a renamed input, and no load-bearing step reduces by construction to the claim being proved. The main theorem's dependence on an unproved conjecture is a genuine conditional assumption and a correctness risk, but it is not circularity. Separately, the unconditional interactive-game argument in Section 7.4 appears to contain a nontrivial independence gap: Claim 8 asserts that a fresh sub-oracle F(r_i,.) is independent of previous rounds, but the shared hidden partition S means queries in earlier rounds can leak information about S. This is a correctness concern about that unconditional result, not a circular reduction, and it does not affect the conditional Theorem 1.1. Overall, no circular step with quotable evidence was found.

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

The main theorem rests on Conjecture 1.5, a new unproved conjecture about quantum query algorithms and dense permutation distributions. Other axioms are standard results in quantum query complexity, expansion, and Fourier analysis. No free parameters are fitted to data; the proof parameters delta and epsilon are chosen for the contradiction and are not empirical. No new physical or mathematical entities are invented. The Section 7 gap is not an axiom but a missing justification in the independence argument.

assumptions (5)
  • ad hoc to paper Conjecture 1.5: quantum query algorithms cannot distinguish delta-dense permutation distributions (with dense inverses) from uniform random permutations with bias more than poly(T, log N) poly(delta).
    This is the load-bearing unproved assumption of Theorem 1.1. It is introduced by the authors (building on GLLZ21's random-function analogue) and used in the QCMA lower bound to replace high min-entropy witness distributions with bit-fixing sources. No proof is given; the paper only provides evidence via a classical analogue and a weaker result for boolean functions.
  • standard math Lemma 2.3: the union of 3 random perfect matchings on [N] is a Delta-expander with probability at least 1 - 1/N.
    Used to ensure that No instances of the Components problem are expanders with high probability. The result is cited from Goldreich's lecture notes.
  • standard math ACL11 lower bound: distinguishing an expander graph from a graph with two components requires Omega(N^{1/4}/log N) quantum queries.
    The QCMA lower bound reduces to this known query lower bound via Lemma 2.5. The paper's Lemma 2.5 derives a lower bound for the uniform L_yes/L_no distributions from ACL11 using the BBBV hybrid argument.
  • standard math Theorem 2.4 (BBBV) and Theorem 2.6 (Ambainis adversary method) are used for query lower bounds.
    Standard tools from quantum query complexity, used in Lemma 2.5 and Theorem 7.5.
  • standard math Theorem 4.2 (DFKO junta approximation) is used in the proof of Lemma 1.4, a side result showing a weaker version of Conjecture 1.2.
    This is a known Fourier-analytic result from prior literature, used only in Section 4 and not in the main conditional separation proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of QMA vs. QCMA and Pseudorandomness." pith.science (2026). https://pith.science/paper/VEZ6SHRF

@misc{pith2026241114416,
  author       = {Pith},
  title        = {Pith review of: QMA vs. QCMA and Pseudorandomness},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VEZ6SHRF}},
  note         = {Machine review of arXiv:2411.14416}
}
abstract

We study a longstanding question of Aaronson and Kuperberg on whether there exists a classical oracle separating $\mathsf{QMA}$ from $\mathsf{QCMA}$. Settling this question in either direction would yield insight into the power of quantum proofs over classical proofs. We show that such an oracle exists if a certain quantum pseudorandomness conjecture holds. Roughly speaking, the conjecture posits that quantum algorithms cannot, by making few queries, distinguish between the uniform distribution over permutations versus permutations drawn from so-called "dense" distributions. Our result can be viewed as establishing a "win-win" scenario: either there is a classical oracle separation of $\mathsf{QMA}$ from $\mathsf{QCMA}$, or there is quantum advantage in distinguishing pseudorandom distributions on permutations.

Figures

Figures reproduced from arXiv: 2411.14416 by the authors.

Figure 1
Figure 1. The algorithm M in the proof of Lemma 6.4. 31 [PITH_FULL_IMAGE:figures/full_fig_p031_1.png] view at source ↗
Figure 2
Figure 2. This figure illustrates the iterative Reconnect [PITH_FULL_IMAGE:figures/full_fig_p036_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 10 canonical work pages

  1. [1]

    The need for stru cture in quantum speedups

    [AA09] Scott Aaronson and Andris Ambainis. The need for stru cture in quantum speedups. arXiv preprint arXiv:0911.0996 ,

    arXiv

  2. [4]

    Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms

    [BSdW22] Nikhil Bansal, Makrand Sinha, and Ronald de Wolf. I nfluence in completely bounded block-multilinear forms and classical simulation of quant um algorithms. arXiv preprint arXiv:2203.00212,

    work page Pith review arXiv

  3. [8]

    Sharp hypercontrac tivity for symmetric groups and its applications

    [KL23] Peter Keevash and Noam Lifshitz. Sharp hypercontrac tivity for symmetric groups and its applications. arXiv preprint arXiv:2307.15030 ,

    arXiv

  4. [9]

    Component mixers and a hardness result for counterfeiting quan- tum money

    [Lut11] Andrew Lutomirski. Component mixers and a hardness result for counterfeiting quan- tum money. arXiv preprint arXiv:1107.0321 ,

    arXiv

  5. [10]

    Fractional certifi cates for bounded functions

    [LZ23] Shachar Lovett and Jiapeng Zhang. Fractional certifi cates for bounded functions. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Schloss- Dagstuhl-Leibniz Zentrum f¨ ur Informatik,

    work page 2023

  6. [13]

    Toward Separating QMA from QCMA with a Classical Oracle

    [Zha24] Mark Zhandry. Toward Separating QMA from QCMA with a Classical Oracle. arXiv preprint arXiv:2411.01718,

    work page Pith review arXiv

  7. [2011]

    Influences of Fourier Completely Bounded Polynomials and Classical Simulation of Quantum Algorithms

    [Gut23] Francisco Escudero Guti´ errez. Influences of Fouri er Completely Bounded Polynomials and Classical Simulation of Quantum Algorithms. arXiv preprint arXiv:2304.06713 ,

    work page Pith review arXiv

  8. [2014]

    Polynomial bounds for decoupling, with applications

    [OZ15] Ryan O’Donnell and Yu Zhao. Polynomial bounds for dec oupling, with applications. arXiv preprint arXiv:1512.01603 ,

    work page Pith review arXiv

Show all 13 references
  1. [2015]

    Random oracles and auxiliary inpu t

    44 [Unr07] Dominique Unruh. Random oracles and auxiliary inpu t. In Advances in Cryptology- CRYPTO 2007: 27th Annual International Cryptology Conference, S anta Barbara, CA, USA, August 19-23,

    2007

  2. [2018]

    Tight quantum time-space tradeoffs for function inversion

    [CGLQ20] Kai-Min Chung, Siyao Guo, Qipeng Liu, and Luowen Qi an. Tight quantum time-space tradeoffs for function inversion. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 673–684. IEEE,

    2020

  3. [2022]

    Non- uniform bounds in the random- permutation, ideal-cipher, and generic-group models

    [CDG18] Sandro Coretti, Yevgeniy Dodis, and Siyao Guo. Non- uniform bounds in the random- permutation, ideal-cipher, and generic-group models. In Advances in Cryptology– CRYPTO 2018: 38th Annual International Cryptology Conference, S anta Barbara, CA, USA, August 19–23, 2018, ...

    2018

  4. [2023]

    Aaronson-Ambainis conjecture is true for random re- strictions

    [Bha24] Sreejata Kishor Bhattacharya. Aaronson-Ambainis conjecture is true for random re- strictions. arXiv preprint arXiv:2402.13952 ,

  5. [2024]

    Oracle separati on of QMA and QCMA with bounded adaptivity

    [BK24] Shalev Ben-David and Srijita Kundu. Oracle separati on of QMA and QCMA with bounded adaptivity. arXiv preprint arXiv:2402.00298 ,

    arXiv

Pith tools

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