REVIEW 3 cited by
Efficient Quantum Algorithms for Estimating Gauss Sums
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original 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.
Forward citations
Cited by 3 Pith papers
-
Quantum Algorithms for Modular Factorials
Given a divisor q of p-1 of intermediate size, a bounded-error quantum algorithm computes n! mod p in time O~(q^c + sqrt(p/q)), breaking the square-root barrier.
-
Infinite temperature at zero energy
Periodic Feynman-Kitaev clocks built from linear feedback shift register circuits have provably volume-law-entangled ground states and almost all eigenstates.
-
On the Complexity of Decoded Quantum Interferometry
DQI resists classical simulation by locating high-probability outputs but is simulable at a low level of the polynomial hierarchy, constructively solves a MacWilliams-based coding bound, and corresponds to low-energy ...
Discussion (0). Continue with ORCID to comment.