Polynomial-Time Solution to the Hidden Subgroup Problem for a Class of\n non-abelian Groups

1998/12/23 by Martin Roetteler, Roetteler, Martin, Thomas Beth +1 · 16 citations
Computer Science · #Quantum Computing Algorithms and Architecture #Matrix Theory and Algorithms #Quantum Information and Cryptography

paper · pdf · doi:10.48550/arxiv.quant-ph/9812070

Abstract

We present a family of non-abelian groups for which the hidden subgroup\nproblem can be solved efficiently on a quantum computer.\n

Cited by

• Revisiting finite Abelian hidden subgroup problem and its distributed exact quantum algorithm
• An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
• Towards a Group Theoretic Quantum Encryption Scheme Based on Generalized Hidden Subgroup Problem
• A survey about Hidden Subgroup Problem from a mathematical and cryptographic perspective
• Quantum Computation and Lattice Problems
• A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
• Normalizer Circuits and Quantum Computation
• The Symmetric Group Defies Strong Fourier Sampling: Part II
• The Hidden Subgroup Problem in Affine Groups: Basis Selection in Fourier Sampling
• The Hidden Subgroup Problem - Review and Open Problems
• The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts
• Hidden Subhypergroup Problem
• Abelian Hypergroups and Quantum Computation
• Quantum Computation Beyond the Circuit Model
• Explicit Multiregister Measurements for Hidden Subgroup Problems
• A Quantum Observable for the Graph Isomorphism Problem

Related

• Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem
• Solution to the Hidden Subgroup Problem for a Class of Noncommutative Groups
• Hidden Subgroup States are Almost Orthogonal
• Polynomial-time quantum algorithm for solving the hidden subgroup problem
• The Hidden Subgroup Problem - Review and Open Problems