.png){kind=icon}
返回
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
摘要
En 中文
函数属性测试领域的研究目标在于确定给定的黑盒布尔函数是否具有特定的给定属性，或与该属性相差ɛ。本文研究了布尔函数的多种属性测试（恒等性、相关性及平衡性），采用了Deutsch-Jozsa算法（针对Deutsch-Jozsa (D-J)问题）以及振幅放大技术。首先，我们研究一个特定的测试问题：即判断给定的n变量布尔函数f是否与给定函数g恒等，或与g相差ɛ，其中ɛ为参数。我们提出一种具有查询复杂度[公式：见原文]的单边误差量子算法来处理此问题，并证明该量子算法是最优的。随后，我们证明该问题的经典随机查询复杂度为[公式：见原文]。其次，我们从功能相关性的角度考虑D-J问题，并令C( f, g)表示f与g的相关性。我们提出了一种使用6次查询区分|C( f, g)| = ɛ和|C( f, g)| = 1的精确量子算法，而该问题的经典确定性查询复杂度为Θ(2n)次查询。最后，我们提出一种用于测试布尔函数是否平衡或与平衡相差ɛ的单边误差量子查询算法，查询次数为[公式：见原文]。我们还证明用于平衡性测试的量子算法是最优的。同时，针对此平衡性测试问题，我们提出一种查询复杂度为O(1/ɛ2)的经典随机算法，该随机算法同样是最优的。此外，我们将本文讨论的问题联系起来，并将其推广到一般情况。
期刊
暂无期刊信息
机构
暂无机构信息
引用论文
暂无论文信息