量子科技中心_量科网

“额头数字”（NOF）通信模型是通信复杂性领域的核心模型。作为其受限变体，单向NOF模型尤其引人关注。建立强力的单向NOF下界将意味着电路复杂性下界突破，解决加性组合数学中的著名难题，并在密码学与分布式计算等领域产生广泛应用。然而，单向NOF模型中的强下界证明仍极具挑战性，该领域许多基础问题悬而未决。其中由Gavinsky与Pudlák（CCC 2008）提出的关键问题，是要在量子与经典单向NOF通信间建立明确的指数级分离。 本文通过构建单向NOF模型中量子与随机化通信复杂性的首个指数级分离，解决了这一开放性问题。具体而言，该研究团队定义了Bar-Yossef、Jayram和Kerenidis（STOC 2004）提出的"隐式匹配问题"的升维变体，并证明其在单向NOF设置下存在(O(logn))成本的量子协议。与之形成鲜明对比的是，研究人员证明了针对该问题的任何k方单向随机化协议都需要Ω(n^{1/3}/2^{k/3})的通信量。值得注意的是，该分离结果甚至适用于k玩家单向通信的广义形式——即首名玩家仅发言一次，其余k−1名玩家可自由通信的场景。