Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1605.00992 · Notices of the American Mathematical Society

The Quantum Computer Puzzle

Gil Kalai

Published Apr 19, 2016• 31 citations
arXivHTMLPDF

Abstract

Quantum computers are hypothetical devices, based on quantum physics, that would enable us to perform certain computations hundreds of orders of magnitude faster than digital computers. This feature is coined as "quantum supremacy" and one aspect or another of such quantum computational supremacy might be brought about in experiments in the near future: by implementing quantum error-correction, systems of non-interacting bosons, exotic new phases of matter called anyons, quantum annealing, or in various other ways. A main concern regarding the feasibility of quantum computers is that quantum systems are inherently noisy: we cannot accurately control them, and we cannot accurately describe them. We will describe an optimistic hypothesis of quantum noise that would allow quantum computing and a pessimistic hypothesis that wouldn't. The quantum computer puzzle is deciding between these two hypotheses. Here is a brief summary of the author's pessimistic point of view as explained in the paper: understanding quantum computers in the presence of noise requires consideration of behavior at different scales. In the small scale, standard models of noise from the mid-90s are suitable, and quantum evolutions and states described by them manifest a very low-level computational power. This small-scale behavior has far-reaching consequences for the behavior of noisy quantum systems at larger scales. On the one hand, it does not allow reaching the starting points for quantum fault tolerance and quantum supremacy, making them both impossible at all scales. On the other hand, it leads to novel implicit ways for modeling noise at larger scales and to various predictions on the behavior of noisy quantum systems.

DOI
10.1090/noti1380

Related papers

An Examination of Different Kinds of Quantum Computing Technologies

Karan Chawla

One of the main drivers for growing the field of quantum computation has been the prospect of creating a quantum computer capable of carrying out Shor's algorithm for huge numbers.Nonetheless, it is critical to recognise that quantum computers will probably only significantly speed up a small subset of issues if one wants to acquire a more comprehensive perspective on them.Building a system that can accommodate a lot of qubits while preserving stability and coherence is one of the biggest problems in quantum computing.Due to their extreme sensitivity to noise and mistakes, quantum systems are particularly susceptible to computing errors.Building a usable quantum computer requires error mitigation and correction, but the techniques for doing this are still in the early phases of research.In quantum computing, all processes and schemes must be reversible in accordance with the law of unitary development.The circuit model is taken into account in the NISQ framework, but there is also the one-way or measurement-based quantum computation approach, which is not reversible but is demonstrated to be comparable to the circuit model.Noisy suggests that the computing capacity of such quantum computers is constrained because of sufficiently high error and decoherence rates.While they are likely too huge to be replicated by traditional computers using brute force, Intermediate-Scale suggests that they are still too small to be mistake corrected, which also adds to the preceding argument about how noisy they are.P stands for the usage of perfect qubits with perfect quantum gates and no decoherence.The capability to control and protect our qubits in a quantum computer to the degree necessary to run such algorithms is commonly described as fault-tolerant quantum computation.This review paper examines the numerous quantum computing strategies, such as Noisy Intermediate Scale Computing (NISQ) , Perfect Intermediate Scale Computing (PISQ), and Fault Tolerant Intermediate Scale Computing (FTISQ), as well as potential future lines of inquiry.

International Journal of Scientific Engineering and Research•Apr 27, 2023•0 citations

Efficient fault-tolerant quantum computing

Andrew M. Steane

