Quantum factoring, discrete logarithms and the hidden subgroup problem

Abstract

Amongst the most remarkable successes of quantum computation are Shor's efficient quantum algorithms for the computational tasks of integer factorisation and the evaluation of discrete logarithms. In this article we review the essential ingredients of these algorithms and draw out the unifying generalization of the so-called abelian hidden subgroup problem. This involves an unexpectedly harmonious alignment of the formalism of quantum physics with the elegant mathematical theory of group representations and fourier transforms on finite groups. Finally we consider the non-abelian hidden subgroup problem mentioning some open questions where future quantum algorithms may be expected to have a substantial impact.

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

Cited by in corpus (42)

• Full-State Quantum Circuit Simulation by Using Data Compression
• The Hidden Subgroup Problem - Review and Open Problems
• QASMBench: A Low-level QASM Benchmark Suite for NISQ Evaluation and Simulation
• Graph isomorphism and adiabatic quantum computing
• Large-Scale Simulation of Shor's Quantum Factoring Algorithm
• The Symmetric Group Defies Strong Fourier Sampling: Part II
• A monomial matrix formalism to describe quantum many-body states
• Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure
• The Hidden Subgroup Problem in Affine Groups: Basis Selection in Fourier Sampling
• Zoology of Atlas-groups: dessins d'enfants, finite geometries and quantum commutation
• Entanglement of Periodic States, the Quantum Fourier Transform and Shor's Factoring Algorithm
• Quantum computation from a quantum logical perspective
• QGo: Scalable Quantum Circuit Optimization Using Automated Synthesis
• New Developments in Quantum Algorithms
• Easy and hard functions for the Boolean hidden shift problem
• Countinuous Quantum Hidden Subgroup Algorithms
• Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem
• Interconnection Networks for Scalable Quantum Computers
• Fully graphical treatment of the quantum algorithm for the Hidden Subgroup Problem
• Quantum Hidden Subgroup Algorithms: The Devil Is in the Details
• Introduction to Grassmann Manifolds and Quantum Computation
• Explicit Multiregister Measurements for Hidden Subgroup Problems
• Supercomputer simulations of transmon quantum computers
• Information compression via hidden subgroup quantum autoencoders
• On solving systems of diagonal polynomial equations over finite fields
• Tight Results on Multiregister Fourier Sampling: Quantum Measurements for Graph Isomorphism Require Entanglement
• Unification of Finite Symmetries in Simulation of Many-body Systems on Quantum Computers
• TILT: Achieving Higher Fidelity on a Trapped-Ion Linear-Tape Quantum Computing Architecture
• Application of quantum algorithms to the study of permutations and group automorphisms
• The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts
• Categorical Quantum Dynamics
• Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups
• Quantum Algorithms for One-Dimensional Infrastructures
• Quantum algorithms for shifted subset problems
• A prime factorization based on quantum dynamics on a spin ensemble (I)
• Towards a Group Theoretic Quantum Encryption Scheme Based on Generalized Hidden Subgroup Problem
• On the classification of two-qubit group orbits and the use of coarse-grained 'shape' as a superselection property
• Signing Information in the Quantum Era
• Approximating uniform quantum channels
• An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group
• Quantum Measurements for Graph Isomorphism Require Entanglement: Tight Results on Multiregister Fourier Sampling (Withdrawn)
• The dihedral hidden subgroup problem