Nowy algorytm dziennika dyskretnego i jego implikacje dla obliczeń kwantowych

Ukazał się nowy artykuł, w którym twierdzono, że quasi-wielomianowy algorytm jest logarytmem dyskretnym. http://arxiv.org/abs/1306.4244

Jeśli jest poprawny, czy oznacza to, że nie mamy już wykładniczej separacji złożoności klasycznego algorytmu i jego wersji kwantowej dla problemu logarytmu dyskretnego? Czy ma to jakiś wpływ na teorię złożoności kwantowej?

Cóż, jedną kluczową obserwacją jest to, że nowy algorytm najwyraźniej działa tylko dla grup formy gdzie p jest małe --- nie daje przyspieszenia dla grup postaci Z p . To drugie jest o wiele bardziej powszechnym ustawieniem, o którym mówią ludzie, zarówno w przypadku kryptografii, jak i algorytmu Shora, a nowy algorytm nie zagraża tam przyspieszeniu kwantowemu. Z drugiej strony tak, chyba że się mylę, to powoduje, że przyspieszenie jest znacznie mniejsze w przypadku Z p k .$Z_{p^k}$$p$$Z_p$$Z_{p^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)$ . To bije poprzednie klasyczne algorytmy$\alpha < 1 / 3$

Algorytm Shora jest wciąż znacznie szybszy, ale pytanie o przyspieszenie wykładnicze zależy tak naprawdę od definicji „wykładniczego”. (Również NFS / FFS były czasem podwykonawczym.)