6

Question

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?

References

[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

sheesymcdeezy
  • 1,746
  • 6
  • 25
  • 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 – glS Feb 15 '24 at 13:32
  • 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. – sheesymcdeezy Feb 15 '24 at 16:34
  • 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)$).

     – fiktor Feb 15 '24 at 18:13
  • 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 – sheesymcdeezy Feb 16 '24 at 15:26
  • @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 – glS Feb 17 '24 at 11:05
  • In the paper they state: "manipulating multiple quantum states can provide an exponential advantage over classical processing of measurements of single-quantum states for certain learning tasks. These include predicting properties of physical systems, performing quantum principal component analysis on noisy states, and learning approximate models of physical dynamics". I am satisfied with this definition of exponential advantage in solving a problem, but I can see how it may not be satisfactory for some. But it seems to me this debate may be out of scope for the original question :) – sheesymcdeezy Feb 18 '24 at 00:27

1 Answers1

7
Egretta.Thula
  • 9,972
  • 1
  • 11
  • 30
  • 1
    There's also Aaronson's cute cubic-Grover algorithm from Bohmian mechanics, but that likely falls into the "contrived" category. – Mark Spinelli Feb 15 '24 at 16:29
  • 4
    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? – Greg Kuperberg Feb 19 '24 at 06:41
  • 1
    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... – sheesymcdeezy Feb 25 '24 at 16:04