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

Abstract

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

16 pages, LaTeX2e, 3 figures

References in corpus (1)

• Elementary gates for quantum computation

Cited by in corpus (29)

• The quantum query complexity of the hidden subgroup problem is polynomial
• From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
• A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
• The Hidden Subgroup Problem - Review and Open Problems
• A Quantum Observable for the Graph Isomorphism Problem
• Quantum Computation Beyond the Circuit Model
• The Symmetric Group Defies Strong Fourier Sampling: Part II
• Optimal measurements for the dihedral hidden subgroup problem
• The Hidden Subgroup Problem in Affine Groups: Basis Selection in Fourier Sampling
• Quantum Hidden Subgroup Algorithms: The Devil Is in the Details
• Explicit Multiregister Measurements for Hidden Subgroup Problems
• Normalizer Circuits and Quantum Computation
• Abelian Hypergroups and Quantum Computation
• Symmetry in quantum walks
• Tight Results on Multiregister Fourier Sampling: Quantum Measurements for Graph Isomorphism Require Entanglement
• Quantum algorithms for solvable groups
• The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts
• Quantum Measurements for Hidden Subgroup Problems with Optimal Sample Complexity
• Hidden Subhypergroup Problem
• Quantum Fourier Sampling is Guaranteed to Fail to Compute Automorphism Groups of Easy Graphs
• An efficient quantum algorithm for the hidden subgroup problem in extraspecial groups
• An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
• Quantum Computation and Lattice Problems
• On the Existence of certain Quantum Algorithms
• Towards a Group Theoretic Quantum Encryption Scheme Based on Generalized Hidden Subgroup Problem
• The hidden subgroup problem and permutation group theory
• Permutation groups, minimal degrees and quantum computing
• Quantum Property Testing for Solvable Groups
• Quantum Measurements for Graph Isomorphism Require Entanglement: Tight Results on Multiregister Fourier Sampling (Withdrawn)