• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Conference on Computational Complexity >Quantum Algorithms for Learning Symmetric Juntas via Adversary Bound
【24h】

Quantum Algorithms for Learning Symmetric Juntas via Adversary Bound

机译：通过对抗约束学习对称Juntas的量子算法

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function f on n variables that only depends on k variables, and, when restricted to them, equals some predefined function h. The task is to identify the variables the function depends on. This is a generalisation of the Bernstein-Vazirani problem (when h is the XOR function) and the combinatorial group testing problem (when h is the OR function). We analyse the general case using the adversary bound, and give an alternative formulation for the quantum query complexity of this problem. We construct optimal quantum query algorithms for the cases when h is the OR function (complexity is square root of k) or the exact-half function (complexity is the fourth power root of k). The first algorithm resolves an open problem from. For the case when h is the majority function, we prove an upper bound of the fourth power root of k. We obtain a quartic improvement when compared to the randomised complexity (if h is the exact-half or the majority function), and a quadratic one when compared to the non-adaptive quantum complexity (for all functions considered in the paper).
机译：在本文中，我们研究了军政府学习问题的以下变体。我们为oracle提供了对仅依赖于k个变量的n个变量的布尔函数f的访问权限，并且在限于它们时，等于某些预定义函数h。任务是确定功能依赖的变量。这是Bernstein-Vazirani问题（当h是XOR函数时）和组合组测试问题（当h是OR函数时）的推广。我们使用对手边界来分析一般情况，并为该问题的量子查询复杂度提供了另一种表述。对于h是OR函数（复杂度是k的平方根）或精确半函数（复杂度是k的四次幂根）的情况，我们构造了最优的量子查询算法。第一种算法从中解决了一个开放性问题。对于h是多数函数的情况，我们证明了k的四次幂根的上限。与随机复杂度相比（如果h是精确一半或多数函数），我们获得了四次改进;与非自适应量子复杂度相比（对于本文中考虑的所有函数），我们获得了二次改进。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号