摘要:我们提供了两个舒适的必要条件,以表征具有精确量子查询复杂性的任何n位部分布尔函数1。使用第一个特征,我们提出所有依赖于n位的n位部分布尔函数,并且可以通过1 Query量子算法准确计算。由于第二个表征,我们构造了一个函数f,该函数f将任何n位部分布尔函数映射到某个整数,并且如果n位部分布尔函数f取决于k位,并且可以通过1 Query量子量算法准确地计算出来,则F(F)是非阳性的。此外,我们还表明,所有n-位部分均值函数的数量取决于k位,并且可以通过1 Query量子算法准确地计算出比上限取决于N和K的上限。最重要的是,上限远远低于所有有效的大n的所有n位部分布尔函数的数量。
主要关键词