01422nas a2200145 4500008004100000245005900041210005900100260001500159520097700174100002201151700002401173700001801197700002401215856003701239 2009 eng d00aEfficient quantum processing of ideals in finite rings0 aEfficient quantum processing of ideals in finite rings c2009/07/313 a Suppose we are given black-box access to a finite ring R, and a list of
generators for an ideal I in R. We show how to find an additive basis
representation for I in poly(log |R|) time. This generalizes a recent quantum
algorithm of Arvind et al. which finds a basis representation for R itself. We
then show that our algorithm is a useful primitive allowing quantum computers
to rapidly solve a wide variety of problems regarding finite rings. In
particular we show how to test whether two ideals are identical, find their
intersection, find 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. These problems appear to be hard classically.
1 aWocjan, Pawel, M.1 aJordan, Stephen, P.1 aAhmadi, Hamed1 aBrennan, Joseph, P. uhttp://arxiv.org/abs/0908.0022v1