Ritchie Chirgwin just published this article in The Register, a British tabloid. The article is a long, soporific piece. Not very original. Writing skill level: about that of a C minus high school student. I tried to submit a comment to his article, twice, to no avail. I wanted to point out some serious errors, but Ritchie will have none of it. How dare I find fault with Narcissus! So I submit my comment here instead:
Sorry, Mr. Chirgwin, but your article is full of false statements. Here are some. You say:
(1)“In certain settings a quantum computer is exponentially more efficient at performing Fourier Transforms than a classical computer.”
That is totally false. A QC can calculate faster than classical computers only “quantum” Fourier transforms, not “classical” Fourier transforms. They are quite different. For a classical Fourier transform, you can “print” all N components of the answer at the end of a each “run”. For a quantum Fourier transform, you can “print” ONLY ONE of the N components of the answer at the end of each “run”. The other N-1 components are destroyed when you print that single one.
(2)“Today, the problem is approached by sampling, using the Metropolis algorithm on a classical computer. The European/Canadian group propose an alteration to that algorithm that uses a quantum computer to obtain the samples.”
Again, very misleading.
The statement refers to the following paper:
Quantum Metropolis Sampling
K. Temme, T.J. Osborne, K.G. Vollbrecht, D. Poulin, F. Verstraete
The problem with this paper by Temme et al is that it not very honest. It doesn’t tell you that their QC algorithm is no faster than classical. There are known QC algorithms which PREDATE the Temme et al algorithm and which can sample faster than classical. They use the Szegedy operators. (See, for example, the work by Rolando Somma, Pawel Wocjan, and my own program called Quibbs). The Temme et al paper doesn’t compare their algorithm with those earlier, faster algorithms because they would look quite bad in the comparison. Like I said, they aren’t very honest.
(3)“Another example is here: a quantum algorithm for solving linear equations (where you have a matrix and a known vector, and wish to compute an unknown vector). For some classes of linear equations, Harrow, Hassidim and Lloyd have demonstrated that a classical computer’s runtime will be exponentially greater than that of a quantum computer.”
That is totally false. Again, with the classical algorithm for solving linear equations, you can print all N components of the answer, but with the quantum one you can “print” ONLY ONE component per run. Equating these two algorithms is quite disingenuous. Check out this post by Eric Dexler, one of the fathers of nanotech: