Debating the Feasibility of Quantum Computing and NISQ Systems

A Critical View on Quantum Computing Gil Kalai Einstein Institute of Mathematics Hebrew University of Jerusalem Efi Arazi School of Computer Science, Reichman University Tel Aviv, June 3, 2025 Ethereum Foundation and Reichman University

Are Quantum Computers Possible? Quantum computers are fascinating hypothetical powerful computers and the debate regarding their possibility represents one of the most important scientific problems of our time. My theory asserts that building scalable quantum computers and even reaching significant milestones towards them are fundamentally impossible.

Overview: The argument against Quantum Computers Noisy intermediate scale quantum systems (NISQ systems) represent a low-level computational ability that will not enable quantum error-correcting codes that are needed for quantum computation. Novelty: computation-complexity reasoning is applied to deduce limits for engineering effort. (Note: here, noise means errors .)

The computational power of NISQ systems NISQ-circuits are computationally very weak, unlikely to allow quantum codes needed for quantum computers. B P

A Recent Quantum Duel at Prague Gil Kalai Qubits are noisy! Matthias Christandl - Qubits are real! The first small and noisy quantum bits have been built, yes, quantum bits are real! For a full-scale quantum computer, we need more and better qubits. This is difficult to achieve. Very difficult, but I will argue that there are no theoretical obstacles that we know of - and that the research is well on-track. Building scalable quantum computers and even achieving early significant milestones in quantum computation is fundamentally impossible. To watch: https://www.youtube.com/live/ykBkZB8JiCg?si=3CxfBp1btlNQEdek

Four Predictions about Quantum computers 1. Inherent Noise for Qubits and Gates Qubit and gates will inherently be noisy. Engineering efforts to reduce this noise will encounter a barrier that prevents achieving the quality required for quantum fault-tolerance. (2-qubit gates are especially important.) The quantum fault-tolerance threshold cannot be reached.

Four Predictions about Quantum computers 2. Correlated Errors in Cat States Cat states (maximally entangled states) will inevitably experience substantially correlated errors. (This is a consequence of the impossibility of quantum fault- tolerance. It is the first step in my study of how quantum processes without quantum fault tolerance behave.)

Four Predictions about Quantum computers 3. Limitations of NISQ Devices Samples generated from quantum computers in the intermediate scale (and boson sampling) correspond to a primitive computational complexity class called LDP (low degree polynomials). As a result, they are incapable of demonstrating quantum supremacy or achieving high-quality quantum error-correction. This argument imposes a computational-complexity-based limit on the engineering efforts to reduce errors in NISQ (Noisy Intermediate- Scale Quantum) devices. (Assertion 3 implies assertion 1.)

Four Predictions about Quantum computers 4. Noise Sensitivity in Small Quantum Circuits The empirical distributions of samples obtained from 12-qubit random circuits inherently contain a significant noise-sensitive component. This means that the empirical distributions are necessarily non-stationary (changing over time) and are inherently unpredictable.

Important points of partial disagreement (1) Matthias Christandl: For a full-scale quantum computer, we need more and better qubits [and gates]. My view: I agree that we need better qubits and gates, but I argue that it is inherently impossible to build qubits and gates of the required quality.

Important points of partial disagreement (2) Matthias Christandl: I will argue that there are no theoretical obstacles that we know of [for achieving full-scale quantum computers]. My view: I agree that there are no definite theoretical obstacles. However, there are serious theoretical concerns that need to be noted. My theory gives a plausible theoretical framework for the impossibility of quantum computers. The debate will largely be decided experimentally.

Other skeptical claims

Earlier skeptical claims (and responses) QC violates the Extended Turing Thesis that represents our understanding of the computational world (Levin, Goldreich, others) Yes indeed! This is a feature not a bug! QC is in tension with the time energy uncertainty principle (TEUP) (Alicki, 2000) TEUP is a misconception, Shor s algorithm clearly shows it! QC is in tension with thermodynamical principles (Alicki 2006) We will be able to use QC to create remarkable novel thermodynamic behavior! Errors will cause QC to fail Quantum error correction and quantum fault tolerance will solve the errors problem! (counter-response) Fault tolerance is based on unphysical assumptions. Implementing quantum fault tolerance is ridiculously hard. It is only very very hard. For more details see: Roadmap for the Debate about Quantum Computers

