Primary source, and the paper the Quantum Algorithm Zoo credits with first formulating this algorithm in full generality. Theorem 1 recovers the hidden linear structure of a function from Z^k to an arbitrary range from an oracle for it, in random quantum polynomial time; Theorem 2 recovers the smallest positive period of a function on the integers that need not be one to one. Its corollaries are that the general discrete logarithm problem and factoring are each solvable in random quantum polynomial time. Consult it for the conditions on the multiplicity of the hidden function, which Theorem 1 pairs with a bound on the number of variables and Theorem 2 does not, and for the junk-bits construction. The generalization to any finite Abelian group is stated once, in the introduction, as a remark.
doi.org/10.1007/3-540-44750-4_34 ↗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.
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
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.
Circuit & simulation
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
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. This record's speedup class, "Superpolynomial", is a secondary source's classification of the oracular algorithms it files this under — not a claim its primary paper makes. 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))..
Implementation
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.
Quantum vs classical
Classical baseline
Compare Quantum query algorithm 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
The general Abelian case as one algorithm. The abstract lists order finding, factoring, discrete logarithms, stabilisers in Abelian groups and hidden subgroups of Abelian groups together, says the eigenvalue-estimation reading of the first four was already known, and shows the general Abelian case can be described and analysed as such too. Section 2 works order finding, Simon's problem, the discrete logarithm and the Abelian stabiliser problem as instances; section 4.3 states the promise; section 5 shrinks the control register to one bit. The appendix, on the many-to-one case, credits the question to Boneh and Lipton and reaches a condition of the same shape as theirs but on the order of the hidden subgroup rather than the period: the multiplicity must be below the smallest prime factor of |K|.
arxiv.org/abs/quant-ph/9903071 ↗The single-query special case the Zoo cites here, and a special case rather than a relaxation: section 1 calls the hidden linear structure problem a special case of the hidden subgroup problem as defined by Brassard and Høyer and by Mosca and Ekert, credits Hallgren with pointing the relationship out, and notes that standard technique would spend Θ(n) queries on it. It is a 2n-bit query problem over the field GF(2^n), solved exactly with one quantum query and a polynomial number of auxiliary operations, namely O(n) Hadamard gates then O(n^2) classical operations after a measurement, against Ω(2^(n/2)) queries classically. The exponential classical bound depends on the field structure and does not carry over to finite rings, and their problem differs from Boneh and Lipton's.
arxiv.org/abs/quant-ph/0011065 ↗