Pith. sign in

REVIEW 3 major objections 5 minor 30 references

The Argument against Quantum Computers

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read 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…

desk verdict 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. read the letter →

arxiv 1908.02499 v1 pith:GPU22I74 submitted 2019-08-07 quant-ph cs.CCmath-phmath.MP

Gil Kalai This is my paper · ORCID
classification quant-phcs.CCmath-phmath.MP
keywords quantumcomputingNISQnoisesensitivitystabilitylow-degreepolynomialserrorcorrectionsupremacybosonsampling
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 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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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

3 major / 5 minor

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.

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 (3)
  1. [§3.4, Conjecture 4] 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.
  2. [§3.1, Assertion (B)] 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.
  3. [§3.2 and §3.4, definitions of LDP and 'well approximated'] 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.
minor comments (5)
  1. [§3.4, citation] The text cites 'Bremmer, Montanaro, and Shepherd' but the reference list has 'Bremner, Montanaro, and Shepherd'; the spelling should be consistent.
  2. [§2.5, Model 6] 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.
  3. [Figure 3 caption] 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.
  4. [§4.3, predictions (e)–(f)] 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.
  5. [References] 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.

Circularity Check

1 steps flagged · score 4.0 of 10

Central premise that NISQ outputs are LDP is stipulated by Conjecture 4, which the paper itself calls 'crucial' to assertion (A); boson theorems give independent content but do not cover general circuits.

  1. self definitional [Section 3.4, Conjecture 4; Section 3.1, Assertion (A)]
    "The following open-ended mathematical conjecture is crucial to part (A) of our analysis, as well as to predictions (b)–(d) in Section 3.2. Conjecture 4: Theorems 2 and 3 both extend to all NISQ computers (in particular, to noisy quantum circuits) and to all realistic forms of noise. (i) When the noise level is constant, distributions given by NISQ systems are well approximated by their low-degree Fourier expansion. ... Assertion (A) of our argument is supported by Conjecture 4(i)."

    Assertion (A) in Section 3.1 defines the load-bearing premise: 'Probability distributions described (robustly) by NISQ devices can be described by low-degree polynomials (LDP).' Conjecture 4(i) is this same statement for constant noise, and the paper says it supports (A). The central claim that NISQ devices occupy the very low-level class LDP is therefore not derived from the proved boson theorems; it is assumed as an open postulate equivalent to the premise. Predictions (b)–(d) are immediate consequences of Conjecture 4, so those 'predictions' are paraphrases of the conjecture rather than independent outputs.

full rationale

Theorems 2 and 3 cite Kalai–Kindler (2014), a self-citation, but under the review rules this is real evidence: the boson-sampling theorem is a parameter-free mathematical statement with stated assumptions that do not include the target conclusion. The circular burden is instead the structure of Conjecture 4: it extends the boson results to all NISQ devices by fiat, and the paper's own text says this conjecture is 'crucial' to assertion (A) and to predictions (b)–(d). That makes the central identification of NISQ outputs with LDP an assumed premise, not a derived result. The paper is transparent about the weakness: Section 3.1 calls assertion (B) 'both a novel and a weak link of our argument' and notes that 'several researchers disagree.' That admission is a limitation in underdetermination, not an additional circular step, and it is weighed here. No fitted parameters are hidden, and the boson results give genuine independent content, so a score of 4 reflects partial circularity in the bridge from bosons to general NISQ circuits rather than a fully forced derivation.

Assumptions & free parameters 0 free parameters · 4 assumptions · 2 invented entities

The paper rigorously proves results only for non-interacting boson sampling, taken from Kalai-Kindler. The generalization to all NISQ circuits is a conjecture, and the step from asymptotic complexity to engineering limits is an acknowledged weak assertion. No numerical parameters are fitted to data.

assumptions (4)
  • ad hoc to paper Conjecture 4: Theorems 2 and 3 extend to all NISQ computers and all realistic forms of noise.
    Stateed in Section 3.4 as 'crucial' to assertion (A); it extends the proven boson-sampling theorems to arbitrary noisy quantum circuits without proof.
  • ad hoc to paper Assertion (B): Asymptotically low-level computational devices cannot lead to superior computation.
    Described in Section 3.1 as 'both a novel and a weak link of our argument'; it transfers asymptotic complexity limits to intermediate-scale engineering with unspecified constants.
  • domain assumption Noise model: every qubit is corrupted with probability t per cycle and every gate is t-imperfect.
    Model 5 in Section 2.4 defines the noise model; the rigorous boson results use Gaussian noise, and Conjecture 4 assumes all realistic noise behaves similarly.
  • domain assumption Weak Extended Church-Turing thesis (WECTT): no classical device can demonstrate computational supremacy.
    Invoked in Section 3.7 to rule out quantum supremacy once NISQ devices are shown to be P-devices; the thesis is treated as a widely accepted background premise.
