Certifying the classical simulation cost of a quantum channel

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.

Figure 1

A general classical communication process. We represent classical information as blue double lines, quantum information as black solid lines, and shared randomness as dotted red lines. (a) A classical channel ${\mathbf{P}}_{\mathcal{N}}$ is generated from a quantum channel $\mathcal{N}$ via Eq. (1). A classical-quantum encoder $\mathrm{\Psi }$ maps the classical input $x\in \mathcal{X}$ into a quantum state ${\rho }_x$. A quantum-classical decoder $\mathrm{\Pi }$ implements POVM ${\left\{{\mathrm{\Pi }}_y\right\}}_{y\in \mathcal{Y}}$. (b) Channel ${\mathbf{P}}_{\mathcal{N}}$ is simulated using shared randomness and a noiseless classical channel via Eq. (2). Alice encodes input $x$ into classical message $m$ with probability $T_{\lambda }\left(m\right|x)$ while Bob decodes message $m$ into output $y$ with probability $R_{\lambda }\left(y\right|m)$. The protocol is coordinated using a shared random value $\lambda$ drawn from sample space $\mathrm{\Lambda }$ with probability $q\left(\lambda \right)$.

Figure 2

A graphical analogy illustrating key features of signaling polytopes. Note that the geometry has been simplified by removing vertices and and projecting the polytope onto a plane. The example shows a hierarchy of three signaling polytopes ${\mathcal{C}}_d^{3\to 3}$ with $d\in [1,3]$. Each signaling polytope is a convex set where hierarchy ${\mathcal{C}}_{d=1}^{3\to 3}\subset {\mathcal{C}}_{d=2}^{3\to 3}\subset {\mathcal{C}}_{d=3}^{3\to 3}$ holds for any $n$ and $n^{\prime }$. The vertices of each polytope are depicted as circles while the facets are lines. The ${\mathcal{C}}_{d=1}^{3\to 3}$ polytope is blue, the ${\mathcal{C}}_{d=2}^{3\to 3}$ polytope is orange, and the ${\mathcal{C}}_{d=3}^{3\to 3}={\mathcal{P}}^{3\to 3}$ polytope is black. A signaling dimension witness constitutes a facet of the signaling polytope. The channel ${\mathbf{P}}_{\text{Red}}$ (red star) has $\kappa \left({\mathbf{P}}_{\text{Red}}\right)=3$ while the channel ${\mathbf{P}}_{\text{Green}}$ (green star) has $\kappa \left({\mathbf{P}}_{\text{Green}}\right)=2$.

Figure 3

A depiction of the required device trust to implement the device-independent certification of the signaling dimension for classical and quantum channels. (a) Alice and Bob certify the signaling dimension of an untrusted classical channel ${\mathbf{P}}_{\mathcal{N}}$ using only the probabilities $P_{\mathcal{N}}\left(y\right|x)$ for all $x\in \mathcal{X}$ and $y\in \mathcal{Y}$. (b) Alice and Bob certify the signaling dimension of an untrusted quantum channel $\mathcal{N}$ using trusted state preparation $\mathrm{\Psi }$ and trusted measurement $\mathrm{\Pi }$. If Alice and Bob do not trust their encode/decode devices, then bounds on the signaling dimension can still be established by treating the quantum communication system as a classical channel.