论文标题
局部布尔功能具有精确的量子1质量复杂性
Partial Boolean functions with exact quantum 1-query complexity
论文作者
论文摘要
我们提供两个足够和必要的条件，以表征任何$ n $ bit的部分布尔函数，具有精确的量子1晶体复杂性。使用第一个表征，我们介绍了所有取决于$ n $位且具有精确量子1的复杂性的$ n $ bit部分布尔函数。由于第二个特征，我们构建了一个函数$ f $，该函数$ f $将任何$ n $ bit的部分布尔函数映射到某个整数，如果$ n $ bit的部分布尔函数$ f $取决于$ k $ lits，并且具有精确的量子1-query复杂性，则$ f（f）$是非阳性的。此外，我们表明，所有$ n $ but的部分布尔函数的数量依赖于$ k $位，并且具有精确的量子1 Query Complacy度不超过$ n^{2} {2} 2^{2^{n-1}（n-1}（1+2^{2-k} {2-k}）
We provide two sufficient and necessary conditions to characterize any $n$-bit partial Boolean function with exact quantum 1-query complexity. Using the first characterization, we present all $n$-bit partial Boolean functions that depend on $n$ bits and have exact quantum 1-query complexity. Due to the second characterization, we construct a function $F$ that maps any $n$-bit partial Boolean function to some integer, and if an $n$-bit partial Boolean function $f$ depends on $k$ bits and has exact quantum 1-query complexity, then $F(f)$ is non-positive. In addition, we show that the number of all $n$-bit partial Boolean functions that depend on $k$ bits and have exact quantum 1-query complexity is not bigger than $n^{2}2^{2^{n-1}(1+2^{2-k})+2n^{2}}$ for all $n\geq 3$ and $k\geq 2$.
