# On Mathematical Arguments Against Quantum Computing

Quantum computing is a very active and rapidly expanding field of research. Many companies and research institutes are spending a lot on this futuristic and potentially game-changing technology. Some even built toy models for a quantum computer in the lab. For instance, see IBM's 50-qubit quantum computer.

However, some scientists are not that optimistic when it comes to the predicted potential advantages of quantum computers in comparison with the classical ones. They believe there are theoretical obstacles and fundamental limitations that significantly reduce the efficiency of quantum computing.

One mathematical argument against quantum computing (and the only one that I am aware of) is based on the Gil Kalai's idea concerning the sensitivity of the quantum computation process to noise, which he believes may essentially affect the computational efficiency of quantum computers.

Question. I look for some references on similar theoretical (rather than practical) mathematical arguments against quantum computing — if there are any. Papers and lectures on potential theoretical flaws of quantum computing as a concept are welcome.

Remark. The theoretical arguments against quantum computing may remind the so-called Goedelian arguments against the artificial intelligence, particularly the famous Lucas-Penrose's idea based on the Goedel's incompleteness theorems. Maybe there could be some connections (and common flaws) between these two subjects, particularly when one considers the recent innovations in QAI such as the Quantum Artificial Intelligence Lab.

Here are some references and following them a short answer.

A good reference for the current situation to start with is John Preskill's recent paper "Quantum Computing in the NISQ era and beyond" NISQ stands for "Noisy Intermediate Scale Quantum" and it is a very useful notion coined by Preskill who also coined the notion of "quantum supremacy" - the ability of quantum computers to perform certain computational tasks hundreds orders of magnitude better than classical computers. The crucial theoretical and experimental issue is to understand quantum devices in the NISQ regime.

As for my papers: The two mathematical theorems on which the argument against quantum computers is largely based, are from my paper Gaussian Noise Sensitivity and BosonSampling with Guy Kindler; In my ICM 2018 paper Three Puzzles on Mathematics, Computation, and Games the feasibility of quantum computers is the third puzzle (Sections 1.3, 1.4 and 4) and it is also related to the Benjamini-Kalai-Schramm notions of noise-stability and noise-sensitivity which is discussed in the second puzzle (Sections 1.2, 3). Another good source is my 2016 paper from the Notices of the AMS "The quantum computer puzzle" and its arxive extended version.

On the practical side, these works give clear predictions (see e.g. my ICM paper) for what we can expect from NISQ devices and, in particular, from quantum computers with 10-80 qubits that many try to build. Those predictions are sharply different from what experimentalists hope to achieve.

On the theoretical side we have a good argument for Scott Aaronson's point number 9. (This argument does not rely on error-correlation.) We also have a clear difference between classical and quantum computing, namely why the argument against quantum computing does not apply to classical computing.

My earlier work from 2006-2012 (See e.g. this paper) indeed studied correlation of errors. These works suggest that in the NISQ regime errors for a pair of entangled qubits will have substantial positive correlation. This is another interesting prediction for current and future NISQ devices. This is part of the theoretical picture because the value of the "fault tolerance threshold" in Scott's point 9 depends on such correlation.

• Fantastic! Thank you very much for providing a detailed account of your approach and adding useful links, Gil! – Morteza Azad Jun 12 '18 at 3:08
• Do any of those arguments apply to topological quantum computers in any way? – Manuel Bärenz Jun 12 '18 at 14:33
• Excellent question! The answer is yes. Scott's point 9 extends from noisy quantum circuits to the microscopic process for building the topological qubits. – Gil Kalai Jun 12 '18 at 18:07

Scott Aaronson has this list of Eleven Objections, involving both mathematics and physics arguments.

What I did is to write out every skeptical argument against the possibility of quantum computing that I could think of. We'll just go through them, and make commentary along the way. Let me just start by saying that my point of view has always been rather simple: it's entirely conceivable that quantum computing is impossible for some fundamental reason. If so, then that's by far the most exciting thing that could happen for us. That would be much more interesting than if quantum computing were possible, because it changes our understanding of physics. To have a quantum computer capable of factoring 10000-digit integers is the relatively boring outcome -- the outcome that we'd expect based on the theories we already have.

So, on to the Eleven Objections:

