There exist a handful of proven quadratic quantum speedups (some examples include [1-3]) and even a few proven exponential quantum speedups (some examples include [4-6]). But there seems to be a dearth in quantum algorithms with proven superquadratic but subexponential speedups. Does anyone know of any (not-too-contrived) examples?


[1] Gilles Brassard, Peter Hoyer, Michele Mosca, Alain Tapp. Quantum Amplitude Amplification and Estimation. Quantum Computation and Quantum Information, Samuel J. Lomonaco, Jr. (editor), AMS Contemporary Mathematics, 305:53-74, 2002. DOI: https://doi.org/10.1145/380752.380757
[2] Ambainis Andris, Bach Eric, Nayak Ashwin, Vishwanath Ashvin, and Watrous John. 2001. One-dimensional quantum walks. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC’01). Association for Computing Machinery, New York, NY, 37–49. DOI: https://dl.acm.org/doi/10.1145/380752.380757
[3] Kerenidis, I. and Prakash, A. A quantum interior point method for LPs and SDPs. ACM Transactions on Quantum Computing, 1(1), 2020. ISSN 2643-6809. DOI: https://doi.org/10.1145/3406306
[4] Peter Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. DOI: https://arxiv.org/abs/quant-ph/9508027
[5] Ryan Babbush, Dominic W. Berry, Robin Kothari, Rolando D. Somma, and Nathan Wiebe. Exponential Quantum Speedup in Simulating Coupled Classical Oscillators. Phys. Rev. X 13, 041041. DOI: https://doi.org/10.1103/PhysRevX.13.041041
[6] Hsin-Yuan Huang et al. ,Quantum advantage in learning from experiments. Science 376,1182-1186 (2022). DOI:10.1126/science.abn7293

  • $\begingroup$ I don't think you can say Shor's is a "proven exponential speedup". There is no proof, nor argument of any kind afaik, that factoring isn't efficiently solvable classically. Also, can Huang's "quantum advantage" be framed in terms of some sort of "exponential advantage"? It's an efficient scheme to perform quantum parameter estimation, but that problem has no (obvious) classical counterpart; so it's not a "quantum advantage" in the same sense as the other ones $\endgroup$
    – glS
    Feb 15 at 13:32
  • $\begingroup$ Maybe I should have been more specific and said "proven exponential speedup over today's state-of-the-art classical algorithms". And when it comes to Huang's paper, I agree it's debatable, but if you start with the premise that you have several copies of an unknown quantum state produced by an experiment, then you can compute the expectation values of observables on those states exponentially faster if you have a quantum computer (with the big caveat that you can efficiently transfer these quantum states into a quantum computer). I hope that this clarifies the spirit of my question. $\endgroup$ Feb 15 at 16:34
  • $\begingroup$ It is debatable whether Shor's speedup itself can be called "exponential": the best known classical algorithm runs in $\exp\left(((8/3)^{2/3} + o(1)) n^{1/3} (\log(n))^{2/3}\right)$ time (where $n$ is the number of bits in $N$—the number to factor). That is, classical complexity is sub-exponential in $n$. That said, you can derive a problem with suspected exp. speedup from Shor's: agree on a polynomial-time algorithm to convert $m = n^{1/3} (\log(n))^{2/3}$-bit strings to odd $n$-bit numbers $N$. Then classical factoring of $N$ is exponential in $m$ and Shor's is polynomial ($O(m^9)$). $\endgroup$
    – fiktor
    Feb 15 at 18:13
  • $\begingroup$ I think I understand your point. You're saying that some may argue that Shor's algorithm - which is of order $\tilde{O}\left((\log N)^2\right)$ - may not be strictly exponentially faster than the general number field sieve algorithm - which is of order $\tilde{O}\left(e^{(\log N)^{1/3}}\right)$ (where $N$ is the integer being factored). I accept that debate, but similar to the previous comment, I hope that the spirit of my question is still well understood despite this particular nuance $\endgroup$ Feb 16 at 15:26
  • $\begingroup$ @sheesymcdeezy regarding Huang's: exponentially faster than what? As far as I understand it, they show that some kinds of state estimation are exponentially faster doing coherent measurements on multiple copies of the state than measuring the states individually. That's interesting and useful (and arguably hardly surprising), but I don't see how to think of it as an "exponential advantage" in the same sense meant when discussing quantum algorithms $\endgroup$
    – glS
    Feb 17 at 11:05

1 Answer 1

  • 1
    $\begingroup$ There's also Aaronson's cute cubic-Grover algorithm from Bohmian mechanics, but that likely falls into the "contrived" category. $\endgroup$ Feb 15 at 16:29
  • 4
    $\begingroup$ I am quietly pleased that my algorithm --- either in the generic form or in the application found by Childs, Jao, and Soukharev --- is the only one listed here with a superpolynomial but subexponential speedup. (Note that we can consider an exponential speedup in a generalized sense: Moving a problem from EXP to BQP. Mine takes a problem from QP, quasipolynomial time, to BQP.) Are there are other natural examples of that? $\endgroup$ Feb 19 at 6:41
  • 1
    $\begingroup$ Egretta.Thula, @Mark Spinalli and Greg Kuperberg, thank you so much! I wonder if there is a way to put them in (vaguely) umbrella categories. Something like the dihedral hidden subgroup problem + elliptic curve isogenies + possibly the exponential congruences might fall under finding subgroups or elements within a group, TDA + tensor PCA in data analysis, the quantum search in search and the Bohmian mechanics in beyond-QC? The reason I thought this exercise might be useful is as a starting point for bridging from algorithm to use-case, but I'm not even sure if my categories make sense... $\endgroup$ Feb 25 at 16:04

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.