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?

$\endgroup$
  • $\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 Mar 30 '18 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 Mar 30 '18 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 Mar 30 '18 at 14:11
5
$\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).

$\endgroup$
  • $\begingroup$ Although it does not directly answer the question, this is very interesting, thank you! $\endgroup$ – Norrius Mar 30 '18 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$ – Vladimir Mar 30 '18 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.