One of the main reasons for query model's prominence in quantum complexity is the presence of concrete lower bounding techniques: polynomial method and adversary method. There have been considerable efforts to not just give lower bounds using these methods but even to compare and relate them. We explore the value of these bounds on quantum query complexity for the class of symmetric functions, arguably one of the most natural and basic set of Boolean functions. We show (using the recently introduced spectral sensitivity) that both these bounds (positive adversary and approximate degree) give the same value for every total symmetric Boolean function. We also look at the quantum query complexity of Gap Majority, a partial symmetric function. It has gained importance recently in regard to understanding the composition of randomized query complexity. We characterize the quantum query complexity of Gap Majority and show a lower bound on noisy randomized query complexity (Ben-David and Blais, FOCS 2020) in terms of quantum query complexity. In addition, we study how large certificate complexity and block sensitivity can be as compared to sensitivity (even up to constant factors) for symmetric functions. We show tight separations, i.e., give upper bound on possible separations and construct functions achieving the same.
翻译:质询模型在量子复杂性方面的突出地位,主要原因之一是存在具体的较低约束技术:多式方法和对称方法。我们付出了相当大的努力,不仅对使用这些方法的下限进行下限,甚至对之进行比较和联系。我们探索了对称函数类别量子查询复杂性的这些界限的价值,可以说是布林函数中最自然和最基本的一组。我们(使用最近引入的光谱敏感度)显示,这两个界限(正对数和近似度)都给每一种对称布林函数带来相同的价值。我们还审视了差距多数的量子查询复杂性,即部分对称功能。我们最近越来越重视随机查询复杂性的构成。我们在量子查询复杂性(Ben-David和Blax,FOCS 2020)上调随机复杂性(Ben-David和Blabs,FOCS )上下限。我们研究,在量子查询复杂性方面,与敏感度(持续因素)相比,证书复杂性和块灵敏度有多大,对于对称性功能的敏感度(我们展示了高度分立功能。我们展示了可能达到的高度分立的分函数。