Physics – Quantum Physics
Scientific paper
2005-04-11
Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005), pp. 469-478
Physics
Quantum Physics
18 pages; v2: updated references on optimal measurement
Scientific paper
10.1109/SFCS.2005.38
We approach the hidden subgroup problem by performing the so-called pretty good measurement on hidden subgroup states. For various groups that can be expressed as the semidirect product of an abelian group and a cyclic group, we show that the pretty good measurement is optimal and that its probability of success and unitary implementation are closely related to an average-case algebraic problem. By solving this problem, we find efficient quantum algorithms for a number of nonabelian hidden subgroup problems, including some for which no efficient algorithm was previously known: certain metacyclic groups as well as all groups of the form (Z_p)^r X| Z_p for fixed r (including the Heisenberg group, r=2). In particular, our results show that entangled measurements across multiple copies of hidden subgroup states can be useful for efficiently solving the nonabelian HSP.
Bacon Dave
Childs Andrew M.
Dam Wim van
No associations
LandOfFree
From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups 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 From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-21400