Algoritma baru untuk log Diskrit dan implikasinya untuk komputasi Quantum

Sebuah makalah baru keluar mengklaim algoritma kuasi-polinomial untuk Logaritma Diskrit. http://arxiv.org/abs/1306.4244

Jika benar, apakah itu berarti kita tidak lagi memiliki pemisahan eksponensial dalam kompleksitas algoritma klasik dan versi kuantumnya untuk masalah logaritma diskrit? Apakah ini memiliki implikasi untuk teori kompleksitas kuantum?

Nah, satu pengamatan penting adalah bahwa algoritma baru ini tampaknya hanya berfungsi untuk kelompok-kelompok dari bentuk mana kecil --- itu tidak memberikan speedup untuk kelompok-kelompok bentuk . Yang terakhir adalah pengaturan yang jauh lebih umum yang dibicarakan orang, baik untuk kriptografi dan algoritma Shor, dan algoritma baru tidak mengancam percepatan kuantum di sana. Di sisi lain, ya, kecuali saya salah itu membuat speedup jauh lebih kecil dalam kasus .$Z_{p^k}$$p$$Z_p$$Z_{p^k}$

Pemahaman saya adalah bahwa jika , algoritma memiliki kompleksitas atas bidang hingga dengan asumsi bahwa$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$

Algoritma Shor masih jauh lebih cepat, tetapi pertanyaan tentang percepatan eksponensial sangat bergantung pada definisi "eksponensial". (Juga NFS / FFS adalah waktu subeksponensial.)