Quantum factoring, discrete logarithms, and the hidden subgroup problem

2000/12/17 by Richard Jozsa · 1 voice · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Abelian group #Algebra over a field #Algorithm #Computer science #Discrete logarithm #Discrete mathematics #Factorization #Generalization #Mathematical analysis #Mathematics #Physics #Pure mathematics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Fourier transform #Quantum Information and Cryptography #Quantum algorithm #Quantum computer #Quantum error correction #Quantum mechanics #Quantum-Dot Cellular Automata #Theoretical computer science #quant-ph

paper · pdf · doi:10.1109/5992.909000

latex2e, 15 pages. Review article prepared for special issue of "IEEE Computing in Science and Engineering"

arxiv created 2000/12/17 · arxiv published 2000/12/17 · arxiv updated 2000/12/17 · openalex publication_date 2001/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

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.

Citations

• Hidden Subgroup States are Almost Orthogonal
• On the Power of Quantum Computation
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

Cited by

• Categorical Quantum Dynamics
• The Hidden Subgroup Problem in Semidirect Products and Quasi-Hamiltonian Groups

Discussions

• More Pedantry: I think it's incorrect (oops) to say that the HSP algorithm is the same as Shor's. Shor only came up with explicit algorithms for Discrete Log and Factorization. I think it was Josza wh [bsky, 0 points, 2 comments]