Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0607046

Quantum Hidden Subgroup Algorithms: An Algorithmic Toolkit

Samuel J. Lomonaco, Louis H. Kauffman

Published Jul 6, 2006• 0 citations
arXivHTMLPDF

Abstract

One of the most promising and versatile approaches to creating new quantum algorithms is based on the quantum hidden subgroup (QHS) paradigm, originally suggested by Alexei Kitaev. This class of quantum algorithms encompasses the Deutsch-Jozsa, Simon, Shor algorithms, and many more. In this paper, our strategy for finding new quantum algorithms is to decompose Shor's quantum factoring algorithm into its basic primitives, then to generalize these primitives, and finally to show how to reassemble them into new QHS algorithms. Taking an "alphabetic building blocks approach," we use these primitives to form an "algorithmic toolkit" for the creation of new quantum algorithms, such as wandering Shor algorithms, continuous Shor algorithms, the quantum circle algorithm, the dual Shor algorithm, a QHS algorithm for Feynman integrals, free QHS algorithms, and more. Toward the end of this paper, we show how Grover's algorithm is most surprisingly "almost" a QHS algorithm, and how this result suggests the possibility of an even more complete "algorithmic tookit" beyond the QHS algorithms.

DOI
10.48550/arxiv.quant-ph/0607046

Related papers

Quantum Hidden Subgroup Algorithms: An Algorithmic Toolkit

Samuel J. Lomonaco, Louis H. Kauffman

Abstract One of the most promising and versatile approaches to creating new quantum algorithms is based on the quantum hidden subgroup (QHS) paradigm, originally suggested by Alexei Kitaev. This class of quantum algorithms encompasses the Deutsch-Jozsa, Simon, Shor algorithms, and many more.

Chapman & Hall/CRC eBooks•Sep 19, 2007•5 citations

Quantum Hidden Subgroup Problems: A Mathematical Perspective

Samuel J. Lomonaco, Louis Hirsch Kauffman

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)).

arXiv:quant-ph/0201095•Jan 22, 2002•14 citations

Is Grover's Algorithm a Quantum Hidden Subgroup Algorithm ?

Samuel J. Lomonaco, Louis Hirsch Kauffman

The arguments given in this paper suggest that Grover's and Shor's algorithms are more closely related than one might at first expect. Specifically, we show that Grover's algorithm can be viewed as a quantum algorithm which solves a non-abelian hidden subgroup problem (HSP). But we then go on to show that the standard non-abelian quantum hidden subgroup (QHS) algorithm can not find a solution to this particular HSP. This leaves open the question as to whether or not there is some modification of the standard non-abelian QHS algorithm which is equivalent to Grover's algorithm.

arXiv:quant-ph/0603140•Mar 15, 2006•0 citations

Continuous quantum hidden subgroup algorithms

Samuel J. Lomonaco, Louis Hirsch Kauffman

In this paper we show how to construct two continuous variable and one continuous functional quantum hidden subgroup (QHS) algorithms. These are respectively quantum algorithms on the additive group of reals R, the additive group R/Z of the reals R mod 1, i.e., the circle, and the additive group Paths of L2 paths x:[0,1] → Rn in real n-space Rn.

arXiv:quant-ph/0304084•Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Aug 5, 2003•8 citations

Geometric-Algebra Quantum-Like Algorithms: Simon's Algorithm

Tomasz Magulski, Łukasz Orłowski

This is continuation of the approach to performing quantum algorithms using geometric structures which was presented by Aerts and Czachor. We solve the Simon's problem which, next to the Shor's alghorithm, is a representative of a quantum hidden subgroup class. We also highlight some advantages resulting from the fact that no quantum mechanics is involved.

arXiv:0705.4289•May 29, 2007•1 citation

Quantum Algorithms

Michele Mosca

This article surveys the state of the art in quantum computer algorithms, including both black-box and non-black-box results. It is infeasible to detail all the known quantum algorithms, so a representative sample is given. This includes a summary of the early quantum algorithms, a description of the Abelian Hidden Subgroup algorithms (including Shor's factoring and discrete logarithm algorithms), quantum searching and amplitude amplification, quantum algorithms for simulating quantum mechanical systems, several non-trivial generalizations of the Abelian Hidden Subgroup Problem (and related techniques), the quantum walk paradigm for quantum algorithms, the paradigm of adiabatic algorithms, a family of ``topological'' algorithms, and algorithms for quantum tasks which cannot be done by a classical computer, followed by a discussion.

•Aug 4, 2008•27 citations
One of the most promising and versatile approaches to creating new quantum algorithms is based on the quantum hidden subgroup (QHS) paradigm, originally suggested by Alexei Kitaev. This class of quantum algorithms encompasses the Deutsch-Jozsa, Simon, Shor algorithms, and many more. In this paper, our strategy for finding new quantum algorithms is to decompose Shor's quantum factoring algorithm into its basic primitives, then to generalize these primitives, and finally to show how to reassemble them into new QHS algorithms. Taking an "alphabetic building blocks approach," we use these primitives to form an "algorithmic toolkit" for the creation of new quantum algorithms, such as wandering Shor algorithms, continuous Shor algorithms, the quantum circle algorithm, the dual Shor algorithm, a QHS algorithm for Feynman integrals, free QHS algorithms, and more. Toward the end of this paper, we show how Grover's algorithm is most surprisingly "almost" a QHS algorithm, and how this result suggests the possibility of an even more complete "algorithmic tookit" beyond the QHS algorithms.
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)).
The arguments given in this paper suggest that Grover's and Shor's algorithms are more closely related than one might at first expect. Specifically, we show that Grover's algorithm can be viewed as a quantum algorithm which solves a non-abelian hidden subgroup problem (HSP). But we then go on to show that the standard non-abelian quantum hidden subgroup (QHS) algorithm can not find a solution to this particular HSP. This leaves open the question as to whether or not there is some modification of the standard non-abelian QHS algorithm which is equivalent to Grover's algorithm.
This article surveys the state of the art in quantum computer algorithms, including both black-box and non-black-box results. It is infeasible to detail all the known quantum algorithms, so a representative sample is given. This includes a summary of the early quantum algorithms, a description of the Abelian Hidden Subgroup algorithms (including Shor's factoring and discrete logarithm algorithms), quantum searching and amplitude amplification, quantum algorithms for simulating quantum mechanical systems, several non-trivial generalizations of the Abelian Hidden Subgroup Problem (and related techniques), the quantum walk paradigm for quantum algorithms, the paradigm of adiabatic algorithms, a family of ``topological'' algorithms, and algorithms for quantum tasks which cannot be done by a classical computer, followed by a discussion.