1. Works on paper, not in practice.
2. Violates Extended Church-Turing Thesis.
Perhaps the most precise objection from a mathematical point of view. Here is an extended discussion.
3. Not enough "real physics."
4. Small amplitudes are unphysical.Leonid Levin's objection
5. Exponentially large states are unphysical.Paul Davies' objection
6. Quantum computers are just souped-up analog computers.Robert Laughlin's objection
7. Quantum computers aren't like anything we've ever seen before.Dyakonov's objection
8. Quantum mechanics is just an approximation to some deeper theory.
9. Decoherence will always be worse than the fault-tolerance threshold.Gil Kalai's objection
10. We don't need fault-tolerance for classical computers.
11. Errors aren't independent.This is (part of) Gil Kalai's objection

UPDATE (September 2019): objection 2, the violation of the extended Church-Turing thesis, may now have been removed, as discussed by Scott Aaronson.

• Some additional context may be helpful here. These are objections that the author has heard other people make, and not necessarily well-informed people or researchers at that. The comments he makes are more of the form "here's where the fallacy in that particular phrasing of the objection is". There doesn't seem to be much substance in them to me at all, and at times read to me like fallacious armchair conversations themselves. But perhaps I'm missing something. – zibadawa timmy Jun 10 '18 at 23:54
• I thought the OP asked for precise mathematical objections? the above list is definitely intriguing, but lacks additional information about material that would associate with the listed items some more precise mathematical statements. – Suvrit Jun 11 '18 at 0:16
• My argument falls under Scott's point 9. (Point 11 is also part of the picture.) – Gil Kalai Jun 11 '18 at 5:42
• How is the (extended) Church-Turing thesis point precise mathematically? – Wojowu Jun 11 '18 at 7:24
• This list needs a little more curation. At least half of the objections are clearly meaningless. – knzhou Jun 11 '18 at 14:06

The promise of quantum computing supremacy is bunk by Colin Earl references to

1. Polynomial Time and Extravagant Models by Leonid A. Levin
2. On Quantum Computing by Oded Goldreich
3. Note (d) Quantum computers for Chapter 12.8: Undecidability and Intractability by Stephen Wolfram

for doubts against QC expressed by mathematicians, computer scientists, and physicists.

Details for 1: L. Levin does not attack QC, but only its application to break RSA encryption:

The closed-minded cryptographers, however, were not convinced and this result brought a dismissal of the unit-cost model, not RSA.

Another, not dissimilar, attack is raging this very moment. ... Peter Shor ... factors integers in polynomial time using an imaginary analog device, Quantum Computer (QC), inspired by the laws of quantum physics taken to their formal extreme.

His main objection is that Shor's algorithm would require extremely accurate amplitudes:

All such problems, however, are peanuts. The major problem is the requirement that basic quantum equations hold to multi-hundredth if not millionth decimal positions where the significant digits of the relevant quantum amplitudes reside. We have never seen a physical law valid to over a dozen decimals.

Details for 2: O. Goldreich attacks the assumption that arbitrary Unitary transformations can be applied to the quantum state:

QM says that certain things are not impossible, but it does not say that every thing that is not impossible is indeed possible. For example, it says that you cannot make non-Unitary transformations, but this by itself does not mean that you can effect any Unitary transformation that you want.

and he attacks the unit-cost assumption for the basic operation composing those arbitrary transformations:

As far as I am concerned, the QC model consists of exponentially-long vectors and some uniform operations on such vectors. The key point is that the associated complexity measure postulates that each such operation can be effected at unit cost. My main concern is with this postulate. My own intuition is that the cost of such an operation or of maintaining such vectors should be linearly related to the amount of non-degeneracy of these vectors, where the non-degeneracy may vary from a constant to linear in the length of the vector.

However, in the end he admits that he simply does not believe in the exponential speed-ups:

• I believe that our universe is not a miracolous one, allowing exponential speed-ups over the natural model of computation.
• ... in my opinion, those believing that a QC can manipulate or maintain huge objects free of cost should provide a convincing explanation to this fantastic speculation. Being skeptic of this speculation seems to be the default and natural position.

Details for 3: S. Wolfram stresses the point that only very few problems are known where QC offers exponential speed-ups:

But in fact only a very few other examples were found—all ultimately based on very much the same ideas as factoring.