Computational-complexity-based skeptical claims (and responses) QC violates the Extended Turing Thesis that represents our understanding of the computational world (1995-) Yes indeed! This is a feature not a bug! Factoring is very low in the complexity world; don t make a fuss over it. QC (and even bounded depth-quantum circuits) would allow sampling tasks that are beyond the entire polynomial hierarchy. (2005, 2010) This is wonderful and not a reason for concern. (2010-) We can use quantum sampling power to demonstrate experimentally quantum supremacy! (Kalai-Kindler, 2014; Kalai 2016, 2020) Robust computation on NISQ systems represent primitive computational power. Consequently, NISQ systems cannot demonstrate quantum supremacy or good quality quantum error correcting. NISQ computers can be used (or even has been used) to demonstrate quantum supremacy! The matter is in the hands of engineers!

A Brief Assessment of Progress in the Past Decade

David DiVincenzos famous 7-steps road map to quantum computers (2000) 2025: We do not have good-quality logical qubits yet. There is a good theoretical argument (Kalai 2018, based on Kalai-Kindler 2014) that achieving good quality logical qubits is beyond reach for NISQ circuits. Note that John Martinis near-term expectations from 2013 (QSTART), based on the quality of qubits and gates at that time, are not yet fulfilled today in 2025: https://youtu.be/7Pok08VvkeU?si=tsKbnmh-N4_94IRG

Seeking supremacy without fault tolerance Fantastic quantum supremacy claims are unconvincing. There is a good theoretical argument (Kalai-Kindler 2014) that Quantum supremacy requires quantum fault tolerance.

Topological QC MZM claims are unconvincing

Answer by Craig Gidney (Google): I think experiments of this type will refute Gil's arguments, but I would be uncomfortable claiming that yet. I like nice clear don't-even-really-need-statistics answers to questions like this, so personally I'll be waiting for one-in-a-trillion error rates on complex states before saying the physical-noise-is-conspiring position has become indefensible. Comment by Gil Kalai: This is a nice answer, Craig! I'll admit that my argument is refuted much before "one-in-a-trillion error rates on complex states," is demonstrated If you are talking about complex quantum states on 30 qubits, I'd be quite satisfied with one-in-a-thousand error rate. State of the art today: 90-99% (or worse) error rates for complex states.

Important points of partial disagreement (3) Matthias Christandl: The research is well on-track My view: I agree that a lot of brilliant people are involved in this endeavor, and there are good ideas and innovations. There are, however, also concerns about correctness, transparency, and scientific conduct of some major experimental claim. In general, published experimental claims are often not properly scrutinized. So far, my theory is consistent with the outcomes of (credible) experimental progress. We do not know where the track is leading.

Concerns about Google 2019 quantum supremacy claims 1. Some aspects are Too Good to be true . 2. Calibration method indicates a Stone soup . 3. Lack of transparency in Crucial Data. 4. Much better classical algorithms were found.

Are there already stable qubits and quantum computers? Recent fantastic claims: Google (Dec. 2024): Quantum computers achieved in a few minutes a computation that would require 10 septillion years for a classical computer. Microsoft (Feb. 2025): The first topological qubit was created. It is based on a new phase of matter Majorana zero-mode. These fantastic claims by Google and Microsoft are (probably) incorrect.

Advice regarding post-quantum cryptography Make comprehensive study of a) available post-quantum cryptography and b) the relevance of post-quantum cryptography to gaining additional security in any specific case. Wait in implementing post-quantum cryptography for a firm demonstration of DeVincenzo s steps 4-5. (We are still far from this stage.) Implement post-quantum cryptography as an additional layer. In my judgement, it is implausible that we will see Shor s algorithm implemented in the next decades (and if my theory is correct, not even later). Independently scrutinize far-reaching experimental claims. Scrutinize yourself. Whatever you do, be open and transparent.

Conclusion There arguments for the failure of quantum computers, as well as for inherent obstacles to near-term goals. Exploring this avenue presents intriguing scientific challenges and could have significant implications for various areas of quantum physics. are compelling (though not yet definitive)

Thank you very much! !

A Frequently asked question Isn t it the case that quantum systems manifest quantum computational supremacy but we just are unable to harness it? Isn t it even harder to simulate on a classical computer probability distributions from NISQ computers? If so, because of noise they represent even stronger quantum supremacy! Answer: I will explain why this is not the case.

Additional take-home messages There is large amount of uncertainty regarding the question at-large and regarding specific far-reaching experimental claims. This is not really a duel and certainly not a war. It is a fascinating scientific debate.

Menu Part II: Background: Boolean circuits; quantum circuits; efficient computation Part III: The Argument Against Quantum Computers; Part IV: Noise Stability and sensitivity for boson sampling; Part V: The failure of quantum computation - underlying principles and consequences; Part VI: The Analysis of Google s 2019 experiment and other QC experiments

