Efficient Quantum Algorithms for Estimating Gauss Sums

Details Efficient Quantum Algorithms for Estimating Gauss Sums Efficient Quantum Algorithms for Estimating Gauss Sums

2002-07-23

arxiv.org/abs/quant-ph/0207131v1

Physics

Quantum Physics

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

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Efficient Quantum Algorithms for Estimating Gauss Sums does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient Quantum Algorithms for Estimating Gauss Sums, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Quantum Algorithms for Estimating Gauss Sums will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-469487