Page "Quantum algorithm" Paragraph 10

A Gauss sum is a type of exponential sum.

The best known classical algorithm for estimating these sums takes exponential time.

Since the discrete logarithm problem reduces to Gauss sum estimation, an efficient classical algorithm for estimating Gauss sums would imply an efficient classical algorithm for computing discrete logarithms, which is considered unlikely.

However, quantum computers can estimate Gauss sums to polynomial precision in polynomial time.