{"id":"bcc3adf7-41b9-4b5b-b34a-9fe100c788b0","arxiv_id":"2508.05720","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Assuming quantum computers are strictly more powerful than classical ones, the problem of deciding whether a given quantum circuit beats a specific classical simulation heuristic is solvable by quantum computers but not by classical computers.","lead":"This paper proposes five tests for deciding when a quantum advantage is real and proves that, under a widely believed assumption, spotting which circuits beat the best-known classical simulator is itself a quantum-hard task. Generalists should care because it suggests the space of genuine quantum advantages is larger than classical theory can map.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"NO-case separation uses an unjustified uniform bound over inputs; requires a second-moment averaging argument.","rationale":"The reader identified Lemma 1 as the weakest assumption. I independently checked the Weingarten calculation in Lemma 1 and found the contraction constant 2/5 to be correct: for a single-qubit Pauli under a Haar-random two-qubit gate, the average squared weight-1 projection is 2/5 of the original norm, and the layer-wise argument in (D.17)-(D.25) is valid. The Markov concentration step is also sufficient for the heuristic bound. Thus the reader's main concern does not actually land.\n\nHowever, a more significant gap appears in the NO-case separation. The proof requires that with high probability over U, the true expectation <x|U†Z1U|x> is small for all inputs x simultaneously. An approximate 2-design only controls moments for each fixed x; the union bound over exponentially many x fails. This is a genuine logical gap in the written proof. It is repairable via a second-moment average over x, which suffices for the 'no advantage' definition because only a 2/3 fraction of inputs need small error. Therefore the central claim is likely correct, but the manuscript should be revised to replace the uniform bound with the average argument.\n\nGiven this, the CONDITIONAL verdict remains appropriate: the theorem is probably sound but the proof needs a concrete fix. I would not change the reader's verdict, hence UNCHANGED.","tokens_in":35871,"tokens_out":35424,"duration_ms":344825,"concrete_test":"Verify the amended NO-case proof: prove that with probability ≥1−1/poly(n) over the random circuit U, (1/2^n)Σ_x <x|U†Z1U|x>^2 ≤ poly(n)/2^n, using only the approximate-2-design property. Then show the fraction of x with |<x|U†Z1U|x>| ≥ 1/3 is ≤ 9/poly(n); if this chain of inequalities holds, the written gap is repairable and the central theorem stands. If it fails, the reduction can output a non-promise instance in the NO case and the classical-hardness argument collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The classical-hardness proof (Appendix D) has a gap in the NO case. After constructing C_new, the paper asserts (D.6–D.7, D.40) that because U is an 1/poly(n)-approximate unitary 2-design, |<x|U†Z1U|x>| ≤ 1/poly(n) with high probability for every input x. This does not follow. A 2-design controls the first two moments of Y_x = <x|U†Z1U|x> for each fixed x; Chebyshev gives P(|Y_x| > 1/poly(n)) = O(poly(n)/2^n). The union bound over all 2^n x gives failure probability O(poly(n)), not small, so the uniform 'for all x' statement is unsupported. The NO-case separation (needed to conclude D(C_new)=0 when C? is a NO instance) is therefore not rigorously established as written. The gap is repairable: the 2-design property implies E_U[(1/2^n)Σ_x |Y_x|^2] ≈ 1/2^n, so by Markov over U and then over x, with probability ≥1-1/poly(n) the fraction of inputs with |Y_x| ≥ 1/3 is ≤ 9/poly(n) < 1/3, which is all the definition of 'no advantage' requires. I also checked the reader's flagged Lemma 1: the 2/5 contraction constant is correct (Weingarten gives the claimed factor), so that is not the main weakness.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This perspective paper proposes five keystone properties for assessing quantum advantages (predictability, typicality, robustness, verifiability, usefulness), surveys four realms of quantum advantage, and discusses empirical and conceptual forms of future advantage. Its technical center is Theorem 4 (Appendix D), formalizing the informal Theorem 1: for the fixed classical heuristic LowWeightPauliProp with k=1, the promise problem DetectingQuantumAdvantage—decide whether a given circuit disagrees with the heuristic by at least 1/3 on at least 2/3 of inputs—is in BQP and, assuming BPP≠BQP, is not in BPP. The proof constructs an amplified BQP instance, appends a random circuit U with a controlled inverse, and shows that for YES instances the true expectation of Z1 is essentially ±1 while the heuristic estimate decays as (2/5)^L; for NO instances the true expectation is pseudo-random while the heuristic remains tiny. The paper also contains self-contained material on noisy quantum sensing (Appendix B) and a survey of classical simulation heuristics (Appendix C).","tokens_in":36224,"tokens_out":15333,"duration_ms":197548,"significance":"If the main theorem is correct after repair, it is a substantive meta-complexity-style result: detecting advantage over a specific classical simulation heuristic is itself quantumly easy and classically hard, conditional on BPP≠BQP. The paper is explicit that this is a conditional separation and that it concerns a promise decision problem, not a property of every individual circuit. The reduction is well structured and largely elementary. I checked the key contraction estimate in Lemma 1: the claimed 2/5 factor per random two-qubit gate layer follows from the Weingarten calculation in Eqs. (D.22)–(D.25), so the reader's flagged concern about Lemma 1 is not the main weakness. The broader ‘unpredictability’ rhetoric in Section IV.C should be read with the formal theorem's caveats, but as a conditional separation the result is interesting and appropriate for a perspective aiming to connect complexity theory with the quantum-advantage debate.","major_comments":[{"comment":"The NO-case separation is not rigorously established as written. The text asserts that because U is an approximate unitary 2-design, |<x|U†Z1U|x>| ≤ 1/poly(n) with high probability, and then concludes that this holds for any input bitstring x. This does not follow: for a fixed x, a 2-design controls the first two moments of Y_x = <x|U†Z1U|x>, giving P(|Y_x| > 1/poly(n)) = O(poly(n)/2^n); a union bound over all 2^n inputs yields only constant failure probability, not a high-probability uniform bound. Inequality (D.40) relies on this uniform bound, and the NO case collapses without it. The gap is repairable: the 2-design property gives E_U[(1/2^n)Σ_x |Y_x|^2] ≈ O(1/2^n). By Markov over U, with probability at least 1−1/poly(n), the fraction of x with |Y_x| ≥ 1/3 is at most 9/poly(n) < 1/3, which is all that Definition 7's ‘no advantage’ condition requires. The proof should be revised to use","section":"Appendix D, Step 3 (NO case), Eqs. (D.6)–(D.7) and (D.40)"}],"minor_comments":[{"comment":"The Weingarten calculation is correct, but the step is quite terse. A short derivation or an explicit citation to the precise second-moment formula for Haar-random two-qubit unitaries would make the lemma easier to verify.","section":"Eq. (D.22)"},{"comment":"The paper states that depth L linear in n gives an ε=O(1/2^n)-approximate unitary 2-design, citing [19, 132, 133]. Since the proof later chooses L > 6(n+mℓ+1), please state explicitly the metric for the approximation and the required depth dependence (including constants), so that the choice of L is visibly compatible with the cited results.","section":"Appendix D, Step 1"},{"comment":"The informal theorem and the discussion of ‘unpredictable quantum advantages’ should be careful to say that the formal result concerns a promise decision problem about a fixed classical heuristic (LowWeightPauliProp with k=1), not an intrinsic property of every quantum circuit or all conceivable classical methods. The current wording is acceptable for a perspective but could mislead readers outside complexity theory.","section":"Theorem 1 and Section IV.C"},{"comment":"The BQP upper bound assumes that LowWeightPauliProp with k=1 can be evaluated classically in polynomial time for arbitrary polynomial-size circuits. This is true but should be stated explicitly, since Appendix C's runtime theorem is stated only for locally scrambling circuit ensembles.","section":"Appendix D, Quantumly Easy part"},{"comment":"The sampling step uses the 2/3 versus 1/3 gap correctly, but the presentation would be clearer if it explicitly noted that the promise excludes the intermediate regime and that the Chernoff bound applies to the estimated fraction.","section":"Definition 7 and Step 4 of the BQP algorithm"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is by leading authors and the perspective is likely to attract attention. The main formal claim is defensible, but the NO-case proof has a genuine gap that is localized and repairable; the repair I outline uses only a second-moment average over inputs. I also want the editor to note that the paper's broad interpretive claims in Section IV.C are stronger than the formal theorem, which should be tempered during revision. The self-citations are extensive but generally standard and relevant. Overall, a major revision with the NO-case argument fixed would likely make the paper suitable for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the useful part: the DetectingQuantumAdvantage theorem. It's a new conditional separation — in BQP, not in BPP unless BPP=BQP — for the problem of deciding whether a circuit beats the low-weight Pauli heuristic. The reduction is standard meta-complexity but the construction is neat: amplify a BQP circuit, randomize with a 2-design, and use the heuristic's decay to make YES/NO distinguishable. The BQP upper bound is straightforward sampling; the classical hardness direction is the right idea.\n\nThe five-keystone framework (predictability, typicality, robustness, verifiability, usefulness) is a reasonable synthesis of existing evaluation criteria, not a deep new paradigm. The paper is mostly perspective, and the theorem is the actual contribution.\n\nNow the soft spots. The stress-test note is right: the NO-case proof asserts that for every x, |<x|U†Z1U|x>| ≤ 1/poly(n) with high probability over U, and that does not follow from the 2-design property alone. Chebyshev plus union bound over all 2^n x gives failure probability O(poly(n)), not small. This is a gap in the written proof. It is also clearly repairable: the second moment over x concentrates, so a Markov argument shows the fraction of inputs with large |Y_x| is small, which is all Definition 7 requires. The authors should supply that argument.\n\nThe reader's flagged Lemma 1 — the 2/5 contraction per layer — I checked and it's fine; the Weingarten factor is correct, and the proof gives enough detail. Not the main weakness.\n\nThe abstract overstates the result: 'inherently unpredictable' without mentioning the condition BPP≠BQP and the fact that the result is for a specific classical heuristic. That is worth tempering.\n\nWho is this for? Readers thinking about how to evaluate quantum advantage claims and meta-complexity people. It's a perspective, so it won't be everyone's cup of tea. But the theorem deserves a proper referee. I'd send it to review and ask for the NO-case fix and abstract revision.","headline":"A perspective with a genuinely new conditional meta-complexity theorem; the main gap in the written proof is real but fixable, and the abstract overstates it.","tokens_in":36678,"tokens_out":2125,"would_cite":false,"duration_ms":24836,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P68"],"pacs":["03.67.-a"],"model":"deepseek-v4-flash","headline":"This paper proves that some genuine quantum advantages cannot be detected by any efficient classical algorithm, assuming quantum computers are truly more powerful than classical ones, and that the act of predicting a quantum advantage is it","keywords":["quantum advantage","meta-complexity","BQP","BPP","Pauli propagation","classical simulation heuristics","quantum sensing","verifiability"],"falsifier":"Sample many instances of an L-layer random two-qubit brickwork circuit, run LowWeightPauliProp with k=1 on the observable Z_1, and record the squared Frobenius norm of the truncated backward-evolved operator; if its average over circuits deviates from (2/5)^L or if the fraction of circuits with norm above $2^{{-L/2}}$ does not decay exponentially, Lemma 1 fails. Also check directly whether the omitted high-weight Pauli components contribute significantly to the true expectation value for the constructed circuit C_new on NO instances.","tokens_in":35799,"feed_emoji":"⚛️","tokens_out":5685,"duration_ms":68302,"temperature":0.7,"pith_summary":"The paper is a perspective on how to recognize quantum advantages, organized around five keystone properties—predictability, typicality, robustness, verifiability, and usefulness—and a survey of advantages in computation, learning and sensing, cryptography and communication, and memory. Its main theorem states that, assuming BPP≠BQP, the problem of deciding whether a given quantum circuit beats a standard classical simulation heuristic is itself in BQP but not in BPP. That means some genuine quantum advantages cannot be certified by classical computation; the act of predicting quantum advantage requires quantum computation. The authors use this to argue that the full landscape of quantum advantage is richer and more surprising than current classical theory can foresee.","feed_headline":"Predicting quantum advantage is itself a quantum task","feed_subtitle":"A proof: deciding whether a circuit beats a classical simulator is hard for classical computers, assuming quantum power is real.","key_machinery":"The low-weight Pauli propagation heuristic is the classical baseline: it evolves an observable backward through the circuit and truncates to Pauli operators of weight at most 1. The proof's other ingredients are random two-qubit circuit layers that form approximate unitary 2-designs, and Lemma 1, which says that one layer of backward propagation shrinks the expected squared Frobenius norm of the truncated observable by exactly 2/5, so after enough layers the heuristic produces exponentially small outputs. A coherent majority vote of the BQP circuit controls whether the random unitary is applied or cancelled, creating the YES/NO separation on which the hardness reduction rests.","core_discovery":"The paper's central proof result is that the decision problem DetectingQuantumAdvantage—which asks whether a given quantum circuit's output statistics differ from the predictions of the low-weight Pauli propagation heuristic on a typical input—is solvable in quantum polynomial time but not in classical polynomial time unless BPP=BQP. In other words, if quantum computers are genuinely more powerful than classical ones, then the task of telling a genuine quantum advantage from a pseudo-advantage is itself a problem with a quantum advantage. The proof takes any BQP decision problem, amplifies it by a coherent majority vote, and splices it into a random scrambling circuit so that YES instances m","pith_inferences":["Editorial extension: Lemma 1's contraction constant 2/5 should be measurable in small random brickwork circuits; if its decay rate departs from (2/5)^L, the theorem's gap would need a different heuristic analysis.","Editorial extension: If detecting advantage is hard for every classical heuristic, then quantum computers may be needed to audit classical simulation software, shaping benchmarking protocols for near-term quantum processors.","Editorial extension: The theorem suggests a hierarchy of meta-advantages—achieving a quantum advantage can be easier than recognizing or verifying one—so 'useful quantum utility' claims may require quantum-assisted verification.","Editorial extension: Analogous detection problems for other quantum resources, such as quantum memory in learning or entanglement in communication, might exhibit similar classical unpredictability, extending the argument beyond computation."],"forward_implications":["Under BPP≠BQP, no polynomial-time classical algorithm can reliably certify absence of quantum advantage relative to a heuristic whose failure set is unknown; the certification problem itself is quantum.","A quantum computer can detect such an advantage by sampling a constant number of random inputs, comparing measured output probabilities with the heuristic's predictions, and applying a Chernoff bound.","The meta-complexity message extends beyond LowWeightPauliProp: any classical heuristic with unknown failure set inherits the hardness, so claims that a circuit is classically simulable should be treated as conjectural unless backed by quantum sampling.","For sensing, entanglement-based Heisenberg-limited sensitivity is not robust to generic local noise; separable strategies achieve the optimal scaling, meaning robustness must be part of any claimed sensing advantage.","The five keystone properties give a checklist for evaluating whether a proposed quantum advantage is likely to survive noise, apply to typical instances, and deliver practical value."],"supporting_citations":[{"why":"Supplies the rigorous guarantee that low-weight Pauli propagation is efficient and accurate for locally scrambling circuits, making it the concrete classical heuristic targeted by DetectingQuantumAdvantage.","marker":"[40]"},{"why":"Establishes that random quantum circuits of polynomial depth form approximate 2-designs, used in the proof to make the NO-instance true expectation small.","marker":"[132]"},{"why":"Extends the design property to approximate polynomial designs, supporting the use of random two-qubit layers throughout the construction.","marker":"[133]"},{"why":"The body of classical simulation work that low-weight Pauli propagation generalizes, defining the family of heuristics the paper targets.","marker":"[33-41]"},{"why":"Cited for random unitaries in low depth, providing a design construction consistent with the polynomial-depth random circuits used in the proof.","marker":"[19]"},{"why":"Supplies the no-go result for entanglement-enhanced sensing under generic noise, which underpins Theorem 2 and the robustness discussion.","marker":"[52]"},{"why":"Provides the exponential quantum communication advantage example used in Puzzle 3 to illustrate genuine, non-computational quantum advantages.","marker":"[8]"},{"why":"Exemplifies how apparent quantum advantages can dissolve under clever classical algorithms, motivating the need for detecting genuine vs pseudo advantages.","marker":"[5]"}],"fun_headline_variants":["Proving quantum advantage is a quantum advantage","Detecting quantum power needs quantum power","The proof that spotting quantum wins needs quantum","Quantum advantage detection is quantum-hard","When seeing quantum advantage requires quantum"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The proof assumes that one step of weight-1 Pauli propagation shrinks the expected squared Frobenius norm of the observable by exactly 2/5 per random two-qubit layer; if that constant is wrong or does not concentrate well enough, the heuristic's outputs on the constructed circuits would not be uniformly small and the YES/NO separation used to prove classical hardness collapses.","fun_headline_variants_meta":{"raw":{"variants":["Proving quantum advantage is a quantum advantage","Detecting quantum power needs quantum power","The proof that spotting quantum wins needs quantum","Quantum advantage detection is quantum-hard","When seeing quantum advantage requires quantum"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000116,"raw_usage":{"total_tokens":876,"prompt_tokens":675,"completion_tokens":201,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":419,"completion_tokens_details":{"reasoning_tokens":154}},"tokens_in":419,"tokens_out":201,"duration_ms":2864,"temperature":1.0,"reasoning_tokens":154,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T23:21:28.364568+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Sample many instances of an L-layer random two-qubit brickwork circuit, run LowWeightPauliProp with k=1 on the observable Z_1, and record the squared Frobenius norm of the truncated backward-evolved operator; if its average over circuits deviates from (2/5)^L or if the fraction of circuits with norm above $2^{{-L/2}}$ does not decay exponentially, Lemma 1 fails. Also check directly whether the omitted high-weight Pauli components contribute significantly to the true expectation value for the constructed circuit C_new on NO instances.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Extends the design property to approximate polynomial designs, supporting the use of random two-qubit layers throughout the construction."}],"review_version":1}