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

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{2}^{n-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.

Corrected some typos and replaced the (dim) proof of Theorem 1 with a much more elegant one. This paper is the extended journal version of the conference version arXiv:1401.4126. The journal version contains considerable new material. See comment to the first version for a list of the new material

References in corpus (8)

• On the reality of the quantum state
• Non-locality and Communication Complexity
• Is a system's wave function in one-to-one correspondence with its elements of reality?
• Implications of the Pusey-Barrett-Rudolph quantum no-go theorem
• Epistemic view of quantum states and communication complexity of quantum channels
• Communication cost of classically simulating a quantum channel with subsequent rank-1 projective measurement
• Communication Complexity of Channels in General Probabilistic Theories
• Exponential communication gap between weak and strong classical simulations of quantum communication

Cited by in corpus (8)

• Is the quantum state real? An extended review of $\psi$-ontology theorems
• No Return to Classical Reality
• Simple Communication Complexity Separation from Quantum State Antidistinguishability
• Communication complexity and the reality of the wave-function
• Information-based measure of nonlocality
• Tight bounds for antidistinguishability and circulant sets of pure quantum states
• Optimal measurements for nonlocal correlations
• Simple algorithm for computing the communication complexity of quantum communication processes