Abstract Can quantum processes be simulated using only classical resources? This question delineates the boundary between classical and quantum models and clarifies the origin of quantum advantage in information processing. We address this question through the task of quantum channel simulation, where a sender (Alice) holds the classical description of a quantum state and wishes to transmit it to a receiver (Bob) for measurement. Prior work has shown that, for qubit channels, 2 bits of forward communication with shared randomness suffice to reproduce the statistics of any single-qubit measurement. We argue, however, that true channel simulation requires reproducing statistics of joint measurements—including entangled effects—on Alice’s state and an auxiliary system held by Bob. Such scenarios naturally arise in network communication, where some nodes know the state, while others do not. We prove that a perfect qubit channel cannot be simulated with any finite amount of classical communication, even using the most general multi-round, bidirectional protocols. We further show that this no-go result is rooted in the necessity of reproducing statistics associated with entangled effects. On the other hand, we show that noisy qubit channels, such as depolarizing channels, admit classical simulation, though the required communication diverges as noise decreases.
Abstract Can quantum processes be simulated using only classical resources? This question delineates the boundary between classical and quantum models and clarifies the origin of quantum advantage in information processing. We address this question through the task of quantum channel simulation, where a sender (Alice) holds the classical description of a quantum state and wishes to transmit it to a receiver (Bob) for measurement. Prior work has shown that, for qubit channels, 2 bits of forward communication with shared randomness suffice to reproduce the statistics of any single-qubit measurement. We argue, however, that true channel simulation requires reproducing statistics of joint measurements—including entangled effects—on Alice’s state and an auxiliary system held by Bob. Such scenarios naturally arise in network communication, where some nodes know the state, while others do not. We prove that a perfect qubit channel cannot be simulated with any finite amount of classical communication, even using the most general multi-round, bidirectional protocols. We further show that this no-go result is rooted in the necessity of reproducing statistics associated with entangled effects. On the other hand, we show that noisy qubit channels, such as depolarizing channels, admit classical simulation, though the required communication diverges as noise decreases.
We consider general prepare-and-measure scenarios in which Alice can transmit qubit states to Bob, who can perform general measurements in the form of positive operator-valued measures (POVMs). We show that the statistics obtained in any such quantum protocol can be simulated by the purely classical means of shared randomness and two bits of communication. Furthermore, we prove that two bits of communication is the minimal cost of a perfect classical simulation. In addition, we apply our methods to Bell scenarios, which extends the well-known Toner and Bacon protocol. In particular, two bits of communication are enough to simulate all quantum correlations associated to arbitrary local POVMs applied to any entangled two-qubit state.
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.
Dual to the usual noisy channel coding problem, where a noisy (classical or quantum) channel is used to simulate a noiseless one, reverse Shannon theorems concern the use of noiseless channels to simulate noisy ones, and more generally the use of one noisy channel to simulate another. For channels of nonzero capacity, this simulation is always possible, but for it to be efficient, auxiliary resources of the proper kind and amount are generally required. In the classical case, shared randomness between sender and receiver is a sufficient auxiliary resource, regardless of the nature of the source, but in the quantum case, the requisite auxiliary resources for efficient simulation depend on both the channel being simulated, and the source from which the channel inputs are coming. For tensor power sources (the quantum generalization of classical memoryless sources), entanglement in the form of standard ebits (maximally entangled pairs of qubits) is sufficient, but for general sources, which may be arbitrarily correlated or entangled across channel inputs, additional resources, such as entanglement-embezzling states or backward communication, are generally needed. Combining existing and new results, we establish the amounts of communication and auxiliary resources needed in both the classical and quantum cases, the tradeoffs among them, and the loss of simulation efficiency when auxiliary resources are absent or insufficient. In particular, we find a new single-letter expression for the excess forward communication cost of coherent feedback simulations of quantum channels (i.e., simulations in which the sender retains what would escape into the environment in an ordinary simulation), on nontensor-power sources in the presence of unlimited ebits but no other auxiliary resource. Our results on tensor power sources establish a strong converse to the entanglement-assisted capacity theorem.
Dual to the usual noisy channel coding problem, where a noisy (classical or quantum) channel is used to simulate a noiseless one, reverse Shannon theorems concern the use of noiseless channels to simulate noisy ones, and more generally the use of one noisy channel to simulate another. For channels of nonzero capacity, this simulation is always possible, but for it to be efficient, auxiliary resources of the proper kind and amount are generally required. In the classical case, shared randomness between sender and receiver is a sufficient auxiliary resource, regardless of the nature of the source, but in the quantum case the requisite auxiliary resources for efficient simulation depend on both the channel being simulated, and the source from which the channel inputs are coming. For tensor power sources (the quantum generalization of classical IID sources), entanglement in the form of standard ebits (maximally entangled pairs of qubits) is sufficient, but for general sources, which may be arbitrarily correlated or entangled across channel inputs, additional resources, such as entanglement-embezzling states or backward communication, are generally needed. Combining existing and new results, we establish the amounts of communication and auxiliary resources needed in both the classical and quantum cases, the tradeoffs among them, and the loss of simulation efficiency when auxiliary resources are absent or insufficient. In particular we find a new single-letter expression for the excess forward communication cost of coherent feedback simulations of quantum channels (i.e. simulations in which the sender retains what would escape into the environment in an ordinary simulation), on non-tensor-power sources in the presence of unlimited ebits but no other auxiliary resource. Our results on tensor power sources establish a strong converse to the entanglement-assisted capacity theorem.
This chapter begins our exploration of “dynamic” information-processing tasks in quantum Shannon theory, where the term “dynamic” indicates that a quantum channel connects a sender to a receiver and their goal is to exploit this resource for communication. We specifically consider the scenario where a sender Alice would like to communicate classical information to a receiver Bob, and the capacity theorem that we prove here is one particular generalization of Shannon's noisy channel coding theorem from classical information theory (overviewed in Section 2.2). In later chapters, we will see other generalizations of Shannon's theorem, depending on what resources are available to assist their communication or depending on whether they are trying to communicate classical or quantum information. For this reason and others, quantum Shannon theory is quite a bit richer than classical information theory. The naive approach to communicate classical information over a quantum channel is for Alice and Bob simply to mimic the approach used in Shannon's noisy channel coding theorem. That is, they select a random classical code according to some distribution pX(x) , and Bob performs individual measurements of the outputs of a noisy quantum channel according to some POVM. The POVM at the output induces some conditional probability distribution pY∣X(y∣x) , which we can in turn think of as an induced noisy classical channel. The classical mutual information I(X; Y) of this channel is an achievable rate for communication, and the best strategy for Alice and Bob is to optimize the mutual information over all of Alice's inputs to the channel and over all measurements that Bob could perform at the output.
A fundamental limitation of quantum communication is that a single qubit can carry at most 1 bit of classical information. For an important class of quantum communication channels, known as entanglement-breaking, this limitation holds even if the sender and receiver share entangled particles. But does this mean that, for the purpose of communicating classical messages, a noisy entanglement-breaking qubit channel can be replaced by a noisy bit channel? Here we answer the question in the negative. We introduce a game, similar to the Monty Hall problem in classical statistics, where a sender assists a receiver in finding a valuable item (the prize) hidden into one of four possible boxes, while avoiding a hazardous item (the bomb) hidden in one of the remaining three boxes. We show that no classical strategy using a noisy bit channel can ensure that the bomb is avoided, even if the sender and receiver share arbitrary amounts of randomness. In contrast, communication of a qubit through a class of noisy entanglement-breaking channels, which we call quantum NOT channels, allows the players to deterministically avoid the bomb and to find the prize with a guaranteed nonzero probability. Our findings show that the communication of classical messages through a noisy entanglement-breaking qubit channel assisted by quantum entanglement cannot, in general, be simulated by communication through a noisy bit channel assisted by classical correlations.