Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Quantum computing: survey and analysis
Savchuk M., Fesenko A. Cybernetics and Systems Analysis55 (1):10-21,2019.Type:Article
Date Reviewed: Aug 20 2020

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.

Reviewer:  Christoph F. Strnadl Review #: CR147042 (2102-0048)
Bookmark and Share
  Reviewer Selected
Featured Reviewer
 
 
Physics (J.2 ... )
 
 
Parallelism And Concurrency (F.1.2 ... )
 
 
Models Of Computation (F.1.1 )
 
 
Systems And Information Theory (H.1.1 )
 
 
Introductory And Survey (A.1 )
 
Would you recommend this review?
yes
no
Other reviews under "Physics": Date
Computational astrophysics
Arnett W. Communications of the ACM 28(4): 354-357, 1985. Type: Article
Sep 1 1985
Computer simulation methods: in theoretical physics
Heermann D., Springer-Verlag New York, Inc., New York, NY, 1986. Type: Book (9780378169660)
Jul 1 1987
Computing in high energy physics
Hertzberger L., Hoogland W. (ed)  Computing in high energy physics,Amsterdam, The Netherlands,1986. Type: Whole Proceedings
Mar 1 1989
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy