Physics – Quantum Physics
Scientific paper
2006-04-24
Quantum Information and Computation, 8, 0345-0358 (2008)
Physics
Quantum Physics
11 pages. Adding an application to quantum encryption schemes and correcting editorial errors
Scientific paper
One of the central issues in the hidden subgroup problem is to bound the sample complexity, i.e., the number of identical samples of coset states sufficient and necessary to solve the problem. In this paper, we present general bounds for the sample complexity of the identification and decision versions of the hidden subgroup problem. As a consequence of the bounds, we show that the sample complexity for both of the decision and identification versions is $\Theta(\log|\HH|/\log p)$ for a candidate set $\HH$ of hidden subgroups in the case that the candidate subgroups have the same prime order $p$, which implies that the decision version is at least as hard as the identification version in this case. In particular, it does so for the important instances such as the dihedral and the symmetric hidden subgroup problems. Moreover, the upper bound of the identification is attained by the pretty good measurement. This shows that the pretty good measurement can identify any hidden subgroup of an arbitrary group with at most $O(\log|\HH|)$ samples.
Hayashi Masahito
Kawachi Akinori
Kobayashi Hirotada
No associations
LandOfFree
Quantum Measurements for Hidden Subgroup Problems with Optimal Sample Complexity 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 Quantum Measurements for Hidden Subgroup Problems with Optimal Sample Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Measurements for Hidden Subgroup Problems with Optimal Sample Complexity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-583428