publication . Preprint . 2009

Quantum Fourier Transform Over Galois Rings

Zhang, Yong;
Open Access English
  • Published: 16 Apr 2009
Galois rings are regarded as "building blocks" of a finite commutative ring with identity. There have been many papers on classical error correction codes over Galois rings published. As an important warm-up before exploring quantum algorithms and quantum error correction codes over Galois rings, we study the quantum Fourier transform (QFT) over Galois rings and prove it can be efficiently preformed on a quantum computer. The properties of the QFT over Galois rings lead to the quantum algorithm for hidden linear structures over Galois rings.
arXiv: Mathematics::Number TheoryMathematics::Commutative Algebra
free text keywords: Quantum Physics
Download from

[1] P. Shor, Algorithms for Quantum Computation: Discrete Logrithms and Factorization, in Proceedings, 35th Annunal Symposium on Foudation of Computer Science (IEEE Press, Los Alamitos, CA, 1994).

[2] M. Nielsen and I. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 1999).

[3] J. N. de Beaudrap, R. Cleve and J. Watrous, Sharp Quantum vs. Classical Query Complexity Separation, arxiv: quant-ph/0011065v2.

[4] W. van Dam and S. Hallgren, Efficient Quantum Algorithms for Shifted Quadratic Character Problems, arXiv: quant-ph/0011067.

[5] T. Decker, J. Draisma and P. Wocjan, Efficient Quantum Algorithm for Identifying Hidden Polynomials, arXiv:0706.1219.

[6] B.R. MacDonald, Finite Rings with Identity (Marcel Dekker, 1974).

[7] G. Bini and F. Flamini, Finite Commutative Rings and Their Applications (Kluwer Academic Publishers, 2002).

[8] Z.X. Wan, Lectures on Finite Fields and Galois Rings (World Scientific, Singapore, 2003).

[9] A. Calderbank, E. Rains, P. Shor and N. Sloane, Quantum Error Correction via Codes over GF(4), IEEE Transactions on Information Theory, 44(4) (1998) 1369. [OpenAIRE]

[10] A.R. Hammons, P.V. Kumar, A. R. Calderbank, N. J. A. Sloane and P. Sol´e, The Z4-Linearity of Kerdock, Preparata, Goethals and Related Codes. IEEE Trans. Inform. Theory, 40 (1994), 301-319 [OpenAIRE]

[11] V. Shoup, A Computational Introduction to Number Theory and Algebra (Cambridge University Press, 2005).

[12] L. Hales and S. Hallgren, An Improved Quantum Fourier Thransform Algorithm and Applications, Proceedings of 41st Annual Symposium on Foundations of Computer Science (2000).

[13] E. Fredkin and T. Toffoli, Conservative Logic, Int. Journal of Theor. Phys., 21 (1982) 219-253.

Any information missing or wrong?Report an Issue