arXiv:2609.17690
Quantum Encodings, Private Messages, and Communication Complexity
Tom Gur, Miryam Mi-Ying Huang, Er-Cheng Tang
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.
AI Summary
The paper studies how pre-shared entanglement affects the quantum resources needed for quantum decomposable randomized encodings (QDRE) and quantum private simultaneous message (QPSM) protocols. It establishes a bidirectional connection between these models, allowing communication bounds to translate into bounds on quantum encoding size. The communication model treats classical communication as free and counts quantum communication separately. For every channel from $n$ input qubits to $m$ output qubits, it gives a QPSM protocol using $m$ qubits of quantum communication and exponential pre-shared entanglement. Thus channels with constant-size quantum outputs need only $O(1)$ quantum communication, while classical-output channels need none. With only $O(n)$ pre-shared entanglement, every one-qubit-output channel admits an $O(n)$-quantum-communication protocol. A converse establishes a channel and a constant $c>0$ for which protocols with at most $cn$ pre-shared entanglement require $\Omega(n)$ quantum communication. For the structured class of Clifford-induced channels, $O(n)$ pre-shared entangled qubits suffice for $O(1)$ quantum communication. Analogous encoding-size bounds follow through the QDRE–QPSM connection. These results concern a resource model in which classical communication is uncharged; the general output-size upper bound also uses exponential entanglement. The supplied text contains the abstract but no technical sections, so proof techniques, precise error and privacy guarantees, and any further stated limitations cannot be assessed from it.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.