EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM

DOI10.1142/S0129054103001996zbMATH Open1101.68582arXivquant-ph/0102014OpenAlexW1967900748MaRDI QIDQ5696935FDOQ5696935

Authors: Gábor Ivanyos, Frédéric Magniez, Miklos Santha 

Publication date: 19 October 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Abstract: In this paper we show that certain special cases of the hidden subgroup problem can be solved in polynomial time by a quantum algorithm. These special cases involve finding hidden normal subgroups of solvable groups and permutation groups, finding hidden subgroups of groups with small commutator subgroup and of groups admitting an elementary Abelian normal 2-subgroup of small index or with cyclic factor group.

Full work available at URL: https://arxiv.org/abs/quant-ph/0102014

Recommendations

• The Hidden Subgroup Problem and Quantum Computation Using Group Representations
• Quantum solution to the hidden subgroup problem for poly-near-Hamiltonian groups
• Normal subgroup reconstruction and quantum computation using group representations
• Quantum mechanical algorithms for the nonabelian hidden subgroup problem
• scientific article; zbMATH DE number 1304334

zbMATH Keywords

quantum computinghidden subgroup problemBlack-box groups

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Cites Work

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• On the Power of Quantum Computation
• On the minimal degrees of projective representations of the finite Chevalley groups
• Projective Representations of Minimum Degree of Group Extensions

Cited In (34)

• Quantum property testing of group solvability
• Quantum solution to the hidden subgroup problem for poly-near-Hamiltonian groups
• Niederreiter cryptosystems using quasi-cyclic codes that resist quantum Fourier sampling
• Is Grover's algorithm a quantum hidden subgroup algorithm?
• Normal subgroup reconstruction and quantum computation using group representations
• Hidden translation and translating coset in quantum computing
• There are no post-quantum weakly pseudo-free families in any nontrivial variety of expanded groups
• Quantum algorithms for a set of group theoretic problems
• The Hidden Subgroup Problem and Quantum Computation Using Group Representations
• On the quantum complexity of the continuous hidden subgroup problem
• Title not available (Why is that?)
• An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Extraspecial Groups
• Sample complexity of hidden subgroup problem
• Title not available (Why is that?)
• Complexity classes of equivalence problems revisited
• An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
• Title not available (Why is that?)
• On quantum algorithms for noncommutative hidden subgroups
• Permutation groups, minimal degrees and quantum computing.
• An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups
• Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• Title not available (Why is that?)
• Reduction of the semigroup-action problem on a module to the hidden-subgroup problem
• The quantum query complexity of the abelian hidden subgroup problem
• Hidden translation and orbit coset in quantum computing
• Quantum algorithms for solvable groups
• Quantum algorithms for the hidden subgroup problem on some semi-direct product groups by reduction to abelian cases
• Quantum Algorithms for Abelian Difference Sets and Applications to Dihedral Hidden Subgroups
• Solutions to the hidden subgroup problem on some metacyclic groups
• Efficient quantum algorithms for the hidden subgroup problem over semi-direct product groups
• Quantum mechanical algorithms for the nonabelian hidden subgroup problem
• Quantum Algorithms for Some Hidden Shift Problems
• Graph Isomorphism is in SPP
• Quantum algorithms for algebraic problems

This page was built for publication: EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5696935)