and that even for those few problems where exponential speed-ups are expected, it remains unclear which idealizations have been used, and what might actually be needed to perform those quantum computations:

And even in the case of factoring there are questions about the idealizations used. It does appear that only modest precision is needed for the initial amplitudes. And it seems that perturbations from the environment can be overcome using versions of error-correcting codes. But it remains unclear just what might be needed actually to perform for example the final measurements required.

• The objections in #2 are mathematically meaningless. The author claims that intuitively, some unitary operations should be very expensive to perform, and gives no evidence why that should be. Moreover, it is already known how to perform the unitary operations needed for, e.g. Shor's algorithm, at the level of "direct laser pulses at atoms 1, 2, 3...". It is like saying intuitively, all sorting algorithms should take exponential time, because long unsorted lists look very confusing to the eye, and hence refusing to open an algorithms textbook. – knzhou Jun 11 '18 at 14:11
• Only #1 is a fair objection. Neither #2 or #3 contain any mathematical content, or even physical content. A vague philosophical unease is not a real objection, and if we took such unease seriously we would never have progressed beyond classical mechanics. – knzhou Jun 11 '18 at 14:16
• @PaulSiegel Surely that is what is being done right now, and there is definitely a lot of work to be done. My point is that most of the objections above are not even real objections, as they have perfectly straightforward answers that were figured out decades ago. It is like arguing classical computers can’t exist because they would inevitably get wet in the rain and stop working, when we know roofs exist. – knzhou Jun 11 '18 at 18:33
• @knzhou After the feedback, I started to add my own opinion about the objections to the answer. However, then I realized that dismissing Leonid A. Levin arguments, or explaining why I agree with Oded Goldreich objections (but not with his bias against exponential speed-up) is simply not a good idea for me. Those pieces are longer than just the quoted parts, and their authors play in a higher league than me. But perhaps you appreciate a good read by Craig Gidney: Why Will Quantum Computers be Slow? – Thomas Klimpel Jun 11 '18 at 20:22
• As for Leonid Levin's argument, my algorithm only requires exponentially precise amplitudes if you believe that the universe is a classical computer running a simulation of quantum mechanics. This seems to be what Levin believes. What it really needs is that the gates are exactly unitary (automatic in any kind of quantum universe) and that the amplitudes are reasonably close to the desired ones. (Maybe one part in $10^4$, depending on how much overhead you're willing to spend on error correction.) – Peter Shor Jun 14 '18 at 14:38

I don't see any mathematical arguments against QC in this thread and I don't see how there can really be any. Quantum mechanics as expostulated by von Neumann and others is an axiomatic mathematical theory, and "QC is a thing" is a theorem in that theory.

Does that theory actually describe the natural universe that we live in, precisely enough that QC is really physically possible? The objections to QC in this thread and elsewhere basically say "probably not". I can accept those arguments: classical mechanics is beautiful and precise, but breaks down at extreme scales, and maybe QM is the same way. But that's a scientific objection, not a mathematical one. It's probably more fruitful to ask for the physical arguments against QC.

I do know there are QC skeptics among physicists. I don't know if there are real believers ($\overset {def} =$ "a realizable quantum computer can factor 2048 bit RSA moduli with Shor's algorithm") among them. Theoretical computer scientists may have an easier time of it, since for them it's just a matter of working out the math.

