Bietet Quantencomputer eine Beschleunigung bei der Bewertung transzendentaler Funktionen?

9

Mit dem Problem der ganzzahligen Faktorisierung ist bekannt, dass Shors Algorithmus im Vergleich zu klassischen Algorithmen eine erhebliche (exponentielle?) Beschleunigung bietet. Gibt es ähnliche Ergebnisse in Bezug auf grundlegendere Mathematik, wie die Bewertung transzendentaler Funktionen?

Nehmen wir an, ich möchte , ln 5 oder cosh 10 berechnen . In der klassischen Welt könnte ich eine Erweiterung wie die Taylor-Reihe oder einen iterativen Algorithmus verwenden. Gibt es Quantenalgorithmen, die schneller sein können als ein klassischer Computer, sei es asymptotisch besser, weniger Iterationen mit derselben Genauigkeit oder schneller um die Wanduhrzeit?Sünde⁡2ln⁡5cosh⁡10

algorithm speedup Norrius
quelle
Es gibt bereits klassische Algorithmen, die diese in einer Handvoll Taktzyklen mit angemessener Genauigkeit (z. B. 80 Bit) auswerten können (und die tatsächlich auf CPUs implementiert sind). Es ist unwahrscheinlich, dass eine Qualitätskontrolle wesentlich schneller durchgeführt werden kann. Fragen Sie nach extrem hoher Präzision (zB 1 Million Bit)?
Poncho
@poncho Es macht zwar Sinn, dass grundlegende Dinge wie diese nahezu perfekt optimiert wurden, aber ich frage mich, ob diese Funktionen etwas enthalten, das genutzt werden kann, um bei einer Qualitätskontrolle noch schneller zu sein. Auch wenn der Effekt nur bei extremen Präzisionsanforderungen sichtbar ist.
Norrius
4
@poncho "Es ist unwahrscheinlich, dass eine Qualitätskontrolle wesentlich schneller durchgeführt werden kann." Die Leute hielten es für unwahrscheinlich, dass es Verbesserungen beim naiven Multiplikationsalgorithmus geben würde, aber jetzt haben wir Karatsuba. Sie fragen sich vielleicht , wenn wir würden wollen einen besseren Algorithmus (ja, zB für Präzision, wie Sie angegeben), aber es ist eigentlich nicht so seltsam , eine gewisse Verbesserung zu erwarten.
Diskrete Eidechse

Antworten:

6

Das einzige, was ich mir vorstellen kann, ist der Algorithmus zum Finden von Matrixleistungen, der eine superpolynomielle Geschwindigkeit aufweist. Es stammt aus dieser Liste von Quantenalgorithmen (es scheint jedoch etwas veraltet zu sein).

Vladimir
quelle
Obwohl es die Frage nicht direkt beantwortet, ist dies sehr interessant, danke!
Norrius
@Norrius Nun, ich habe meine Aufmerksamkeit auf konzentriert Are there similar results regarding more basic maths. Leider konnte ich nichts verwandteres finden.
Vladimir