{"id":"dc8fa1af-9d76-4ca9-b42e-4f23bb165485","arxiv_id":"2411.14416","paper_version":4,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Assuming a quantum pseudorandomness conjecture for dense permutation distributions, there exists a classical oracle relative to which QMA differs from QCMA.","lead":"This paper shows that if a certain conjecture about quantum algorithms and random permutations is true, then there is a classical oracle that separates the complexity classes QMA and QCMA, a long-open question in quantum complexity. The result creates a win-win scenario: either the separation exists, or quantum computers have an advantage in distinguishing pseudorandom permutations.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Conditional proof of Theorem 1.1 appears sound; the load-bearing risk is the unproved Conjecture 1.5, with a separate non-central gap in the Section 7.4 independence argument.","rationale":"The reader's weakest assumption is Conjecture 1.5, and I agree that this is the only load-bearing risk in the central conditional claim. I did not find an internal inconsistency in the proof of Theorem 1.1: the decomposition lemma and the reduction appear valid, and the reconnect lemma's regularity argument checks out. I also verified the Section 7.4 concern is real; it is a genuine gap in a secondary claim but should not change the CONDITIONAL verdict on the main theorem. The concrete test I propose targets the conjecture's minimal nontrivial regime, which would either reveal a counterexample or provide the missing empirical evidence. Therefore the verdict remains UNCHANGED.","tokens_in":37381,"tokens_out":28946,"duration_ms":306971,"concrete_test":"Search for a counterexample to Conjecture 1.5 in its minimal nontrivial regime: for N = 8, 12, 16 and delta = 0.25, 0.1, generate delta-dense permutation distributions with delta-dense inverse (for example, uniform permutations conditioned on a random 2-cycle or 3-cycle), and compute the optimal two-query quantum distinguishing bias between such a source and the uniform permutation by solving the standard semidefinite program for two-query quantum query algorithms. If the bias exceeds C * delta * log N for a reasonable absolute constant C in this regime, the quantitative form of Conjecture 1.5 is called into question; if no violation appears, the conjecture survives its first nontrivial test.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main theorem is a conditional implication. I checked the chain in Sections 3-6 for internal errors: the min-entropy decomposition (Lemma 3.3), the reduction from (k,delta)-dense to delta-dense permutation tuples (Lemma 4.5), the transformation from a QCMA verifier to a few-query distinguisher between L^rho_yes and L^rho_no, and the reconnect/uniformity argument (Lemma 6.6) all appear to cohere. The decisive weakness is therefore the conjecture itself: Conjecture 1.5 asserts a poly(T, log N)-query bound for all dense permutation tuples with dense inverse, but the paper supplies no proof and only analogous evidence (the classical [CDG18] claim and the boolean-function Lemma 1.4). If the conjecture fails in the parameter regime used (delta = 1/poly(T, log N), T = N^{o(1)}), then the separation collapses. Separately, the unconditional interactive-game proof in Section 7.4 has a real gap: Claim 8 says that for a fresh r_i, F(r_i,.) is independent of previous rounds, but all proper sub-oracles share the same hidden partition S; queries to earlier F(r_j,.) leak information about S, so the fresh sub-oracle is not independent of the adversary's prior state. This invalidates the claimed unconditional separation as written, though it does not affect Theorem 1.1.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":37590,"tokens_out":6527,"duration_ms":69604,"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":[{"comment":"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.","section":"Section 7.4, Claim 8"},{"comment":"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.","section":"Section 7.4, Theorem 7.5"}],"minor_comments":[{"comment":"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.","section":"Abstract and Introduction"},{"comment":"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.","section":"Section 2.3, Lemma 2.5"},{"comment":"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.","section":"Section 7.2"},{"comment":"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.","section":"Section 7.5"}],"recommendation":"major_revision","confidential_remarks":"The conditional main theorem is a strong and carefully argued contribution, and the conditional part of the paper could be publishable after revision. The unconditional Section 7 is currently not sound as written because of the independence gap in Claim 8; this needs either a repair or a clear downgrade to a conditional/sketch status. The paper would also benefit from a more prominent statement that Conjecture 1.5 is unproved and that the central result is therefore conditional on a new, strong pseudorandomness assumption."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe headline: this paper gives a conditional classical-oracle separation of QMA from QCMA, assuming a quantum pseudorandomness conjecture for permutations. The conditional proof in Sections 3–6 looks sound to me. The separate unconditional interactive-game section has a real gap that should be fixed.\n\nWhat is new: prior separations required quantum oracles, distributional oracles, or restricted verifiers. Here, for the first time, a standard classical oracle separation is shown under a plausible conjecture, with no restrictions on the verifier. The raw-permutation model, the min-entropy decomposition with both forward and inverse denseness, and the planting reduction are genuinely useful and clearly presented. The paper is also honest: it states the conjecture explicitly and gives a partial result (Lemma 1.4) for very few queries, plus a clean treatment of the known classical analogue.\n\nSoft spots, in proportion: the main theorem is only as good as Conjecture 1.5. The conjecture asserts a poly(T, log N) bound for all dense permutation tuples with dense inverse; the authors provide evidence but no proof. If the conjecture fails in the parameter regime used (delta = 1/poly(T), T = N^{o(1)}), the separation collapses. That is a load-bearing assumption, but the paper clearly labels it as a conjecture.\n\nA more concrete problem: Section 7.4's Claim 8 says that a fresh oracle F(r_i,.) is independent of previous rounds. This is not true. All proper sub-oracles share the same hidden partition S, and queries to earlier sub-oracles leak information about S. The adversary's state is therefore correlated with the fresh sub-oracle, so the sequential-repetition soundness argument does not go through as written. This gap affects the claimed unconditional interactive-game separation and the simplified proof of the distributional oracle separation; it does not affect Theorem 1.1.\n\nWho this is for: researchers working on quantum complexity oracle separations; also cryptographers interested in the pseudorandomness conjecture. The paper deserves a serious referee. I would recommend sending it to a top theory venue, with a request that the authors either fix the independence claim or restrict the unconditional section to what survives.","headline":"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.","tokens_in":38200,"tokens_out":2746,"would_cite":true,"duration_ms":26469,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","68Q17"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"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.","keywords":["QMA vs QCMA","classical oracle separation","quantum pseudorandomness","dense random permutations","min-entropy decomposition","quantum query algorithms","graph oracle","interactive oracle games"],"falsifier":"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.","tokens_in":37054,"feed_emoji":"🔀","tokens_out":7629,"duration_ms":71249,"temperature":0.7,"pith_summary":"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.","feed_headline":"Classical-oracle QMA vs QCMA gap follows from one permutation bet","feed_subtitle":"The result turns a long-open question into a conditional theorem with a cryptographic byproduct.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Poses the original question of whether a classical oracle separates QMA from QCMA, which this paper targets.","marker":"[AK07]"},{"why":"Supplies the Components problem and the high-level QCMA lower-bound strategy that this paper adapts.","marker":"[NN23]"},{"why":"Provides the quantum query lower bound for distinguishing expander graphs from disconnected ones that the reduction contradicts.","marker":"[ACL11]"},{"why":"Establishes the classical probabilistic-query analogue of the permutation pseudorandomness conjecture and gives the min-entropy decomposition lemma adapted in Section 3.","marker":"[CDG18]"},{"why":"Provides the bit-fixing/witness-structure approach that, combined with [NN23], yields the proof structure here.","marker":"[LLPY24]"},{"why":"Formulated the boolean-function quantum pseudorandomness conjecture and connected it to the Aaronson-Ambainis conjecture, giving context for Conjecture 1.2.","marker":"[GLLZ21]"}],"fun_headline_variants":["QMA vs QCMA separation hinges on quantum permutation bet","Conditional QMA–QCMA separation from one pseudorandomness bet","Quantum proof power gap tied to permutation distinguishing bet","Classical oracle gap between QMA and QCMA if permutation bet holds","One permutation bet decides classical-oracle QMA vs QCMA"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["QMA vs QCMA separation hinges on quantum permutation bet","Conditional QMA–QCMA separation from one pseudorandomness bet","Quantum proof power gap tied to permutation distinguishing bet","Classical oracle gap between QMA and QCMA if permutation bet holds","One permutation bet decides classical-oracle QMA vs QCMA"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000781,"raw_usage":{"total_tokens":3389,"prompt_tokens":822,"completion_tokens":2567,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":438,"completion_tokens_details":{"reasoning_tokens":2480}},"tokens_in":438,"tokens_out":2567,"duration_ms":16680,"temperature":1.0,"reasoning_tokens":2480,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:14:54.858670+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}