What is the argument that practical quantum computers cannot be built?

Question

An answer to another question mentions that

There are arguments that suggests that such machines ["quantum Turing machines"] cannot even be built...

I'm not sure I fully understand the problem, so perhaps I'm not asking the right question, but here's what I could gather.

The slides are presented in a lecture (from 2013) by Professor Gil Kalai (Hebrew University of Jerusalem and Yale University). I watched most of the lecture, and it seems his claim is that there is a barrier to creating fault-tolerant quantum computers (FTCQ), and this barrier probably lies around creating logical qubits from physical components. (timestamp 26:20):

It sounds like the reason for such a barrier is due to the problem of noise and error-correction. And even though current research takes into account noise, it doesn't do so in the right manner (this is the part I don't understand).

I know many people (e.g., Scott Aaronson) are skeptical of this claim of impossibility, but I'm just trying to better understand the argument:

What is the reason for suggesting that practical quantum computers cannot be built (as presented by Professor Gil Kalai, and has anything changed since 2013)?

Answer 1

If your intent is to understand Gil Kalai's arguments, I recommend the following blog post of his: My Argument Against Quantum Computers: An Interview with Katia Moskvitch on Quanta Magazine (and the links therein).

For good measure, I'd also throw in Perpetual Motion of The 21st Century? (especially the comments). You can also see the highlights in My Quantum Debate with Aram Harrow: Timeline, Non-technical Highlights, and Flashbacks I and My Quantum Debate with Aram II. Finally, if you haven't already, see Scott Aaronson's Whether or not God plays dice, I do.

First, a brief summary of Kalai's view from his Notices article (see also The Quantum Computer Puzzle @ Notices of the AMS):

Understanding quantum computers in the presence of noise requires consideration of behavior at different scales. In the small scale, standard models of noise from the mid-90s are suitable, and quantum evolutions and states described by them manifest a very low-level computational power. This small-scale behavior has far-reaching consequences for the behavior of noisy quantum systems at larger scales. On the one hand, it does not allow reaching the starting points for quantum fault tolerance and quantum supremacy, making them both impossible at all scales. On the other hand, it leads to novel implicit ways for modeling noise at larger scales and to various predictions on the behavior of noisy quantum systems.

Second, a recent argument for why he thinks classical error correction is possible but quantum error correction is not.

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.

(In the above mentioned conversation with Aram Harrow, it is pointed out that if one were to take Kalai's initial arguments directly, then even classical error correction would not possible.)

In the post, Kalai goes on to argue that a primitive quantum computer would not be able to do error correction.

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.

Kalai also gave a lecture (YouTube) on why topological quantum computing would not work.

Answer 2

Q: "What is the reason for suggesting that practical quantum computers cannot be built (as presented by Professor Gil Kalai, and has anything changed since 2013)?".

In an interview titled "Perpetual Motion of The 21st Century?" Prof. Kalai states:

"For quantum systems there are special obstacles, such as the inability to make exact copies of quantum states in general. Nevertheless, much of the theory of error-correction has been carried over, and the famous threshold theorem shows that fault-tolerant quantum computation (FTQC) is possible if certain conditions are met. The most-emphasized condition sets a threshold for the absolute rate of error, one still orders of magnitude more stringent than what current technology achieves but approachable. One issue raised here, however, is whether the errors have sufficient independence for these schemes to work or correlations limited to what they can handle.".

In an earlier paper of his titled "Quantum Computers: Noise Propagation and Adversarial Noise Models" he states:

Page 2: "The feasibility of computationally superior quantum computers is one of the most fascinating scientific problems of our time. The main concern regarding quantum-computer feasibility is that quantum systems are inherently noisy. The theory of quantum error correction and fault-tolerant quantum computation (FTQC) provides strong support for the possibility of building quantum computers. In this paper we will discuss adversarial noise models that may fail quantum computation. This paper presents a critique of quantum error correction and skepticism on the feasibility of quantum computers.".

Page 19: "The main issue is therefore to understand and describe the fresh (or infinitesimal) noise operations. The adversarial models we consider here should be regarded as models for fresh noise. But the behavior of accumulative errors in quantum circuits that allow error propagation is sort of a “role model” for our models of fresh noise.

The common picture of FTQC asserts:

• Fault tolerance will work if we are able to reduce the fresh gate/qubit errors to below a certain threshold. In this case error propagation will be suppressed.

What we propose is:

• Fault tolerance will not work because the overall error will behave like accumulated errors for standard error propagation (for circuits that allow error propagation), although not necessarily because of error propagation.

Therefore, for an appropriate modeling of noisy quantum computers the fresh errors should behave like accumulated errors for standard error propagation (for circuits that allow error propagation).

(As a result, in the end we will not be able to avoid error propagation.)".

Page 23: "Conjecture B: In any noisy quantum computer in a highly entangled state there will be a strong effect of error synchronization.

We should informally explain already at this point why these conjectures, if true, are damaging. We start with Conjecture B. The states of quantum computers that apply error-correcting codes needed for FTQC are highly entangled (by any formal definition of “high entanglement”). Conjecture B will imply that at every computer cycle there will be a small but substantial probability that the number of faulty qubits will be much larger than the threshold. This is in contrast to standard assumptions that the probability of the number of faulty qubits being much larger than the threshold decreases exponentially with the number of qubits. Having a small but substantial probability of a large number of qubits to be faulty is enough to fail the quantum error correction codes.".

See also his paper: "How Quantum Computers Fail: Quantum Codes, Correlations in Physical Systems, and Noise Accumulation".

Many people disagee, and much has changed, see this Wikipedia page: "Quantum Threshold Theorem", or this paper "Experimental Quantum Computations on a Topologically Encoded Qubit", there's even this paper on quantum metrology where the authors claim that: "Making use of coherence and entanglement as metrological quantum resources allows to improve the measurement precision from the shot-noise or quantum limit to the Heisenberg limit." in their paper: "Quantum metrology with a transmon qutrit" by utilizing additional dimensions.

Answer 3

I can’t comment on the specifics of his arguments, because I don’t claim to understand them fully. But in general, we have to wonder whether quantum mechanics will continue to be valid for many qubit systems and states that are deep within the Hilbert space.

Physics is all about observing nature, building theories, confirming the theories, and then finding where they break down. Then the cycle begins again.

We have never had quantum systems as clean, well-controlled and large as current quantum processors. Devices capable of pulling off ‘supremacy’ are even further beyond our current experimental experience. So it is valid to wonder if this unprobed corner of QM might be where it all breaks down. Perhaps new ‘post-quantum’ effects will appear, that effectively act as uncorrectable forms of noise.

Of course, most of us don’t think it will. And we hope it won’t, or there will be no quantum computers. Nevertheless, we must be open to the possibility we are wrong.

And the minority who think quantum computing will fail should be open to the idea that they are wrong, too. Hopefully, they won’t turn out to be the new brand of ‘Bell violation deniers’.