A number of ML algorithms have demonstrated to have polynomial speed-up:

enter image description here

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?

  • 2
    $\begingroup$ this might be useful: Focus beyond quadratic speedups for error-corrected quantum advantage arxiv.org/abs/2011.04149 $\endgroup$
    – KAJ226
    Jan 2, 2021 at 23:09
  • 1
    $\begingroup$ @KAJ226, a very nice resource indeed! Although I have to admit I'm a bit sad that quadratic speedups aren't good enough. $\endgroup$ Jan 2, 2021 at 23:40

1 Answer 1


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:

  1. Things don't look so great for quadratic speedups, but they look much better for quartic speedups.

  2. 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.