8
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ There are already classical algorithms that can evaluate those to reasonable (e.g. 80 bit) precision in a handful of clock cycles (and they are actually implemented on CPUs); it seems unlikely that a QC can perform significantly faster than that. Are you asking about extremely high precision (e.g. 1 million bit)? $\endgroup$
    – poncho
    Commented Mar 30, 2018 at 13:57
  • $\begingroup$ @poncho It does make sense that basic stuff like this has been optimised to near perfection, but I'm wondering if there is something in these functions that can be exploited to be even faster on a QC. Even if the effect can be seen only at extreme precision requirements. $\endgroup$
    – Norrius
    Commented Mar 30, 2018 at 14:10
  • 4
    $\begingroup$ @poncho "it seems unlikely that a QC can perform significantly faster than that". People thought that it was unlikely that there would be improvements to the naive multiplication algorithm, but now we have Karatsuba. You might wonder if we would want a better algorithm (yes, e.g. for precision, as you stated), but it is actually not so strange to expect some improvement. $\endgroup$
    – Discrete lizard
    Commented Mar 30, 2018 at 14:11

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Although it does not directly answer the question, this is very interesting, thank you! $\endgroup$
    – Norrius
    Commented Mar 30, 2018 at 19:05
  • $\begingroup$ @Norrius Well, I concentrated my attention on Are there similar results regarding more basic maths. Unfortunately, I couldn't find anything more related. $\endgroup$
    – Bracula
    Commented Mar 30, 2018 at 20:33

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.