Quantum Encodings, Private Messages, and Communication Complexity
Abstract
We study the complexity of quantum decomposable randomized encodings (QDRE). We establish a bi-directional connection between the QDRE model and the communication complexity model of quantum private simultaneous message protocols (QPSM), where classical communication is free, and quantum communication is the primary complexity measure. We show the following upper and lower bounds. (1) For every quantum channel mapping n to m qubits, we give a QPSM protocol with quantum communication m, using exponential pre-shared entanglement. In particular, constant-output channels have O(1) quantum communication, and classical-output channels require no quantum communication. (2) With O(n) pre-shared entanglement, every one-qubit-output channel has an O(n)-quantum-communication QPSM protocol. Conversely, there exists a channel and a constant c>0 for which any protocol with at most cn pre-shared entanglement requires Ω(n) quantum communication. (3) In contrast, we identify a structured class of quantum channels, Clifford-induced channels, for which there exist QPSM protocols with O(n) pre-shared entangled qubits and only O(1) quantum communication complexity. Through our connection, we obtain analogous upper and lower bounds on the quantum encoding size of QDRE. Our results show that the amount of pre-shared entanglement plays a central role in quantum encoding size and quantum communication complexity.
Related
- Concrete Functions in Private Simultaneous Quantum Messages: Quantum Advantages and Structural Limitations
- Private communication via zero-private-capacity quantum channels
- The exact strong converse exponent for private communication over quantum channels
- An exponential strong converse for private communication over degradable quantum channels
- On the quantum communication complexity of total functions
BibTeX
@misc{gur2026quantum,
title = {{Quantum Encodings, Private Messages, and Communication Complexity}},
author = {Tom Gur and Miryam Mi-Ying Huang and Er-Cheng Tang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17690},
eprint = {2609.17690},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17690},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Quantum Encodings, Private Messages, and Communication Complexity
AU - Tom Gur
AU - Miryam Mi-Ying Huang
AU - Er-Cheng Tang
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17690
UR - https://arxiv.org/abs/2609.17690
AB - We study the complexity of quantum decomposable randomized encodings (QDRE). We establish a bi-directional connection between the QDRE model and the communication complexity model of quantum private simultaneous message protocols (QPSM), where classical communication is free, and quantum communication is the primary complexity measure. We show the following upper and lower bounds. (1) For every quantum channel mapping n to m qubits, we give a QPSM protocol with quantum communication m, using exponential pre-shared entanglement. In particular, constant-output channels have O(1) quantum communication, and classical-output channels require no quantum communication. (2) With O(n) pre-shared entanglement, every one-qubit-output channel has an O(n)-quantum-communication QPSM protocol. Conversely, there exists a channel and a constant c>0 for which any protocol with at most cn pre-shared entanglement requires Ω(n) quantum communication. (3) In contrast, we identify a structured class of quantum channels, Clifford-induced channels, for which there exist QPSM protocols with O(n) pre-shared entangled qubits and only O(1) quantum communication complexity. Through our connection, we obtain analogous upper and lower bounds on the quantum encoding size of QDRE. Our results show that the amount of pre-shared entanglement plays a central role in quantum encoding size and quantum communication complexity.
ER -