Quantum measurements for hidden subgroup problems with optimal sample complexity
Quantum measurements for hidden subgroup problems with optimal sample complexity
复制标题
DOI：
10.26421/qic8.3-4-8
复制
发表时间：
2006-04
期刊：
影响因子：
--
通讯作者：
Masahito Hayashi;Akinori Kawachi;Hirotada Kobayashi
中科院分区：
文献类型：
--
作者：
Masahito Hayashi;Akinori Kawachi;Hirotada Kobayashi
隐子群问题的核心问题之一是约束样本复杂度，即，陪集状态的相同样本的数量对于解决该问题是足够和必要的。在本文中，我们提出了一般的范围内的识别和决策版本的隐藏子群问题的样本复杂性。作为结果的界限，我们表明，样本复杂性的决定和识别版本是Θ（log| H|/ log p），这意味着在这种情况下决策版本至少与标识版本一样难。特别是，它这样做的重要情况下，如二面角和对称隐藏子群问题。此外，识别的上界是通过相当好的测量的一个变体来获得的。这意味着相当好的测量的概念是非常有用的识别隐藏的子群在一个任意的组与最佳的样本复杂度。
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 Θ(log |H|/ log p) for a candidate set H of hidden subgroups in the case where the candidate nontrivial 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 cases such as the dihedral and the symmetric hidden subgroup problems. Moreover, the upper bound of the identification is attained by a variant of the pretty good measurement. This implies that the concept of the pretty good measurement is quite useful for identification of hidden subgroups over an arbitrary group with optimal sample complexity.