|
| related topics |
| {algorithm, log, probability} |
| {let, theorem, proof} |
| {group, space, representation} |
| {phase, path, phys} |
| {force, casimir, field} |
| {field, particle, equation} |
| {cos, sin, state} |
|
Efficient Quantum Algorithms for Estimating Gauss Sums
Wim van Dam, Gadiel Seroussi
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.
- oai_identifier:
- oai:arXiv.org:quant-ph/0207131
- categories:
- quant-ph cs.DM math.NT
- comments:
- LaTeX, 11 pages, 1 figure, required packages: amsmath, amsfonts,
amssymb, theorem, graphics and psfrag
- arxiv_id:
- quant-ph/0207131
- report_no:
- HPL-2002-208
- created:
- 2002-07-22
Full article ▸
|
|
| related documents |
| 0302022v1 |
| 0511272v1 |
| 9905026v1 |
| 0505007v3 |
| 0201152v1 |
| 9903071v1 |
| 0010034v1 |
| 9706003v4 |
| 0304131v1 |
| 0403140v2 |
| 0011052v2 |
| 0410042v1 |
| 0607148v3 |
| 0504067v3 |
| 9907020v2 |
| 0206089v2 |
| 0106152v1 |
| 0210141v2 |
| 0010021v1 |
| 0306042v1 |
| 0210077v1 |
| 0610235v2 |
| 0303175v1 |
| 0609220v1 |
| 0401053v1 |
|