Algorithms · Computational number theory
Exponential congruences over a finite field
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.
Attested & literatureUpdated
- Record typeLiterature reference
- Speedup class (secondary source)Polynomial
- Primary source on the speedupStated 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 costq^(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))).
- Papers1
A part this method uses, worked through
This page says Shor's algorithm
— here is a concrete, runnable instance of it.
Order-finding for 7 mod 15
3 counting qubits, 4 work qubits, finding the order of 7 modulo 15 (the order is 4: 7⁴ mod 15 = 1).
Where it ends up
- 00010006%
- 00010106%
- 00011006%
- 00011106%
- 12 more outcomes75%
The counting register reads 000, 010, 100 or 110, each equally likely, corresponding to the four powers k = 0, 1, 2, 3 of the order r = 4; the work register ends entangled with the counting outcome, holding one of 1, 7, 4 or 13. Repeating this and applying the continued-fractions step of the full algorithm to a nonzero outcome recovers the order r = 4 exactly.
Open this part in StudioA part this method uses, worked through
This page says Grover search
— here is a concrete, runnable instance of it.
Grover's algorithm finds |101⟩
3 qubits, searching for |101⟩ among 8 states, with 2 Grover iterations.
Where it ends up
- 10195%
- 0001%
- 1101%
- 0011%
- 4 more outcomes3%
Measuring gives 101, the marked state, with high probability.
One of its steps changes only phase: the outcome probabilities stay put while the state does not.
Open this part in StudioGiven 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.
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 →
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)))..
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 →
- 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))).
- Speedup class
- Polynomial (checked against the record's own primary paper, which states it)
- 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
This record is not a concrete 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.
Nobody has reviewed this record for gaps yet.
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.
Related entries
- Discrete logarithm on a quantum computer
Algorithms
- Grover unstructured search
Algorithms
- Shor period finding
Algorithms
References
- Classical and Quantum Algorithms for Exponential Congruences
Wim van Dam, Igor E. Shparlinski · 2008
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.