Hidden translation and orbit coset in quantum computing

We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of non-abelian groups including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in Z p n , whenever p is a fixed prime. For the induction step, we introduce the problem Orbit Coset generalizing both Hidden Translation and Hidden Subgroup , and prove a powerful self-reducibility result: Orbit Coset in a finite group G is reducible to Orbit Coset in G/N and subgroups of N , for any solvable normal subgroup N of G .

Authors

• Katalin Friedl
• Gábor Ivanyos
• Frédéric Magniez
• Miklos Santha
• Pranab Sen

Keywords

No keywords are indexed for this paper.