• None, 1) It is good to think about "mathematical argument" here as a model + theorems about the model + interpretation of these theorems. 2) Failure of QC does not mean that QM must fail. See, e.g., the second paragraph in John Preskill's paper arxiv.org/abs/1207.6131 . – Gil Kalai Jun 14 '18 at 20:37
• @Gil: I believe that failure of QC means that the physical laws as we currently understand them must fail. Your conjectures add correlated noise to quantum mechanic processes in a way that is not described by the current equations of physics (although I don't know that it's ruled out by current physical experiments). – Peter Shor Sep 1 '18 at 20:47
• @PeterShor . Dear Peter, as I tried to emphasize in my answer here ( mathoverflow.net/a/302561/1532 ) about my approach, my argument regarding the failure of quantum computers does not rely on correlated noise but only on the ordinary models of noise that the fault tolerance theorems (starting with your theorem) use. (The conjectured modeling of correlated noise for entangled qubits, that I studied earlier, emerges from the failure of quantum fault tolerance.) My argument concerns the rate of noise and is based on two phenomena proved in my work with Guy Kindler on “Boson Sampling”. – Gil Kalai Sep 2 '18 at 16:31
• (cont.) It is reasonable to conjecture that these two phenomena extend to general NISQ (Noisy Intermediate Scale Quantum) systems and general forms of noise. This suggests bold predictions regarding near term experiments and also a good argument for why noisy NISQ systems dont support both supremacy and good quality quantum error correction. In addition to the links from my answer here, here is a relevant link to slides of my ICM2018 lecture. Please, have a look at them. gilkalai.files.wordpress.com/2018/08/kalai-icm2018.pptx . (slide 37 might be especially relevant to your comment.) – Gil Kalai Sep 2 '18 at 16:35
• Dear @PeterShor , The actual video of my ICM 2018 lecture can be found here youtu.be/oR-ufBz13Eg and naturally it gives more details than the slides. – Gil Kalai Sep 22 '18 at 19:07

Update: It can be useful to start this answer with a link to a 1998 paper of John Preskill Quantum Computing: Pro and Con, which responds to skeptical views by Serge Haroche, Rolf Landauer and others. Preskill's paper contains a table with 13 objections and responses that has some overlap with Aaronson's objections listed in Carlo Beenakker's answer and with Aaronson's list of responses listed in this answer.

Scott Aaronson wrote (in a 2006 blog post) 13 arguments for quantum computers and against the skeptical views. These 13 points involve both physics and mathematics (and mathematical challenges for skeptics), and also arguments of philosophical, historical, and sociological nature.

Scott's post was written upon the request of our friend, MO celebrity, Greg Kuperberg. To complement the answer by Carlo Beenakker, and give a wider view on Morteza Azad's question, let's go on to Scott's list of 13 pro quantum computer arguments:

1) The Obvious Argument. Quantum mechanics has been the foundation for all non-gravitational physics since 1926.

2) The Experimental Argument. Impressive experimental progress had been demonstrated.

3) The Better-Shor-Than-More Argument. Skeptical alternatives may well lead to computational powers beyond the ability of quantum computers rather than reinstating the Extended Church-Turing Thesis.

4) The Sure/Shor Argument. Skeptics should present unreacheable quantum states.

5) The Linearity Argument. Linearily of quantum mechanics refutes the analogy with analog computers. (Point 6 in Scott's other list.)

6) The Fault-Tolerance Argument. The Threshold Theorem states that even if a quantum computer is subject to noise, we can still use it to do universal computation.

7) The What-A-Waste Argument. If quantum mechanics were an accurate description of reality, yet quantum computing was still impossible then we’d have to accept that Nature was doing a staggering amount of quantum computation that could never be “extracted.”

8) The Non-Extravagance Argument. The computational power of quantum computers is stronger than the usual ones, but not so strong that it encompasses NP-complete problems.

9) The Turn-The-Tables Argument. If building quantum computers that outperform classical ones is fundamentally impossible, then it must be possible to write classical computer programs that efficiently simulate any quantum system found in Nature (such as superconductors and quark-gluon plasmas).

10) The Island-In-Theoryspace Argument. It seems all but impossible to change quantum mechanics while retaining its nice properties.

11) The Only-Game-In-Town Argument. No picture of the world in which quantum computing is impossible, is being actively developed by any research community anywhere.

12) The Historical Argument. It took many generations between the time that ideas for "airplanes" and "computers" were conceived and the time these ideas where implemented.

13) The Trademark-Twist Argument. What is BQP, if not P=BPP with Nature’s trademark little twist?

One possibility that hasn't been mentioned is $\text{P} = \text{BQP}$. This would constitute a mathematical argument "against" quantum computing because it means classical computing is just as powerful — in this world quantum computers are possible, but we don't need them. In contrast to the quote from Scott Aaronson in Carlo Beenakker's answer, this resolution would involve no new physics, but it would still be an exciting and unexpected outcome.

