标题： 最优测量在二面体隐藏子群问题中的应用 显示英文标题

标题： Optimal measurements for the dihedral hidden subgroup problem

摘要： 我们考虑二面体群隐藏子群问题，即区分隐藏子群状态的问题。我们证明了求解这个问题的最优测量方法是所谓的“相当好的测量”。然后我们证明了这种测量的成功概率作为密度 $\nu$ = k / log N 的函数表现出明显的阈值，其中 k 是隐藏子群状态的副本数量，2N 是二面体群的阶数。 特别是，当 $\nu$ < 1 时，最优测量（因此任何测量）识别隐藏子群的成功概率以 log N 的指数形式衰减，而当 $\nu$ > 1 时，最优测量识别隐藏子群的成功概率为常数阶。因此，二面体群提供了这样一个群 G 的例子：需要 Ω(log|G|) 个隐藏子群状态来解决隐藏子群问题。 我们还考虑了确定答案单个比特的最优测量，并表明它也表现出相同的阈值。 最后，我们考虑通过量子电路实现最优测量，从而进一步建立二面体群隐藏子群问题与平均情况子集和问题之间的联系。特别是，我们证明了对于最优测量的受限版本的有效量子算法将意味着子集和问题的有效量子算法，并且相反，能够从子集和解中进行量子采样允许实现最优测量。 显示英文摘要

摘要： We consider the dihedral hidden subgroup problem as the problem of distinguishing hidden subgroup states. We show that the optimal measurement for solving this problem is the so-called pretty good measurement. We then prove that the success probability of this measurement exhibits a sharp threshold as a function of the density nu=k/log N, where k is the number of copies of the hidden subgroup state and 2N is the order of the dihedral group. In particular, for nu<1 the optimal measurement (and hence any measurement) identifies the hidden subgroup with a probability that is exponentially small in log N, while for nu>1 the optimal measurement identifies the hidden subgroup with a probability of order unity. Thus the dihedral group provides an example of a group G for which Omega(log|G|) hidden subgroup states are necessary to solve the hidden subgroup problem. We also consider the optimal measurement for determining a single bit of the answer, and show that it exhibits the same threshold. Finally, we consider implementing the optimal measurement by a quantum circuit, and thereby establish further connections between the dihedral hidden subgroup problem and average case subset sum problems. In particular, we show that an efficient quantum algorithm for a restricted version of the optimal measurement would imply an efficient quantum algorithm for the subset sum problem, and conversely, that the ability to quantum sample from subset sum solutions allows one to implement the optimal measurement.