首页    期刊浏览 2024年12月06日 星期五
登录注册

文章基本信息

  • 标题:Single-Query Learning from Abelian and Non-Abelian Hamming Distance Oracles
  • 本地全文:下载
  • 作者:David A. Meyer ; James Pommersheim
  • 期刊名称:Chicago Journal of Theoretical Computer Science
  • 印刷版ISSN:1073-0486
  • 出版年度:2010
  • 卷号:2010
  • 出版社:MIT Press ; University of Chicago, Department of Computer Science
  • 摘要:

    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.

国家哲学社会科学文献中心版权所有