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

Black-box groupshidden subgroup problemquantum computing

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Nonnumerical algorithms (68W05) 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 minimal degrees of projective representations of the finite Chevalley groups
• On the Power of Quantum Computation
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Projective Representations of Minimum Degree of Group Extensions

Cited in

(34)

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

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)