What scientific findings did you come to in your study? For what types of problems are quantum computers most likely to be faster?
Torsten Hoefler: We compared the performance of a market-leading classical chip to an optimistically designed quantum chip, each for the same problem. This way, we are the first to have identified what exactly is required for quantum computers to achieve real speed advantage. Our analysis shows that with pretty much all algorithms, the classical computer is faster for very small problem sizes and the quantum computer is faster for very large problem sizes.
This is because the time to solve certain problems on a quantum computer grows more slowly with the size of the problems than on classical computers (see graphic). That’s what we call quantum speedup. We also see that, in general, quantum computers are comparatively faster and more practical for “big compute” problems on small data, but they are not practical for big data problems.
Due to limitations of input and output bandwidth, big data is a problem which classical computer calculate faster. Furthermore, classical computers also solve a search problem in a database faster than a quantum computer. Therefore, quantum computing has been falsely hyped in the context of big data.
One of your findings is that “quadratic speedup” is not good enough for quantum computers to really take advantage of their potential speedup advantages.
Torsten Hoefler: In our study we show that quadratic speedups, which reduce computation time by taking the square root of an algorithm's running time, are insufficient for practical quantum advantage in the foreseeable future. We see that if only quadratic speedup is implemented, then for many problems quantum computation will still take several months, which would be too slow and too expensive in practice.
From this, we derive that at least cubic or quartic speedups based on the third and fourth roots are required, because only then thousands or millions of computing operations are feasible. But even cubic or quartic speedups are only the lowest requirement. It is necessary to focus on exponential speedups, where the running time of the quantum algorithm is the logarithm of the running time of the classical algorithm. Therefore, the most promising candidates for achieving real practical quantum advantages are small-data problems with exponential speedup.
What needs to be done differently to eventually achieve true high-speed quantum computation?
Torsten Hoefler: One decisive key to realising quantum speedup are more novel quantum algorithms. Without significant algorithmic improvements, a wide range of often-cited applications is unlikely to result in practical quantum advantage. From a practical perspective, most of the quantum algorithms we have today are not enabling real quantum speedups.
Even if we know that cubic, quartic, or exponential algorithms result in higher quantum speedups than quadratic algorithms, the real situation still is, that by today we just don't know many cubic or quartic speedup algorithms. Currently, many quantum speedup algorithms rely on quadratic quantum speedup, based on the well-known Grover algorithm.
We argue that designing more Grover style algorithms is not enough. For developing new quantum algorithms that really make a difference, algorithmic research needs to focus on algorithms that enable high quantum speedup in practice. Otherwise, quantum computers might not outperform the fastest devices of classical computers.
