L'informatique quantique fournit-elle une accélération dans l'évaluation des fonctions transcendantales?

9

Avec le problème de la factorisation des nombres entiers, l'algorithme de Shor est connu pour fournir une accélération substantielle (exponentielle?) Par rapport aux algorithmes classiques. Y a-t-il des résultats similaires concernant les mathématiques plus élémentaires, telles que l'évaluation des fonctions transcendantales?

Disons que je veux calculer , ln 5 ou cosh 10 . Dans le monde classique, je pourrais utiliser une expansion comme la série Taylor ou un algorithme itératif. Existe-t-il des algorithmes quantiques qui peuvent être plus rapides que ce qu'un ordinateur classique peut faire, que ce soit asymptotiquement meilleur, moins d'itérations avec la même précision, ou plus rapide par horloge murale?péché⁡2ln⁡5matraque⁡dix

algorithm speedup Norrius
la source
Il existe déjà des algorithmes classiques qui peuvent évaluer ceux-ci avec une précision raisonnable (par exemple 80 bits) dans une poignée de cycles d'horloge (et ils sont en fait mis en œuvre sur les CPU); il semble peu probable qu'un QC puisse fonctionner beaucoup plus rapidement que cela. Vous demandez une précision extrêmement élevée (par exemple 1 million de bits)?
poncho
@poncho Il est logique que des choses de base comme celle-ci aient été optimisées à la perfection, mais je me demande s'il y a quelque chose dans ces fonctions qui peut être exploité pour être encore plus rapide sur un QC. Même si l'effet n'est visible qu'à des exigences de précision extrêmes.
Norrius
4
@poncho "il semble peu probable qu'un QC puisse fonctionner beaucoup plus vite que cela". Les gens pensaient qu'il était peu probable que des améliorations soient apportées à l'algorithme de multiplication naïf, mais nous avons maintenant Karatsuba. Vous vous demandez peut-être si nous voudrions un meilleur algorithme (oui, par exemple pour la précision, comme vous l'avez dit), mais il n'est en fait pas si étrange de s'attendre à une amélioration.
Lézard discret

Réponses:

6

La seule chose à laquelle je peux penser est l' algorithme pour trouver des puissances matricielles qui a une vitesse superpolynomiale. C'est à partir de cette liste d'algorithmes quantiques (il semble cependant être un peu dépassé).

Vladimir
la source
Bien qu'il ne réponde pas directement à la question, c'est très intéressant, merci!
Norrius
@Norrius Eh bien, j'ai concentré mon attention sur Are there similar results regarding more basic maths. Malheureusement, je n'ai rien trouvé de plus lié.
Vladimir