Algorithms · Hidden-period / factoring
Ideals in a finite black-box ring
Given black-box access to a finite ring R, not necessarily commutative, together with a list of generators for an ideal I in R, find an additive basis representation for I.
Attested & literatureUpdated
Open on the mapView frozen graph
- Record typeLiterature reference
- Speedup class (secondary source)Superpolynomial
- Primary source on the speedupNot checked against the primary source yet
- Reported costpoly(log |R|) time to find an additive basis representation for an ideal I in a finite ring R, the same order the Zoo states for finding additive generators of (R,+) itself, against known classical algorithms that the Zoo says scale as poly(|R|); neither source quotes an exponent, a constant factor or a gate count, and neither quotes a separate cost for any of the ideal problems derived from the basis.
- Papers1
Given black-box access to a finite ring R, not necessarily commutative, together with a list of generators for an ideal I in R, find an additive basis representation for I. The Zoo sets the problem in a model where black boxes implement the addition and multiplication operations on a finite ring R, not necessarily commutative, and records that under addition alone R forms a finite Abelian group (R,+), and that a quantum computer can find in poly(log |R|) time a set of additive generators whose cyclic subgroups decompose (R,+) as a direct product, the number of those generators being polylogarithmic in |R|; that decomposition is what allows efficient computation of a multiplication tensor for R. Wocjan, Jordan, Ahmadi and Brennan carry this from the ring to its ideals: given black-box access to R and a list of generators for an ideal I, their algorithm finds an additive basis representation for I, which the abstract describes as a generalization of a quantum algorithm of Arvind et al. that finds a basis representation for R itself. The paper then treats that basis as a primitive and derives from it procedures to test whether two ideals are identical, find their intersection and their quotient, prove whether a given ring element belongs to a given ideal, prove whether a given element is a unit and if so find its inverse, find the additive and multiplicative identities, compute the order of an ideal, solve linear equations over rings, decide whether an ideal is maximal, find annihilators, and test the injectivity and surjectivity of ring homomorphisms. The abstract states that these problems appear to be hard classically.
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 →
The Zoo sets the problem in a model where black boxes implement the addition and multiplication operations on a finite ring R, not necessarily commutative, and records that under addition alone R forms a finite Abelian group (R,+), and that a quantum computer can find in poly(log |R|) time a set of additive generators whose cyclic subgroups decompose (R,+) as a direct product, the number of those generators being polylogarithmic in |R|; that decomposition is what allows efficient computation of a multiplication tensor for R. Wocjan, Jordan, Ahmadi and Brennan carry this from the ring to its ideals: given black-box access to R and a list of generators for an ideal I, their algorithm finds an additive basis representation for I, which the abstract describes as a generalization of a quantum algorithm of Arvind et al. that finds a basis representation for R itself. The paper then treats that basis as a primitive and derives from it procedures to test whether two ideals are identical, find their intersection and their quotient, prove whether a given ring element belongs to a given ideal, prove whether a given element is a unit and if so find its inverse, find the additive and multiplicative identities, compute the order of an ideal, solve linear equations over rings, decide whether an ideal is maximal, find annihilators, and test the injectivity and surjectivity of ring homomorphisms. The abstract states that these problems appear to be hard classically. 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 checked against the primary source yet. Reported cost: poly(log |R|) time to find an additive basis representation for an ideal I in a finite ring R, the same order the Zoo states for finding additive generators of (R,+) itself, against known classical algorithms that the Zoo says scale as poly(|R|); neither source quotes an exponent, a constant factor or a gate count, and neither quotes a separate cost for any of the ideal problems derived from the basis..
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)
- Superpolynomial
- Primary source on the speedup
- Not checked against the primary source yet
- Reported cost
- poly(log |R|) time to find an additive basis representation for an ideal I in a finite ring R, the same order the Zoo states for finding additive generators of (R,+) itself, against known classical algorithms that the Zoo says scale as poly(|R|); neither source quotes an exponent, a constant factor or a gate count, and neither quotes a separate cost for any of the ideal problems derived from the basis.
- Speedup class
- Superpolynomial (not yet checked against the record's own primary paper)
- Complexity basis
- abstract of arXiv:0908.0022: "We show how to find an additive basis representation for I in poly(log |R|) time." Quantum Algorithm Zoo entry "Finite Rings and Ideals", with the scraped spacing normalized and its LaTeX rendered into Unicode: "on a quantum computer one can find in poly(log |R|) time a set of additive generators {h₁, …, hₘ} ⊂ R" and, from the clause that follows in the same sentence, "m is polylogarithmic in |R|", and, for the classical side, "Known classical algorithms for these problems scale as poly(|R|)." Neither clause carries an exponent, a constant factor, a gate count or a qubit count.
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Hidden-period / factoring 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: Ideals in a finite black-box ring
PROBLEM: Given black-box access to a finite ring R, not necessarily commutative, together with a list of generators for an ideal I in R, find an additive basis representation for I.
IDEA: The Zoo sets the problem in a model where black boxes implement the addition and multiplication operations on a finite ring R, not necessarily commutative, and records that under addition alone R forms a finite Abelian group (R,+), and that a quantum computer can find in poly(log |R|) time a set of additive generators whose cyclic subgroups decompose (R,+) as a direct product, the number of those generators being polylogarithmic in |R|; that decomposition is what allows efficient computation of a multiplication tensor for R. Wocjan, Jordan, Ahmadi and Brennan carry this from the ring to its ideals: given black-box access to R and a list of generators for an ideal I, their algorithm finds an additive basis representation for I, which the abstract describes as a generalization of a quantum algorithm of Arvind et al. that finds a basis representation for R itself. The paper then treats that basis as a primitive and derives from it procedures to test whether two ideals are identical, find their intersection and their quotient, prove whether a given ring element belongs to a given ideal, prove whether a given element is a unit and if so find its inverse, find the additive and multiplicative identities, compute the order of an ideal, solve linear equations over rings, decide whether an ideal is maximal, find annihilators, and test the injectivity and surjectivity of ring homomorphisms. The abstract states that these problems appear to be hard classically.
REPORTED COST: poly(log |R|) time to find an additive basis representation for an ideal I in a finite ring R, the same order the Zoo states for finding additive generators of (R,+) itself, against known classical algorithms that the Zoo says scale as poly(|R|); neither source quotes an exponent, a constant factor or a gate count, and neither quotes a separate cost for any of the ideal problems derived from the basis.
BASIS: abstract of arXiv:0908.0022: "We show how to find an additive basis representation for I in poly(log |R|) time." Quantum Algorithm Zoo entry "Finite Rings and Ideals", with the scraped spacing normalized and its LaTeX rendered into Unicode: "on a quantum computer one can find in poly(log |R|) time a set of additive generators {h₁, …, hₘ} ⊂ R" and, from the clause that follows in the same sentence, "m is polylogarithmic in |R|", and, for the classical side, "Known classical algorithms for these problems scale as poly(|R|)." Neither clause carries an exponent, a constant factor, a gate count or a qubit count.
PRIMARY SOURCE: Pawel M. Wocjan, Stephen P. Jordan, Hamed Ahmadi, Joseph P. Brennan (2009), Efficient quantum processing of ideals in finite rings — https://arxiv.org/abs/0908.0022
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.
Where this sits
This record is named by the layer graph at:
- Recover the period of a periodic function Slot
Takes A circuit evaluating f on a superposition of inputs, the promise that f is periodic, the kind of object its period is (an integer in a finite cyclic group, an irrational real, a lattice of rank r), and — where the period is not an integer — the precision wanted. Returns The period: an exact integer where the group is finite, or an approximation to the requested precision together with the classical post-processing that turned the measured samples into it.
Related entries
- Discrete logarithm on a quantum computer
Algorithms
- Shor period finding
Algorithms
- Hidden nonlinear structures over finite fields
Algorithms
- Quantum Fourier Transform
Algorithms
References
- Efficient quantum processing of ideals in finite rings
Pawel M. Wocjan, Stephen P. Jordan, Hamed Ahmadi, Joseph P. Brennan · 2009
Primary source: it states the poly(log |R|) additive basis representation for an ideal I given by a list of generators, describes that result as generalizing the quantum algorithm of Arvind et al. for R itself, and presents the basis as a primitive from which the ideal problems listed above are derived. Consult it for the black-box ring model it assumes and for the cost of each derived problem, since the abstract quotes only the one bound.