Neuer Algorithmus für das diskrete Protokoll und seine Auswirkungen auf das Quantencomputing

In einer neuen Veröffentlichung wurde der quasi-polynomiale Algorithmus für den diskreten Logarithmus beschrieben. http://arxiv.org/abs/1306.4244

Wenn richtig, bedeutet dies, dass wir keine exponentielle Trennung in der Komplexität eines klassischen Algorithmus und seiner Quantenversion für das diskrete Logarithmusproblem mehr haben? Hat dies Auswirkungen auf die Theorie der Quantenkomplexität?

Nun, eine entscheidende Beobachtung ist, dass der neue Algorithmus anscheinend nur für Gruppen der Form funktioniert, wobei klein ist - es gibt keine Beschleunigung für Gruppen der Form . Letzteres ist die häufigere Einstellung, von der die Leute sowohl für die Kryptographie als auch für Shors Algorithmus sprechen, und der neue Algorithmus gefährdet die Quantenbeschleunigung dort nicht. Auf der anderen Seite, ja, wenn ich mich nicht irre, wird die Beschleunigung im -Fall viel kleiner .$Z_{p^k}$Z p Z p $p$$Z_p$$Z_{p^k}$

Mein Verständnis ist, dass wenn , der Algorithmus eine Komplexität n O ( log n ) über endliche Felder F q k hat, vorausgesetzt, dass k = O ( q ) ist . Allgemeiner gesagt , der Algorithmus hat die Komplexität L q k ( α , O ( 1 ) ) in finite Felder F q k mit q ~ L q k ( α $k = O (q)$$n^{O (\log n)}$$F_{q^k}$$k = O (q)$$L_{q^k} (\alpha, O (1))$$F_{q_k}$$q \sim L_{q^k} (\alpha)$$\alpha < 1 / 3$ .

Shors Algorithmus ist immer noch viel schneller, aber die Frage nach der exponentiellen Beschleunigung hängt wirklich von der Definition von "exponentiell" ab. (Auch NFS / FFS waren subexponentiell.)