If Quantum Computers are not Possible Why are Classical Computers Possible?

As most of my readers know, I regard quantum computing as unrealistic. You can read more about it in my Notices AMS paper and its extended version (see also this post) and in the discussion of Puzzle 4 from my recent puzzles paper (see also this post). The amazing progress and huge investment in quantum computing (that I presented and update  routinely in this post) will put my analysis to test in the next few years.

Guy Kindler and I identified a very primitive complexity class LDP that describes noisy quantum systems in the small scales (few bosons, qubits etc.) 

Today I would like to discuss, with the help of illustrations, a central issue in the debate about quantum computing: In view of a putative impossibility (and obvious difficulty) of quantum computing, why  is classical computing possible (and so ubiquitous)? This was a major challenge that Aram Harrow raised in our 2012 debate (in this post), and it goes back to Dave Bacon and others. My 2014 work with Guy Kindler on noisy BosonSampling (taking them as an analogy for noisy quantum circuits) leads to a fairly detailed answer that I will explain below, mainly with illustrations.

The picture behind the question

A common view: in principle, there is no difference between achieving quantum computing via quantum error-correcting codes and achieving classical computing via classical error-correcting codes. 

Why are classical information and computation possible?

Encoding by repetition, and decoding by “majority” are both supported by low degree polynomials

Encoding by repetition refers to a logical ‘one’ encoded by many physical ones and the same with zero.  Approximate version of majority enables decoding. Both encoding and decoding are supported by low degree polynomials. (A variant which is more realistic is that one is encoded by 70% ones (say) and zero by 30% ones.)

Why are robust quantum information and quantum computation impossible?

It is commonly expected that creating good-quality quantum error correcting codes is harder than demonstrating quantum supremacy.

Unlike the repetition/majority mechanism which is supported by very primitive computational power, creating a quantum error correcting code and the easier task of demonstrating quantum supremacy are not likely to be achieved by devices which are very low-level in terms of computational complexity.

This is the difference!

(Quantum supremacy refers to the ability of quantum computers to perform computations which are infeasible for classical computers. )

The computational complexity picture

Bounded depth computation () is an extremely primitive computational complexity class. Sampling tasks that can be performed approximately by low degree polynomials represent an even more primitive computational task. (The proof that LPD is in is quite clever but seems to Guy and me quite irrelevant to quantum computing 🙂 )

LDP is so low-level that it allows efficient learning!

(This leads to the following prediction: distributions coming from pure quantum states that can be approached by noisy quantum devices  allows efficient approximate learning.)

The underlying principles

Very simple, isn’t it?

The notion of “primitive computational devices” in both principles applies to the asymptotic behavior. The second principle extends to quantum devices that do not involve quantum error-correction.

Can you be a little more formal?

Let me try. (Trying to understand how insights from the theory of computation relate to real life computation is quite important.)

I don’t know how general is this insight. (I asked about it in TCSoverflow.) Note that this insight gave the rationale for the threshold theorem to start with.

My older stuff about correlated errors

My earlier work (Section 6 of the Notices paper, and earlier works cited there) proposes other goals that appear to be  easier than creating quantum error correcting codes and I expect them to be impossible.

The remarkable IBM machine applies two-qubit CNOT gates. One can expect that errors for the gated qubits have large positive correlation. This is not controversial but it would be nice to check it.

You can implement CNOT gate indirectly by a chain of other gates. I expect that it will not be possible  to reduce the positive correlation by a process that reaches the CNOT indirectly.  (You can experience the IBM quantum computer  here.)

A question by Ady Stern

It is a positive and not terribly small constant!  I am not sure what “fundamental” means.

(Sometimes, I get corrected when I pronounce my name correctly.)

The quality of my argument

But maybe the processes for quantum error-correction have more than meets the eye?

Why not just improve the physical qubits?

Q: But why can’t you simply create good enough qubits to allow universal quantum circuits with 50 qubits?

A: This will allow very primitive devices (in terms of the asymptotic behavior of computational complexity) to perform superior computation.

Q: This is an indirect explanation. Can you give an explanation on the level of a single qubit?

A: Yes, if the qubit is of too high quality, the microscopic process leading to it also demonstrates a primitive device leading to a superior computation.

Topological quantum computing?

What about topological quantum computing?

See this videotaped lecture.

Is Nature a malicious opponent of quantum computing?

My model of errors is precisely the ordinary model.

What do you mean by “primitive computational devices”?

The fate of Quantum Mechanics

What about the huge efforts and resources for building quantum computers or intermediate tasks?

Also the Commonwealth Bank

I talked about the problem with Dave Bacon in 2006

(Inspiration: math with bad drawing)