A computação quântica fornece alguma aceleração na avaliação das funções transcendentais?

Com o problema de fatoração de número inteiro, o algoritmo de Shor é conhecido por fornecer uma aceleração substancial (exponencial?) Em comparação com algoritmos clássicos. Existem resultados semelhantes em relação a matemáticas mais básicas, como avaliar funções transcendentais?

Digamos que eu quero calcular o , ou . No mundo clássico, eu poderia usar uma expansão como a série Taylor ou algum algoritmo iterativo. Existem algoritmos quânticos que podem ser mais rápidos do que o que um computador clássico pode fazer, seja assintoticamente melhor, menos iterações com a mesma precisão ou mais rápido no tempo do relógio de parede? $\sin2$ $\ln{5}$ $\cosh10$

algorithm speedup Norrius
fonte

Já existem algoritmos clássicos que podem avaliar esses dados com precisão razoável (por exemplo, 80 bits) em alguns ciclos de clock (e eles são realmente implementados em CPUs); parece improvável que um CQ possa ter um desempenho significativamente mais rápido que isso. Você está perguntando sobre precisão extremamente alta (por exemplo, 1 milhão de bits)?

Poncho

@poncho Faz sentido que coisas básicas como essa tenham sido otimizadas até quase a perfeição, mas estou me perguntando se há algo nessas funções que pode ser explorado para ser ainda mais rápido em um CQ. Mesmo que o efeito possa ser visto apenas em requisitos de extrema precisão.

Norrius 30/03

@poncho "parece improvável que um CQ possa executar significativamente mais rápido que isso". As pessoas pensavam que era improvável que houvesse melhorias no algoritmo de multiplicação ingênuo, mas agora temos o Karatsuba. Você pode se perguntar se queremos um algoritmo melhor (sim, por exemplo, para precisão, como você afirmou), mas na verdade não é tão estranho esperar alguma melhoria.

Lagarto discreto

A computação quântica fornece alguma aceleração na avaliação das funções transcendentais?

Respostas: