机构名称：
¥ 2.0
摘要：我们对 Arunachalam、Briët 和 Palazuelos (SICOMP'19) 的主要结果进行了新的介绍，并表明量子查询算法由一类新的多项式来表征，我们称之为傅里叶完全有界多项式。我们推测所有这样的多项式都有一个影响变量。这个猜想比著名的 Aaronson-Ambainis (AA) 猜想（计算理论'14）要弱，但对量子查询算法的经典模拟具有相同的含义。我们通过证明它适用于齐次傅里叶完全有界多项式来证明 AA 猜想的一个新案例。这意味着如果 d 查询量子算法的输出是 2 次 d 的齐次多项式 p，那么它有一个影响变量至少为 Var [ p ] 2。此外，我们给出了 Bansal、Sinha 和 de Wolf (CCC'22 和 QIP'23) 的结果的另一种证明，表明块多线性完全有界多项式具有影响变量。我们的证明更简单，获得更好的常数，并且不使用随机性。
傅立叶完全有界多项式的影响...
主要关键词
相关文件推荐
