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.

I asked a related question over at quantumcomputing.SE that might provide some useful references: https://quantumcomputing.stackexchange.com/questions/1622/what-is-the-argument-that-practical-quantum-computers-cannot-be-built — Ben Burns, Jun 11 '18 at 02:49
By the way, while there are some physics-related tags such as quantum-field-theory and quantum-mechanics, I couldn't find any quantum-computing tag to add to this post. As a sub-branch of computation theory, it sounds mathematically relevant to me. — Morteza Azad, Jun 11 '18 at 06:18
The quantum-computation tag exists, and I added it (at the expense of the computer-science tag, because there is a limit of 5). — Carlo Beenakker, Jun 11 '18 at 06:36
@CarloBeenakker (+1) Oh! How careless of me! Thank you for the edit, Carlo! :-) — Morteza Azad, Jun 11 '18 at 07:28
Naively I believed that the main problem against quantum computer was the absence of quantum error correction until Peter Shor found out such an algorithm. — Philippe Gaucher, Jun 11 '18 at 08:24
Peter Shor's seminal paper on quantum error correction is at https://journals.aps.org/pra/abstract/10.1103/PhysRevA.52.R2493 — Carlo Beenakker, Jun 11 '18 at 19:00
https://rjlipton.wordpress.com/2011/01/23/is-factoring-really-in-bqp-really/ — Turbo, Jul 22 '18 at 23:36
Will we ever have a quantum computer? https://link.springer.com/book/10.1007/978-3-030-42019-2 — Michel Dyakonov, Apr 22 '20 at 10:31

Gil Kalai · Answer 1 · 2018-06-11T20:03:19.933

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 03: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
To understand what NISQ computers = Noisy Intermediate Scale Quantum computers mean, replace Q by C: Noisy Intermediate Scale Classical computers. Then it will become evident that this NISC computer is just a piece of junk, that cannot calculate anything at all. Same for NISQ computers — Michel Dyakonov, Aug 05 '20 at 17:29

Carlo Beenakker · Answer 2 · 2019-09-24T12:22:00.757

46

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:

Works on paper, not in practice.
Violates Extended Church-Turing Thesis.
_{Perhaps the most precise objection from a mathematical point of view. Here is an extended discussion.}
Not enough "real physics."
Small amplitudes are unphysical._{Leonid Levin's objection}
Exponentially large states are unphysical._{Paul Davies' objection}
Quantum computers are just souped-up analog computers._{Robert Laughlin's objection}
Quantum computers aren't like anything we've ever seen before._{Dyakonov's objection}
Quantum mechanics is just an approximation to some deeper theory.
Decoherence will always be worse than the fault-tolerance threshold._{Gil Kalai's objection}
We don't need fault-tolerance for classical computers.
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.

edited Sep 24 '19 at 12:22

answered Jun 10 '18 at 21:37

Carlo Beenakker

177,695

28

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
23

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 00:16
1

@Suvrit: You have to click on the link to Scott Aaronson's blog to get a more detailed story, although even there, the discussion is rather vague. – Jim Conant Jun 11 '18 at 02:55
20

My argument falls under Scott's point 9. (Point 11 is also part of the picture.) – Gil Kalai Jun 11 '18 at 05:42
8

How is the (extended) Church-Turing thesis point precise mathematically? – Wojowu Jun 11 '18 at 07:24
8

This list needs a little more curation. At least half of the objections are clearly meaningless. – knzhou Jun 11 '18 at 14:06
5

@JimConant of course; I've read Scott's blog post and visit his blog now and then; however, this answer does not answer the original question at all, and leaves one longing desperately for some math :-) – Suvrit Jun 11 '18 at 19:49
2

There is a sort of a (proposed) "cousin" on the extended Church-Turing thesis (ECT) that plays a role in my analysis. The principle is "asymptotically-low-level computational devices cannot lead to superior computations." It is applied in the NISQ-regime. This putative principle is of interest both for algorithms and for physical systems. Unlike the ECT, the main application is for low computational power so we do not depend on CC conjectures. I asked about it here https://cstheory.stackexchange.com/questions/27312/practically-good-algorithms-of-a-very-low-computational-complexity-class – Gil Kalai Jun 13 '18 at 16:02
@Carlo I don't understand why you say that the "quantum supremacy" talk by Google has anything to do with violating the Extended Church-Turing thesis. – Nike Dattani Oct 11 '19 at 14:13
that's how Scott Aaronson interprets the implications of the Google experiment: "Quantum mechanics appears to violate the Extended Church-Turing Thesis." – Carlo Beenakker Oct 11 '19 at 15:12
Quantum computers aren't like anything we've ever seen before.(Dyakonov's objection). - This is a nonsensical product of Aaronson's fantasy. Should I reply by: :"Aaronson believes in quantum computing because they aren't like anything we've ever seen before"

Michel Dyakonov

Apr 06 '20 at 11:43

Dear @CarloBeenakker. 1) It is an interesting (and delicate) question weather the "quantum supremacy" experiments violate the extended Church-Turing hypothesis. 2) Successful "quantum supremacy" experiments do refute my argument and my predictions. 3) The 2019 "quantum supremacy" claims appears now to be refuted by quick classical algorithms and doubts were raised about other aspects of those experiments. – Gil Kalai Nov 21 '21 at 04:35

score 28 · Answer 3 · answered Jun 11 '18 at 07:49

28

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

Polynomial Time and Extravagant Models by Leonid A. Levin
On Quantum Computing by Oded Goldreich
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.

answered Jun 11 '18 at 07:49

Thomas Klimpel

2,444

I like the first point in particular. Most expositions of Shor's algorithm present it as working using "perfect arithmetic", but I haven't seen before a single one which would mention how much precision we actually need. – Wojowu Jun 11 '18 at 13:32
13

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
The objections in #3 are also meaningless; the final measurement step in a quantum algorithm is perfectly straightforward and not unlike any other quantum measurement. – knzhou Jun 11 '18 at 14:12
5

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
1

@knzhou If someone claimed before the first classical computer were built that it would be possible to alphabetically sort all of the words in Shakespeare in $O(n \log n)$ time, my response would be "Mergesort is a cool idea, but the burden of proof is on you to show that you can build machinery which can store and manipulate that quantity of data in a sufficiently reliable way, and that the constants are practically reasonable." This skepticism would also have been the "default and natural position" even though the objection was eventually overcome after decades of hard engineering. – Paul Siegel Jun 11 '18 at 18:17
5

@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
1

@knzhou My knowledge of quantum computing is shallow and a bit dated, but my understanding is that Goldreich's core concern is a bit more serious than that. For instance, if the straightforward answer is "quantum error correction" then I'm not sure it is known whether experimentally validated techniques actually can scale in practice. Extending your metaphor, the existence of the traditional roof isn't good enough if the design specs call for direct sunlight, or can only be installed underneath the Niagra Falls. But I don't know the practitioners' side very well, so I can't be sure. – Paul Siegel Jun 11 '18 at 19:12
1

@PaulSiegel That's a fair concern but that was not my reading. My impression is that, as quoted here, he "attacks the assumption that arbitrary unitary transformations" can be done. It is certainly true that it is hard to approximate an arbitrary unitary, but the whole point of Shor's algorithm is that we know perfectly well how how to implement it with a small number of gates; showing this would be the second thing in any lecture on it. Many of the objections posted here seem to come from a very cushy armchair. – knzhou Jun 11 '18 at 19:59
5

@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
3

@ThomasKlimpel That linked piece is, in my opinion, a much better take on the subject! Thanks for showing me it. – knzhou Jun 11 '18 at 20:28
However, I'm curious: if one objection is it requires a million decimal agreement, could this not be considered a good thing at least for pure science, anyways - it would offer the most stupendously accurate tests of a physical law we could possibly imagine bar none, and thus if there are any "trans-quantum" effects in the world this could provide a key experimental access point to them? – The_Sympathizer Jun 12 '18 at 07:41
@PaulSiegel maybe not the best example since plenty of skepticism is still warranted about which models are realistic. In the multi-tape and RAM models an issue is how can memory fetches or tape-head communication happen in polynomial time with a speed limit of c? But in single-tape model, mergesort is super-quadratic. – Dan Brumleve Jun 12 '18 at 20:51
10

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
Oded Goldreich's argument also seems to be based on the idea that the universe is somehow a classical computer (or similar machine) running a simulation of quantum mechanics. – Peter Shor Jun 14 '18 at 18:19
1

@PeterShor Oded Goldreich's argument is not so much based on a "wrong" idea of the universe, as it is based on skepticism as the default position. Scott Aaronson calls this a "hands-off" approach, but he nevertheless tries to argue why Goldreich's views are wrong in the end: I demonstrate that gratitude by explaining why Goldreich’s views about quantum computing are wrong! Note that Aaronson agrees that quantum states really are exponentially-long vectors, but he argues that the same is true for a classical probability description of n particl – Thomas Klimpel Jun 14 '18 at 23:23
@Thomas Klimpel: Goldreich says "those believing that a QC can manipulate or maintain huge objects `free of cost' (i.e., at unit cost) should provide a convincing explanation to this fantastic speculation." I think this idea that arbitrary exponential-length vectors are huge objects that are expensive while some "degenerate" exponential-length vectors can be manipulated easily shows that Goldreich's mental model is that of a classical computer simulating a quantum mechanical universe. – Peter Shor Jun 15 '18 at 11:01
@PeterShor I should not talk for Goldreich. He discussed with Aaronson, so his reaction should give some indications about the real issues. That said, I do agree that the unit cost assumption is questionable. In a classical computer, I can plug-in additional memory chips to increase the memory. The idealization that this won't increase the cost of basic operations makes sense to me. But I doubt that it will be possible to increase the memory of a quantum computer like that. Hence the unit cost idealization feels questionable to me, even if assuming exponential costs would be just as wrong. – Thomas Klimpel Jun 15 '18 at 18:48
I had some email discussion with Levin. He says that his argument isn't based on the idea that the universe is classical at base, but he wasn't able to explain his argument so that I could understand it. – Peter Shor Jul 05 '18 at 03:17
"QM says that certain things are not impossible, but it does not say that every thing that is not impossible is indeed possible." Actually, it literally does https://en.wikipedia.org/wiki/Totalitarian_principle – Zemyla Mar 23 '20 at 04:18

Gil Kalai · Answer 4 · 2018-06-23T17:57:33.780

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?

Thank you for adding this comprehensive additional answer explaining Scott's points, Gil! I really enjoyed reading this summary. — Morteza Azad, Jun 17 '18 at 16:16

score 12 · Answer 5 · answered Jun 14 '18 at 05:36

12

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.

answered Jun 14 '18 at 05:36

none

121

5
None, 1) It is good to think about "mathematical argument" here as a model + theorems about the model + interpretation of these theorems.
1. Failure of QC does not mean that QM must fail. See, e.g., the second paragraph in John Preskill's paper https://arxiv.org/abs/1207.6131 .
– Gil Kalai Jun 14 '18 at 20:37
5

@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 01 '18 at 20:47
@PeterShor . Dear Peter, as I tried to emphasize in my answer here ( https://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 02 '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. https://gilkalai.files.wordpress.com/2018/08/kalai-icm2018.pptx . (slide 37 might be especially relevant to your comment.) – Gil Kalai Sep 02 '18 at 16:35
@GilKalai: There seem to be two ways the quantum fault-tolerance theorem can fail. (a) correlated noise. (b) noise that is too large for the theorem to apply. I think experiments already show that (b) is unlikely (since there are variations of the theorem which have quite high thresholds, but which have ridiculously huge, although polynomial overheads). – Peter Shor Sep 02 '18 at 17:40
@Peter : 1) my argument (slides 33-36) is precisely why you cannot get below the fault-tolerance threshold (in terms of qubit noise rate, and gate noise rate and form).Yes this is (b); Regarding predictions from current experiments see slides 30-32. I dont share your optimism (but we will both be wiser in the next months/years) 3) When I say "need mathematical formulation..." I refer to my papers for more details. (Surely, more can be done.) We share the view (but not everybody) that if QC fails there is a lot to be learned. Your statement is a bit too strong. See John's wording. – Gil Kalai Sep 02 '18 at 17:42
1

Dear @PeterShor , The actual video of my ICM 2018 lecture can be found here https://youtu.be/oR-ufBz13Eg and naturally it gives more details than the slides. – Gil Kalai Sep 22 '18 at 19:07

score 6 · Answer 6 · edited Jun 15 '20 at 07:27

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)

score 5 · Answer 7 · answered Jun 12 '18 at 18:42

5

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.

answered Jun 12 '18 at 18:42

Dan Brumleve

2,254

6

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
2

The argument is the fact that it's unsolved not the statement itself. – Dan Brumleve Jun 12 '18 at 19:56
16

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
It's a good point, but it still matters, because we need additional assumptions to compare fine-grained complexities. For example, what does it mean to say a classical algorithm takes $O(n)$ time? (See my comment below Thomas Klimpel's answer.) – Dan Brumleve Jun 12 '18 at 22:38
4

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 https://www.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
5

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

Michel Dyakonov · Answer 8 · 2019-10-24T11:17:02.920

5

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?

edited Oct 24 '19 at 11:17

answered Oct 24 '19 at 11:06

Michel Dyakonov

69

7

My response is that asking whether a quantum computer is analog or digital is asking like whether an electron is a wave or a particle—it has some properties of each. In particular, error correction works in theory much better for quantum computers than for analog computers. – Peter Shor Oct 24 '19 at 12:49
1

