Computing the Communication Complexity of Quantum Channels

A two-party quantum communication process with classical inputs and outcomes can be simulated by replacing the quantum channel with a classical one. The minimal amount of classical communication required to reproduce the statistics of the quantum process is called its communication complexity. In the case of many instances simulated in parallel, the minimal communication cost per instance is called the asymptotic communication complexity. Previously, we reduced the computation of the asymptotic communication complexity to a convex minimization problem. In most cases, the objective function does not have an explicit analytic form, as the function is defined as the maximum over an infinite set of convex functions. Therefore, the overall problem takes the form of a minimax problem and cannot directly be solved by standard optimization methods. In this paper, we introduce a simple algorithm to compute the asymptotic communication complexity. For some special cases with an analytic objective function one can employ available convex-optimization libraries. In the tested cases our method turned out to be notably faster. Finally, using our method we obtain $1.238$ bits as a lower bound on the asymptotic communication complexity of a noiseless quantum channel with the capacity of 1 qubit. This improves the previous bound of $1.208$ bits.A two-party quantum communication process with classical inputs and outcomes can be simulated by replacing the quantum channel with a classical one. The minimal amount of classical communication required to reproduce the statistics of the quantum process is called its communication complexity. In the case of many instances simulated in parallel, the minimal communication cost per instance is called the asymptotic communication complexity. Previously, we reduced the computation of the asymptotic communication complexity to a convex minimization problem. In most cases, the objective function does not have an explicit analytic form, as the function is defined as the maximum over an infinite set of convex functions. Therefore, the overall problem takes the form of a minimax problem and cannot directly be solved by standard optimization methods. In this paper, we introduce a simple algorithm to compute the asymptotic communication complexity. For some special cases with an analytic objective function one can employ available convex-optimization libraries. In the tested cases our method turned out to be notably faster. Finally, using our method we obtain $1.238$ bits as a lower bound on the asymptotic communication complexity of a noiseless quantum channel with the capacity of 1 qubit. This improves the previous bound of $1.208$ bits.

arXiv:1512.03257Physical Review AApr 11, 20163 citations

Quantum Computing and Communication Complexity

Ronald de Wolf

Sep 1, 200165 citations

Quantum Communication Complexity

Gilles Brassard A

Foundations of PhysicsOct 24, 2003141 citations

Quantum Encodings, Private Messages, and Communication Complexity

Tom Gur, Miryam Mi-Ying Huang, Er-Cheng Tang

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

Necessary and sufficient optimality conditions for classical simulations of quantum communication processes

A. Montina, Stefan Wolf

We consider the process consisting of preparation, transmission through a quantum channel, and subsequent measurement of quantum states. The communication complexity of the channel is the minimal amount of classical communication required for classically simulating it. Recently, we reduced the computation of this quantity to a convex minimization problem with linear constraints. Every solution of the constraints provides an upper bound on the communication complexity. In this paper, we derive the dual maximization problem of the original one. The feasible points of the dual constraints, which are inequalities, give lower bounds on the communication complexity, as illustrated with an example. The optimal values of the two problems turn out to be equal (zero duality gap). By this property, we provide necessary and sufficient conditions for optimality in terms of a set of equalities and inequalities. We use these conditions and two reasonable but unproven hypotheses to derive the lower bound $n\ifmmode\times\else\texttimes\fi{}{2}^{n\ensuremath{-}1}$ for a noiseless quantum channel with capacity equal to $n$ qubits. This lower bound can have interesting consequences in the context of the recent debate on the reality of the quantum state.We consider the process consisting of preparation, transmission through a quantum channel, and subsequent measurement of quantum states. The communication complexity of the channel is the minimal amount of classical communication required for classically simulating it. Recently, we reduced the computation of this quantity to a convex minimization problem with linear constraints. Every solution of the constraints provides an upper bound on the communication complexity. In this paper, we derive the dual maximization problem of the original one. The feasible points of the dual constraints, which are inequalities, give lower bounds on the communication complexity, as illustrated with an example. The optimal values of the two problems turn out to be equal (zero duality gap). By this property, we provide necessary and sufficient conditions for optimality in terms of a set of equalities and inequalities. We use these conditions and two reasonable but unproven hypotheses to derive the lower bound $n\ifmmode\times\else\texttimes\fi{}{2}^{n\ensuremath{-}1}$ for a noiseless quantum channel with capacity equal to $n$ qubits. This lower bound can have interesting consequences in the context of the recent debate on the reality of the quantum state.

arXiv:1402.6299Physical Review AJul 8, 201410 citations

The complexity of quantum computation

孝志三原

Jan 1, 19970 citations

1.238

bits as a lower bound on the asymptotic communication complexity of a noiseless quantum channel with the capacity of 1 qubit. This improves the previous bound of

1.208

bits.

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.

n

qubits. This lower bound can have interesting consequences in the context of the recent debate on the reality of the quantum state.