dorsal/arxiv
View SchemaQuantum Hidden Subgroup Problems: A Mathematical Perspective
| Authors | Samuel J. Lomonaco, Jr., Louis H. Kauffman |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0201095 |
| URL | https://arxiv.org/abs/quant-ph/0201095 |
Abstract
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)).
{
"annotation_id": "fcea55f0-d7fe-4e82-baf9-d236a09c3ccc",
"date_created": "2026-03-02T18:01:49.434000Z",
"date_modified": "2026-03-02T18:01:49.434000Z",
"file_hash": "c044aa16a184cbf53b4dd4c178a48730c9f698fb12b42bf686ee570deeffa722",
"private": false,
"record": {
"abstract": "The ultimate objective of this paper is to create a stepping stone to the\ndevelopment of new quantum algorithms. The strategy chosen is to begin by\nfocusing on the class of abelian quantum hidden subgroup algorithms, i.e., the\nclass of abelian algorithms of the Shor/Simon genre. Our strategy is to make\nthis class of algorithms as mathematically transparent as possible. By the\nphrase \"mathematically transparent\" we mean to expose, to bring to the surface,\nand to make explicit the concealed mathematical structures that are inherently\nand fundamentally a part of such algorithms. In so doing, we create symbolic\nabelian quantum hidden subgroup algorithms that are analogous to the those\nsymbolic algorithms found within such software packages as Axiom, Cayley,\nMaple, Mathematica, and Magma.\n As a spin-off of this effort, we create three different generalizations of\nShor\u0027s quantum factoring algorithm to free abelian groups of finite rank. We\nrefer to these algorithms as wandering (or vintage Z_Q) Shor algorithms. They\nare essentially quantum algorithms on free abelian groups A of finite rank n\nwhich, with each iteration, first select a random cyclic direct summand Z of\nthe group A and then apply one iteration of the standard Shor algorithm to\nproduce a random character of the \"approximating\" finite group A=Z_Q, called\nthe group probe. These characters are then in turn used to find either the\norder P of a maximal cyclic subgroup Z_P of the hidden quotient group H_phi, or\nthe entire hidden quotient group H_phi. An integral part of these wandering\nquantum algorithms is the selection of a very special random transversal, which\nwe refer to as a Shor transversal. The algorithmic time complexity of the first\nof these wandering Shor algorithms is found to be O(n^2(lgQ)^3(lglgQ)^(n+1)).",
"arxiv_id": "quant-ph/0201095",
"authors": [
"Samuel J. Lomonaco, Jr.",
"Louis H. Kauffman"
],
"categories": [
"quant-ph"
],
"title": "Quantum Hidden Subgroup Problems: A Mathematical Perspective",
"url": "https://arxiv.org/abs/quant-ph/0201095"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "c24537dc-b8bf-404d-b825-a425b1686fac",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}