In theory - yes, but not in practice. Maybe the theory misses some features of the real world? – Michel Dyakonov Oct 24 '19 at 13:07
2

... or possibly quantum computers don't have the accuracy yet to implement error correction. – Peter Shor Oct 24 '19 at 13:10
1

Like any theory, the error correction scheme is based on certain assumptions. Which cannot be fulfilled in our world. Maybe elsewhere... – Michel Dyakonov Oct 24 '19 at 13:14
Dear Peter, Can you estimate what accuracy in gates, and measurements is required to implement reliable error correction? With what precision should the direction of the z-axis be defined? With what precision the energies of the up and down states should be equal? If not, there will be a free evolution with frequency (E_up - E_down)/h. For an electron spin in the Earth's magnetic field this frequency is 1MHz. Have we to screen this magnetic field and if yes, with what accuracy? There is quite a lot of similar questions without any answers. – Michel Dyakonov Oct 24 '19 at 13:58
2

We can indeed estimate the accuracy needed, assuming that the errors in quantum gates are independent. If we don't assume that, we have to show that very slight correlations in quantum gate errors don't conspire to add up in just the wrong way to derail the quantum computation. This might be very difficult to prove in theory. Experiment will show whether this happens. – Peter Shor Jan 26 '20 at 19:36
Math is clear and beautiful. On the contrary, life and the physical world in general are messy. One cannot address personal life problems with math because any assumptions one might make will be wrong. The same applies to the physical world. Only a good understanding (as good as possible) of the physical world can tell us what is possible and what is not possible – Michel Dyakonov Feb 06 '20 at 15:16

score 2 · Answer 9 · answered Jul 17 '18 at 21:00

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.

I fully agree with "Attempting to bound the computational capacity of a quantum computer based on classical theory is a fruitless endeavor." In my opinion the great difference between classical and quantum computing is that in the latter case we must deal with continuous variables. As we know from experience, an on/off switch is very reliable, it might fail only after many thousands of operations. In contrast, errors in qubits are inevitable from the start: not a single operation can be exact. So the real question is: what precision in needed? Is 1% sufficient, or do we need 10^(-10)? — Michel Dyakonov, Nov 10 '19 at 17:36

Craig Feinstein · Answer 10 · 2018-06-18T16:47:05.873

0

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.

edited Jun 18 '18 at 16:47

answered Jun 15 '18 at 16:32

Craig Feinstein

2,549

1

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 04:03
3

...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 04:05
7

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 09:56
4

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 09:58
4

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
Jim Conant, it is true that a deeper alternative theory could also explain why we could fail to build a large scale quantum computer, but if one goes by Occam's razor, digial mechanics would be the simplest and therefore the best theory. After all, it is even simpler than quantum mechanics. – Craig Feinstein Jun 17 '18 at 01:54
Will Sawin, your objection makes no sense. First of all the fact that my paper was published as a preprint on vixra (instead of arxiv) does not imply anything about whether it is correct or not. There are bad papers on arxiv and bad papers on vixra and also good papers on both. – Craig Feinstein Jun 17 '18 at 02:09
Will Sawin, calculating the interference patterns of the double slit experiment are not resource intensive at all. Feynman shows you how to do it on the first pages of the 3rd volume of his lectures. You do not need to use his famous path interval to do this. – Craig Feinstein Jun 17 '18 at 02:19
Will Sawin, particle spin is a consequence of special relativity combined with quantum mechanics. My paper only talks about the Newtonian situation. As for how things generalize to quantum field theory, simply read more Hall and Reginatto papers. Your comment about individual particles not following the uncertainty principle also does not make sense. Everything in QM is subject to the uncertainty principle. – Craig Feinstein Jun 17 '18 at 02:39
@WillSawin: thanks for the additional clarification. – Jim Conant Jun 18 '18 at 16:05
@JimConant, Will Sawin has answered a question of mine before on mathoverflow, so I take what he says seriously, even though I completely disagree with him in this instance. Could you please enlighten me as to how he clarified things for you? Maybe I am misunderstanding something. – Craig Feinstein Jun 18 '18 at 22:41
I claimed above that "particle spin is a consequence of special relativity combined with quantum mechanics." But it is actually not so simple. See http://quantumchymist.blogspot.com/2014/04/is-spin-relativistic-effect-l-and-first.html – Craig Feinstein Jun 22 '18 at 16:43
1

