Strong Fourier Sampling Fails over $G^n$

Details Strong Fourier Sampling Fails over $G^n$ Strong Fourier Sampling Fails over $G^n$

2005-11-07

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

Physics

Quantum Physics

12 pages

Scientific paper

We present a negative result regarding the hidden subgroup problem on the powers $G^n$ of a fixed group $G$. Under a condition on the base group $G$, we prove that strong Fourier sampling cannot distinguish some subgroups of $G^n$. Since strong sampling is in fact the optimal measurement on a coset state, this shows that we have no hope of efficiently solving the hidden subgroup problem over these groups with separable measurements on coset states (that is, using any polynomial number of single-register coset state experiments). Base groups satisfying our condition include all nonabelian simple groups. We apply our results to show that there exist uniform families of nilpotent groups whose normal series factors have constant size and yet are immune to strong Fourier sampling.

Affiliated with

Also associated with

No associations

Rating

Strong Fourier Sampling Fails over $G^n$ 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 Strong Fourier Sampling Fails over $G^n$, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strong Fourier Sampling Fails over $G^n$ will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-336778