量子科技中心_量科网

量子通信复杂度领域的一个重大开放问题是：量子协议在计算全布尔函数时，是否可能比经典协议指数级更高效；目前的主流猜想认为不可能。在一项开创性工作中，Razborov (2002) 针对形如 $$ F(x,y) = f(x_1 \land y_1, \ldots, x_n \land y_n) $$ 的AND函数（其中外层函数 $f$ 为对称函数）解决了该问题，证明了这些函数的有界误差量子通信复杂度与经典通信复杂度之间存在多项式关系。此后，将该结果推广至所有AND函数的问题一直悬而未决，并被多位研究者提出。在本工作中，该团队以强形式解决了该问题。研究证明，对于任意布尔函数 $f$，函数 $f \circ \mathrm{AND}_2$ 的有界误差量子通信复杂度与经典确定性通信复杂度之间存在多项式关系（在 $n$ 的多对数因子范围内）。该团队通过证明两者的复杂度均由 $f$ 的德摩根稀疏度的对数（在多项式损失范围内）刻画，从而得到上述结论。该研究建立在Chattopadhyay、Dahiya 和 Lovett (2025) 关于非稀疏布尔函数结构刻画的最新工作之上，并将该工作推广至一般AND函数，从而解决了相关猜想。