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

DOI10.1142/S0129054103001996MaRDI QIDQ5696935zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(33)

• Quantum algorithms for algebraic problems
• Is Grover's algorithm a quantum hidden subgroup algorithm?
• Quantum solution to the hidden subgroup problem for poly-near-Hamiltonian groups
• Niederreiter cryptosystems using quasi-cyclic codes that resist quantum Fourier sampling
• Normal subgroup reconstruction and quantum computation using group representations
• Hidden translation and translating coset in quantum computing
• On the quantum complexity of the continuous hidden subgroup problem
• The Hidden Subgroup Problem and Quantum Computation Using Group Representations
• Quantum algorithms for a set of group theoretic problems
• There are no post-quantum weakly pseudo-free families in any nontrivial variety of expanded groups
• scientific article; zbMATH DE number 1406124 (Why is no real title available?)
• An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Extraspecial Groups
• Sample complexity of hidden subgroup problem
• scientific article; zbMATH DE number 5320411 (Why is no real title available?)
• Complexity classes of equivalence problems revisited
• An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
• scientific article; zbMATH DE number 1304334 (Why is no real title available?)
• Permutation groups, minimal degrees and quantum computing.
• On quantum algorithms for noncommutative hidden subgroups
• Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups
• scientific article; zbMATH DE number 7378343 (Why is no real title available?)
• 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
• Graph Isomorphism is in SPP
• Quantum Algorithms for Some Hidden Shift 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)