• How is $P=BQP$ an "argument"? It's an unsolved hypothesis which is (AFAIK) believed to be false. – Wojowu Jun 12 '18 at 19:00
• The argument is the fact that it's unsolved not the statement itself. – Dan Brumleve Jun 12 '18 at 19:56
• It doesn't matter whether $P = BQP$ or not. Even if $P=BQP$, quantum computing could be much faster than classical computers ... definitely for Grover's algorithm, and there might be even better speedups, depending on the proof of $P = BQP$. If a classical algorithm took $n^{10}$ and a quantum algorithm $n^2$, then you might want to run the quantum algorithm in practice. – Peter Shor Jun 12 '18 at 22:20
• To complement Peter's answer. A technical point: P=BQP does not mean that (up to polynomial reductions) classical computing is as powerful as quantum computing, because, e.g. sampling problems that quantum computers can perform likely represent stricktly larger complexity class. See here scottaaronson.com/blog/?p=3827#comment-1767741 . And I am not even sure that sampling problems is the end of the road. Maybe there are even harder algorithmic tasks that QC can perform, and "P=Q" goes beyond QSAMPLING in P? ( Scott would know.) – Gil Kalai Jun 13 '18 at 20:30
• Also it is a tricky question when you say "A mathematical theorem X is an argument for Y". For example, if X= "Peter Shor's famous factoring theorem", for many people X was an argument for "Computationally superior quantum computers is a possibility!", for some people X was an argument "against quantum computers" and yet for other people X was an argument for "classical polynomial algorithm for factoring ". It was perfectly rational to regard X as an argument for all these statements inspite of some tensions between them. – Gil Kalai Jun 13 '18 at 20:43

Adding to the arguments on the possible theoretical (dis)advantages of quantum computers in comparison with the classical ones in this thread, let me mention that a recently published paper of Ran Raz and Avishay Tal titled "Oracle Separation of BQP and PH" provides some theoretical ground in favor of quantum computers.

[They] defined a specific kind of computational problem. They prove, with a certain caveat, that quantum computers could handle the problem efficiently while traditional computers would bog down forever trying to solve it.

Computer scientists have been looking for such a problem since 1993, when they first defined a class of problems known as “BQP,” which encompasses all problems that quantum computers can solve.

Since then, computer scientists have hoped to contrast BQP with a class of problems known as “PH,” which encompasses all the problems workable by any possible classical computer — even unfathomably advanced ones engineered by some future civilization. Making that contrast depended on finding a problem that could be proven to be in BQP but not in PH. ...

(cf. Quanta Magazine: Finally, a Problem That Only Quantum Computers Will Ever Be Able to Solve)

I wrote a paper "Why do we live in a quantum world" that assumes that "Quantum mechanics is just an approximation to some deeper theory", which is number 8 in Scott Aaronson's list of eleven objections to quantum computing (shown in another answer).

My paper shows, using a very interesting result by Hall and Reginatto published in 2002, that if one assumes that our universe is a digital computer (which Konrad Zuse and Edward Fredkin hypothesized around 50 years ago) that attempts to simulate the laws of classical Newtonian mechanics as well as it can given the fact that it only has a finite amount of memory, then the laws of physics will be an approximation of quantum mechanics. I call this new theory digital mechanics in my paper.

Furthermore, I show that one can test whether digital mechanics is true by attempting to build a large-scale quantum computer that can factor integers - if one is successful in building such a machine, then digital mechanics is false. And if one does everything possible to successfully build such a machine but is nevertheless unsuccessful in building one, then digital mechanics is confirmed and quantum mechanics is only an approximation. This is all based on the assumption that it is impossible to efficiently factor integers on a digital computer, which is generally believed to be true.

The fact that Google has recently announced that it has built a 72 qubit quantum computer (but has not calibrated or tested it yet) is very exciting to me, because such a machine seems large enough to test the digital mechanics hypothesis. If Google's quantum computer is successful, then digital mechanics is probably false and if Google's quantum computer is unsuccessful, then this would be confirmation that digital mechanics true. I hope we find out soon.

According to the quantum computing experts, quantum computing must be possible in principle if quantum mechanics is correct, so I do not see how any of Scott Aaronson's list of 11 objections to quantum computing are valid except for number 8, "Quantum mechanics is just an approximation to some deeper theory". Full disclosure: I used to believe some of the other objections, but not anymore after talking with some quantum computing experts.

