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:1402.6299 · Physical Review A

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

A. Montina, Stefan Wolf

Published Jul 8, 2014• 10 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.90.012309

Related papers

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

A. Montina, Stefan Wolf

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.

arXiv:1401.4126•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•4 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

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

Bounding the classical cost of simulating quantum behaviors in the prepare-and-measure scenario

Sebastian Schlösser, Matthias Kleinmann

We study the prepare-and-measure scenario in which Alice transmits a quantum system to Bob, who then performs a quantum measurement. The quantum state of the system is unknown to Bob, and the measurement is unknown to Alice. It has recently been shown that shared randomness and two bits of classical communication are necessary and sufficient to simulate the transmission of a qubit. We show that the communication cost can be reduced to an average of $1.89$ bits. We then study restricted sets of state preparations: First, for a restriction to real-valued qubit states, if the communication of a classical trit is sufficient, we show that the corresponding protocol must have a convoluted form. We then reduce the smallest qubit scenario requiring two bits of classical communication to only $6$ state preparations and $5$ measurements. For a qutrit, it is not known whether the communication cost is finite; we identify a scenario that requires at least $5$ classical messages, already for the simulation of the real qutrit. Finally, we develop a method for restricted sets of states, that allows us to lower bound the classical communication cost based solely on the set of quantum states.

quant-pharXiv:2603.01255•Mar 3, 2026•0 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

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
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×\else\texttimes\fi2n\ensuremath−1n\ifmmode\times\else\texttimes\fi{}{2}^{n\ensuremath{-}1}n\ifmmode×\else\texttimes\fi2n\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.
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.
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.
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.
We study the prepare-and-measure scenario in which Alice transmits a quantum system to Bob, who then performs a quantum measurement. The quantum state of the system is unknown to Bob, and the measurement is unknown to Alice. It has recently been shown that shared randomness and two bits of classical communication are necessary and sufficient to simulate the transmission of a qubit. We show that the communication cost can be reduced to an average of 1.891.891.89 bits. We then study restricted sets of state preparations: First, for a restriction to real-valued qubit states, if the communication of a classical trit is sufficient, we show that the corresponding protocol must have a convoluted form. We then reduce the smallest qubit scenario requiring two bits of classical communication to only 666 state preparations and 555 measurements. For a qutrit, it is not known whether the communication cost is finite; we identify a scenario that requires at least 555 classical messages, already for the simulation of the real qutrit. Finally, we develop a method for restricted sets of states, that allows us to lower bound the classical communication cost based solely on the set of quantum states.
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.
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.