Kalai (2016) posed 'the quantum computer puzzle': deciding between an optimistic hypothesis of quantum noise — that universal quantum circuits can be realized with a small bounded error rate regardless of the number of qubits, so that large-scale fault-tolerant quantum computers are possible — and a pessimistic hypothesis — that in every realization of universal quantum circuits the error rate scales up (at least) linearly with the number of qubits, so that quantum computers are not possible. A decade of subsequent work has probed the question from both sides: provable constant-depth quantum advantage robust to local noise, supremacy and 'utility' experiments on noisy processors together with classical algorithms that reproduce or spoof those outputs, and below-threshold quantum error correction on surface codes. Neither a scalable fault-tolerant machine nor any impossibility theorem exists, so the puzzle — including whether noisy sub-threshold devices can exhibit robust quantum advantage, and the experimental adjudication of Kalai's seventeen predictions — remains open.

Background

A quantum computer processes information by applying arranged sequences of quantum-mechanical operations ('quantum circuits') to quantum bits (qubits), and for some tasks — most famously integer factoring via Shor's algorithm — the quantum circuit model offers exponential speedups over known classical computation; a demonstrated separation of this kind is called 'quantum supremacy' or quantum advantage. Real devices are 'noisy': each operation and each qubit is subject to uncontrolled errors due to unwanted coupling to the environment, and if the error rate per operation were fixed and independent across qubits, a large computation would be corrupted with near certainty. The threshold theorem of quantum fault tolerance (developed in the mid-1990s) asserts that, provided the physical error rate per operation lies below a threshold of roughly 0.001–0.01 and the noise meets natural locality and weak-correlation conditions, quantum error-correcting codes can be concatenated or scaled so that arbitrarily long quantum computations are performed with arbitrarily small logical error rate, with only moderate (polylogarithmic) overhead. The leading practical such scheme is the surface code, which encodes each logical qubit in a two-dimensional grid of physical qubits whose linear extent (the code distance) determines how rapidly the logical error rate is suppressed as the code is enlarged. This theorem underwrites the standard expectation that large-scale fault-tolerant quantum computers are possible, but it is conditional: it assumes the noise itself does not become systematically worse as the system grows or more strongly correlated with the computation being attempted. In his paper 'The Quantum Computer Puzzle' (expanded version; the short version appeared in the Notices of the AMS, May 2016), Gil Kalai formalized the issue as a choice between two hypotheses, quoted here verbatim. Optimistic hypothesis: 'It is possible to realize universal quantum circuits with a small bounded error level regardless of the number of qubits. The effort required to obtain a bounded error level for universal quantum circuits increases moderately with the number of qubits. Therefore, large-scale fault-tolerant quantum computers are possible.' Pessimistic hypothesis: 'The error rate in every realization of universal quantum circuits scales up (at least) linearly with the number of qubits. The effort required to obtain a bounded error level for any implementation of universal quantum circuits increases (at least) exponentially with the number of qubits. Thus, quantum computers are not possible.' (Linear scaling means that doubling the number of qubits doubles the probability that a single qubit is corrupted in a small time interval.) Kalai's supporting picture, partly developed with Guy Kindler using noise-sensitivity methods and the boson-sampling model (a restricted quantum-computing scheme based on non-interacting photons, whose output probabilities are hard to sample classically), is that noisy quantum evolutions at small scale are described by low-degree polynomials in the amplitudes; such evolutions allow robust classical information but never reach the starting points for fault tolerance or supremacy. From the pessimistic hypothesis Kalai derives seventeen predictions about physics and computation, including: correlated errors on entangled qubit pairs ('noisy cat states'); error synchronization across many qubits; error rates growing with the complexity of the computed evolution; that logical qubits cannot be made substantially more stable than the underlying physical qubits; that achievable quantum states are limited by bounded-depth, bounded-degree approximations; that noise is well modeled by 'time-smoothing' (correlating an evolution with a time-averaged version of itself); that noise respects the symmetries of the state it corrupts; that noise fluctuations in interacting NN-element systems scale like NN rather than N\sqrt{N}; and that teleportation of highly entangled ('complicated') states and reversal of certain quantum evolutions are impossible in principle. He also frames the era of noisy intermediate-scale quantum (NISQ) devices — a term coined by Preskill — as the regime where the puzzle will be adjudicated: the pessimistic hypothesis 'predicts a decisive failure for all of these attempts to demonstrate quantum supremacy, or very stable logical qubits', while the optimistic hypothesis predicts sub-threshold devices can already show quantum advantage. The puzzle is thus simultaneously an experimental question (do error-corrected logical qubits keep improving as they scale, and do noisy shallow circuits outperform all classical algorithms?) and a theoretical one (is there a mathematically precise, physically faithful theory of noise that decides between the hypotheses?).

Problem Statement

