Abstract
We study the complexity of some computational problems on finite black-box rings whose elements are encoded as strings of a given length and the ring operations are performed by a black-box oracle. We give a polynomial-time quantum algorithm to compute a basis representation for a given black-box ring. Using this result we obtain polynomial-time quantum algorithms for several natural computational problems over black-box rings.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, M., Kayal, N., Saxena, N.: PRIMES is in P. Annals of Mathematics 160(2), 781–793 (2004)
Agrawal, M., Saxena, N.: Automorphisms of Finite Rings and Applications to Complexity of Problems. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 1–17. Springer, Heidelberg (2005)
Babai, L.: Local Expansion of Vertex-Transitive Graphs and Random Generation in Finite Groups. In: STOC 1991, pp. 164–174 (1991)
Babai, L.: Bounded Round Interactive Proofs in Finite Groups. SIAM J. Discrete Math. 5(1), 88–111 (1992)
Balcázar, J.L., DÃaz, J., Gabarró, D.: Structural Complexity I. ETACS Monographs on Theoretical Computer Science. Springer, Heidelberg (1988) (I)
Balcázar, J.L., DÃaz, J., Gabarró, D.: Structural Complexity II. ETACS Monographs on Theoretical Computer Science. Springer, Heidelberg (1990) (II)
Babai, L., Moran, S.: Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes. Journal Comput. Syst. Sciences 36(2), 254–276 (1988)
McDonald, B.R.: Finite Rings with Identity. Marcel Dekker Inc., New York (1974)
Babai, L., Szemerédi, E.: On the complexity of matrix group problems I. In: Proc. 25th IEEE Sympos. on the Foundation of Computer Science, pp. 229–240 (1984)
Vazirani, U., Bernstein, E.: Quantum Complexity Theory. Special issue on Quantum Computation of the Siam Journal of Computing (October 1997)
Cheung, K.K.H., Mosca, M.: Decomposing Finite Abelian Groups. Los Alamos Preprint Archive, quant-ph/0101004 (2001)
Eberly, W.: Computations for algebras and group representations, PhD thesis. University of Toronto (1989)
Friedl, K., Rónyai, L.: Polynomial time solutions for some problems in computational algebra. In: Proc. 17th Ann. Symp. Theory of Computing, pp. 153–162 (1985)
Kayal, N., Saxena, N.: On the Ring Isomorphism and Automorphism Problems. In: IEEE Conference on Computational Complexity, pp. 2–12 (2005)
Lenstra Jr., H.W.: Algorithms in algebraic number theory. Bulletin of the AMS 26(2), 211–244 (1992)
Shor, P.: Polynomial time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing 26(5), 1484–1509 (1997)
Sanders, T., Shokrollahi, M.A.: Deciding properties of polynomials without factoring. In: Proc. 38th IEEE Foundations of Computer Science, pp. 46–55 (1997)
Gathen, J.v.z., Gerhard, J.: Modern Computer Algebra, 2nd edn. Cambridge University Press, Cambridge (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Arvind, V., Das, B., Mukhopadhyay, P. (2006). The Complexity of Black-Box Ring Problems. In: Chen, D.Z., Lee, D.T. (eds) Computing and Combinatorics. COCOON 2006. Lecture Notes in Computer Science, vol 4112. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11809678_15
Download citation
DOI: https://doi.org/10.1007/11809678_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-36925-7
Online ISBN: 978-3-540-36926-4
eBook Packages: Computer ScienceComputer Science (R0)