@CraigFeinstein Sorry, I meant individual particles don't follow the Schrodinger equation, not that they don't follow the uncertainty principle. Furthermore, while it's true that the interference pattern is not hard to compute, your claim requires in addition to that, that the interference pattern arise from a reasonable computational approximation to classical mechanics, which you have not demonstrated. – Will Sawin Jun 26 '18 at 11:13
1

@CraigFeinstein A priori, reproducing the double split with a computational approximation to classical physics seems unlikely, as it requires keeping track of both possible particle paths at once (to see whether the path was measured), which is memory intensive. This is only a factor of 2 increase, so it doesn't necessarily make it hard to compute in practice. But it does make it hard to see how it could arise as an approximation. – Will Sawin Jun 26 '18 at 11:19
@WillSawin, When you said, "individual particles don't follow the Schrodinger equation", I assume you mean that one can only see the probability distribution described by the Schrodinger equation when one observes an ensemble of particles. – Craig Feinstein Jun 26 '18 at 16:30
@WillSawin, you said, "your claim requires in addition to that, that the interference pattern arise from a reasonable computational approximation to classical mechanics, which you have not demonstrated." My claim is that if one assumes that the universe is a digital computer that attempts to simulate the laws of Newtonian mechanics as well as it can, then the laws of physics will be an approximation of QM; I never say anything about a "computational approximation to classical mechanics". – Craig Feinstein Jun 26 '18 at 16:44
1

@CraigFeinstein 1. No, I mean the evolution of the probability distribution for two particles, even if they don't interact, differs from the independent evolution of the probability distribution for two particles each described by their own Schrodinger equation. 2. If a digital computer attempts to simulate the laws of Newtonian mechanics as well as it can, the result would be something I would describe as a "computational approximation to classical mechanics". – Will Sawin Jun 26 '18 at 16:57
@WillSawin 1. That is correct, but only if the two particles interact. 2. OK, I will assume that is what you mean when you say "computational approximation". You said above that you did not see how the interference pattern of the double slit experiment arises from a "computational approximation" to classical mechanics. But I'm claiming that it does, since it satisfies Schrodinger's equation and it is easy to compute. (If it were difficult to compute, the computer generating the universe would have to compute something different than Schrodinger's equation, perhaps just noise.) – Craig Feinstein Jun 26 '18 at 17:27
1

@CraigFeinstein 1. Even if they aren't interacting currently, it is impossible to treat them independently if they interacted at any point in the past. 2. You propose that the Schrodinger equation arises from dynamically allocated memory for particles positions and velocitie in a Newtonian simulation. But then you propose that the computer, in the case of the double-split experiment, doesn't use this method, but instead uses a different computational procedure to simulate Schrodinger. But why doesn't it simply simulate the Newtonian version, which is also easy in this case? – Will Sawin Jun 26 '18 at 17:44
Let us continue this discussion in chat. – Craig Feinstein Jun 26 '18 at 18:58

score 0 · Answer 11 · answered Mar 02 '20 at 16:26

0

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...

answered Mar 02 '20 at 16:26

Michel Dyakonov

69

https://www.springer.com/gp/book/9783030420185 – Michel Dyakonov Mar 02 '20 at 16:28
4

After three hundred years of hard work by thousands of researchers, there was no proof of Fermat's Last Theorem. – Gerry Myerson Mar 02 '20 at 22:18
Thus we still don't know whether this theorem is correct, or not. – Michel Dyakonov Mar 03 '20 at 09:50
3

Well, we didn't, until Wiles & Taylor proved it, 25 years ago. – Gerry Myerson Mar 03 '20 at 10:55
I didn't know about this. OK then. – Michel Dyakonov Mar 03 '20 at 14:09
However, math and physics are very different – Michel Dyakonov Mar 03 '20 at 14:10
3

Yes, they are. But are you saying there have never been any problems in physics that were open for a quarter of a century (or longer) before finally being solved? – Gerry Myerson Mar 03 '20 at 21:39
2

Certainly there were such problems. The great difference with the current situation is that those researchers and the media did not announce every day and everywhere that their future results will change our world forever (although in some cases such changes did indeed occur) – Michel Dyakonov Mar 04 '20 at 10:03

On mathematical arguments against Quantum computing

11 Answers11

Linked