Attested & literatureAlgorithmsComputational number theory2026-08-12

Exponential congruences over a finite field

exponential congruencediscrete logarithmcharacter sumsgrover searchfinite field

Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.

Given elements a, b, c, f, g of the multiplicative group of a finite field F_q, decide whether the exponential congruence af^x + bg^y = c has a solution in nonnegative integers x and y, and find one if it does. The problem generalizes the discrete logarithm and is connected to the hidden subgroup problem over semidirect product groups. Character-sum bounds do the number-theoretic work: if f and g have large enough multiplicative orders, a solution is guaranteed to exist inside a provably small search box, and a variance and Parseval argument sharpens that box in the typical case. The classical algorithm then factors q−1, bounds the box, and for each y in it computes a classical discrete logarithm to test for a matching x. The quantum algorithm keeps that structure and changes two things: Shor's algorithm replaces the classical discrete-logarithm subroutine, and Grover search replaces the exhaustive scan over the y-range. A sharper variant runs the Boyer-Brassard-Høyer-Tapp bounded-error search directly over the actual solutions when the product of the two orders is large enough. The paper reports six bounds in all, classical and quantum, worst case and typical case.

Circuit & simulation

problem

encodetransform

algorithm

transformmeasure

readout

measure

What this takes and returns

TakesNothingWhat joins here

No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.

Nothing in the Atlas meets this end.

ReturnsNothingWhat joins here

No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.

Nothing in the Atlas meets this end.

This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →

How it works

Character-sum bounds do the number-theoretic work: if f and g have large enough multiplicative orders, a solution is guaranteed to exist inside a provably small search box, and a variance and Parseval argument sharpens that box in the typical case. The classical algorithm then factors q−1, bounds the box, and for each y in it computes a classical discrete logarithm to test for a matching x. The quantum algorithm keeps that structure and changes two things: Shor's algorithm replaces the classical discrete-logarithm subroutine, and Grover search replaces the exhaustive scan over the y-range. A sharper variant runs the Boyer-Brassard-Høyer-Tapp bounded-error search directly over the actual solutions when the product of the two orders is large enough. The paper reports six bounds in all, classical and quantum, worst case and typical case. This record's speedup class, "Polynomial", is a secondary source's classification of the algebraic and number theoretic algorithms it files this under — not a claim its primary paper makes. Stated by the primary source: "While still superpolynomial in log q, this quantum algorithm is significantly faster than the best known classical algorithm, which has time complexity q^{9/8}(log q)^{O(1)}. Thus it gives an example of a natural problem where quantum algorithms provide about a cubic speed-up over classical ones.". Reported cost: q^(3/8)(log q)^(O(1)) on a quantum computer in the worst case, against q^(9/8)(log q)^(O(1)) for the best known classical algorithm. In the typical case the figures are q^(1/3)(log q)^(O(1)) quantum and q(log q)^(O(1)) classical. A sharper quantum variant runs in q^(1/2)(st)^(−1/4)(log q)^(O(1)) in terms of the multiplicative orders s and t, which the paper bounds above by O(q^(1/8)(log q)^(O(1)))..

Implementation

FrameworkUnsupported

exponential-congruences.txt

ALGORITHM: Exponential congruences over a finite field
PROBLEM: Given elements a, b, c, f, g of the multiplicative group of a finite field F_q, decide whether the exponential congruence af^x + bg^y = c has a solution in nonnegative integers x and y, and find one if it does. The problem generalizes the discrete logarithm and is connected to the hidden subgroup problem over semidirect product groups.
IDEA: Character-sum bounds do the number-theoretic work: if f and g have large enough multiplicative orders, a solution is guaranteed to exist inside a provably small search box, and a variance and Parseval argument sharpens that box in the typical case. The classical algorithm then factors q−1, bounds the box, and for each y in it computes a classical discrete logarithm to test for a matching x. The quantum algorithm keeps that structure and changes two things: Shor's algorithm replaces the classical discrete-logarithm subroutine, and Grover search replaces the exhaustive scan over the y-range. A sharper variant runs the Boyer-Brassard-Høyer-Tapp bounded-error search directly over the actual solutions when the product of the two orders is large enough. The paper reports six bounds in all, classical and quantum, worst case and typical case.
REPORTED COST: q^(3/8)(log q)^(O(1)) on a quantum computer in the worst case, against q^(9/8)(log q)^(O(1)) for the best known classical algorithm. In the typical case the figures are q^(1/3)(log q)^(O(1)) quantum and q(log q)^(O(1)) classical. A sharper quantum variant runs in q^(1/2)(st)^(−1/4)(log q)^(O(1)) in terms of the multiplicative orders s and t, which the paper bounds above by O(q^(1/8)(log q)^(O(1))).
BASIS: abstract of arXiv:0804.1109: "A quantum algorithm with time com- plexity q^{3/8}(log q)^{O(1)} is presented… this quantum algorithm is significantly faster than the best known classi- cal algorithm, which has time complexity q^{9/8}(log q)^{O(1)}."; section 4.1, Theorem 3: "…in time q^{3/8}(log q)^{O(1)} on a quantum computer."; section 4.2, Theorem 5, for the typical case: "…in time q^{1/3}(log q)^{O(1)} on a quantum computer."; section 3.2, Theorem 2, for the classical typical case: "…in deterministic time q(log q)^{O(1)} on a classical computer."; section 4.1, Theorem 4: "…in time q^{1/2}(st)^{-1/4}(log q)^{O(1)} on a quantum computer," with "the running time of the algorithm of Theorem 4 is upper bounded by O(q^{1/8}(log q)^{O(1)})".
PRIMARY SOURCE: Wim van Dam, Igor E. Shparlinski (2008), Classical and Quantum Algorithms for Exponential Congruences — https://arxiv.org/abs/0804.1109