Abstract Quantum computing1—the processing of information according to the fundamental laws of physics—offers a means to solve efficiently a small but significant set of classically intractable problems. Quantum computers are based on the controlled manipulation of entangled quantum states, which are extremely sensitive to noise and imprecision; active correction of errors must therefore be implemented without causing loss of coherence. Quantum error-correction theory2, 3, 4, 5, 6, 7, 8, 9 has made great progress in this regard, by predicting error-correcting ‘codeword’ quantum states. But the coding is inefficient and requires many quantum bits10, 11, 12, which results in physically unwieldy fault-tolerant quantum circuits10, 11, 12, 13, 14, 15, 16, 17, 18. Here I report a general technique for circumventing the trade-off between the achieved noise tolerance and the scale-up in computer size that is required to realize the error correction. I adapt the recovery operation (the process by which noise is suppressed through error detection and correction) to simultaneously correct errors and perform a useful measurement that drives the computation. The result is that a quantum computer need be only an order of magnitude larger than the logic device contained within it. For example, the physical scale-up factor10, 11 required to factorize a thousand-digit number is reduced from 1, 500 to 22, while preserving the original tolerated gate error rate (10−5) and memory noise per bit (10−7). The difficulty of realizing a useful quantum computer is therefore significantly reduced.

•Sep 18, 1998•127 citations

The Argument against Quantum Computers

Gil Kalai

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.

arXiv:1908.02499•Aug 7, 2019•12 citations

QUANTUM COMPUTATION

Dorit Aharonov

In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if built, might be used as a dramatically powerful computational tool. This review is about to tell the story of theoretical quantum computation. I left out the developing topic of experimental realizations of the model, and neglected other closely related topics which are quantum information and quantum communication. As a result of narrowing the scope of this paper, I hope it has gained the benefit of being an almost self contained introduction to the exciting field of quantum computation. The review begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models, I define quantum computers, and discuss the issue of universal quantum gates. Quantum algorithms, including Shor's factorization algorithm and Grover's algorithm for searching databases, are explained. I will devote much attention to understanding what the origins of the quantum computational power are, and what the limits of this power are. Finally, I describe the recent theoretical results which show that quantum computers maintain their complexity power even in the presence of noise, inaccuracies and finite precision. I tried to put all results in their context, asking what the implications to other issues in computer science and physics are. In the end of this review I make these connections explicit, discussing the possible implications of quantum computation on fundamental physical questions, such as the transition from quantum to classical physics.

arXiv:quant-ph/9812037•WORLD SCIENTIFIC eBooks•Mar 1, 1999•139 citations

Noise-Induced Thermalization in Quantum Systems

Sameer Dambal, Yu Zhang, Eric R Bittner +1 more

In the current Noisy Intermediate-Scale Quantum era, noise is widely regarded as the primary obstacle to achieving fault-tolerant quantum computation. However, certain stages of the quantum computing pipeline can, in fact, benefit from this noise. In this work, we exploit the Eigenstate Thermalization Hypothesis to show that noise generically accelerates a fundamental task in quantum computing -- the preparation of Gibbs states. We demonstrate this behavior using classical and quantum simulations with Haar-random and phase-flip noise, respectively, on a spin-1/2 chain with a local Hamiltonian. Our non-integrable model sees ~3.5x faster thermalization in the presence of noise, while our integrable model, which would not otherwise thermalize, reaches a thermal state due to noise. Since certifying a local Gibbs state is relatively easy on a quantum computer, our approach provides a new practical solution to a key problem in quantum computing. More broadly, these results establish a new paradigm in which noise can be harnessed on quantum computers, enabling practical advantages before the years of fault-tolerance.

quant-pharXiv:2512.14842•New Journal of Physics•Dec 18, 2025•3 citations

Achieving fault tolerance against amplitude-damping noise

Akshaya Jayashankar, Long D. H. My, Hui Khoon Ng +1 more

With the intense interest in small, noisy quantum computing devices comes the push for larger, more accurate---and hence more useful---quantum computers. While fully fault-tolerant quantum computers are, in principle, capable of achieving arbitrarily accurate calculations using devices subjected to general noise, they require immense resources far beyond our current reach. An intermediate step would be to construct quantum computers of limited accuracy enhanced by lower-level, and hence lower-cost, noise-removal techniques. This is the motivation for our paper, which looks into fault-tolerant encoded quantum computation targeted at the dominant noise afflicting the quantum device. Specifically, we develop a protocol for fault-tolerant encoded quantum computing components in the presence of amplitude-damping noise, using a 4-qubit code and a recovery procedure tailored to such noise. We describe a universal set of fault-tolerant encoded gadgets and compute the pseudothreshold for the noise, below which our scheme leads to more accurate computation. Our paper demonstrates the possibility of applying the ideas of quantum fault tolerance to targeted noise models, generalizing the recent pursuit of biased-noise fault tolerance beyond the usual Pauli noise models. We also illustrate how certain aspects of the standard fault tolerance intuition, largely acquired through Pauli-noise considerations, can fail in the face of more general noise.

