تقرير
On Query-to-Communication Lifting for Adversary Bounds
| العنوان: | On Query-to-Communication Lifting for Adversary Bounds |
|---|---|
| المؤلفون: | Anshu, Anurag, Ben-David, Shalev, Kundu, Srijita |
| سنة النشر: | 2020 |
| المجموعة: | Computer Science Quantum Physics |
| مصطلحات موضوعية: | Quantum Physics, Computer Science - Computational Complexity |
| الوصف: | 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. Comment: 39 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2012.03415 |
| رقم الأكسشن: | edsarx.2012.03415 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |