Hidden Translation and Orbit Coset in Quantum Computing

Details Hidden Translation and Orbit Coset in Quantum Computing Hidden Translation and Orbit Coset in Quantum Computing

2002-11-15

arxiv.org/abs/quant-ph/0211091v2

Physics

Quantum Physics

New and simpler proofs, and also different intermediate results. 21 pages

Scientific paper

We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of non-abelian solvable 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 Translationand Hidden Subgroup, and prove a powerful self-reducibility result: Orbit Coset in a finite solvable group $G$ is reducible to instances of Orbit Coset in $G/N$ and $N$, for appropriate normal subgroups $N$ of $G$. Our self-reducibility framework combined with Kuperberg's subexponential quantum algorithm for solving Hidden Translation in any abelian group, leads to subexponential quantum algorithms for Hidden Translation and Hidden Subgroup in any solvable group.

Affiliated with

Also associated with

No associations

Rating

Hidden Translation and Orbit Coset in Quantum Computing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hidden Translation and Orbit Coset in Quantum Computing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hidden Translation and Orbit Coset in Quantum Computing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-630173