Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1401.4126 · IEEE International Symposium on Information Theory (ISIT)

Lower bounds on the communication complexity of two-party (quantum) processes

A. Montina, Stefan Wolf

Published Jun 1, 2014• 4 citations
arXivHTMLPDF

Abstract

The process of state preparation, its transmission and subsequent measurement can be classically simulated through the communication of some amount of classical information. Recently, we proved that the minimal communication cost is the minimum of a convex functional over a space of suitable probability distributions. It is now proved that this optimization problem is the dual of a geometric programming problem, which displays some appealing properties. First, the number of variables grows linearly with the input size. Second, the objective function is linear in the input parameters and the variables. Finally, the constraints do not depend on the input parameters. These properties imply that, once a feasible point is found, the computation of a lower bound on the communication cost in any two-party process is linearly complex. The studied scenario goes beyond quantum processes. We illustrate the method by analytically deriving some non-trivial lower bounds. Finally, we conjecture the lower bound n2nfor a noiseless quantum channel with capacity n qubits.

DOI
10.1109/isit.2014.6875080

Related papers

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.

arXiv:1402.6299•Physical Review A•Jul 8, 2014•10 citations

Simple algorithm for computing the communication complexity of quantum communication processes

A. Hansen, A. Montina, Stefan Wolf

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.03257•Physical Review A•Apr 11, 2016•3 citations

Communication cost of classically simulating a quantum channel with subsequent rank-1 projective measurement

A. Montina

A process of preparation, transmission, and subsequent projective measurement of a qubit can be simulated by a classical model with only two bits of communication and some amount of shared randomness. However, to the best of our knowledge, no model for $n$ qubits with a finite amount of classical communication is known at present. A lower bound for the communication cost can provide useful hints for a generalization. It is known, for example, that the amount of communication must be greater than $c{2}^{n}$, where $c\ensuremath{\simeq}0.01$. The proof uses a quite elaborate theorem of communication complexity. Using a mathematical conjecture known as the ``double cap conjecture,'' we strengthen this result by presenting a geometrical and extremely simple derivation of the lower bound ${2}^{n}\ensuremath{-}1$. Only rank-1 projective measurements are involved in the derivation.

arXiv:1110.5944•Physical Review A•Dec 29, 2011•15 citations

The communication complexity of non-signaling distributions

Julien Degorre, Marc Kaplan, Sophie Laplante +1 more

We study a model of communication complexity that encompasses many well-studied problems, including classical and quantum communication complexity, the complexity of simulating distributions arising from bipartite measurements of shared quantum states, and XOR games. In this model, Alice gets an input $x$, Bob gets an input $y$, and their goal is to each produce an output $a,b$ distributed according to some pre-specified joint distribution $p(a,b|x,y)$. Our results apply to any non-signaling distribution, that is, those where Alice's marginal distribution does not depend on Bob's input, and vice versa.~~~By taking a geometric view of the non-signaling distributions, we introduce a simple new technique based on affine combinations of lower-complexity distributions, and we give the first general technique to apply to all these settings, with elementary proofs and very intuitive interpretations. Specifically, we introduce two complexity measures, one which gives lower bounds on classical communication, and one for quantum communication. These measures can be expressed as convex optimization problems. We show that the dual formulations have a striking interpretation, since they coincide with maximum violations of Bell and Tsirelson inequalities. The dual expressions are closely related to the winning probability of XOR games. Despite their apparent simplicity, these lower bounds subsume many known communication complexity lower bound methods, most notably the recent lower bounds of Linial and Shraibman for the special case of Boolean functions. We show that as in the case of Boolean functions, the gap between the quantum and classical lower bounds is at most linear in the size of the support of the distribution, and does not depend on the size of the inputs. This translates into a bound on the gap between maximal Bell and Tsirelson inequality violations, which was previously known only for the case of distributions with Boolean outcomes and uniform marginals. It also allows us to show that for some distributions, information theoretic methods are necessary to prove strong lower bounds. ~~~ Finally, we give an exponential upper bound on quantum and classical communication complexity in the simultaneous messages model, for any non-signaling distribution. One consequence of this is a simple proof that any quantum distribution can be approximated with a constant number of bits of communication.

