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.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.

quant-pharXiv:2609.17690Sep 17, 20260 citations

Basic protocols in quantum communication

Daowen Qiu

Elsevier eBooksAug 29, 20250 citations

Calculation of Bit Error Rates for Superdense and ALOHA based Quantum Communication

Md. Esa Ibn Eunus, Md Ariful Haque, Md. Saifur Rahman

Quantum communication allows us to share information by using the quantum states of qubits. Superdense coding is a very popular protocol or scheme for quantum communication, which uses entangled qubits. Entangled qubits can also be used to share information using an ALOHA based protocol. Performance evaluation of these protocols is essential for their implementation in quantum communication. In this paper, we calculate the bit error rates (BERs) of these two entanglement-based quantum communication schemes. It has been noticed that the BER performance is improved in an ALOHA based scheme compared to the Superdense coding scheme. However, without using any error correction schemes, the BERs are still very high in both the cases compared to the classical communication methods. The BER performance can be further improved by using the appropriate error correction schemes, which are under investigation.Quantum communication allows us to share information by using the quantum states of qubits. Superdense coding is a very popular protocol or scheme for quantum communication, which uses entangled qubits. Entangled qubits can also be used to share information using an ALOHA based protocol. Performance evaluation of these protocols is essential for their implementation in quantum communication. In this paper, we calculate the bit error rates (BERs) of these two entanglement-based quantum communication schemes. It has been noticed that the BER performance is improved in an ALOHA based scheme compared to the Superdense coding scheme. However, without using any error correction schemes, the BERs are still very high in both the cases compared to the classical communication methods. The BER performance can be further improved by using the appropriate error correction schemes, which are under investigation.

IEEE International Conference on Telecommunications and Photonics (ICTP)Dec 22, 20216 citations

Analysis of Quantum Communication Protocols

Springer eBooksSep 1, 20060 citations

Shared Randomness and Quantum Communication in the Multi-Party Model

Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang

We study shared randomness in the context of multi-party number-in-hand communication protocols in the simultaneous message passing model. We show that with three or more players, shared randomness exhibits new interesting properties that have no direct analogues in the two-party case. First, we demonstrate a hierarchy of modes of shared randomness, with the usual shared randomness where all parties access the same random string as the form in the hierarchy. We show exponential separations between its levels, and some of our bounds may be of independent interest. For example, we show that the equality function can be solved by a protocol of constant length using the weakest form of shared randomness, which we call XOR-shared Second, we show that quantum communication cannot replace shared randomness in the k-party case, where k >= 3 is any constant. We demonstrate a promise function GP_k that can be computed by a classical protocol of constant length when (the form of) shared randomness is available, but any quantum protocol without shared randomness must send n^Omega(1) qubits to compute it. Moreover, the quantum complexity of GP_k remains n^Omega(1) even if the second strongest mode of shared randomness is available. While a somewhat similar separation was already known in the two-party case, in the multi-party case our statement is qualitatively stronger: * In the two-party case, only a relational communication problem with similar properties is known. * In the two-party case, the gap between the two complexities of a problem can be at most exponential, as it is known that 2^(O(c)) log n qubits can always replace shared randomness in any c-bit protocol. Our bounds imply that with quantum communication alone, in general, it is not possible to simulate efficiently even a three-bit three-party classical protocol that uses shared randomness.We study shared randomness in the context of multi-party number-in-hand communication protocols in the simultaneous message passing model. We show that with three or more players, shared randomness exhibits new interesting properties that have no direct analogues in the two-party case. First, we demonstrate a hierarchy of modes of shared randomness, with the usual shared randomness where all parties access the same random string as the form in the hierarchy. We show exponential separations between its levels, and some of our bounds may be of independent interest. For example, we show that the equality function can be solved by a protocol of constant length using the weakest form of shared randomness, which we call XOR-shared Second, we show that quantum communication cannot replace shared randomness in the k-party case, where k >= 3 is any constant. We demonstrate a promise function GP_k that can be computed by a classical protocol of constant length when (the form of) shared randomness is available, but any quantum protocol without shared randomness must send n^Omega(1) qubits to compute it. Moreover, the quantum complexity of GP_k remains n^Omega(1) even if the second strongest mode of shared randomness is available. While a somewhat similar separation was already known in the two-party case, in the multi-party case our statement is qualitatively stronger: * In the two-party case, only a relational communication problem with similar properties is known. * In the two-party case, the gap between the two complexities of a problem can be at most exponential, as it is known that 2^(O(c)) log n qubits can always replace shared randomness in any c-bit protocol. Our bounds imply that with quantum communication alone, in general, it is not possible to simulate efficiently even a three-bit three-party classical protocol that uses shared randomness.

Oct 4, 20124 citations

Design and Analysis of Quantum Communication Protocols

Chitra Shukla

Mar 18, 20151 citation

n

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.