Decomposing Finite Abelian Groups

2001/01/05 by Kevin K. H. Cheung, Michele Mosca, Cheung, Kevin K. H. +1 · 1 citation
Computer Science · Physics and Astronomy · #Data Structures and Algorithms (cs.DS) #F.1 #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.DS #quant-ph

paper · pdf · doi:10.48550/arxiv.cs/0101004

6 pages

arxiv created 2001/01/05 · arxiv updated 2009/11/30

Abstract

This paper describes a quantum algorithm for efficiently decomposing finite Abelian groups. Such a decomposition is needed in order to apply the Abelian hidden subgroup algorithm. Such a decomposition (assuming the Generalized Riemann Hypothesis) also leads to an efficient algorithm for computing class numbers (known to be at least as difficult as factoring).

Cited by

• The Hidden Subgroup Problem in Semidirect Products and Quasi-Hamiltonian Groups
• Group Order is in QCMA

Related

• Fully graphical treatment of the quantum algorithm for the Hidden Subgroup Problem
• Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem
• Hidden Subhypergroup Problem
• Polynomial-Time Solution to the Hidden Subgroup Problem for a Class of\n non-abelian Groups
• Revisiting finite Abelian hidden subgroup problem and its distributed exact quantum algorithm