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.
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
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.
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 →
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.
How it works
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..
Implementation
Unsupported
finite-ring-ideals.txt
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 inpoly(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 aspoly(|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.
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.
Declared gaps
Nobody has reviewed this record for gaps yet.
Literature & references
Efficient quantum processing of ideals in finite rings2009 · Pawel M. Wocjan, Stephen P. Jordan, Hamed Ahmadi, Joseph P. Brennan
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.