Single query learning from abelian and non-abelian Hamming distance oracles
Single query learning from abelian and non-abelian Hamming distance oracles
复制标题
从阿贝尔和非阿贝尔汉明距离预言机进行单查询学习
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
James Pommersheim
中科院分区：
文献类型：
--
作者：
D. Meyer;James Pommersheim
我们研究的问题，确定一个n位字符串使用一个单一的量子查询的预言计算查询和隐藏字符串之间的汉明距离。oracle在维度r的响应寄存器上的标准动作是通过循环的幂（1. r），所有这些，当然，通勤。我们引入了一个新的模型的行动的预言-一般置换在S_r-并探讨如何成功的概率取决于r和映射从汉明距离置换。特别地，我们证明了当r = 2时，对于偶数n，成功概率是1，并且正确地选择地图，而对于奇数n，成功概率不能是1，对于任何选择。此外，对于小奇数n和r = 3，我们证明了数字的最佳映射的图像产生一个非阿贝尔组的排列。
We study the problem of identifying an n-bit string using a single quantum query to an oracle that computes the Hamming distance between the query and hidden strings. The standard action of the oracle on a response register of dimension r is by powers of the cycle (1...r), all of which, of course, commute. We introduce a new model for the action of an oracle--by general permutations in S_r--and explore how the success probability depends on r and on the map from Hamming distances to permutations. In particular, we prove that when r = 2, for even n the success probability is 1 with the right choice of the map, while for odd n the success probability cannot be 1 for any choice. Furthermore, for small odd n and r = 3, we demonstrate numerically that the image of the optimal map generates a non-abelian group of permutations.