invented entities (2)
  • LDP (low-degree polynomial distributions) computational class
    purpose: A complexity class proposed to characterize probability distributions robustly produced by NISQ devices, used to argue they are too weak for quantum error correction or supremacy.
    Defined in Section 3.1 as a formal class; it is a mathematical construct rather than a directly measurable entity, though the paper's predictions give indirect testable handles.
  • Error synchronization independent evidence
    purpose: A predicted phenomenon where errors on many qubits become positively correlated, degrading error-correction performance beyond what independent-noise models predict.
    Predictions (e), (f), and (g) in Section 4.3 give concrete, measurable consequences: large positive correlations of gate errors and cat-state errors, and strong error-synchronization in surface-code experiments.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Argument against Quantum Computers." pith.science (2026). https://pith.science/paper/GPU22I74

@misc{pith2026190802499,
  author       = {Pith},
  title        = {Pith review of: The Argument against Quantum Computers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GPU22I74}},
  note         = {Machine review of arXiv:1908.02499}
}
read the original abstract

We give a computational complexity argument against the feasibility of quantum computers. We identify a very low complexity class of probability distributions described by noisy intermediate-scale quantum computers, and explain why it will allow neither good-quality quantum error-correction nor a demonstration of "quantum supremacy." Some general principles governing the behavior of noisy quantum systems are derived. Our work supports the "physical Church thesis" studied by Pitowsky (1990) and follows his vision of using abstract ideas about computation to study the performance of actual physical computers.

Figures

Figures reproduced from arXiv: 1908.02499 by the authors.

