Efficient quantum processing of ideals in finite rings Export

@article{citeulike:5344640, abstract = {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.}, archivePrefix = {arXiv}, author = {Wocjan, Pawel M. and Jordan, Stephen P. and Ahmadi, Hamed and Brennan, Joseph P.}, citeulike-article-id = {5344640}, citeulike-linkout-0 = {http://arxiv.org/abs/0908.0022}, citeulike-linkout-1 = {http://arxiv.org/pdf/0908.0022}, day = {31}, eprint = {0908.0022}, keywords = {algorithms, computation, mathematics, physics, quantum-computation}, month = {Jul}, posted-at = {2009-08-04 18:49:39}, priority = {2}, title = {Efficient quantum processing of ideals in finite rings}, url = {http://arxiv.org/abs/0908.0022}, year = {2009} }

TY - JOUR ID - citeulike:5344640 L3 - citeulike-article-id:5344640 N2 - 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. TI - Efficient quantum processing of ideals in finite rings KW - algorithms KW - computation KW - mathematics KW - physics KW - quantum-computation AU - Wocjan, Pawel AU - Jordan, Stephen AU - Ahmadi, Hamed AU - Brennan, Joseph PY - 2009/Jul/31/ UR - http://arxiv.org/abs/0908.0022 ER -