← Back to papers
On quantum computation of Kloosterman sums
Peter Bruin·July 10, 2018
MathematicsPhysics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
We give two quantum algorithms for computing (twisted) Kloosterman sums attached to a finite field $\mathbf{F}$ of $q$ elements. The first algorithm computes a quantum state containing, as its coefficients with respect to the standard basis, all Kloosterman sums for $\mathbf{F}$ twisted by a given multiplicative character, and runs in time polynomial in $\log q$. The second algorithm computes a single Kloosterman sum to a prescribed precision, and runs in time quasi-linear in $\sqrt{q}$.