With quantum supremacy allegedly having been achieved by Google, the need for short, correct, and accessible introductions into the quantum computing (QC) realm certainly is going to rise. Regrettably, this paper is an egregious failure in that respect and certainly should not have been published in the current form. Nevertheless, I’ll use some of the errors and deficiencies of the paper to highlight important concepts a reader might want to identify in other (better) introductions.
Let’s turn to quantum supremacy first with the claim that QC is absolutely faster for some problems than ordinary computing. This is fueled by a few quantum algorithms (for example, factoring integers using Shor’s algorithm) that provide an exponential speed-up compared to the best currently known classical algorithms. Unbelievably to any expert, the paper mistakenly claims that, according to a result by Grover, the complexity of every(!) algorithm can be reduced at least quadratically when executed on a quantum computer. This is simply wrong. We know of some classes of algorithms where QC cannot provide any speed-up at all, or, at most, a polynomial speed-up. In general, however, it is very hard to proof lower bounds on classical computing and Grover’s result for a very particular search problem is one of the few where this has been achieved.
Being based on the (strange) logic of quantum mechanics, QC makes use of several concepts that have no classical counterpart. For instance, we know that any quantum algorithm operating on pure “states” and providing exponential speed-up needs “entanglement.”
The famous no-cloning theorem, the fact that you cannot reliably copy unknown quantum “states,” forms the basis for quantum cryptography. The authors, however, manage to get this completely wrong, writing “it is impossible to reproduce the state of a photon after measurement,” omitting the crucial qualifier, “unknown”!
“Entanglement” is mentioned occasionally but not explained at all. Against the backdrop that the authors do not even bother to explain that the |0> and |1> kets form an orthogonal basis of the 2D Hilbert space of a qubit, and their utterly dysfunctional introduction of a tensor product (it is almost understandable, albeit not acceptable).
Quantum parallelism is a common pattern found in many quantum algorithms. Hence, the authors rightfully introduce the Walsh-Hadamard transformation H and the generic reversible version of a function f, Uf. Besides the fact that they never bother to explain how transformations look, they then simply forget to include H before applying Uf. The result, then, is completely nonsense.
The paper’s summaries of several important genuine quantum algorithms (Deutsch, Deutsch-Jozsa, Bernstein-Vazirani, and Shor) are so terse and formalistic to be completely incomprehensible for anyone but an expert.
To be fair, not every paragraph contains errors or is unintelligible, but I fail to recognize any reason why a reader should bother to dig and sift through this mess.
