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:2102.12543 · Physical Review Research

Certifying the classical simulation cost of a quantum channel

Brian Doolittle, Eric Chitambar

Published Oct 26, 2021• 13 citations
arXivHTMLPDF

Abstract

A fundamental objective in quantum information science is to determine the cost in classical resources of simulating a particular quantum system. The classical simulation cost is quantified by the signaling dimension which specifies the minimum amount of classical communication needed to perfectly simulate a channel's input-output correlations when unlimited shared randomness is held between encoder and decoder. This paper provides a collection of device-independent tests that place lower and upper bounds on the signaling dimension of a channel. Among them, a single family of tests is shown to determine when a noisy classical channel can be simulated using an amount of communication strictly less than either its input or its output alphabet size. In addition, a family of eight signaling dimension witnesses is presented that completely characterize when any four-outcome measurement channel, such as a Bell measurement, can be simulated using one communication bit and shared randomness. Finally, we bound the signaling dimension for all partial replacer channels in $d$ dimensions. The bounds are found to be tight for the special case of the erasure channel.

DOI
10.1103/physrevresearch.3.043073

Related papers

Quantum communication and Bell nonlocality require infinite classical communication to simulate

Carlos de Gois, Thyago S. R. Santos, Carlos Vieira

A quantum system of any fixed dimension can be prepared in a continuum of states, yet it cannot be used to transmit an unlimited amount of classical information. Similarly, the correlations observed between measurement outcomes on separate parts of a shared quantum system can be stronger than classical correlations, but they cannot transmit information. These fundamental limitations suggest that the statistics observed from quantum communication and quantum correlations may admit a simulation using a finite amount of classical communication. This expectation is confirmed in the smallest nontrivial quantum dimension, with two classical bits being necessary and sufficient to exactly simulate qubit communication and all correlations between qubits. Despite significant efforts during the previous decades, this remained the only solved case. Here we resolve both problems for every quantum dimension. The solution reveals an unexpected qualitative transition starting at dimension four: no finite amount of classical communication can exactly simulate ququart communication nor all quantum correlations of two entangled ququarts, even with unlimited shared randomness. One might have expected this transition, if it existed, to appear already for qutrits. Instead, we construct an explicit protocol that exactly simulates qutrit communication using $357$ classical bits, and consequently, all correlations of two entangled qutrits.

quant-pharXiv:2609.04182•Sep 4, 2026•5 citations

Classical Communication Cost of a Bipartite Quantum Channel Assisted by Non-Signaling Correlations

Chengkai Zhu, Xuanqiang Zhao, Xin Wang

Understanding the classical communication cost of simulating a quantum channel is a fundamental problem in quantum information theory, which becomes even more intriguing when considering the role of non-locality in quantum information processing. This paper investigates the bidirectional classical communication cost of simulating a bipartite quantum channel assisted by non-signalling correlations, which are permitted across the spatial dimension between the two parties. By introducing non-signalling superchannels, we present lower and upper bounds on the one-shot $ε$-error one-way classical communication cost of a bipartite channel via its smooth max-relative entropy of one-way classical communication, and establish that the asymptotic exact cost is given by its max-relative entropy of one-way classical communication. For the bidirectional scenario, we derive semidefinite programming (SDP) formulations for the one-shot exact bidirectional classical communication cost via non-signalling bipartite superchannels. We further introduce a channel's bipartite conditional min-entropy as an efficiently computable lower bound on the asymptotic cost of bidirectional classical communication. Our results in both one-shot and asymptotic settings provide lower bounds on the entanglement-assisted simulation cost in scenarios where entanglement is available to the two parties. Moreover, we propose a seesaw-based algorithm to compute an upper bound on the minimum simulation error via local operations and shared entanglement, which provides valuable insights into the relationship between non-signalling bipartite superchannels and more physically realizable protocols. Numerical experiments demonstrate the effectiveness of our bounds in estimating communication costs for various quantum channels, showing that our bounds can be tight in different scenarios.

arXiv:2408.02506•IEEE Transactions on Information Theory•May 9, 2025•1 citation

Classical Simulation of Quantum Channel Families: Unbounded Cost Separation and Sharp Noise–Error Scaling

Huayu Liu

When the input measurement is fixed across a channel family, the simulation of binary output tests allows test-dependent responses, whereas preparing a quantum output requires one normalized state per recorded branch. We prove an unbounded separation between the optimized outcome costs of these tasks for families admitting a common mother measurement. The channel choices are specified by classical descriptions. For an explicit family of qubit channels, six outcomes suffice for all binary tests, whereas the exact channel cost is finite at every positive level of additional depolarizing noise and diverges as the noise vanishes. The family is the image of an explicit CPTP processor with a fixed finite-dimensional program and qubit input and output. For noise fraction λ and uniform output-channel diamond-norm error ε, the minimum common-measurement cost has the sharp order (λ + ε)^{−2/3} for 0 < λ + ε ≤ 1/2, both when channels are approximated independently and when the approximating family is generated by a single CPTP processor on the same spaces. The lower bound holds for arbitrary approximating channels subject only to the common-measurement budget. At each sufficiently small positive noise level, one finite common mother serves an entire full-dimensional process neighborhood of radius proportional to λ, throughout which the same cost law and six-outcome binary-test simulator persist.

•Nov 11, 2026•0 citations

The Quantum Reverse Shannon Theorem and Resource Tradeoffs for Simulating Quantum Channels

Charles H. Bennett, Igor Devetak, Aram W. Harrow +2 more

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.

arXiv:0912.5537•IEEE Transactions on Information Theory•Mar 5, 2014•287 citations