arXiv:2107.05485•Physical Review Research•Apr 11, 2022•24 citations
Quantum computers are hypothetical devices, based on quantum physics, that would enable us to perform certain computations hundreds of orders of magnitude faster than digital computers. This feature is coined as "quantum supremacy" and one aspect or another of such quantum computational supremacy might be brought about in experiments in the near future: by implementing quantum error-correction, systems of non-interacting bosons, exotic new phases of matter called anyons, quantum annealing, or in various other ways. A main concern regarding the feasibility of quantum computers is that quantum systems are inherently noisy: we cannot accurately control them, and we cannot accurately describe them. We will describe an optimistic hypothesis of quantum noise that would allow quantum computing and a pessimistic hypothesis that wouldn't. The quantum computer puzzle is deciding between these two hypotheses. Here is a brief summary of the author's pessimistic point of view as explained in the paper: understanding quantum computers in the presence of noise requires consideration of behavior at different scales. In the small scale, standard models of noise from the mid-90s are suitable, and quantum evolutions and states described by them manifest a very low-level computational power. This small-scale behavior has far-reaching consequences for the behavior of noisy quantum systems at larger scales. On the one hand, it does not allow reaching the starting points for quantum fault tolerance and quantum supremacy, making them both impossible at all scales. On the other hand, it leads to novel implicit ways for modeling noise at larger scales and to various predictions on the behavior of noisy quantum systems.
One of the main drivers for growing the field of quantum computation has been the prospect of creating a quantum computer capable of carrying out Shor's algorithm for huge numbers.Nonetheless, it is critical to recognise that quantum computers will probably only significantly speed up a small subset of issues if one wants to acquire a more comprehensive perspective on them.Building a system that can accommodate a lot of qubits while preserving stability and coherence is one of the biggest problems in quantum computing.Due to their extreme sensitivity to noise and mistakes, quantum systems are particularly susceptible to computing errors.Building a usable quantum computer requires error mitigation and correction, but the techniques for doing this are still in the early phases of research.In quantum computing, all processes and schemes must be reversible in accordance with the law of unitary development.The circuit model is taken into account in the NISQ framework, but there is also the one-way or measurement-based quantum computation approach, which is not reversible but is demonstrated to be comparable to the circuit model.Noisy suggests that the computing capacity of such quantum computers is constrained because of sufficiently high error and decoherence rates.While they are likely too huge to be replicated by traditional computers using brute force, Intermediate-Scale suggests that they are still too small to be mistake corrected, which also adds to the preceding argument about how noisy they are.P stands for the usage of perfect qubits with perfect quantum gates and no decoherence.The capability to control and protect our qubits in a quantum computer to the degree necessary to run such algorithms is commonly described as fault-tolerant quantum computation.This review paper examines the numerous quantum computing strategies, such as Noisy Intermediate Scale Computing (NISQ) , Perfect Intermediate Scale Computing (PISQ), and Fault Tolerant Intermediate Scale Computing (FTISQ), as well as potential future lines of inquiry.
Abstract Quantum computing1—the processing of information according to the fundamental laws of physics—offers a means to solve efficiently a small but significant set of classically intractable problems. Quantum computers are based on the controlled manipulation of entangled quantum states, which are extremely sensitive to noise and imprecision; active correction of errors must therefore be implemented without causing loss of coherence. Quantum error-correction theory2, 3, 4, 5, 6, 7, 8, 9 has made great progress in this regard, by predicting error-correcting ‘codeword’ quantum states. But the coding is inefficient and requires many quantum bits10, 11, 12, which results in physically unwieldy fault-tolerant quantum circuits10, 11, 12, 13, 14, 15, 16, 17, 18. Here I report a general technique for circumventing the trade-off between the achieved noise tolerance and the scale-up in computer size that is required to realize the error correction. I adapt the recovery operation (the process by which noise is suppressed through error detection and correction) to simultaneously correct errors and perform a useful measurement that drives the computation. The result is that a quantum computer need be only an order of magnitude larger than the logic device contained within it. For example, the physical scale-up factor10, 11 required to factorize a thousand-digit number is reduced from 1, 500 to 22, while preserving the original tolerated gate error rate (10−5) and memory noise per bit (10−7). The difficulty of realizing a useful quantum computer is therefore significantly reduced.
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.
In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if built, might be used as a dramatically powerful computational tool. This review is about to tell the story of theoretical quantum computation. I left out the developing topic of experimental realizations of the model, and neglected other closely related topics which are quantum information and quantum communication. As a result of narrowing the scope of this paper, I hope it has gained the benefit of being an almost self contained introduction to the exciting field of quantum computation. The review begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models, I define quantum computers, and discuss the issue of universal quantum gates. Quantum algorithms, including Shor's factorization algorithm and Grover's algorithm for searching databases, are explained. I will devote much attention to understanding what the origins of the quantum computational power are, and what the limits of this power are. Finally, I describe the recent theoretical results which show that quantum computers maintain their complexity power even in the presence of noise, inaccuracies and finite precision. I tried to put all results in their context, asking what the implications to other issues in computer science and physics are. In the end of this review I make these connections explicit, discussing the possible implications of quantum computation on fundamental physical questions, such as the transition from quantum to classical physics.
In the current Noisy Intermediate-Scale Quantum era, noise is widely regarded as the primary obstacle to achieving fault-tolerant quantum computation. However, certain stages of the quantum computing pipeline can, in fact, benefit from this noise. In this work, we exploit the Eigenstate Thermalization Hypothesis to show that noise generically accelerates a fundamental task in quantum computing -- the preparation of Gibbs states. We demonstrate this behavior using classical and quantum simulations with Haar-random and phase-flip noise, respectively, on a spin-1/2 chain with a local Hamiltonian. Our non-integrable model sees ~3.5x faster thermalization in the presence of noise, while our integrable model, which would not otherwise thermalize, reaches a thermal state due to noise. Since certifying a local Gibbs state is relatively easy on a quantum computer, our approach provides a new practical solution to a key problem in quantum computing. More broadly, these results establish a new paradigm in which noise can be harnessed on quantum computers, enabling practical advantages before the years of fault-tolerance.
With the intense interest in small, noisy quantum computing devices comes the push for larger, more accurate---and hence more useful---quantum computers. While fully fault-tolerant quantum computers are, in principle, capable of achieving arbitrarily accurate calculations using devices subjected to general noise, they require immense resources far beyond our current reach. An intermediate step would be to construct quantum computers of limited accuracy enhanced by lower-level, and hence lower-cost, noise-removal techniques. This is the motivation for our paper, which looks into fault-tolerant encoded quantum computation targeted at the dominant noise afflicting the quantum device. Specifically, we develop a protocol for fault-tolerant encoded quantum computing components in the presence of amplitude-damping noise, using a 4-qubit code and a recovery procedure tailored to such noise. We describe a universal set of fault-tolerant encoded gadgets and compute the pseudothreshold for the noise, below which our scheme leads to more accurate computation. Our paper demonstrates the possibility of applying the ideas of quantum fault tolerance to targeted noise models, generalizing the recent pursuit of biased-noise fault tolerance beyond the usual Pauli noise models. We also illustrate how certain aspects of the standard fault tolerance intuition, largely acquired through Pauli-noise considerations, can fail in the face of more general noise.