{"id":"arxiv/2609.17690","url":"https://arxiv.org/abs/2609.17690","tags":["quant-ph"],"score":0,"title":"Quantum Encodings, Private Messages, and Communication Complexity","domain":"quant-ph","source":"arxiv","authors":["Tom Gur","Miryam Mi-Ying Huang","Er-Cheng Tang"],"reviews":0,"subject":"quant-ph","summary":"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)$…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-15","reactions":{}}