{"id":"aa913d5d-3040-4ebc-8b64-459c9bf7e02b","arxiv_id":"1908.02499","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Gil Kalai argues that NISQ devices are computationally weak enough that quantum supremacy and quantum error correction will both fail.","lead":"This paper argues that noisy intermediate-scale quantum devices will never achieve quantum supremacy or support quantum error correction because their outputs can be described by low-degree polynomials, a very weak computational class. It offers falsifiable predictions about near-term experiments and connects the debate to the physical Church-Turing thesis.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The paper's feasibility conclusion rests on unformalized bridging principle (B), explicitly called a 'weak link' in §3.1; even a proof of Conjecture 4 would not yield the NISQ-scale engineering predictions without explicit finite-size, finite-noise bounds.","rationale":"The reader correctly identifies Conjecture 4 as a key open step, and I agree that the generalization from boson sampling to all NISQ circuits is unproved. However, the most load-bearing gap for the paper's central feasibility claim is assertion (B), the asymptotic-to-finite engineering bridge. Even a fully proved Conjecture 4 would only show that, in the limit, NISQ output distributions are low-degree and hence classically simulable; it would not show that a 50-qubit device at current noise rates cannot be improved, nor that Schoelkopf's law will break 'now'. The paper itself flags (B) as a weak link and notes that several researchers find it unconvincing, so this is not an external objection but an internal, acknowledged limitation. The verdict should remain CONDITIONAL: the paper is a coherent, honest argument with falsifiable predictions, but its main conclusion is not established unless the missing quantitative bridge is supplied or the near-term predictions are systematically confirmed.","tokens_in":13406,"tokens_out":13795,"duration_ms":157620,"concrete_test":"For noisy boson sampling (the only case with proven theorems), extract or compute explicit finite-size bounds from Kalai–Kindler (2014): for n=20,50 and depolarizing rates t=10^-4,10^-3,10^-2, bound the total-variation distance between the exact noisy distribution and its degree-d Fourier–Hermite truncation, and the correlation with the noiseless distribution. Then compare the resulting 'robust' and 'chaotic' thresholds with currently reported gate and qubit error rates and with the n=20 qubit threshold claimed in prediction (d). If these bounds cannot be made explicit, or if the thresholds are far from current rates, assertion (B) is not supported; if the explicit thresholds match current engineering limits, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.1 states: 'Assertion (B) requires special attention and it can be regarded as both a novel and a weak link of our argument... Several researchers disagree with this part of my analysis and find it unconvincing.' The central claim that noisy quantum systems will not permit QEC or supremacy requires more than (A): it requires that asymptotic membership in LDP, a class far inside P, implies a finite-size ceiling on qubit/gate quality close to today's capabilities. The paper supplies no quantitative version of this implication. Theorems 2–3 and Conjecture 4 are statements about limits as system size grows (fixed t for Theorem 2/Conjecture 4(i); t above 1/n for Theorem 3/Conjecture 4(ii)). Predictions (a)–(d) are about explicit ranges (n up to 20–500, noise rates near current values). Without explicit bounds on the low-degree approximation error as a function of n and t—or a derivation of the claimed noise ceiling—the asymptotic results do not constrain the engineering constants. The Ramsey-number analogy in §3.1 is a heuristic, not a transfer theorem. Thus the strongest conclusion of the paper is underdetermined by its own mathematics, even if Conjecture 4 were proved.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper argues that noisy intermediate-scale quantum (NISQ) computers describe probability distributions in a very low complexity class, LDP (distributions approximated by low-degree polynomials), and that this class cannot support quantum supremacy or the quantum error-correcting codes needed for fault-tolerant quantum computation. The argument combines rigorous theorems of Kalai and Kindler for noisy boson sampling (Theorems 2 and 3), an unproved extension of those theorems to all NISQ systems (Conjecture 4), and an informal bridging principle (Assertion B) from asymptotic computational complexity to finite-size engineering limits. The paper also makes concrete predictions about near-term experiments, including failure of boson-sampling supremacy, random-circuit supremacy, and surface-code demonstrations, and proposes three general principles about noise stability, time-dependent noise, and correlated noise.","tokens_in":13706,"tokens_out":3363,"duration_ms":38671,"significance":"If the argument held, it would overturn the standard expectation that quantum error correction and quantum supremacy are achievable and would support the physical Church–Turing thesis. The paper has real strengths: the boson-sampling core is grounded in an external, parameter-free derivation by Kalai and Kindler; the predictions are specific enough to be falsified by near-term experiments; and the author is unusually explicit about which steps are conjectural and which are weak. These strengths are substantial and make the paper valuable as a research program and as a target for further investigation, even though the central claim is not established by the manuscript itself.","major_comments":[{"comment":"Conjecture 4 is the main load-bearing step: it asserts that Theorems 2 and 3, proved only for non-interacting bosons, extend to all NISQ computers and all realistic forms of noise. This is essentially identical to assertion (A), which is the central claim that NISQ distributions are low-level. The conjecture is labeled 'crucial' and is open; the cited supporting results (Gao–Duan, Bremner–Montanaro–Shepherd) do not prove it for the general circuit model. As written, the paper's main conclusion is therefore conditional on an unproved statement that largely restates the desired conclusion.","section":"§3.4, Conjecture 4"},{"comment":"The inference from asymptotic low-level complexity to finite-size engineering impossibility is unformalized. The paper itself says Assertion (B) 'can be regarded as both a novel and a weak link' and notes that researchers disagree. No quantitative version is supplied: the theorems involve limits as n grows with unspecified constants, while the predictions concern specific small ranges such as 'no more than 20 qubits' or noise rates near current values. The Ramsey-number analogy is a heuristic, not a transfer theorem. Without explicit finite-n, finite-noise bounds, or some other derivation of the claimed noise ceiling, predictions (a) and (d) do not follow from Theorems 2 and 3 even if Conjecture 4 were proved.","section":"§3.1, Assertion (B)"},{"comment":"The central class LDP and the phrase 'well approximated by low-degree polynomials' are not defined with precise quantitative content. The paper does not specify the degree bound, the approximation metric, or how the error depends on system size n and noise rate t. As a result, the claimed consequence that LDP is 'well inside bounded-depth computation' and the inference that such distributions cannot support quantum supremacy are not checkable statements. A formal definition and explicit error bounds would be needed to convert Conjecture 4 into a theorem with the stated implications.","section":"§3.2 and §3.4, definitions of LDP and 'well approximated'"}],"minor_comments":[{"comment":"The text cites 'Bremmer, Montanaro, and Shepherd' but the reference list has 'Bremner, Montanaro, and Shepherd'; the spelling should be consistent.","section":"§3.4, citation"},{"comment":"The definition of NISQ computers as circuits with at most 500 qubits is informal and is later used more broadly to include non-circuit devices such as topological qubit experiments; the scope of the term should be clarified.","section":"§2.5, Model 6"},{"comment":"The caption says the 'huge computational gap ... vanishes in the noisy versions,' but this is a visual summary of Theorems 2 and 3 for noisy boson sampling rather than a proved statement for general NISQ devices; the caption should indicate the scope.","section":"Figure 3 caption"},{"comment":"Predictions (e) and (f) state that 'every pair' of gated qubits or cat-state qubits will have positively correlated errors; this universality is not operational without specifying the gate sequence and error model, and it would be helpful to state a quantitative version.","section":"§4.3, predictions (e)–(f)"},{"comment":"Reference [11] contains the typo 'arXive:1706.03215' instead of 'arXiv:1706.03215,' and reference [16] is the arXiv version of Kalai and Kindler rather than a published version; the citation should be updated if a published version exists.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"This manuscript is a position paper whose central claims are explicitly conditional on an open conjecture and a self-acknowledged weak bridging principle. The author is transparent about these limitations, and the falsifiable predictions give the paper value as a research program. I would not reject the paper outright; it could be suitable after major revision that either proves or sharply formalizes the unproved steps, or substantially reframes the claims as a conjectural program rather than a settled argument. The main risk is that a reader could mistake the conditional structure for an established impossibility result."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe thing to know: this is the clearest, most candid statement of Gil Kalai's long-standing argument that noisy quantum systems will never yield fault-tolerant quantum computers. It is not a proof. It is a carefully assembled position paper that separates rigorous results, explicit conjectures, and an openly acknowledged weak link. If you want the strongest version of the anti-quantum-computing case, read this.\n\nThe genuinely new contribution is the low-degree polynomial (LDP) class as the computational signature of NISQ devices, plus the packaging of that claim into concrete falsifiable predictions (a)–(g), from qubit-quality ceilings to error synchronization. The paper earns credit for flagging its own limitations: Conjecture 4 is stated as open and 'crucial,' and Assertion (B) is called 'both a novel and a weak link.' That transparency lets the reader see exactly where the argument needs reinforcement.\n\nThe soft spots are the ones Kalai names. Conjecture 4 extends the rigorous boson-sampling theorems to all NISQ circuits and all realistic noise models, and nothing in the paper proves it. The step from asymptotic complexity to engineering constants is heuristic; even a proof of Conjecture 4 would not pin down the claimed qubit-quality ceiling without quantitative finite-size bounds. The Ramsey-number analogy in §3.1 is illustrative, not a transfer theorem. So the central claim is conditional, as the reader's report says.\n\nWhere I part from the reader slightly: I do not see the unproven conjecture as disqualifying. The paper is an argument, not a theorem, and it is upfront about that. Its value is in sharpening a real disagreement into testable form. The predictions are specific enough that near-term experiments can weigh in.\n\nWho this is for: anyone working on quantum error correction, quantum supremacy experiments, or the physical Church–Turing thesis. It deserves a serious referee. I would send it out, with the instruction that the referee focus on whether Conjecture 4 has any plausible route to proof and whether the bridging principle (B) can be made quantitative. A referee should not reject it for being speculative; it is openly speculative. The right verdict is: a serious, falsifiable challenge that should be engaged, not dismissed.","headline":"The strongest, most honest case against scalable quantum computing that exists, but it openly rests on an unproven conjecture and a heuristic bridge from asymptotics to engineering constants.","tokens_in":14195,"tokens_out":3016,"would_cite":true,"duration_ms":30327,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper argues that noisy quantum devices—NISQ computers—produce only low-degree-polynomial distributions and therefore can neither demonstrate quantum supremacy nor support the quantum error-correcting codes a useful quantum computer…","keywords":["quantum computing","NISQ","noise sensitivity","noise stability","low-degree polynomials","quantum error correction","quantum supremacy","boson sampling"],"falsifier":"A decisive test would be a 50–100-qubit random-circuit sampling experiment at a fixed, small noise rate whose output distribution cannot be approximated by any low-degree polynomial within small total variation distance, while repeated runs remain mutually correlated and track the noiseless distribution; that would refute Conjecture 4 and with it the argument.","tokens_in":13177,"feed_emoji":"⚛️","tokens_out":10997,"duration_ms":108733,"temperature":0.7,"pith_summary":"This paper argues that the quantum computers we can actually build are fundamentally weak: the probability distributions produced by noisy intermediate-scale quantum (NISQ) devices can be approximated by low-degree polynomials, putting them in a complexity class far below what quantum supremacy requires. If that holds, two central goals of quantum computing—demonstrating quantum supremacy and constructing the quantum error-correcting codes needed for fault tolerance—are both out of reach. The argument is computational in nature and stays within quantum mechanics; it does not rely on unproven complexity conjectures like P≠NP, though its extension from boson sampling to all NISQ circuits rests on an explicit open conjecture. The payoff is concrete and testable: near-term quantum experiments aimed at supremacy and error correction will fail, and qubit and gate quality cannot be pushed much beyond today's best.","feed_headline":"Noisy quantum computers are too weak for supremacy or error correction","feed_subtitle":"A complexity argument places NISQ outputs among low-degree polynomials, predicting near-term quantum goals will fail.","key_machinery":"The load-bearing mechanism is the Fourier–Hermite expansion of the boson-sampling output under Gaussian noise, where noise damps high-degree terms exponentially in the degree. For a constant noise rate, only low-degree terms survive, so the noisy distribution is approximated by a low-degree polynomial—the class the paper calls LDP. The same expansion shows that above a 1/n noise rate the correlation with the ideal distribution vanishes, making outputs chaotic. The paper conjectures that this noise-stability/noise-sensitivity dichotomy extends from non-interacting bosons to every NISQ circuit and every realistic form of noise, which would make LDP the universal description of robust NISQ outputs. LDP is low enough to exclude quantum supremacy yet high enough to support the rudimentary repetition-and-majority classical error correction that robust classical information uses.","core_discovery":"On the paper's own terms, the central claim is that robust output distributions of NISQ devices belong to LDP—the class of distributions approximated by low-degree polynomials—which sits strictly inside bounded-depth classical computation. Since LDP cannot host quantum supremacy and cannot encode the stable logical qubits that quantum error correction needs, noisy quantum systems cannot be scaled into useful quantum computers. The argument is anchored in two rigorous theorems for non-interacting bosons: at constant noise the noisy sampling distribution is close to its low-degree Hermite expansion, and at noise rates above 1/n the noisy distribution loses all correlation with the ideal one. The paper's open conjecture extends both theorems to all NISQ circuits and all realistic noise, and this conjecture is what carries the weight of the general conclusion. From this the paper derives three principles—noise stability of low-entropy states, inherent noisiness of time-dependent evolutions, and positively correlated noise for entangled qubits—and predicts that the effort to control k qubits will fail exponentially in k, probably already near 20 qubits.","pith_inferences":["The LDP criterion offers a practical diagnostic: any proposed quantum device whose output cannot be approximated by low-degree polynomials would already be outside the NISQ regime, so small-scale failures of low-degree approximation can serve as early warnings.","If the conjecture holds, the argument naturally extends beyond circuit hardware to analog quantum simulators and topological-qubit efforts that forgo quantum error correction, though the paper treats that extension only as plausible.","The predicted chaotic regime could be calibrated experimentally: measuring cross-run correlations of 20–30-qubit random circuits while gradually reducing noise would locate the transition where correlation with the ideal distribution vanishes, testing the conjecture before bigger devices exist.","The paper implies a general principle the author leaves implicit: robust information in nature is always classical repetition-majority coding, which would mean quantum fault tolerance cannot bootstrap from noisy physical primitives and would require an entirely different route."],"forward_implications":["Near-term goals—boson sampling with 10–20 bosons, random circuits with 50–100 qubits, and distance-5 surface codes—will fail, with difficulties already visible at the corresponding baby scales.","Qubit and gate quality cannot be improved far beyond current levels; the expected tenfold-coherence-every-three-years trend will break before the fault-tolerance threshold is reached.","At constant noise, NISQ outputs are classically simulable by low-degree polynomial approximations; at subconstant noise in a wide range, outputs become chaotic and different runs of the same experiment decorrelate.","Because achieving quantum supremacy is easier than building good quantum error-correcting codes, and NISQ devices can do neither, fault-tolerant universal quantum computation is not achievable by incremental improvements to NISQ systems.","The weak extended Church–Turing thesis is sufficient: once NISQ devices are recognized as low-level classical computing devices, their outputs cannot demonstrate computational supremacy."],"supporting_citations":[{"why":"Supplies Theorems 2 and 3, the rigorous noise-stability and noise-sensitivity results for noisy boson sampling on which the whole argument is built.","marker":"Kalai and Kindler (2014)"},{"why":"Supplies the noise-sensitivity and noise-stability theory of Boolean functions and the low-degree Fourier machinery that the boson-sampling analysis adapts.","marker":"Benjamini, Kalai, and Schramm (1999)"},{"why":"Defines boson sampling and gives the hardness argument for the noiseless case, the quantum-supremacy baseline the paper claims noisy devices cannot reach.","marker":"Aaronson and Arkhipov (2013)"},{"why":"Provides the canonical efficient quantum algorithm whose existence motivates the need for quantum error correction and makes the paper's failure claim consequential.","marker":"Shor (1994)"},{"why":"States the threshold theorem, showing that low enough noise would enable fault-tolerant quantum computing, which the paper argues is unreachable because noise cannot be lowered enough.","marker":"Aharonov and Ben-Or (1997)"},{"why":"Gives evidence that noisy quantum circuits are classically simulable, supporting the conjectured extension of the boson-sampling results.","marker":"Gao and Duan (2018)"},{"why":"Shows sparse noisy commuting quantum computations remain classically simulable, adding support for the low-complexity claim.","marker":"Bremmer, Montanaro, and Shepherd (2017)"}],"fun_headline_variants":["Noisy quantum computers can't achieve supremacy or error correction","Quantum supremacy impossible for noisy intermediate-scale devices","Complexity proof: NISQ outputs are low-degree polynomials, too weak","Near-term quantum computers can't scale: noise defeats error correction","Why quantum computers will fail: they are only low-degree polynomials"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument stands on Conjecture 4: the two theorems proved for noisy non-interacting bosons also hold for every NISQ circuit and every realistic noise model, so that any fixed-noise NISQ output is low-degree-polynomial approximable and subconstant-noise outputs are chaotic.","fun_headline_variants_meta":{"raw":{"variants":["Noisy quantum computers can't achieve supremacy or error correction","Quantum supremacy impossible for noisy intermediate-scale devices","Complexity proof: NISQ outputs are low-degree polynomials, too weak","Near-term quantum computers can't scale: noise defeats error correction","Why quantum computers will fail: they are only low-degree polynomials"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000286,"raw_usage":{"total_tokens":1623,"prompt_tokens":824,"completion_tokens":799,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":440,"completion_tokens_details":{"reasoning_tokens":715}},"tokens_in":440,"tokens_out":799,"duration_ms":9072,"temperature":1.0,"reasoning_tokens":715,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:41:50.902936+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A decisive test would be a 50–100-qubit random-circuit sampling experiment at a fixed, small noise rate whose output distribution cannot be approximated by any low-degree polynomial within small total variation distance, while repeated runs remain mutually correlated and track the noiseless distribution; that would refute Conjecture 4 and with it the argument.","supporting_citations":[],"review_version":1}