Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
A number of ML algorithms have demonstrated to have polynomial speed-up:
But this (I'm assuming) is without error correcting qubits. How practical are algorithms that only exhibit polynomial speed-up when error correction is taken into account? For example, will we need millions and millions of qubits to be able to even compete with modern computers?
Yes, many QML algorithms only yield polynomial (quadratic) speedups. Some, as seen in the table, do yield exponential speedups, and of those most rely on the quantum linear systems algorithm (QLSA, also known as the HHL) as a core subroutine.
Are QML algorithms with a quadratic speedup (or any such quantum algorithm, for that matter) practical? It's unclear. But, there have been a few papers published by Craig Gidney and collaborators that, through numerical simulations, indicate that:
Things don't look so great for quadratic speedups, but they look much better for quartic speedups.
Even some exponential speedups may not be practical without some fundamental improvements to error correcting approaches and, in the case of the log-time QML algorithms, I/O methods. See this paper by Gidney on factoring a 2048 bit RSA key and note his discussion of the constant factors of Shor's algorithm and the challenges they present. Also see Aaronson's classic paper about the limitations of HHL, Read the Fine Print.
Notably, in the second paper referenced, Gidney discusses the overhead due to error correction by magic state distillation with a 3D surface code. This is what Google appears to be pursuing and is currently a favorite, but there are other approaches to error correction that may ultimately win out.
Finally, I'd like to make the assertion that speedups under the quantum query model are not the only types of advantage that may be useful come fault tolerant quantum computing – other types of advantage are of interest, too. For example, see this recent paper by Abbas et al. on an apparent quantum advantage in certain quantum neural networks in terms of generalization error of the learned function and trainability.
