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

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 , o . 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? $\sin2$ $\ln{5}$ $\cosh10$

algorithm speedup 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

@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

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

Respuestas: