¿La computación cuántica proporciona alguna aceleración en la evaluación de las funciones trascendentales?

9

Con el problema de la factorización de enteros, se sabe que el algoritmo de Shor proporciona una aceleración sustancial (¿exponencial?) En comparación con los algoritmos clásicos. ¿Hay resultados similares con respecto a las matemáticas más básicas, como evaluar las funciones trascendentales?

Digamos que quiero calcular , ln 5 o cosh 10 . En el mundo clásico, podría usar una expansión como la serie Taylor o algún algoritmo iterativo. ¿Existen algoritmos cuánticos que pueden ser más rápidos de lo que puede hacer una computadora clásica, ya sea asintóticamente mejor, menos iteraciones con la misma precisión o más rápido por el tiempo del reloj de pared?pecado2En5 5aporrear10

Norrius
fuente
Ya existen algoritmos clásicos que pueden evaluarlos con una precisión razonable (por ejemplo, 80 bits) en un puñado de ciclos de reloj (y en realidad se implementan en las CPU); parece poco probable que un control de calidad pueda funcionar significativamente más rápido que eso. ¿Está preguntando acerca de una precisión extremadamente alta (por ejemplo, 1 millón de bits)?
poncho
@poncho Tiene sentido que cosas básicas como esta se hayan optimizado casi a la perfección, pero me pregunto si hay algo en estas funciones que pueda explotarse para ser aún más rápido en un control de calidad. Incluso si el efecto se puede ver solo con requisitos de precisión extrema.
Norrius
44
@poncho "parece poco probable que un control de calidad pueda funcionar significativamente más rápido que eso". La gente pensaba que era poco probable que hubiera mejoras en el ingenuo algoritmo de multiplicación, pero ahora tenemos Karatsuba. Puede que se pregunte si queremos desear un mejor algoritmo (sí, por ejemplo, para la precisión, como ha afirmado), pero en realidad no es tan extraño esperar alguna mejora.
Lagarto discreto

Respuestas:

6

Lo único en lo que puedo pensar es en el algoritmo para encontrar potencias matriciales que tiene una velocidad superpolinómica. Es de esta lista de algoritmos cuánticos (aunque parece estar un poco desactualizado).

Vladimir
fuente
Aunque no responde directamente a la pregunta, esto es muy interesante, ¡gracias!
Norrius
@ Norrius Bueno, concentré mi atención Are there similar results regarding more basic maths. Lamentablemente, no pude encontrar nada más relacionado.
Vladimir