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/0012084 · Computing in Science & Engineering

Quantum factoring, discrete logarithms, and the hidden subgroup problem

Richard Jozsa

Published Jan 1, 2001• 148 citations
arXivHTMLPDF

Abstract

Among the most remarkable successes of quantum computation are Shor's efficient quantum algorithms for the computational tasks of integer factorization and the evaluation of discrete logarithms. This article reviews the essential ingredients of these algorithms and draws out the unifying generalization of the so-called hidden subgroup problem.

DOI
10.1109/5992.909000

Related papers

Quantum Factoring, Discrete Logarithms, and the Hidden Subgroup Problem

JozsaRichard

Among the most remarkable successes of quantum computation are Shor's efficient quantum algorithms for the computational tasks of integer factorization and the evaluation of discrete logarithms. In...

IEEE Multimedia•Mar 1, 1996•0 citations

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•30 citations

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.

arXiv:0808.0369•Aug 4, 2008•73 citations

The Hidden Subgroup Problem and Quantum Computation Using Group Representations

Sean Hallgren, Alexander C. Russell, Amnon Ta‐Shma

The hidden subgroup problem is the foundation of many quantum algorithms. An efficient solution is known for the problem over abelian groups, employed by both Simon's algorithm and Shor's factoring and discrete log algorithms. The nonabelian case, however, remains open; an efficient solution would give rise to an efficient quantum algorithm for graph isomorphism. We fully analyze a natural generalization of the algorithm for the abelian case to the nonabelian case and show that the algorithm determines the normal core of a hidden subgroup: in particular, normal subgroups can be determined. We show, however, that this immediate generalization of the abelian algorithm does not efficiently solve graph isomorphism.

SIAM Journal on Computing•Jan 1, 2003•107 citations

Dihedral Hidden Subgroup Problem: A Survey

Hirotada Kobayashi, François Le Gall

After Shor's discovery of an efficient quantum algorithm for integer factoring, hidden subgroup problems play a central role in developing efficient quantum algorithms. In spite of many intensive studies, no efficient quantum algorithms are known for hidden subgroup problems for many non-Abelian groups. Of particular interest are the hidden subgroup problems for the symmetric group and for the dihedral group, because an efficient algorithm for the former implies an efficient solution to the graph isomorphism problem, and that for the latter essentially solves a certain lattice-related problem whose hardness is assumed in cryptography. This paper focuses on the latter case and gives a comprehensive survey of known facts related to the dihedral hidden subgroup problem.

IPSJ Digital Courier•Jan 1, 2005•7 citations

Applications of abelian algebraic structures in quantum computation

Kevin C. Zatloukal

Shor's groundbreaking algorithms for integer factoring and discrete logarithm [58], along with their later generalizations 116, 35, 49, 18], demonstrated a unique ability of quantum computers to solve problems defined on abelian groups.In this thesis, we study ways in which that ability can be leveraged in order to solve problems on more complex structures such as non-abelian groups and hypergroups.This leads to new quantum algorithms for the hidden subgroup problem on nilpotent groups whose order is a product of large primes, the hidden subhypergroup problem on both strongly integral hypergroups and ultragroups, testing equivalence of group extensions, and computing the component parts of the cohomology groups of both group extensions and a generalization of simplicial complexes, amongst other problems.For each of those listed, we also show that no classical algorithm can achieve similar efficiency under standard cryptographic assumptions.

•Jan 1, 2016•0 citations
Among the most remarkable successes of quantum computation are Shor's efficient quantum algorithms for the computational tasks of integer factorization and the evaluation of discrete logarithms. This article reviews the essential ingredients of these algorithms and draws out the unifying generalization of the so-called hidden subgroup problem.
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.
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.
The hidden subgroup problem is the foundation of many quantum algorithms. An efficient solution is known for the problem over abelian groups, employed by both Simon's algorithm and Shor's factoring and discrete log algorithms. The nonabelian case, however, remains open; an efficient solution would give rise to an efficient quantum algorithm for graph isomorphism. We fully analyze a natural generalization of the algorithm for the abelian case to the nonabelian case and show that the algorithm determines the normal core of a hidden subgroup: in particular, normal subgroups can be determined. We show, however, that this immediate generalization of the abelian algorithm does not efficiently solve graph isomorphism.
After Shor's discovery of an efficient quantum algorithm for integer factoring, hidden subgroup problems play a central role in developing efficient quantum algorithms. In spite of many intensive studies, no efficient quantum algorithms are known for hidden subgroup problems for many non-Abelian groups. Of particular interest are the hidden subgroup problems for the symmetric group and for the dihedral group, because an efficient algorithm for the former implies an efficient solution to the graph isomorphism problem, and that for the latter essentially solves a certain lattice-related problem whose hardness is assumed in cryptography. This paper focuses on the latter case and gives a comprehensive survey of known facts related to the dihedral hidden subgroup problem.
Shor's groundbreaking algorithms for integer factoring and discrete logarithm [58], along with their later generalizations 116, 35, 49, 18], demonstrated a unique ability of quantum computers to solve problems defined on abelian groups.In this thesis, we study ways in which that ability can be leveraged in order to solve problems on more complex structures such as non-abelian groups and hypergroups.This leads to new quantum algorithms for the hidden subgroup problem on nilpotent groups whose order is a product of large primes, the hidden subhypergroup problem on both strongly integral hypergroups and ultragroups, testing equivalence of group extensions, and computing the component parts of the cohomology groups of both group extensions and a generalization of simplicial complexes, amongst other problems.For each of those listed, we also show that no classical algorithm can achieve similar efficiency under standard cryptographic assumptions.