...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Quantum information processing >A quantum algorithm for approximating the influences of Boolean functions and its applications
【24h】

A quantum algorithm for approximating the influences of Boolean functions and its applications

机译：一种近似布尔函数影响的量子算法及其应用

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We investigate the influences of variables on a Boolean function f based on the quantum Bernstein-Vazirani algorithm. A previous paper (Floess et al. in Math Struct Comput Sci 23:386, 2013) has proved that if an n-variable Boolean function f (x(1) ,..., x(n)) does not depend on an input variable x(i), using the Bernstein-Vazirani circuit for f will always output y that has a 0 in the ith position. We generalize this result and show that, after running this algorithm once, the probability of getting a 1 in each position i is equal to the dependence degree of f on the variable x(i), i.e., the influence of x(i) on f. Based on this, we give an approximation algorithm to evaluate the influence of any variable on a Boolean function. Next, as an application, we use it to study the Boolean functions with juntas and construct probabilistic quantum algorithms to learn certain Boolean functions. Compared with the deterministic algorithms given by Floess et al., our probabilistic algorithms are faster.
机译：我们研究基于量子伯恩斯坦-瓦兹拉尼算法的变量对布尔函数f的影响。先前的论文（Floess等人，Math Struct Comput Sci 23：386，2013）已证明，如果n变量布尔函数f（x（1），...，x（n））不依赖于输入变量x（i），使用Bernstein-Vazirani电路为f，将始终输出在第i个位置具有0的y。我们对该结果进行概括，并表明，在运行该算法一次之后，在每个位置i上获得1的概率等于f对变量x（i）的依赖程度，即x（i）对变量x的影响。 F。基于此，我们给出一种近似算法来评估任何变量对布尔函数的影响。接下来，作为一个应用程序，我们使用它来研究带有juntas的布尔函数，并构造概率量子算法来学习某些布尔函数。与Floess等人给出的确定性算法相比，我们的概率算法更快。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号