Physics – Quantum Physics
Scientific paper
2002-01-22
Physics
Quantum Physics
63 pages, 4 figures, Table of Contents is included in paper. Typos corrected. Flowcharts of algorithms added. To appear in AMS
Scientific paper
The ultimate objective of this paper is to create a stepping stone to the development of new quantum algorithms. The strategy chosen is to begin by focusing on the class of abelian quantum hidden subgroup algorithms, i.e., the class of abelian algorithms of the Shor/Simon genre. Our strategy is to make this class of algorithms as mathematically transparent as possible. By the phrase "mathematically transparent" we mean to expose, to bring to the surface, and to make explicit the concealed mathematical structures that are inherently and fundamentally a part of such algorithms. In so doing, we create symbolic abelian quantum hidden subgroup algorithms that are analogous to the those symbolic algorithms found within such software packages as Axiom, Cayley, Maple, Mathematica, and Magma. As a spin-off of this effort, we create three different generalizations of Shor's quantum factoring algorithm to free abelian groups of finite rank. We refer to these algorithms as wandering (or vintage Z_Q) Shor algorithms. They are essentially quantum algorithms on free abelian groups A of finite rank n which, with each iteration, first select a random cyclic direct summand Z of the group A and then apply one iteration of the standard Shor algorithm to produce a random character of the "approximating" finite group A=Z_Q, called the group probe. These characters are then in turn used to find either the order P of a maximal cyclic subgroup Z_P of the hidden quotient group H_phi, or the entire hidden quotient group H_phi. An integral part of these wandering quantum algorithms is the selection of a very special random transversal, which we refer to as a Shor transversal. The algorithmic time complexity of the first of these wandering Shor algorithms is found to be O(n^2(lgQ)^3(lglgQ)^(n+1)).
Jr.
Kauffman Louis H.
Lomonaco Samuel J.
No associations
LandOfFree
Quantum Hidden Subgroup Problems: A Mathematical Perspective does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum Hidden Subgroup Problems: A Mathematical Perspective, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Hidden Subgroup Problems: A Mathematical Perspective will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-301177