Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic Resources
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915932597649408 |
|---|---|
| author | Chowdhury, Snehasish Roy Naik, Sahil Gopalkrishna Chakraborty, Ananya Patra, Ram Krishna Ghosh, Subhendu B. Ghosal, Pratik Banik, Manik Maity, Ananda G. |
| author_facet | Chowdhury, Snehasish Roy Naik, Sahil Gopalkrishna Chakraborty, Ananya Patra, Ram Krishna Ghosh, Subhendu B. Ghosal, Pratik Banik, Manik Maity, Ananda G. |
| contents | Quantum systems are known to offer advantages over their classical counterpart in communication complexity protocols, where the aim is to minimize the amount of information exchange between distant parties to compute global functions of their distributed inputs. In this work, we establish that any one-way communication protocol implemented using a prime-dimensional quantum system -- restricted to stabilizer-state encodings and Clifford-operation decodings -- can be exactly simulated by transmitting a classical system of the same dimension, given access to shared randomness between the sender and receiver. In direct analogy with the Gottesman-Knill theorem, which attributes quantum computational speedup to non-stabilizer resources, commonly known as the magic resources, our result identifies the same non-stabilizer resources as the essential ingredient for the quantum advantage in one-way communication complexity. Furthermore, we present explicit tasks where even a 'minimal magic resource' suffices to achieve a provable quantum advantage, highlighting its efficient use in communication protocols. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_19369 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic Resources Chowdhury, Snehasish Roy Naik, Sahil Gopalkrishna Chakraborty, Ananya Patra, Ram Krishna Ghosh, Subhendu B. Ghosal, Pratik Banik, Manik Maity, Ananda G. Quantum Physics Quantum systems are known to offer advantages over their classical counterpart in communication complexity protocols, where the aim is to minimize the amount of information exchange between distant parties to compute global functions of their distributed inputs. In this work, we establish that any one-way communication protocol implemented using a prime-dimensional quantum system -- restricted to stabilizer-state encodings and Clifford-operation decodings -- can be exactly simulated by transmitting a classical system of the same dimension, given access to shared randomness between the sender and receiver. In direct analogy with the Gottesman-Knill theorem, which attributes quantum computational speedup to non-stabilizer resources, commonly known as the magic resources, our result identifies the same non-stabilizer resources as the essential ingredient for the quantum advantage in one-way communication complexity. Furthermore, we present explicit tasks where even a 'minimal magic resource' suffices to achieve a provable quantum advantage, highlighting its efficient use in communication protocols. |
| title | Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic Resources |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2506.19369 |