标题： 量子查询复杂度的读多次公式 显示英文标题

标题： The quantum query complexity of read-many formulas

摘要： 量子查询复杂度评估任何具有n个黑盒输入位的只读公式是Theta(sqrt(n))。 然而，对于多读公式（即输入具有扇出的公式）的相应问题尚未被充分理解。 尽管最优的只读公式评估算法可以应用于任何公式，但如果输入具有较大的扇出，该算法可能不是最优的。 我们给出一个用于评估具有n个输入、大小为S且有G个门的任何公式的算法，使用O(min{n, sqrt{S}, n^{1/2} G^{1/4}})次量子查询。 此外，我们证明该算法是最佳的，因为对于任何n,S,G，都存在一个具有n个输入、大小不超过S且门数不超过G的公式，其需要 Omega(min{n, sqrt{S}, n^{1/2} G^{1/4}})次查询。 我们还表明，该算法在任意特定深度k >= 3的电路中仍然几乎是最佳的，并且我们给出了一个大小为线性的深度2电路，其需要Omega (n^{5/9})次查询。 这些结果的应用包括布尔矩阵乘积验证的Omega (n^{19/18})下界，具有有限扇出的常数深度电路的量子查询复杂度的几乎精确表征，几个函数（包括PARITY）的新公式门数下界，以及一个线性大小的AC^0电路的构造，该电路只能通过具有Omega(n^{2-epsilon})个门的公式来评估。 显示英文摘要

摘要： The quantum query complexity of evaluating any read-once formula with n black-box input bits is Theta(sqrt(n)). However, the corresponding problem for read-many formulas (i.e., formulas in which the inputs have fanout) is not well understood. Although the optimal read-once formula evaluation algorithm can be applied to any formula, it can be suboptimal if the inputs have large fanout. We give an algorithm for evaluating any formula with n inputs, size S, and G gates using O(min{n, sqrt{S}, n^{1/2} G^{1/4}}) quantum queries. Furthermore, we show that this algorithm is optimal, since for any n,S,G there exists a formula with n inputs, size at most S, and at most G gates that requires Omega(min{n, sqrt{S}, n^{1/2} G^{1/4}}) queries. We also show that the algorithm remains nearly optimal for circuits of any particular depth k >= 3, and we give a linear-size circuit of depth 2 that requires Omega (n^{5/9}) queries. Applications of these results include a Omega (n^{19/18}) lower bound for Boolean matrix product verification, a nearly tight characterization of the quantum query complexity of evaluating constant-depth circuits with bounded fanout, new formula gate count lower bounds for several functions including PARITY, and a construction of an AC^0 circuit of linear size that can only be evaluated by a formula with Omega(n^{2-epsilon}) gates.