Quantum Query Complexity of Almost All Functions with Fixed On-Set
Quantum Query Complexity of Almost All Functions with Fixed On-Set
复制标题
几乎所有固定 on-set 函数的量子查询复杂度
DOI：
10.1007/s00037-016-0139-6
复制
发表时间：
2016
影响因子：
1.4
通讯作者：
S. Yamashita
中科院分区：
文献类型：
--
作者：
A. Ambainis;K. Iwama;M. Nakanishi;H. Nishimura;R. Raymond;S. Tani;S. Yamashita
本文研究了具有on-set大小的setof-variable布尔函数中几乎所有函数的量子查询复杂度，其中on-set大小是函数为真的输入个数.主要结果是，对于除多项式小分数外的所有函数，量子查询复杂度为常数。这与以下函数中最难的函数的量子查询复杂度完全不同：相比之下，几乎所有的函数都具有与最难的函数相同的随机查询复杂性，直到一个常数因子。
This paper considers the quantum query complexity of almost all functions in the setof-variable Boolean functions with on-set size, where the on-set size is the number of inputs on which the function is true. The main result is that, for all functions inexcept its polynomially small fraction, the quantum query complexity isfor a constant. This is quite different from the quantum query complexity of the hardest function in:. In contrast, almost all functions inhave the same randomized query complexityas the hardest one, up to a constant factor.