Hidden Subgroup States are Almost Orthogonal

Details Hidden Subgroup States are Almost Orthogonal Hidden Subgroup States are Almost Orthogonal

1999-01-14

arxiv.org/abs/quant-ph/9901034v1

Physics

Quantum Physics

5 pages, no figures

Scientific paper

It is well known that quantum computers can efficiently find a hidden subgroup $H$ of a finite Abelian group $G$. This implies that after only a polynomial (in $\log |G|$) number of calls to the oracle function, the states corresponding to different candidate subgroups have exponentially small inner product. We show that this is true for noncommutative groups also. We present a quantum algorithm which identifies a hidden subgroup of an arbitrary finite group $G$ in only a linear (in $\log |G|$) number of calls to the oracle function. This is exponentially better than the best classical algorithm. However our quantum algorithm requires an exponential amount of time, as in the classical case.

Affiliated with

Also associated with

No associations

Rating

Hidden Subgroup States are Almost Orthogonal 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 Subgroup States are Almost Orthogonal, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hidden Subgroup States are Almost Orthogonal will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-597699