Decide the quantum computer puzzle as posed by Kalai (2016): determine which of the following two hypotheses about noise in physical implementations of universal quantum circuits is true. (1) The optimistic hypothesis: it is possible to realize universal quantum circuits with a small bounded error level regardless of the number of qubits, with the effort to do so growing only moderately with system size, so that large-scale fault-tolerant quantum computers are possible. (2) The pessimistic hypothesis: in every realization of universal quantum circuits the per-qubit error rate scales up (at least) linearly with the number of qubits — doubling the qubit count doubles the probability that a given qubit is corrupted in a small time interval — so that bounded-error universal circuits require effort growing (at least) exponentially with system size and quantum computers are not possible. The paper attaches related tests and evidence to this decision — the behavior of noisy, non-fault-tolerant (sub-threshold) devices in the bounded-depth regime relative to the best classical algorithms, and seventeen predictions derived from the pessimistic hypothesis (correlated noise on entangled qubit pairs, error synchronization, error-rate growth with evolution complexity, the claim that logical qubits cannot be substantially more stable than physical qubits, bounded-degree approximation of achievable states, time-smoothed noise, symmetry-respecting noise, noise fluctuations scaling like NN rather than N\sqrt{N} in interacting systems, among others) — which the paper proposes to test in supremacy-era experiments; these bear on the decision but are not separate required deliverables of an answer. Acceptable forms of a decision include a scalable fault-tolerant quantum computer or a decisive experimental scaling demonstration establishing the optimistic hypothesis, or a rigorous theory/no-go result — a mathematically precise and physically faithful noise framework under which no realistic implementation of universal quantum circuits can achieve bounded error at growing system size — establishing the pessimistic one.

References

  1. Gil Kalai, "The Quantum Computer Puzzle (Expanded Version)" (2016), arXiv:1605.00992, DOI 10.48550/arXiv.1605.00992, https://arxiv.org/abs/1605.00992 (expanded version of the paper in Notices of the AMS, May 2016)
  2. Gil Kalai and Guy Kindler, "Gaussian Noise Sensitivity and BosonSampling" (2014), arXiv:1409.3093, DOI 10.48550/arXiv.1409.3093, https://arxiv.org/abs/1409.3093
  3. John Preskill, "Quantum Computing in the NISQ era and beyond", Quantum 2, 79 (2018), DOI 10.22331/q-2018-08-06-79, https://doi.org/10.22331/q-2018-08-06-79
  4. Sergey Bravyi, David Gosset, Robert König, "Quantum advantage with shallow circuits", Science 362, 308–311 (2018), DOI 10.1126/science.aar3106, https://doi.org/10.1126/science.aar3106
  5. Sergey Bravyi, David Gosset, Robert König, Marco Tomamichel, "Quantum advantage with noisy shallow circuits", Nature Physics 16, 1040–1045 (2020), DOI 10.1038/s41567-020-0948-z, https://doi.org/10.1038/s41567-020-0948-z
  6. Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, et al., "Quantum supremacy using a programmable superconducting processor", Nature 574, 505–510 (2019), DOI 10.1038/s41586-019-1666-5, https://doi.org/10.1038/s41586-019-1666-5
  7. Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, Umesh Vazirani, "A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling", Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), 945–957, DOI 10.1145/3564246.3585234, https://doi.org/10.1145/3564246.3585234
  8. Youngseok Kim, Andrew Eddins, Sajant Anand, Ken Xuan Wei, Ewout van den Berg, Sami Rosenblatt, Hasan Nayfeh, Yantao Wu, Michael Zaletel, Kristan Temme, Abhinav Kandala, "Evidence for the utility of quantum computing before fault tolerance", Nature 618, 500–505 (2023), DOI 10.1038/s41586-023-06096-3, https://doi.org/10.1038/s41586-023-06096-3
  9. Google Quantum AI and Collaborators (Rajeev Acharya, Igor Aleiner, Trond I. Andersen, et al.), "Suppressing quantum errors by scaling a surface code logical qubit", Nature 614, 676–681 (2023), DOI 10.1038/s41586-022-05434-1, https://doi.org/10.1038/s41586-022-05434-1
  10. Joseph Tindall, Matthew Fishman, E. Miles Stoudenmire, Dries Sels, "Efficient Tensor Network Simulation of IBM's Eagle Kicked Ising Experiment", PRX Quantum 5, 010308 (2024), DOI 10.1103/prxquantum.5.010308, https://doi.org/10.1103/prxquantum.5.010308
  11. Tomislav Begušić, Johnnie Gray, Garnet Kin-Lic Chan, "Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance", Science Advances 10, eadk4321 (2024), DOI 10.1126/sciadv.adk4321, https://doi.org/10.1126/sciadv.adk4321
  12. Gil Kalai, "The Argument Against Quantum Computers, the Quantum Laws of Nature, and Google's Supremacy Claims", in Laws: Rigidity and Dynamics, pp. 75–121, World Scientific (2024), DOI 10.1142/9789811292316_0006, https://doi.org/10.1142/9789811292316_0006
  13. Google Quantum AI and Collaborators (Rajeev Acharya, Dmitry A. Abanin, Laleh Aghababaie-Beni, Igor Aleiner, Trond I. Andersen, et al.), "Quantum error correction below the surface code threshold", Nature 638, 920–926 (online December 2024), DOI 10.1038/s41586-024-08449-y, https://doi.org/10.1038/s41586-024-08449-y (preprint arXiv:2408.13687)
  14. Thomas Schuster, Chao Yin, Xun Gao, Norman Y. Yao, "A Polynomial-Time Classical Algorithm for Noisy Quantum Circuits", Physical Review X 15, 041018 (2025), DOI 10.1103/xct1-7kf2, https://doi.org/10.1103/xct1-7kf2