论文标题
在某些类别的布尔函数中，经典的量子分离 - 使用平等决策树进行分析
Classical-Quantum Separations in Certain Classes of Boolean Functions-- Analysis using the Parity Decision Trees
论文作者
论文摘要
在本文中，我们研究了使用奇偶校验决策树方法的几个布尔函数类别的确定性（经典）查询复杂性（$ d $）与确切的量子查询复杂性（$ q_e $）之间的分离。我们首先将$ n $变量上的查询友好（QF）函数定义为具有最低确定性查询复杂性$（d（f））$的函数。我们观察到，对于每个$ n $，都存在不可分类的QF函数类，以便$ d（f）= q_e（f）$。此外，我们表明，对于$ n $的某些值，所有QF函数都是不可分割的。然后，我们为$ n $的某些其他值提出QF函数，特别是可以证明分离的功能，尤其是$ q_e（f）= d（f）-1 $。在相关的工作中，我们还研究了Maiorana McFarland（M-M）型弯曲功能。我们表明，虽然对于任何M-M Bent函数$ f $ $ n $变量$ d（f）= n $，但可以将分隔作为$ \ frac {n} {2} {2} \ leq q_e（f）\ leq \ leq \ lceil \ lceil \ frac \ frac {3n} {3n} {4} {4} \ rceil $。我们的结果强调了如何分析不同类别的布尔函数，以利用平等决策树方法利用经典的量子分离。
In this paper we study the separation between the deterministic (classical) query complexity ($D$) and the exact quantum query complexity ($Q_E$) of several Boolean function classes using the parity decision tree method. We first define the Query Friendly (QF) functions on $n$ variables as the ones with minimum deterministic query complexity $(D(f))$. We observe that for each $n$, there exists a non-separable class of QF functions such that $D(f)=Q_E(f)$. Further, we show that for some values of $n$, all the QF functions are non-separable. Then we present QF functions for certain other values of $n$ where separation can be demonstrated, in particular, $Q_E(f)=D(f)-1$. In a related effort, we also study the Maiorana McFarland (M-M) type Bent functions. We show that while for any M-M Bent function $f$ on $n$ variables $D(f) = n$, separation can be achieved as $\frac{n}{2} \leq Q_E(f) \leq \lceil \frac{3n}{4} \rceil$. Our results highlight how different classes of Boolean functions can be analyzed for classical-quantum separation exploiting the parity decision tree method.