Tensor Norms and the Classical Communication Complexity of Nonlocal Quantum Measurement

Yaoyun Shi, Yufan Zhu

We initiate the study of quantifying nonlocality of a bipartite measurement by the minimum amount of classical communication required to simulate the measurement. We derive general upper bounds in terms of some tensor norms of the measurement operator. As applications, we show that (a) if the amount of communication is a constant, then quantum and classical communication protocols with an unlimited amount of shared entanglement or shared randomness compute the same class of functions; and (b) it requires only a constant amount of communication to classically generate an approximation of the output distribution resulting from local measurements on an entangled quantum state, as long as the number of measurement outcomes is a constant.

arXiv:quant-ph/0511071•SIAM Journal on Computing•Jan 1, 2008•20 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•26 citations
A fundamental objective in quantum information science is to determine the cost in classical resources of simulating a particular quantum system. The classical simulation cost is quantified by the signaling dimension which specifies the minimum amount of classical communication needed to perfectly simulate a channel's input-output correlations when unlimited shared randomness is held between encoder and decoder. This paper provides a collection of device-independent tests that place lower and upper bounds on the signaling dimension of a channel. Among them, a single family of tests is shown to determine when a noisy classical channel can be simulated using an amount of communication strictly less than either its input or its output alphabet size. In addition, a family of eight signaling dimension witnesses is presented that completely characterize when any four-outcome measurement channel, such as a Bell measurement, can be simulated using one communication bit and shared randomness. Finally, we bound the signaling dimension for all partial replacer channels in ddd dimensions. The bounds are found to be tight for the special case of the erasure channel.
A quantum system of any fixed dimension can be prepared in a continuum of states, yet it cannot be used to transmit an unlimited amount of classical information. Similarly, the correlations observed between measurement outcomes on separate parts of a shared quantum system can be stronger than classical correlations, but they cannot transmit information. These fundamental limitations suggest that the statistics observed from quantum communication and quantum correlations may admit a simulation using a finite amount of classical communication. This expectation is confirmed in the smallest nontrivial quantum dimension, with two classical bits being necessary and sufficient to exactly simulate qubit communication and all correlations between qubits. Despite significant efforts during the previous decades, this remained the only solved case. Here we resolve both problems for every quantum dimension. The solution reveals an unexpected qualitative transition starting at dimension four: no finite amount of classical communication can exactly simulate ququart communication nor all quantum correlations of two entangled ququarts, even with unlimited shared randomness. One might have expected this transition, if it existed, to appear already for qutrits. Instead, we construct an explicit protocol that exactly simulates qutrit communication using 357357357 classical bits, and consequently, all correlations of two entangled qutrits.
Understanding the classical communication cost of simulating a quantum channel is a fundamental problem in quantum information theory, which becomes even more intriguing when considering the role of non-locality in quantum information processing. This paper investigates the bidirectional classical communication cost of simulating a bipartite quantum channel assisted by non-signalling correlations, which are permitted across the spatial dimension between the two parties. By introducing non-signalling superchannels, we present lower and upper bounds on the one-shot εεε-error one-way classical communication cost of a bipartite channel via its smooth max-relative entropy of one-way classical communication, and establish that the asymptotic exact cost is given by its max-relative entropy of one-way classical communication. For the bidirectional scenario, we derive semidefinite programming (SDP) formulations for the one-shot exact bidirectional classical communication cost via non-signalling bipartite superchannels. We further introduce a channel's bipartite conditional min-entropy as an efficiently computable lower bound on the asymptotic cost of bidirectional classical communication. Our results in both one-shot and asymptotic settings provide lower bounds on the entanglement-assisted simulation cost in scenarios where entanglement is available to the two parties. Moreover, we propose a seesaw-based algorithm to compute an upper bound on the minimum simulation error via local operations and shared entanglement, which provides valuable insights into the relationship between non-signalling bipartite superchannels and more physically realizable protocols. Numerical experiments demonstrate the effectiveness of our bounds in estimating communication costs for various quantum channels, showing that our bounds can be tight in different scenarios.
When the input measurement is fixed across a channel family, the simulation of binary output tests allows test-dependent responses, whereas preparing a quantum output requires one normalized state per recorded branch. We prove an unbounded separation between the optimized outcome costs of these tasks for families admitting a common mother measurement. The channel choices are specified by classical descriptions. For an explicit family of qubit channels, six outcomes suffice for all binary tests, whereas the exact channel cost is finite at every positive level of additional depolarizing noise and diverges as the noise vanishes. The family is the image of an explicit CPTP processor with a fixed finite-dimensional program and qubit input and output. For noise fraction λ and uniform output-channel diamond-norm error ε, the minimum common-measurement cost has the sharp order (λ + ε)^{−2/3} for 0 < λ + ε ≤ 1/2, both when channels are approximated independently and when the approximating family is generated by a single CPTP processor on the same spaces. The lower bound holds for arbitrary approximating channels subject only to the common-measurement budget. At each sufficiently small positive noise level, one finite common mother serves an entire full-dimensional process neighborhood of radius proportional to λ, throughout which the same cost law and six-outcome binary-test simulator persist.
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.
We initiate the study of quantifying nonlocality of a bipartite measurement by the minimum amount of classical communication required to simulate the measurement. We derive general upper bounds in terms of some tensor norms of the measurement operator. As applications, we show that (a) if the amount of communication is a constant, then quantum and classical communication protocols with an unlimited amount of shared entanglement or shared randomness compute the same class of functions; and (b) it requires only a constant amount of communication to classically generate an approximation of the output distribution resulting from local measurements on an entangled quantum state, as long as the number of measurement outcomes is a constant.
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.