Figure 1
Figure 1. The (conjectured) view of some main computational complexity classes. The red ellipse [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. NISQ circuits are computationally very weak and therefore unlikely to create quantum error [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. The huge computational gap (left) between boson sampling (purple) and fermion sampling [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Low-entropy quantum states give probability distributions described by low degree polyno [PITH_FULL_IMAGE:figures/full_fig_p015_4.png]
Figure 5
Figure 5. Figure 5: Human imagination allows for a cat with an unusual geometry. Drawing by Netta Kasher [PITH_FULL_IMAGE:figures/full_fig_p018_5.png]
Figure 6
Figure 6. Figure 6: Itamar Pitowsky around 1985 way, in the work of Jeff Kahn and myself where we disproved Borsuk’s conjecture (Kahn and Kalai 1993). Over the years, Itamar and I became interested in Arrow’s impossibility theorem (Arrow 1950), which Itamar regarded as a major 20th-centur…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 26 canonical work pages

  1. [1]

    Aaronson and A

    S. Aaronson and A. Arkhipov, The computational complexity of linear optics,Theory of Computing4 (2013), 143–252

    work page 2013

  2. [2]

    Aharonov and M

    D. Aharonov and M. Ben-Or, Fault-tolerant quantum computation with constant error, STOC ’97, ACM, New York, 1999, pp. 176–188

    work page 1999

  3. [3]

    Arrow, A difficulty in the theory of social welfare, Journal of Political Economy 58 (1950) , 328–346

    K. Arrow, A difficulty in the theory of social welfare, Journal of Political Economy 58 (1950) , 328–346

    work page 1950

  4. [4]

    Barkai, and S

    N. Barkai, and S. Leibler. Robustness in simple biochemical networks, Nature, 387 (1997), 913

    work page 1997

  5. [5]

    Benjamini, G

    I. Benjamini, G. Kalai, and O. Schramm, Noise sensitivity of Boolean functions and applications to perco- lation, Publications Math´ematiques de l’Institut des Hautes ´Etudes Scientifiques 90 (1999), 5–43

    work page 1999

  6. [6]

    M. J. Bremner, A. Montanaro, and D. J. Shepherd, Achieving quantum supremacy with sparse and noisy commuting quantum computations, Quantum 1, 8 (2017)

    2017

  7. [7]

    C. T. Chubb and S. T. Flammia, Statistical mechanical models for quantum codes with correlated noise, arXiv:1809.10704

    arXiv

  8. [8]

    Deutsch, Quantum theory, the Church–Turing principle and the universal quantum computer,Proceedings of the Royal Society of London A 400 (1985), 96–117

    D. Deutsch, Quantum theory, the Church–Turing principle and the universal quantum computer,Proceedings of the Royal Society of London A 400 (1985), 96–117

    work page 1985

Show all 30 references
  1. [9]

    R. P. Feynman, Simulating physics with computers, International Journal of Theoretical Physics 21 (1982), 467–488

    1982

  2. [10]

    Gao and L

    X. Gao and L. Duan, Efficient classical simulation of noisy quantum computation, arXiv:1810.03176

    arXiv

  3. [11]

    Johansson and J.-A

    N. Johansson and J.-A. Larsson, Realization of Shor’s algorithm at room temperature, arXive:1706.03215

    arXiv

  4. [12]

    Kahn and G

    J. Kahn and G. Kalai, A counterexample to Borsuk’s conjecture, Bulletin of the American Mathematical Society 29 (1993), 60–62

    1993

  5. [13]

    Kalai, The quantum computer puzzle, Notices of the American Mathematical Society63 (2016), 508–516

    G. Kalai, The quantum computer puzzle, Notices of the American Mathematical Society63 (2016), 508–516

    2016

  6. [14]

    Kalai, The quantum computer puzzle (expanded version), arXiv:1605.00992

    G. Kalai, The quantum computer puzzle (expanded version), arXiv:1605.00992

    arXiv

  7. [15]

    Kalai, Three puzzles on mathematics, computation and games, Proceedings of the International Congress of Mathematicians 2018, Rio de Janeiro, V ol

    G. Kalai, Three puzzles on mathematics, computation and games, Proceedings of the International Congress of Mathematicians 2018, Rio de Janeiro, V ol. I, pp. 551–606

    2018

  8. [16]

    Kalai and G

    G. Kalai and G. Kindler, Gaussian noise sensitivity and BosonSampling, arXiv:1409.3093

    arXiv

  9. [17]

    A. Y . Kitaev, Quantum error correction with imperfect gates, in Quantum Communication, Computing, and Measurement , Plenum Press, New York, 1997, pp. 181–188. 20

    1997

  10. [18]

    Knill, R

    E. Knill, R. Laflamme, and W. H. Zurek, Resilient quantum computation: Error models and thresholds, Proceedings of the Royal Society of London A 454 (1998), 365–384

    1998

  11. [19]

    B. D. McKay and S. P. Radziszowski, R(4,5)=25, Journal of Graph Theory 19 (1995), 309–322

    1995

  12. [20]

    Pitowsky, The physical Church thesis and physical computational complexity, lyuun, A Jerusalem Philo- sophical Quarterly 39 (1990), 81–99

    I. Pitowsky, The physical Church thesis and physical computational complexity, lyuun, A Jerusalem Philo- sophical Quarterly 39 (1990), 81–99

    1990

  13. [21]

    Pitowsky, Correlation polytopes: Their geometry and complexity, Mathematical Programming A50 (1991), 395–414

    I. Pitowsky, Correlation polytopes: Their geometry and complexity, Mathematical Programming A50 (1991), 395–414

    1991

  14. [22]

    Polterovich, Symplectic geometry of quantum noise, Communications in Mathematical Physics 327 (2014), 481–519

    L. Polterovich, Symplectic geometry of quantum noise, Communications in Mathematical Physics 327 (2014), 481–519

    2014

  15. [23]

    Preskill, Quantum computing: Pro and con, Proceedings of the Royal Society of London A 454 (1998), 469–486

    J. Preskill, Quantum computing: Pro and con, Proceedings of the Royal Society of London A 454 (1998), 469–486

    1998

  16. [24]

    Preskill, Sufficient condition on noise correlations for scalable quantum computing, Quantum Information and Computing 13 (2013), 181–194

    J. Preskill, Sufficient condition on noise correlations for scalable quantum computing, Quantum Information and Computing 13 (2013), 181–194

    2013

  17. [25]

    P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum com- puter, SIAM Rev.41 (1999), 303–332. (Earlier version,Proceedings of the 35th Annual Symposium on Foun- dations of Computer Science, 1994.)

    1999

  18. [26]

    P. W. Shor, Scheme for reducing decoherence in quantum computer memory, Physical Review A 52 (1995), 2493–2496

    1995

  19. [27]

    A. M. Steane, Error-correcting codes in quantum theory, Physical Review Letters 77 (1996), 793–797

    1996

  20. [28]

    Troyansky and N

    L. Troyansky and N. Tishby, Permanent uncertainty: On the quantum evaluation of the determinant and the permanent of a matrix, in Proceedings of the 4th Workshop on Physics and Computation, 1996

    1996

  21. [29]

    Wigderson, Mathematics and Computation, Princeton University Press, 2019

    A. Wigderson, Mathematics and Computation, Princeton University Press, 2019

    2019

  22. [30]

    Wolfram, Undecidability and intractability in theoretical physics, Physical Review Letters 54 (1985), 735–738

    S. Wolfram, Undecidability and intractability in theoretical physics, Physical Review Letters 54 (1985), 735–738. 21

    1985

Pith tools

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