Lower bounds on quantum query complexity for symmetric functions

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 that the recently introduced measure of spectral sensitivity give the same value as both these bounds (positive adversary and approximate degree) 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.

查询模型在量子复杂性中占据重要地位的主要原因之一是存在具体的下界技术：多项式方法和对手方法。人们不仅付出了大量努力使用这些方法给出下界，甚至还对它们进行比较和关联。我们探讨了这些界在对称函数类（可以说是最自然和基本的布尔函数集之一）的量子查询复杂性方面的价值。我们表明，对于每一个全对称布尔函数，最近引入的频谱敏感度度量给出的值与这两个界（正对手界和近似度）相同。我们还研究了间隙多数（一种部分对称函数）的量子查询复杂性。它最近在理解随机查询复杂性的组合方面变得很重要。我们刻画了间隙多数的量子查询复杂性，并根据量子查询复杂性给出了有噪随机查询复杂性的一个下界（本 - 大卫和布莱斯，FOCS 2020）。此外，我们研究了对于对称函数，与敏感度相比（甚至到常数因子），证书复杂性和块敏感度可以有多大。我们展示了紧密的分离，即给出可能分离的上界并构造实现相同分离的函数。