Roadmap for the Debate about Quantum Computers

Here is a roadmap for the debate about quantum computers from my perspective. Skeptical claims are in blue, responses to these claims are in purple. Points 1-8 represent skeptical claims made over the years, while points a-p are replies to these skeptical claims. Points (i)-(x) are replies to some of these replies. Underlined claims were made by me. Green boldface indicates points of agreement. 

1. The understanding of noise is a crucial ingredient of any model of computation. Noise may cause quantum computing to fail.

   • a) Noise is not fundamental. There is no inherent “noise” in quantum mechanics.

     • (i) A realistic computational model must include also the modeling of errors.

   • b) Quantum error correction and quantum fault tolerance have the potential to deal successfully with noise and various forms of inaccuracies.

   • c) Topological quantum computing gives an alternative avenue for quantum computing that does not depend on the circuit model.

2. General forms of quantum noise (in particular, correlated errors) will fail quantum error correction.

   • d) These types of general noise are not physical.

   • e) These types of general noise would cause classical computation to fail as well.

   • f) For arbitrary forms of noise, if the error rate is sufficiently small, log-depth quantum computing survives.

3. Specific physical noise models differ from the ideal model.

   • g) We will be able to extend the threshold theorem to these models as well.

     • (ii) All those extensions still assume common properties that might be unrealistic.

4. There will be a systematic relationship between the “signal” and the noise. For example, the noise for a pair of entangled qubits will be highly correlated. (This argument extends to attempts to build quantum gadgets needed for topological quantum computing.)

   • h) This cannot be: how would nature know what the intended state is? It is like saying, “wet roads cause rain to pour.”

     • (iii) This systematic relation can be a general rule if you consider special-purpose quantum computational devices.

     • (iv) This systematic relation holds for NISQ (noisy intermediate scale quantum) systems and more generally for systems that do not apply quantum fault tolerance. This systematic relation describes quantum physics “above the quantum fault tolerance threshold.”

   • i) Such a principle would harm classical computation as well, unless you believe that by a miracle the threshold for fault tolerance lies between what is required for classical and quantum computation.

     • (v) The argument about the miraculous location of the threshold is incorrect because classical computers are not universal quantum computers.

5. NISQ computers represent a primitive classical computational power (LDP), which implies an inherent reason they cannot achieve quantum computational supremacy. This suggests there is an absolute lower bound on noise rates that prevents effective quantum error correction. 

   • j) It is incorrect to apply asymptotic insights (on the number of qubits) to systems with only tens or a few hundred qubits.

     • (vi) We commonly apply asymptotic insights to small systems.

   • k) But why classical information and computation are possible?

     • (vii) The computational class LDP still supports classical information.

   • l) The Google 2019 experiment refutes this argument.

     • (Agreed upon) Google’s 2019 supremacy claims appear to be incorrect.

   • m) Some aspects of the Google 2019 experiment and its replications are promising and support basic assumptions about quantum noise.

     • (viii) These aspects of Google 2019 appear to be incorrect as well.

   • n) (New) The 2019 Google experiment was long ago superseded. Several recent experiments, including Google’s “septillion years advantage over classical” and other results from IBM, Quantinuum, QuEra, and USTC, are more robust.

     • (ix) We need to scrutinize these assertions as well. Gradual experimental progress is expected to hit a barrier, and fantastical experimental claims are expected to be falsified.

6. Building quantum computers is a ridiculously hard engineering task.

   • o) It is very hard but not ridiculously hard; progress is being made, and a long-term approach is necessary.

     • (x) Even achieving near-term tasks is inherently impossible.

     • (Agreed upon) We may have an opportunity to test this matter in the next few years.

7. (Simplified) Quantum computations conflict with important principles and laws from physics and computing theory:

   • 7.1 The time-energy uncertainty principle.

   • 7.2 The effective Church-Turing thesis.

   • 7.3 Several principles of thermodynamics.

   • 7.4 Bohr’s selection principle.

   • p) (Simplified) These physical and computational rules are not universally correct, which is part of what makes quantum computation so remarkable as it would enable novel physical and computational behaviors.

8. Quantum computers will allow sampling according to the exact values of permanents. Achieving it is implausible given that computing permanents is #P complete.

Summary

Proponents of Quantum Computers: BQP is the computational complexity class representing our quantum physical world. BQP characterizes the complexity of quantum processes on a microscopic scale, as evidenced by the challenges of simulating quantum physics on classical computers. Building quantum computers is primarily an engineering task, and pursuing this endeavor will drive exciting scientific progress across various fields. Many promising avenues exist, ranging from different implementations of quantum circuits to non-abelian anyons and topological quantum computing. Numerous impressive experimental results have already been achieved.

Skeptics of Quantum Computers: BPP is the computational class representing computation in the physical world. Classical information and computation are sustained in our noisy quantum world through the “averaging” of noisy quantum information.  Quantum computational supremacy or high quality quantum error correction are inherently impossible and there is no compelling evidence for them in natural quantum processes. Advances in experimental quantum computing should be scrutinized carefully. Gradual experimental progress is expected to hit a barrier, and fantastical experimental claims are unlikely to withstand rigorous examination.

A “meta claim” of proponents is that there is no symmetry between the two sides of the debate: the prevalent view shared by many experts is that quantum computation is possible. 

_____________

Future Plans for Quantum Posts

I am planning an ambitious post, “Some Quantum Mysteries,” which will explore several mysteries in quantum physics, many of which are connected to quantum information theory. The first item is about the elusive Majorana zero modes, and the second item is about the security of quantum key distributions.

As a spinoff of the mysteries post, I am also writing two posts on the debate surrounding quantum computing. The first will summarize a few skeptical perspectives on quantum computing from Robert Alicki, Michel Dyakonov, Leonid Levin, Oded Goldreich, and others. The second post will begin with the roadmap presented here, briefly outline my own skeptical views with relevant links, and then delve into the broader debate, including counterarguments from John Preskill, Aram Harrow, Scott Aaronson, Dave Bacon, Boaz Barak, and others.

Seven assertions about quantum computing

In my previous post, I presented seven assertions about quantum computing that emerged from my research. My primary goal was to articulate these assertions as clearly as possible. (Of course, there is much to discuss regarding the arguments for their validity, precise quantitative formulations, falsifiable predictions, and their place within the broader context of the quantum computing endeavor.)