论文标题
在查询到通信的对手界限
On Query-to-Communication Lifting for Adversary Bounds
论文作者
论文摘要
我们研究了与量子对手界相关的模型的查询到沟通定理。我们的结果如下： 1。我们表明，经典的对手绑定的升力升至具有恒定小工具的随机通信复杂性上的下限。我们还表明，经典的对手结合是一种比以前被称为临界块灵敏度的措施的严格强度下限技术，这使我们的提升定理是使用恒定小工具的最强升降定理之一。 2。转向量子模型，我们显示了在某些“诚实但充满激情”的模型中提升定理的量子定理与安全的2方量子计算之间的联系。假设这种安全的2方计算是不可能的，我们表明，使用恒定小工具的量子交流的简化版本是对量子通信下限的简化版本。我们还提供了一个无条件的提升定理，该定理降低了有限的量子量子通信协议。 3。最后，我们在查询复杂性方面给出了一些新的结果。我们表明，经典的对手和积极的量子对手在四边形相关。我们还表明，正重量量子对手永远不会大于近似程度的平方。这两种关系甚至都用于部分功能。
We investigate query-to-communication lifting theorems for models related to the quantum adversary bounds. Our results are as follows: 1. We show that the classical adversary bound lifts to a lower bound on randomized communication complexity with a constant-sized gadget. We also show that the classical adversary bound is a strictly stronger lower bound technique than the previously-lifted measure known as critical block sensitivity, making our lifting theorem one of the strongest lifting theorems for randomized communication complexity using a constant-sized gadget. 2. Turning to quantum models, we show a connection between lifting theorems for quantum adversary bounds and secure 2-party quantum computation in a certain "honest-but-curious" model. Under the assumption that such secure 2-party computation is impossible, we show that a simplified version of the positive-weight adversary bound lifts to a quantum communication lower bound using a constant-sized gadget. We also give an unconditional lifting theorem which lower bounds bounded-round quantum communication protocols. 3. Finally, we give some new results in query complexity. We show that the classical adversary and the positive-weight quantum adversary are quadratically related. We also show that the positive-weight quantum adversary is never larger than the square of the approximate degree. Both relations hold even for partial functions.