This is a literature reference record, not an executable circuit.

A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.

Quantum vs classical

Classical baseline

Compare Computational number theory with the strongest classical method for the same instance, input budget, and output metric.

Quantum claim

This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.

How to compare

Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.

Declared gaps

Nobody has reviewed this record for gaps yet.

Literature & references

Classical and Quantum Algorithms for Exponential Congruences2008 · Wim van Dam, Igor E. Shparlinski

Primary source, and the source of both the quantum and the classical figures this record compares. Consult it for the character-sum bounds that fix the search box, for the distinction between the worst case and the typical case that produces two different pairs of bounds, and for section 6, where the authors keep efficient solution in time polynomial in log q open — the sentence that stops the cubic speedup from being read as tractability.

arxiv.org/abs/0804.1109 ↗

Verification

Attested & literature

Peer-reviewed paper

Method: Curation only. The problem statement and speedup class were checked against the Quantum Algorithm Zoo's entry "Solving Exponential Congruences" (Algebraic and Number Theoretic Algorithms); the primary reference's title, authors and submission year were read from its arXiv abs page; the complexity claim was taken from a clause of that paper's abstract (abstract of arXiv:0804.1109: "A quantum algorithm with time com- plexity q^{3/8}(log q)^{O(1)} is presented… this quantum algorithm is significantly faster than the best known classi- cal algorithm, which has time complexity q^{9/8}(log q)^{O(1)}."; section 4.1, Theorem 3: "…in time q^{3/8}(log q)^{O(1)} on a quantum computer."; section 4.2, Theorem 5, for the typical case: "…in time q^{1/3}(log q)^{O(1)} on a quantum computer."; section 3.2, Theorem 2, for the classical typical case: "…in deterministic time q(log q)^{O(1)} on a classical computer."; section 4.1, Theorem 4: "…in time q^{1/2}(st)^{-1/4}(log q)^{O(1)} on a quantum computer," with "the running time of the algorithm of Theorem 4 is upper bounded by O(q^{1/8}(log q)^{O(1)})".). No circuit was constructed, simulated or run.
Result: Pass · the record's problem, speedup class and primary reference agree with the two sources named above.
Caveat: This is a literature record: nothing was constructed, compiled, simulated or run, and no congruence was solved here. The speedup is real and stated by the authors, but it is a speedup between two algorithms that are both superpolynomial in the input size — the input is q written in binary, so log q is the length, and the abstract itself opens the comparison with "While still superpolynomial in log q". Section 5 says the same of every algorithm in the paper, and section 6 keeps efficient solution in time (log q)^(O(1)) open as a problem. So a cubic speedup here does not make the problem tractable, and this record should not be read as one that does. The classical figure is the best known algorithm rather than a proved lower bound. The rigorous subexponential discrete-logarithm algorithms that could sharpen the classical side are, as the paper notes, known only for special fields such as prime fields and binary fields. The elliptic-curve analogue is asserted to follow at the cost of only typographical changes but is not carried out. The bounds are asymptotic with unnamed (log q)^(O(1)) factors, so no gate count, qubit count or constant follows from them.

Facts

Record type: Literature reference
Speedup class (secondary source): Polynomial
Primary source on the speedup: Stated by the primary source: "While still superpolynomial in log q, this quantum algorithm is significantly faster than the best known classical algorithm, which has time complexity q^{9/8}(log q)^{O(1)}. Thus it gives an example of a natural problem where quantum algorithms provide about a cubic speed-up over classical ones."
Reported cost: q^(3/8)(log q)^(O(1)) on a quantum computer in the worst case, against q^(9/8)(log q)^(O(1)) for the best known classical algorithm. In the typical case the figures are q^(1/3)(log q)^(O(1)) quantum and q(log q)^(O(1)) classical. A sharper quantum variant runs in q^(1/2)(st)^(−1/4)(log q)^(O(1)) in terms of the multiplicative orders s and t, which the paper bounds above by O(q^(1/8)(log q)^(O(1))).
Secondary source for the speedup class: Quantum Algorithm Zoo — "Solving Exponential Congruences"
Section it is filed under: Algebraic and Number Theoretic Algorithms
Complexity basis: abstract of arXiv:0804.1109: "A quantum algorithm with time com- plexity q^{3/8}(log q)^{O(1)} is presented… this quantum algorithm is significantly faster than the best known classi- cal algorithm, which has time complexity q^{9/8}(log q)^{O(1)}."; section 4.1, Theorem 3: "…in time q^{3/8}(log q)^{O(1)} on a quantum computer."; section 4.2, Theorem 5, for the typical case: "…in time q^{1/3}(log q)^{O(1)} on a quantum computer."; section 3.2, Theorem 2, for the classical typical case: "…in deterministic time q(log q)^{O(1)} on a classical computer."; section 4.1, Theorem 4: "…in time q^{1/2}(st)^{-1/4}(log q)^{O(1)} on a quantum computer," with "the running time of the algorithm of Theorem 4 is upper bounded by O(q^{1/8}(log q)^{O(1)})".
Circuit: Not supplied

Source

Classical and Quantum Algorithms for Exponential Congruences ↗

Kind: curated reference
Reviewed by: Leona Quantum curation pass
License: Citation metadata only; source publication terms apply