Quantum Information and Computation•Jul 1, 2011•11 citations

Epistemic View of Quantum States and Communication Complexity of Quantum Channels

A. Montina

The communication complexity of a quantum channel is the minimal amount of classical communication required for classically simulating a process of state preparation, transmission through the channel and subsequent measurement. It establishes a limit on the power of quantum communication in terms of classical resources. We show that classical simulations employing a finite amount of communication can be derived from a special class of hidden variable theories where quantum states represent statistical knowledge about the classical state and not an element of reality. This special class has attracted strong interest very recently. The communication cost of each derived simulation is given by the mutual information between the quantum state and the classical state of the parent hidden variable theory. Finally, we find that the communication complexity for single qubits is smaller than 1.28 bits. The previous known upper bound was 1.85 bits.

arXiv:1206.2961•Physical Review Letters•Sep 12, 2012•28 citations

Classical communication rates for simulating quantum resources

A. Montina, Marcel Pfaffhauser, Stefan Wolf

Quantum theory is, in some sense, “non-classical.” For instance, the behavior of entangled systems (i.e., shared quantum information) under measurements cannot, in general, be explained by shared classical information. With classical communication, on the other hand, both the correlations entanglement leads to as well as quantum channels can be reproduced in principle. Here, crucial questions are whether the required communications is finite; if so, then its exact amount is related to the “degree of non-classicality” of the quantum primitive. We apply information-theoretic results such as the reverse Shannon theorem for determining the required communication in the asymptotic limit. The communication complexity of a quantum channel is the minimal amount of classical communication required for classically simulating the process of preparation, transmission through the channel, and subsequent measurement of a quantum state. At present, only little is known about this quantity. Our generic procedure allows for systematically evaluating the communication complexity of channels in any general probabilistic theory, in particular quantum theory. The procedure is constructive and provides the most efficient classical protocols. We illustrate it by evaluating the communication complexity of sending single qubits over a noiseless quantum channel with some finite sets of quantum states and measurements. As a second application, we determine the classical-communication rate required for the simulation of the behavior under measurements of entangled states. Here, the communication cost can be directly interpreted as the “non-classicality” of the correlation. A particular example is the simulation of non-maximally entangled pure qubit pairs, where we find the required communication rate to behave monotonically with the strength of the entanglement. For different measures of non-locality, such as the number of required non-local (PR) boxes, another behavior had been reported for the single-shot scenario.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•0 citations
The process of state preparation, its transmission and subsequent measurement can be classically simulated through the communication of some amount of classical information. Recently, we proved that the minimal communication cost is the minimum of a convex functional over a space of suitable probability distributions. It is now proved that this optimization problem is the dual of a geometric programming problem, which displays some appealing properties. First, the number of variables grows linearly with the input size. Second, the objective function is linear in the input parameters and the variables. Finally, the constraints do not depend on the input parameters. These properties imply that, once a feasible point is found, the computation of a lower bound on the communication cost in any two-party process is linearly complex. The studied scenario goes beyond quantum processes. We illustrate the method by analytically deriving some non-trivial lower bounds. Finally, we conjecture the lower bound n2nfor a noiseless quantum channel with capacity n qubits.
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 nnn qubits. This lower bound can have interesting consequences in the context of the recent debate on the reality of the quantum state.
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.2381.2381.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.2081.2081.208 bits.
A process of preparation, transmission, and subsequent projective measurement of a qubit can be simulated by a classical model with only two bits of communication and some amount of shared randomness. However, to the best of our knowledge, no model for nnn qubits with a finite amount of classical communication is known at present. A lower bound for the communication cost can provide useful hints for a generalization. It is known, for example, that the amount of communication must be greater than c2nc{2}^{n}c2n, where $c\ensuremath{\simeq}0.01$. The proof uses a quite elaborate theorem of communication complexity. Using a mathematical conjecture known as the ``double cap conjecture,'' we strengthen this result by presenting a geometrical and extremely simple derivation of the lower bound ${2}^{n}\ensuremath{-}1$. Only rank-1 projective measurements are involved in the derivation.
We study a model of communication complexity that encompasses many well-studied problems, including classical and quantum communication complexity, the complexity of simulating distributions arising from bipartite measurements of shared quantum states, and XOR games. In this model, Alice gets an input xxx, Bob gets an input yyy, and their goal is to each produce an output a,ba,ba,b distributed according to some pre-specified joint distribution p(a,b∣x,y)p(a,b|x,y)p(a,b∣x,y). Our results apply to any non-signaling distribution, that is, those where Alice's marginal distribution does not depend on Bob's input, and vice versa.~~~By taking a geometric view of the non-signaling distributions, we introduce a simple new technique based on affine combinations of lower-complexity distributions, and we give the first general technique to apply to all these settings, with elementary proofs and very intuitive interpretations. Specifically, we introduce two complexity measures, one which gives lower bounds on classical communication, and one for quantum communication. These measures can be expressed as convex optimization problems. We show that the dual formulations have a striking interpretation, since they coincide with maximum violations of Bell and Tsirelson inequalities. The dual expressions are closely related to the winning probability of XOR games. Despite their apparent simplicity, these lower bounds subsume many known communication complexity lower bound methods, most notably the recent lower bounds of Linial and Shraibman for the special case of Boolean functions. We show that as in the case of Boolean functions, the gap between the quantum and classical lower bounds is at most linear in the size of the support of the distribution, and does not depend on the size of the inputs. This translates into a bound on the gap between maximal Bell and Tsirelson inequality violations, which was previously known only for the case of distributions with Boolean outcomes and uniform marginals. It also allows us to show that for some distributions, information theoretic methods are necessary to prove strong lower bounds. ~~~ Finally, we give an exponential upper bound on quantum and classical communication complexity in the simultaneous messages model, for any non-signaling distribution. One consequence of this is a simple proof that any quantum distribution can be approximated with a constant number of bits of communication.
The communication complexity of a quantum channel is the minimal amount of classical communication required for classically simulating a process of state preparation, transmission through the channel and subsequent measurement. It establishes a limit on the power of quantum communication in terms of classical resources. We show that classical simulations employing a finite amount of communication can be derived from a special class of hidden variable theories where quantum states represent statistical knowledge about the classical state and not an element of reality. This special class has attracted strong interest very recently. The communication cost of each derived simulation is given by the mutual information between the quantum state and the classical state of the parent hidden variable theory. Finally, we find that the communication complexity for single qubits is smaller than 1.28 bits. The previous known upper bound was 1.85 bits.
Quantum theory is, in some sense, “non-classical.” For instance, the behavior of entangled systems (i.e., shared quantum information) under measurements cannot, in general, be explained by shared classical information. With classical communication, on the other hand, both the correlations entanglement leads to as well as quantum channels can be reproduced in principle. Here, crucial questions are whether the required communications is finite; if so, then its exact amount is related to the “degree of non-classicality” of the quantum primitive. We apply information-theoretic results such as the reverse Shannon theorem for determining the required communication in the asymptotic limit. The communication complexity of a quantum channel is the minimal amount of classical communication required for classically simulating the process of preparation, transmission through the channel, and subsequent measurement of a quantum state. At present, only little is known about this quantity. Our generic procedure allows for systematically evaluating the communication complexity of channels in any general probabilistic theory, in particular quantum theory. The procedure is constructive and provides the most efficient classical protocols. We illustrate it by evaluating the communication complexity of sending single qubits over a noiseless quantum channel with some finite sets of quantum states and measurements. As a second application, we determine the classical-communication rate required for the simulation of the behavior under measurements of entangled states. Here, the communication cost can be directly interpreted as the “non-classicality” of the correlation. A particular example is the simulation of non-maximally entangled pure qubit pairs, where we find the required communication rate to behave monotonically with the strength of the entanglement. For different measures of non-locality, such as the number of required non-local (PR) boxes, another behavior had been reported for the single-shot scenario.