The Argument Against Quantum Computers – A Very Short Introduction

Left: Gowers’s book Mathematics a very short introduction. Right C. elegans; Boson Sampling can be seen as the C. elegans of quantum computing. (See, this paper.)

Update (January 6, 2021): Tomorrow January, 7, 8:30 AM Israel time, I give a lecture on this topic at the CQT (Center for Quantum Technologies) Thirteenth Anniversary meeting in Singapore. The entire program looks exciting and my own lecture is at 8:30 AM Israel Time. Registration is open and free. Here are the slides.

Happy new year to all my readers.

Today, I will briefly explain the main argument in my theory regarding quantum computers. In this post I will use the term HQCA (“Huge Quantum Computational Advantage”) instead of “quantum supremacy” that Google uses and “quantum advantage” that IBM and  Jiuzhang Boson Sampling group use. Before we move to the main topic of the post, here are two related updates.

Boson Sampling update

A group of researchers mainly from USTC in Hefei, China, claimed to achieve a fantastic quantum computational advantage using Jiuzhang, a photonic device for “Boson Sampling”.  It seems plausible now that level-k approximation from my paper Gaussian Noise Sensitivity and BosonSampling with Guy Kindler will “spoof” the claims, namely, will show an efficient way to give samples of similar fidelity on a digital computer. (There are other related approaches for spoofing the claim, mainly one by Jelmer Renema, and there are interesting connections between Jelmer’s approximations and ours. Sergio Boixo, John Martinis, and other researchers also raised concerns regarding the new HQCA claims.) While it will probably take several weeks or months to clarify it further, it is already clear, that in view of Kindler and mine 2014 results, the claims of achieving in 200 seconds samples that require millions of computing years on current supercomputers are unfounded.

For more details  see my post about the recent HQCA Boson Sampling experiment, and also Scott Aaronson’s recent post.

Scott Aaronson’s apology

Let me mention that Scott Aaronson’s recent post issued the following apology addressed to me, which I gladly welcome:

The argument against quantum computers: a very short introduction

Our starting point is the following recent assertion by Scott Aaronson:

Many colleagues told me they thought experimental BosonSampling was a dead end, because of photon losses and the staggering difficulty of synchronizing 50-100 single-photon sources. They said that a convincing demonstration of quantum supremacy would have to await the arrival of quantum fault-tolerance—or at any rate, some hardware platform more robust than photonics. I always agreed that they might be right. — 

My argument for why all attempts to reach HQCA as well as quantum error-correction via NISQ systems will fail  is based on two claims.  

A) “A convincing demonstration of HQCA would have to await the arrival of quantum fault-tolerance”

B) The error rate required for quantum error correcting codes needed for quantum fault tolerance is even lower than that required for HQCA.

If claims A) and B) are both correct, then it is not possible to reach HQCA as well as good quality quantum error-correction via NISQ systems. In this case, all attempts to reach HQCA as well as quantum error-correction via NISQ systems will fail.

As Scott Aaronson himself asserted, many people in the quantum computing community agree (or used to agree) with claim A). And there is also wide agreement and experimental evidence for claim B). But fewer people see the logical consequence of claims A) and B) put together. 

A little more

The basis for Claim A

We need to put claim A on theoretical grounds. And indeed it is based on a computational complexity assertion for the computational power of NISQ systems, PLUS a heuristic principle (“naturalness”)  on the relation between asymptotic statements and the behaviour of intermediate scale systems.   

My work with Guy Kindler shows that for constant level of noise, NISQ systems represent very low-level computational power that we call LDP. (We studied specifically BosonSampling but the argument extends.)

The naturalness principle is quite common when you relate theory to practice: E.g., when Scott Aaronson and  Sam Gunn argue  that “spoofing” the Google statistical test for 53 qubits is probably very hard for digital computers, they make a similar leap from asymptotic insights to hardness insights for intermediate-scale systems.

Non-stationary and chaotic behaviour

There are several facts that strengthen the argument for claim A. Let me mention one: We already mentioned that for constant level of noise, NISQ systems represent very low-level computational power. Our work also asserts that for a wide range of lower levels of noise the empirical distribution from sampling based on NISQ systems will be very noise-sensitive: we can expect non-stationary and even chaotic empirical outcomes. This is a great thing to test empirically!

But how is it that classical computation is possible?

This is a beautiful piece of the puzzle. The very low computational complexity class describing the power of NISQ systems does support a very rudimentary form of classical error-correction. This is the reason that robust classical information is possible so I can write  this post for you to read. (See also this cartoon post from 2017.)

Topological quantum computing (4 Nick)

Topological quantum computing is a proposed alternative path to very stable quantum qubits and quantum computing. Accepting claims A) and B) does not directly imply that topological quantum computing will fail, but there are good reasons that the argument does extend.

Was HQCA achieved already?

There are two papers claiming it was! One describing the Sycamore Random Circuit Sampling experiment was published in Nature in 2019, and one describing the Jiuzhang Boson Sampling experiment was published in Science in 2020.  I  find both these claims unconvincing.

An Open Problem

One question that certainly comes to mind is whether the technological advances represented by Jiuzhang and earlier on by Sycamore and by other superconducting and ion trapped  NISQ systems, could have technological and scientific fruits even without achieving a computational advantage.

This  is especially interesting if my theory is correct, but it is also interesting if it is not.

More information

A  few of my papers and lectures

The argument against quantum computers, Quantum, Probability, Logic: Itamar Pitowsky’s Work and Influence (M. Hemmo and O. Shenker, eds.), pp. 399–422, Springer, 2019. (Section 3.5 refers to topological quantum computing.)

Three puzzles on mathematics computations, and games, Proc. ICM2018;  

The quantum computer puzzle, Notices AMS, May 2016

Boson Sampling was studied in a 2014 paper by Guy Kindler and me Gaussian Noise Sensitivity and BosonSampling. Our study of Boson Sampling gives the basis to understanding of general NISQ systems.

The argument against quantum computers, the quantum laws of nature, and Google’s supremacy claims, The Intercontinental Academia Laws: Rigidity and Dynamics (M. J. Hannon and E. Z. Rabinovici, eds.), World Scientific, 2020. arXiv:2008.05188.

Slides from my 2019 CERN lecture.

Videotaped lectures

A recent colloquium at Harvard

My ICM 2018 videotaped lecture;  A very easy-going videotaped zoom lecture at USTLC.  (slides)

Eralier posts My collegial supremacy FAQ; Quantum matters.

Boson Sampling as the C. Elegans of quantum computing

Caenorhabditis elegans, or C. elegans for short, is a species of a free-living roundworm whose biological study shed much light on more complicated organisms. In my paper in Itamar Pitowsky’s memorial volume I regard BosonSampling as the C. elegans of quantum computing. Several technical and conceptual aspects of quantum computation are becoming much clearer for this model.

A remark about the terminology

John Preskill’s term “quantum supremacy” is problematic because the word “supremacy” (e.g. “the supremacy of the king”) often refers to superiority or dominance across the board, which is not the case for quantum computation. It is also unfortunate in terms of its connotations. I agree with Preskill that “advantage” is too weak e.g. when it is claimed that the new Boson Sampling experiment can achieve in 200 seconds what would take an ordinary supercomputer millions of years, this is not merely an “advantage.”  This is why I propose “huge quantum computational advantage” (HQCA). 

 

Robert Aumann, Benjamin Netanyahu, and quantum computers

Here is an amusing story (in Hebrew) from an interview of Robert Aumann about  quantum computers and Benjamin Netanyahu