8

With the integer factorisation problem, Shor's algorithm is known to provide a substantial (exponential?) speedup compared to classical algorithms. Are there similar results regarding more basic maths, such as evaluating transcendental functions?

Let's say I want to calculate $\sin2$, $\ln{5}$ or $\cosh10$. In the classical world, I might use an expansion like the Taylor series or some iterative algorithm. Are there quantum algorithms that can be faster than what a classical computer can do, be it asymptotically better, fewer iterations to the same precision, or faster by wall clock time?

Norrius
  • 687
  • 11
  • 18

1 Answers1

6

The only thing I can think of is the algorithm for finding matrix powers which has superpolynomial speed up. It's from this list of quantum algorithms (it seems to be a bit outdated though).

Bracula
  • 161
  • 3