The Abelian hidden subgroup problem

Let G be a finitely generated Abelian group and let H be a subgroup of G such that G/H is finite, and let f be a function on G with the promise that f(g1) = f(g2) if and only if g1 and g2 lie in the same coset of H. The task is to find H, that is, a set of generators for H, by making queries to f. Mosca and Ekert work order finding and period finding as G = Z with hidden subgroup rZ, Simon's problem as G = Z_2^l, and the discrete logarithm as G = Z_r × Z_r. The Zoo credits the first general formulation to Boneh and Lipton and calls attribution difficult: it subsumes many historically important algorithms as special cases, Simon's among them, which inspired Shor's period finding, and underlies the Pell's equation, principal ideal, unit group and class group algorithms. Their Theorem 1 recovers the hidden linear structure of a function from Z^k, Theorem 2 the period of a function on Z that need not be injective; the Abelian generality is one introductory sentence. Mosca and Ekert give the mechanism: f is constant on cosets of a subgroup K and distinct on each coset, and when G is a product of finitely many cyclic groups all are solved by a Fourier transform, a function application and an inverse transform. They then extend the eigenvalue-estimation reading, known already for order finding, factoring, discrete logarithms and Abelian stabilisers, to the general case. The row adds a special case one quantum query solves (Beaudrap, Cleve and Watrous) and two relaxations: Hales and Hallgren for period finding without injectivity, Shparlinski and Winterhof for most-significant-bit oracles.

Record type

Literature reference

Speedup class (secondary source)

Superpolynomial

Primary source on the speedup

Not stated by the primary source — the full text of Boneh and Lipton's 14-page CRYPTO '95 extended abstract, read as a PDF from the first author's Stanford page: abstract, section 1 (Introduction), section 2 (Main Results), section 3 (Applications), the lemmas and proofs of sections 4 through 8, and section 9 (Conclusions and Open Problems). It claims random quantum polynomial time for its own two theorems and for the general discrete logarithm problem and factoring, and names no classical running time, query count or lower bound to compare those against. Searching the extracted text for 'classical', 'exponential', 'lower bound', 'superpolynomial', 'speedup' and 'faster' returns 'classical' only in the abstract's closing sentence about junk bits, and 'lower bound' only in a lemma bounding a sum of roots of unity and in a counting step inside the proof of Theorem 1. was read and makes no such claim

Reported cost

O(log |G|) quantum queries to f against Ω(|G|) classically, both the Zoo's own, and black-box counts, not gate counts. Boneh and Lipton state their results as random quantum polynomial time in n = log q, not a query count, under conditions on the multiplicity m: Theorem 1 needs m and the variable count k at most n^O(1) and m below the smallest prime divisor of q, Theorem 2 the same on m alone. Beaudrap, Cleve and Watrous give a 2n-bit query problem over GF(2^n) solved exactly by one quantum query plus polynomially many auxiliary operations, where standard technique spends Θ(n) queries and bounded-error classical Ω(2^(n/2)).

Speedup class

Superpolynomial (checked against the record's own primary paper, which does not state it)

Complexity basis

Quantum Algorithm Zoo entry "Abelian Hidden Subgroup" (LaTeX rendered into Unicode): "This is solvable on a quantum computer using O(log |G|) queries, whereas classically Ω(|G|) are required." Boneh and Lipton, "Quantum Cryptanalysis of Hidden Linear Functions", section 2 (Main Results), the two conditions of Theorem 1: "Let n = log q then m and k are at most n^O(1)." and "Let p be the smallest prime divisor of q; then m < p."; Theorem 2 repeats the second and imposes the first on m alone. Abstract of arXiv:quant-ph/0011065: "can be solved exactly in the quantum case with a single query (and a polynomial number of auxiliary operations)"; its section 1 adds "exhibiting a 2n-bit query problem", "In the classical setting, Ω(2^(n/2)) queries to the black-box are necessary to solve the problem with bounded error." and the Θ(n) figure for standard hidden-subgroup technique.

Circuit

Not supplied

Quantum vs classical

ALGORITHM: The Abelian hidden subgroup problem
PROBLEM: Let G be a finitely generated Abelian group and let H be a subgroup of G such that G/H is finite, and let f be a function on G with the promise that f(g1) = f(g2) if and only if g1 and g2 lie in the same coset of H. The task is to find H, that is, a set of generators for H, by making queries to f. Mosca and Ekert work order finding and period finding as G = Z with hidden subgroup rZ, Simon's problem as G = Z_2^l, and the discrete logarithm as G = Z_r × Z_r.
IDEA: The Zoo credits the first general formulation to Boneh and Lipton and calls attribution difficult: it subsumes many historically important algorithms as special cases, Simon's among them, which inspired Shor's period finding, and underlies the Pell's equation, principal ideal, unit group and class group algorithms. Their Theorem 1 recovers the hidden linear structure of a function from Z^k, Theorem 2 the period of a function on Z that need not be injective; the Abelian generality is one introductory sentence. Mosca and Ekert give the mechanism: f is constant on cosets of a subgroup K and distinct on each coset, and when G is a product of finitely many cyclic groups all are solved by a Fourier transform, a function application and an inverse transform. They then extend the eigenvalue-estimation reading, known already for order finding, factoring, discrete logarithms and Abelian stabilisers, to the general case. The row adds a special case one quantum query solves (Beaudrap, Cleve and Watrous) and two relaxations: Hales and Hallgren for period finding without injectivity, Shparlinski and Winterhof for most-significant-bit oracles.
REPORTED COST: O(log |G|) quantum queries to f against Ω(|G|) classically, both the Zoo's own, and black-box counts, not gate counts. Boneh and Lipton state their results as random quantum polynomial time in n = log q, not a query count, under conditions on the multiplicity m: Theorem 1 needs m and the variable count k at most n^O(1) and m below the smallest prime divisor of q, Theorem 2 the same on m alone. Beaudrap, Cleve and Watrous give a 2n-bit query problem over GF(2^n) solved exactly by one quantum query plus polynomially many auxiliary operations, where standard technique spends Θ(n) queries and bounded-error classical Ω(2^(n/2)).
BASIS: Quantum Algorithm Zoo entry "Abelian Hidden Subgroup" (LaTeX rendered into Unicode): "This is solvable on a quantum computer using O(log |G|) queries, whereas classically Ω(|G|) are required." Boneh and Lipton, "Quantum Cryptanalysis of Hidden Linear Functions", section 2 (Main Results), the two conditions of Theorem 1: "Let n = log q then m and k are at most n^O(1)." and "Let p be the smallest prime divisor of q; then m < p."; Theorem 2 repeats the second and imposes the first on m alone. Abstract of arXiv:quant-ph/0011065: "can be solved exactly in the quantum case with a single query (and a polynomial number of auxiliary operations)"; its section 1 adds "exhibiting a 2n-bit query problem", "In the classical setting, Ω(2^(n/2)) queries to the black-box are necessary to solve the problem with bounded error." and the Θ(n) figure for standard hidden-subgroup technique.
PRIMARY SOURCE: Dan Boneh, Richard J. Lipton (1995), Quantum Cryptanalysis of Hidden Linear Functions — https://doi.org/10.1007/3-540-44750-4_34

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

• Shor period finding

  Algorithms

• Discrete logarithm on a quantum computer

  Algorithms

• Hidden shift problem

  Algorithms

• Quantum Fourier Transform

  Algorithms