Anything in between quadratic and exponential speedups?

Question

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

Answer 1

• A subexponential-time quantum algorithm for the dihedral hidden subgroup problem by Kuperberg.

• Constructing elliptic curve isogenies in quantum subexponential time by Childs, Jao, and Soukharev.

• A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits by McArdle, Gilyén, and Berta (almost quintic speedup over state-of-the-art classical algorithms)

• Classical and Quantum Algorithms for Tensor Principal Component Analysis by Hastings (achieves a quartic speedup over the best-known classical algorithm)

• Classical and Quantum Algorithms for Exponential Congruences by van Dam and Shparlinski (cubic speedup)

• Quantum Search with Multiple Walk Steps per Oracle Query by Wong and Ambainis (cubic speedup)