• This is a fascinating answer, but strange. If the universe is a digital simulation, where do the laws of physics come from in the "real" universe? It would make more sense to me that there is some underlying digitization, but ascribing that to being in a simulation does not seem like a scientific theory to me. Also, I take issue with the statement "And if one is does everything possible to successfully build such a machine but is nevertheless unsuccessful in building one, then digital mechanics is confirmed and quantum mechanics is only an approximation." I agree that a working quantum... – Jim Conant Jun 16 '18 at 4:03
• ...computer could disprove digital mechanics, but failure to make one work could hardly be said to confirm it. There could be many reasons that we fail to build a working quantum computer...for example a different alternative deeper theory. – Jim Conant Jun 16 '18 at 4:05
• This theory is actually based on an absurd misinterpretation and is not appropriate for Mathoverflow. This shouldn't be very surprising as the linked paper is actually on viXra. It hypothesizes that the Heisenberg uncertainty principle comes from a computer economizing on storage space, with a given number of bits to store position and momentum. It then relies on work of Hall and Reginatto which derives the Schrodinger equation from a form of the uncertainty principle. – Will Sawin Jun 16 '18 at 9:56
• But the notion of position uncertainty that Hall and Reginatto use is endogeneous, it depends on the probability that the particle is at a given point. For instance, the interference patterns in the double-slit experiment are caused by the contributions to the position uncertainty from the trajectories passing through the other slit. So calculating it requires summing over all possible trajectories of the particle - much more resource-intensive than any possible savings from economizing on memory. – Will Sawin Jun 16 '18 at 9:58
• Also the hypothesis does not make the correct positions in the multi-particle setting. Because individual particles do not follow the uncertainty principle, we would have to assume that the computer dynamically reallocates memory for one particle based on, not just uncertainty in its position, but correlations with other particles' positions. Also there is no explanation given for spin and other finite-dimensional Hilbert spaces appearing in quantum mechanics as an approximation of any classical phenomenon, and presumably no such explanation is possible. – Will Sawin Jun 16 '18 at 10:05

A general caution regarding arguments for QC

When quantum mechanics was first formalized in its early days (Schrodinger, Heisenberg, et. al.), it was paradigm-busting. Specifically, quantum mechanics broke classical mechanics and showed that our world, at certain scales and certain energy levels, simply cannot be accurately described by the laws of classical mechanics. In fact, classical mechanics is wildly wrong (black-body radiation, Bell's inequality) or leads to insoluble paradoxes (Schrodinger's cat, two-slit experiment).

I have noticed an implicit (though never explicit) thread running through discussions of the coming of quantum computing, making an analogy between the paradigm-busting of classical mechanics, and a coming paradigm-bust of classical computation. This is especially pronounced in the popular-science rags, where I frequently encounter incorrect claims along the lines of: "Quantum computers soon to solve problems that are impossible to solve on classical computers!"

The mistake in this line of reasoning is most easily seen by comparing and contrasting classical information theory (Shannon), and quantum information theory (QIT). (Note: Classical computation can be recast as an extension of classical information theory -- a bit is a bit is a bit.) There is an important, metaphysical difference between classical mechanics and classical information theory: classical mechanics was a theory of what the world is (an ontic theory), classical information theory is a theory of how the world looks (a phenomenal theory) to classical beings (such as humans). Thus, classical information theory -- and, by extension, classical computation -- cannot be busted by quantum information theory (by extension, quantum computation) because quantum mechanics is itself a phenomenal theory (a theory of how the world looks or behaves in response to stimuli). Classical information theory may be, nay is, an incomplete theory of information in a quantum universe, but it is not an incorrect theory of information in a quantum universe. Thus, quantum theories of computation can only extend but never contradict classical theories of computation.

Attempting to bound the computational capacity of a quantum computer based on classical theory is a fruitless endeavor. The classical cost of transporting a bit from one point in space to another point in space can tell me nothing about the quantum cost except, perhaps, as an upper bound (it could never have to cost more to transport a bit by quantum means than classically). Thus, the limits of classical computation can only ever apply with the proviso "... on a classical computer". And, as Goldreich points out on his website, the achievable computational capacity of a quantum computer remains an unknown. I often sense that QC proponents are over-extrapolating the principles of quantum mechanics, failing to leave room for the discovery of other physical principles that may come to bear when QC is scaled up from a few dozens of qubits to hundreds or thousands of qubits.