Efficient Quantum Algorithms for Estimating Gauss Sums

Simple item page
dc.creatorvan Dam, Wim
dc.creatorSeroussi, Gadiel
dc.date2002-07-23
dc.date.accessioned2026-07-07T06:04:39Z
dc.date.available2026-07-07T06:04:39Z
dc.descriptionWe 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.
dc.descriptionLaTeX, 11 pages, 1 figure, required packages: amsmath, amsfonts, amssymb, theorem, graphics and psfrag
dc.identifierhttps://arxiv.org/abs/quant-ph/0207131
dc.identifierhttp://arxiv.org/abs/quant-ph/0207131
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/90370
dc.subjectQuantum Physics
dc.subjectDiscrete Mathematics
dc.subjectNumber Theory
dc.titleEfficient Quantum Algorithms for Estimating Gauss Sums
dc.typetext

Files

Collections

arXiv