Part II: Background Computers! (Boolean circuits) The basic memory component in classical computing is a bit, which can be in two states, 0 or 1 . A computer (or circuit) has ? bits, and it can perform certain logical operations on them. The NOT gate, acting on a single bit, and the AND gate, acting on two bits, suffice for the full power of classical computing.

Efficient computation There are certain computational tasks that are very easy to formulate (and even to check whether a suggested answer to them is correct), but which are nonetheless impossible to perform because they require too many computational steps. Efficient computation requires that the number of computational steps (gates) is polynomial in the number n of input bits.

Probabilistic bits and random computation

Quantum circuits: qubits

Quantum gates Gates are unitary transformations: We can put one or two qubits through gates representing unitary transformations acting on the corresponding two- or four-dimensional Hilbert spaces, and as for classical computers, there is a small list of gates sufficient for the full power of quantum computing.

Measurement

Quantum circuits

Shors and Grovers algorithms In the 1990s, Peter Shor discovered that quantum computers would allow the execution of certain computational tasks hundreds of orders of magnitude faster than regular computers and would enable us to break most current cryptosystems. Shor s algorithm is an efficient (polynomial time) quantum algorithm to factor an ?-digit number. Another important quantum algorithm from that time is Grover s algorithm.

Efficient computation and Computational complexity

Noisy quantum circuits The term noise refers to a deviation of the computer from the planned program, and in the case of a quantum computer any unwanted interaction or leakage of information leads to such a deviation. Noisy quantum circuits have the property that there exists a certain level of noise for qubits and gates. Noisy intermediate-scale quantum (NISQ) computers: These are simply noisy quantum circuits with at most 200 (say) qubits. In the NISQ regime errors grow exponentially with the number of qubits and gates.

Part III: The Argument Against Quantum Computers

The three ingredients of the argument against quantum computers Noise levels for NISQ computers are inherently high and therefore: a) Such systems cannot demonstrate significant quantum computational advantage. b) Such systems cannot be used for the creation of quantum error-correcting codes. c) Such systems lead to non-stationary and even chaotic probability distributions.

The reason NISQ computers cannot support quantum supremacy NISQ computers cannot support quantum supremacy because when we use computational complexity tools to understand the computational power of NISQ computers, we discover that they describe a very low- level computational class. This low-level computational class does not allow for any complicated computations, much less computational supremacy.

The reason NISQ computers cannot support good-quality quantum error correcting codes It is impossible to build good-quality quantum error-correcting codes because it requires an even lower noise level than that required for demonstrating quantum supremacy.

< < < The rate of noise required by large quantum computers The rate of noise required for good quality quantum error correcting codes. (E.g., good quality surface code) The rate of noise required to demonstrate quantum supremacy The lowest realistic rate of noise for quantum circuits in nature

The noise-sensitive nature of NISQ samples Analysis of the intermediate-scale quantum computer model points to noise- sensitive behavior across a broad range of noise levels. Here we use the term noise-sensitive in the following strong sense: it will not be possible, even probabilistically, to predict the behavior of the computer, namely the distribution of the samples it produces. This is caused by a large noise-sensitive component of the quantum computer samples, namely, small fluctuations in the parameters describing the noise will have a big effect on the distribution of the samples produced by the computer.

The crux of the debate I argue that from the point of view of computational complexity, NISQ devices are, in fact, low-level classical computing devices, and I regard it as strong evidence that engineers will not be able to reach the level of noise required for quantum supremacy and good-quality quantum error correcting codes. Others argue that the existence of low-level simulation (in the NISQ regime) for every fixed level of noise does not have any bearing on the engineering question of reducing the level of noise. These sharply different views will be tested in the next few years.

The reason Classical information and computation are possible The low-level computational complexity class LDP enables the creation of robust classical information and classical computation. (Via the mechanism of repetition and averaging/majority.)

Laws of physics and computations The extended Church Turing thesis ECTT Falsified by quantum computers The quantum extended Church Turing thesis QECTT Widely accepted NISQ = LDP Implied by my theory, would imply ECTT

The computational power of NISQ systems NISQ-circuits are computationally very weak, unlikely to allow quantum codes needed for quantum computers. B P

NISQ devices - near term tasks Goal 1: Demonstrate quantum supremacy on random circuits (namely, circuits that are based on randomly choosing the computation process, in advance), with 50 100 qubits. (proposed in 2015, 2016) Goal 2: Demonstrate quantum supremacy via systems of non- interacting bosons. (proposed in 2012) Goal 3: Create good-quality surface codes on NISQ circuits that require a little over 100-200 qubits. (proposed in 2000 - 2010 ) My prediction (2016): All these near-term tasks are inherently impossible.

(A cartoon from 2017)