List of practical quantum computing algorithms that have speed-up higher than quadratic speed-up?

Question

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

Mark S · Answer

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.

List of practical quantum computing algorithms that have speed-up higher than quadratic speed-up?

One Answer

Add your own answers!

Ask a Question