From this link (provided by @KAJ226's comment in this question), it appears as though current error correction methods are not enough to get practical speedup out of algorithms that have quadratic speedups (before taking error correction into account).

In another post, I showed a chart of speedups of different machine learning algorithms. All of these algorithms do not have quartic or higher speedups (and therefore will not be practical with error correction).

Is there a list of practical algorithms that have quartic or higher speedup? I found one such list called the quantum zoo, but it only provides if a given algorithm is "polynomial" or "superpolynomial." Also it doesn't seem very up-to-date and the impact or practicality of these algorithms is not mentioned (a lot of these seem useless or are very vague).


1 Answer 1


I think your best bet as of now is to derive such a table from the Quantum Algorithm Zoo, which, as you mention although partly dated, would serve as a good starting point but would require reading between the lines. For example, the Zoo mentions a speedup in solving exponential congruences of $\tilde{O}(q^{3/8})$ quantum, but a $\tilde{O}(q^{9/8})$ classical algorithm.

The Quantum Approximate Optimization Algorithm (QAOA) initially appears promising to get the speedups on NISQ-error devices, but it happens that lower bounds on classical algorithms may also be dated and can be significantly improved once a quantum algorithm comes along. This is what has happened with QAOA for Max-E3LIN. See the nice Quanta article here.

  • $\begingroup$ Just to be clear the "exponential congruence" example you give is not faster than quadratic right? $\endgroup$ Commented Jan 10, 2021 at 20:30
  • $\begingroup$ Looking at it closer, yeah it's not faster than quadratic. Sorry for implying it was. $\endgroup$ Commented Jan 10, 2021 at 20:51

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.