Efficient Quantum Algorithms for Estimating Gauss Sums

Abstract

We present an efficient quantum algorithm for estimating Gauss sums over finite fields and finite rings. This is a natural problem as the description of a Gauss sum can be done without reference to a black box function. With a reduction from the discrete logarithm problem to Gauss sum estimation we also give evidence that this problem is hard for classical algorithms. The workings of the quantum algorithm rely on the interaction between the additive characters of the Fourier transform and the multiplicative characters of the Gauss sum.

LaTeX, 11 pages, 1 figure, required packages: amsmath, amsfonts, amssymb, theorem, graphics and psfrag

References in corpus (5)

• Quantum Algorithms Revisited
• Efficient Quantum Algorithms for Shifted Quadratic Character Problems
• Rapid sampling through quantum computing
• The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer
• Solving Shift Problems and Hidden Coset Problem Using the Fourier Transform

Cited by in corpus (12)

• Exponential algorithmic speedup by quantum walk
• Quantum algorithms for algebraic problems
• On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers
• Quantum Computation Beyond the Circuit Model
• Factorization of numbers with Gauss sums: I. Mathematical background
• T-count Optimized Design of Quantum Integer Multiplication
• Quantum Computing and Zeroes of Zeta Functions
• Normalizer Circuits and Quantum Computation
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints
• Quantum algorithm based on the $\epsilon$-random linear disequations for the continuous hidden shift problem
• Quantum algorithms for exponential sums and the evaluation of the Riemann zeta function
• An Efficient Deterministic Quantum Algorithm for the Integer Square-free Decomposition Problem