Observation: "Due to limitations of input and output bandwidth, quantum computers will be practical for 'big compute' problems on small data, not big data problems".
This is the second "key insight" stated for a May 2023 article "Disentangling hype from practicality: On realistically achieving quantum advantage" by Torsten Hoefler, Thomas Häner, and Matthias Troyer, apparently based on a 2020 talk under the same name by Troyer.
However, I had already posted the same observation in 2016: "The interesting quantum computations are not big-data computations. They are big computations on small data. The big-data computations that people carry out, and want to carry out, fundamentally involve much more input and output, exactly the weak point of quantum algorithms."
I think the words "key insight" are overstating the difficulty of this observation. I wouldn't be surprised if the observation was made years earlier. But the results of my literature searches back in 2016 were flooded with incorrect claims that quantum computers will speed up big-data computations. If anyone knows earlier public statements of the above observation, please let me know!
I sent the email shown below to the authors in May 2023. There was no reply. In July 2023, the authors posted their article on arXiv, still saying "quantum computers will be practical for 'big compute' problems on small data, not big data problems", still not crediting this observation to any work before their own.
Subject: big computations on small data
From: "D. J. Bernstein" <djb@math.uic.edu>
Date: Sun, 7 May 2023 22:28:21 +0200
To: torsten.hoefler@inf.ethz.ch, thhaner@microsoft.com, mtroyer@microsoft.com
Dear Prof. Hoefler, Dr. Häner (I presume the Microsoft address still
works), and Dr. Troyer,
I've been reading your CACM review article "Disentangling hype from
practicality" with interest. I noticed that the second statement in the
"Key insights" section of the article---namely
Due to limitations of input and output bandwidth, quantum computers
will be practical for “big compute” problems on small data, not big
data problems
---sounds very much like https://blog.cr.yp.to/20160516-quantum.html
(which isn't cited in the article) saying the following:
But the interesting quantum computations are not big-data
computations. They are _big computations on small data_. The big-data
computations that people carry out, and want to carry out,
fundamentally involve much more input and output, exactly the weak
point of quantum algorithms. Even under extremely optimistic 20-year
projections of progress in building quantum computers, big-data
computations cannot reasonably be expected to see a quantum speedup.
No, Grover's algorithm will _not_ let Google search the Internet more
quickly.
I did some searches at the time for earlier statements of this pattern,
and I didn't find any, although I could certainly have missed something
buried under the flood of contrary claims found by the searches.
---D. J. Bernstein
Version: This is version 2023.11.27 of the "Big computations on small data" web page.