On mathematical arguments against Quantum computing

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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?

Answer 5

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.

Answer 6

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)

Answer 7

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.

Answer 8

Aaronson attributes to me the absolutely nonsensical Objection 7: Quantum computers aren't like anything we've ever seen before.(Dyakonov's objection).

This is entirely a product of his imagination, I have never said or written anything of this kind. What I did say (in a nutshell), is that the hypothetical quantum computer is certainly an analog machine, operating with a huge (very huge) number of continuous parameters, the quantum amplitudes, and doing this with the required precision is hardly possible. After 20 years of efforts by an army of researchers, it is still not possible to honestly factor 15 by Shor's algorithm (which was the starting point of the whole field). Doesn't this tell us something about the future of quantum computing?

Answer 9

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.

Answer 10

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.

Answer 11

There can't be any mathematical arguments against a mathematical theory based on a set of axioms, if there are no mathematical mistakes in this theory. I am quite sure that there are no mistakes. However, the real question is not about that, but rather, whether the quantum computer can be constructed in the physical world we live in. My answer is a definite NO, because not one of the basic axioms can be fulfilled exactly, but only within some limited precision, while the general state of a quantum computer with N qubits is defined by an exponential in N number of parameters. If those parameters are not exactly equal to what the theory assumes them to be (i.e. most of them are exactly zero), the physical computer will crash.
The observable experimental fact is that after a quarter of a century of hard work by thousands of researchers, there still is no error correction, and it is still not possible to factor 15 by Shor, i.e. that there are NO results in practical quantum computing. There are no indications that this situation is going to change in a forseeable future...