note-name = , use-sort-key = false

# Classical communication through quantum causal structures

Kaumudibikash Goswami<EMAIL_ADDRESS>Fabio Costa<EMAIL_ADDRESS>Australian Research Council Centre of Excellence for Engineered Quantum
Systems, School of Mathematics and Physics,
University of Queensland, QLD 4072 Australia

###### Abstract

Quantum mechanics allows operations to be in indefinite causal order. Recently
there have been active discussions on enhanced communication strategies
through exotic causal structures. In light of this, through the process matrix
formalism, we formulate different classical capacities for a bi-partite
quantum process. We find that a one-way communication protocol through an
arbitrary process cannot outperform a causally separable process, i.e., we can
send at most one bit per qubit. Next, we study bi-directional communication
through a causally separable process. Our result shows, a bi-directional
protocol cannot exceed the limit of one way communication protocol. Finally,
we generalise this result to multi-party broadcast communication protocol
through a definite ordered process.

††preprint: APS/123-QED

##  I Introduction

One of the key questions in quantum information is the rate at which a quantum
channel can transmit classical information, as quantified by the _classical
capacity_ of the channel [1, 2]. Holevo’s seminal result [3], and following
work [4, 5], provide upper bounds on the classical capacity, showing that each
qubit can communicate at most one bit of classical information.

In a typical quantum communication protocol, the parties act in a fixed order.
However, more general situations are possible, where causal order might be
uncertain or even not defined. A practical example can be a distributed
system, such as the internet, where different nodes communicate with each
other. In such systems, local clocks can suffer from random errors and delays,
leading to uncertainty in the ordering of the events [6]. Even more radically,
recent developments have shown possibilities of _indefinite_ causal structure,
i.e., scenarios where the lack of order between the parties cannot be reduced
to classical ignorance [7, 8]. From a foundational point of view, this is
relevant, for example, in quantum gravity scenarios, where quantum
superposition of spacetimes can result in an indefinite causal order of events
[9, 10, 11]. Pragmatically, quantum control of causal order has been proposed
as a resource for computation and communication [7, 12, 13, 14, 15, 16, 17,
18, 19], with several experimental implementations already performed [20, 21,
22, 23, 24, 25, 26].

In light of the foundational and applied relevance, it is important to
understand how general quantum causal structure affects classical
communication. In particular, one may wonder whether an indefinite causal
structure can augment the classical communication capacity and possibly exceed
the Holevo bound [5, 4]. However, despite much work on various communication
protocols, the notion of classical capacities in situations where the
communicating parties themselves are indefinitely ordered has not yet been
developed.

We address this gap through the process matrix formalism [8]. We develop
expressions for the asymptotic capacity of a process, under different encoding
and decoding settings, reducing to analogue expressions for quantum channels.
We explore one-way communication protocols through an arbitrary process and
show that such scenarios cannot exceed communication in definite causal order,
i.e., we can send at most one bit per exchanged qubit. We also explore two-
party communication protocols when causal order is definite but unknown
(probabilistic). In such situations, the total bi-directional communication
cannot exceed the maximum one-way communication—again, at most one bit per
qubit in either direction. This extends to a similar bound for communication
between multiple parties in a definite (but possibly probabilistic) causal
order.

We present the work following way. In Section II, we give an introduction to
classical communication through quantum channels. In Section III, we introduce
the framework of the process matrix. In Section IV, we introduce asymptotic
setting for processes, subsequently we define classical capacities of a
process, and developed a bound for one way communication. In Section V we
develop a bound for bi-directional communication protocol. We then generalise
the bound for a multi-party broadcast communication protocol.

##  II  Classical communication through a quantum channel

Let us first review how one can use ordinary quantum channels to send
classical information [2, 27]. In a one-way communication protocol, Alice has
a classical message $m$, prepared according to some probability distribution
$P(m)$, and encodes it into a quantum state $\rho_{m}$. She then sends it to
Bob through a noisy quantum channel $\mathcal{N}$. Upon receiving the state,
Bob extracts the message by using a positive operator valued measure (POVM)
$\left\\{E_{m^{\prime}}\right\\}_{m^{\prime}}$, where $E_{m^{\prime}}\geq 0$,
$\sum_{m^{\prime}}E_{m^{\prime}}=\mathbb{1}$. Here ${m^{\prime}}$ denotes the
measurement outcome. The conditional probability of Bob receiving a message
$m^{\prime}$ given that Alice sends the message $m$ is

$\displaystyle
p(m^{\prime}|m)=\operatorname{Tr}\left[E_{m^{\prime}}\mathcal{N}\left(\rho_{m}\right)\right].$
(1)

The probability of error for a particular message $m$ is

$\displaystyle p_{e}(m)=p({m^{\prime}}{\neq}m{|}m)=1-p(m|m).$ (2)

The goal of the protocol is to minimise the maximal probability of error
$p^{*}_{e}:=\max_{m}p_{e}(m)$. An _asymptotic setting_ is a scenario where
Alice can use $n$ copies of the channel to send a $k$-bit message
$m\in\\{0,1\\}^{k}$, where both $k$ and $n$ can be arbitrarily large. In other
words, she encodes $k$ bits into an $n\geq k$ -bit message
$X_{m}^{(n)}\in\\{0,1\\}^{n}$ and subsequently an $n$-qubit state
$\rho_{m}^{(n)}$ and then sends each qubit through an independent copy of the
channel. The classical capacity of the quantum channel $\mathcal{N}$, is
defined as the maximal rate $C=k/n$ such that asymptotically,
$n\rightarrow{\infty}$, one can achieve noiseless communication,
$p^{*}_{e}\rightarrow{0}$ [28, 2].

Different encoding and decoding strategies can lead to different asymptotic
settings resulting in different classical communication capacities for a
channel $\mathcal{N}$, which we review below. A quantification of classical
communication possible through a channel $\mathcal{N}$ is given by the _Holevo
quantity_ [3], defined as

$\displaystyle\chi(\mathcal{N}):=\underset{p(m),\rho_{m}}{{\mathrm{max}}}\ $
$\displaystyle S\left(\sum p(m)\mathcal{N}(\rho_{m})\right)$
$\displaystyle-\sum p(m)S\left(\mathcal{N}(\rho_{m})\right).$ (3)

Here $S(.)$ is the von Neumann entropy. Having introduced the Holevo quantity
for a channel, it is interesting to see how this quantity is related to
different classical capacities corresponding to different asymptotic
configurations of channels. We discuss it below.

_Product encoding - Product decoding:_ When the input quantum state is a
product state of the form $\rho_{m}^{(n)}{=}\otimes_{i=1}^{n}\rho^{(i)}_{m}$
and the measurement operation is
$E_{m^{\prime}}^{(n)}{=}\otimes_{i=1}^{n}E_{m^{\prime}}^{(i)}$ with each
$E_{m^{\prime}}^{(i)}$ acting on the qubit $\mathcal{N}(\rho^{(i)}_{m})$. Let
us consider, the measurement result produces an $n$-bit string
$Y_{m^{\prime}}^{(n)}\in\\{0,1\\}^{n}$ corresponding to the message
$m^{\prime}$. In the asymptotic setting, $n{\rightarrow}{\infty}$, the
capacity in this setup is given by the conventional definition of classical
capacity obtained by maximising the regularised mutual information,
$I(Y_{m^{\prime}}^{(n)}{:}X_{m}^{(n)})/n$, between Alice’s input and Bob’s
output over the input probability distribution, the encoded quantum states and
decoding measurement operators. The central idea of Shannon’s capacity formula
is that the mutual information $I(Y_{m^{\prime}}^{(n)}{:}X_{m}^{(n)})$ is
additive. Thus, the corresponding capacity is called _one-shot capacity_ ,
$C^{(1)}(\mathcal{N})$. This capacity is determined by the single use of the
channel $\mathcal{N}$, with the optimised mutual information
$I(Y_{m^{\prime}}^{(1)}{:}X_{m}^{(1)})$, corresponding to the single-copy
input and output variables $X_{m}^{(1)}$ and $Y_{m^{\prime}}^{(1)}$
respectively, i.e.

$\displaystyle C^{(1)}(\mathcal{N})$
$\displaystyle=\lim_{n{\rightarrow}{\infty}}\underset{p(m),\rho_{m}^{(n)},E_{m^{\prime}}^{(n)}}{{\mathrm{max}}}\frac{I(Y_{m^{\prime}}^{(n)}{:}X_{m}^{(n)})}{n}$
$\displaystyle=\underset{p(m),\rho_{m}^{(1)},E_{m^{\prime}}^{(1)}}{{\mathrm{max}}}I(Y_{m^{\prime}}^{(1)}{:}X_{m}^{(1)}).$
(4)

_Holevo’s theorem_ [3] states that this quantity is upper bounded by

$C^{(1)}(\mathcal{N})\leq\chi(\mathcal{N}),$ (5)

with the $\chi(\mathcal{N})$ defined in Eq. (II). Hereinafter, for the sake of
clarity, we are going to represent $I(Y_{m^{\prime}}^{(1)}{:}X_{m}^{(1)})$
with $I({m^{\prime}}{:}{m})$.

_Product encoding - Joint decoding:_ The difference with the previous case is
that Bob can perform a joint measurement on the $n$-qubit system. The _Holevo-
Schumacher-Westmoreland (HSW) capacity_ , $C(\mathcal{N})$, associated with
this strategy turns out to be greater than one shot capacity, i.e.
$C(\mathcal{N}){\geq}C^{(1)}(\mathcal{N})$, an effect known as _super-
additivity_. The HSW capacity is simply equal to the Holevo quantity [5, 4]:

$\displaystyle C(\mathcal{N}){=}\chi(\mathcal{N}),$ (6)

where $S(.)$ denotes the von Neumann entropy.

_Joint encoding - Joint decoding:_ Here, Alice uses an entangled $n$-qubit
state to encode the information and Bob performs a joint measurement on his
output. The capacity associated with this strategy is given by _regularised
Holevo quantity_ [3, 5, 4]:

$\displaystyle C^{E}(\mathcal{N}){=}\chi_{\mathrm{reg}}(\mathcal{N}),$ (7)

with

$\displaystyle\chi_{\mathrm{reg}}(\mathcal{N}){=}\lim_{n\to\infty}\frac{\chi(\mathcal{N}^{\otimes
n})}{n}.$ (8)

It has been shown in [29] that the capacity $C^{E}(\mathcal{N})$ in this case
can be even greater than the HSW capacity — $C^{E}(\mathcal{N})\geq
C(\mathcal{N})\geq C^{(1)}(\mathcal{N})$.

The Holevo quantity $\chi(\mathcal{N})$, and consequently the regularised
Holevo quantity $\chi_{\mathrm{reg}}(\mathcal{N})$, are further upper bounded
by $\log(d)$, where $d$ is the output dimension of the channel $\mathcal{N}$.
With this we summarise a sequence of inequalities:

$\displaystyle I(m^{\prime}{:}m)\leq C^{(1)}(\mathcal{N})\leq
C(\mathcal{N})=\chi({\mathcal{N}})$ $\displaystyle\leq
C^{E}(\mathcal{N})=\chi_{\mathrm{reg}}(\mathcal{N})\leq\log(d),$ (9)

with $I(m^{\prime}{:}m)$ being the unoptimized mutual information between
Alice’s input $m$ and Bob’s output $m^{\prime}$. A consequence of this chain
of inequalities is that, for any communication setting, a $d$ dimensional
quantum channel cannot transfer more than $\log(d)$ bits. In other words,
quantum systems can carry at most one bit per qubit.

##  III The Process framework

In conventional quantum communication protocols, the communicating parties act
in a well defined order. However, quantum mechanics allows possibilities,
where the order between the communicating parties is unknown or even
indefinite [9, 7]. This possibility can be modelled within the so-called
process matrix formalism [8, 30, 31]. Consider a situation involving two
parties — Alice and Bob, each acting in a local laboratory. In each run of the
experiment, each of them receives a quantum system in their respective
laboratories, performs some operation on it and sends it out [32]; Alice’s
(Bob’s) input and output systems will be denoted by $A_{I}$ ($B_{I}$) and
$A_{O}$ ($B_{O}$), respectively. Each party can also access an additional
system to perform their local operations. The most general operation is,
therefore, a completely positive (CP) map
$\mathcal{M}:X_{I}{\otimes}X_{I}^{\prime}{\rightarrow}X_{O}{\otimes}X_{O}^{\prime}$,
where, for $X=A,B$; $X_{I}^{\prime},X_{O}^{\prime}$ denote the additional
system and we use the system’s label to represent the corresponding state
space.

It is convenient to represent CP maps as positive semidefinite matrices,
$M{\in}X_{I}{\otimes}X_{I}^{\prime}{\otimes}X_{O}{\otimes}X_{O}^{\prime}$,
using the Choi isomorphism [33]:

$M^{X_{I}X_{I}^{\prime}X_{O}X^{\prime}_{O}}\\\
=\sum_{i,j=1}^{d_{X_{I}}d_{X^{\prime}_{I}}}\left|i\middle\rangle\middle\langle
j\right|^{X_{I}X_{I}^{\prime}}\otimes\mathcal{M}(\left|i\middle\rangle\middle\langle
j\right|^{X_{I}X_{I}^{\prime}}).$ (10)

Here, the set $\\{\left|i\right\rangle\\}$ represents an orthonormal basis in
$X_{I}\otimes X_{I}^{\prime}$ and $d_{X}$ represents the dimension of $X$. If
the map $\mathcal{M}$ is completely positive and trace preserving (CPTP), then
the Choi representation gives an additional constraint

$\operatorname{Tr}_{X_{O}X^{\prime}_{O}}M^{X_{I}X_{I}^{\prime}X_{O}X^{\prime}_{O}}=\mathbb{1}^{X_{I}X_{I}^{\prime}}.$
(11)

A CPTP map (also called _channel_) represents an operation that can be
performed with probability one, while a CP, trace non-increasing map generally
is the conditional transformation corresponding to a particular outcome of a
measurement.

The resource connecting the two communicating parties is described by the
_process matrix_ $W^{A_{I}A_{O}B_{I}B_{O}}$. This encodes the background
process that governs how the systems on which the parties act relate to each
other, be it a shared state, a channel from one to the other, or more general
scenarios. The process matrix $W$ has to satisfy a set of constraints:

$\displaystyle W$ $\displaystyle\geq 0,$ (12)
$\displaystyle\operatorname{Tr}W$ $\displaystyle=d_{A_{O}}d_{B_{O}},$ (13)
${}_{B_{I}B_{O}}W$ $\displaystyle=_{A_{O}B_{I}B_{O}}W,$ (14)
$\displaystyle_{A_{I}A_{O}}W$ $\displaystyle=_{B_{O}A_{I}A_{O}}W,$ (15)
$\displaystyle W$ $\displaystyle=_{A_{O}}W+_{B_{O}}W-_{A_{O}B_{O}}W.$ (16)

Here, ${{}_{x}}W:=\mathbb{1}^{x}/d_{x}\otimes Tr_{x}W$ is the ‘trace-and-
replace’ notation [30], which discards subsystem $x$ and replaces it with the
normalised identity. Here appropriate reordering of the tensor factors is
implied. The concatenation of Alice’s (Bob’s) local operation
$\mathcal{M}^{A}$ and $\mathcal{M}^{B}$ with the process $W$ is given by
$W{*}M^{A}{*}M^{B}$ where $M^{A}$ ($M^{B}$) is the Choi representation of the
map $\mathcal{M}^{A}$ ($\mathcal{M}^{B}$) and ‘*’ is the link product [34]
defined as

$\displaystyle
P*Q:=\operatorname{Tr}_{\mathcal{P}\cap\mathcal{Q}}[(\mathbb{1}^{\mathcal{P}\setminus\mathcal{Q}}\otimes
P^{T_{\mathcal{P}\cap\mathcal{Q}}})(Q\otimes\mathbb{1}^{\mathcal{Q}\setminus\mathcal{P}})].$
(17)

Here, $\mathcal{P}$ and $\mathcal{Q}$ are the Hilbert spaces associated with
$P$ and $Q$, the superscript ‘$T_{\mathcal{P}\cap\mathcal{Q}}$’ represents
partial transpose on the shared Hilbert spaces.

Figure 1:  A process $W^{A_{I}A_{O}B_{I}B_{O}}$ with two CPTP maps
$A^{A^{\prime}_{I}A_{I}A_{O}}$ and $B^{B_{I}B_{O}B^{\prime}_{O}}$ forms a new
channel $\mathcal{N}(\mathcal{A},\mathcal{B},W)$, as in Eq. (18), with input
system $A^{\prime}_{I}$ and the output system $B^{\prime}_{O}$. Alice can use
this channel to communicate to Bob by encoding the quantum state $\rho_{m}$ at
her input system and Bob performing a POVM measurement $E_{m^{\prime}}$ at his
output system.

##  IV One directional communication through an indefinitely ordered process

In this section we introduce our classical communication protocol through an
arbitrary process as shown in Fig. 1. In this protocol, both Alice and Bob can
use some quantum channels $\mathcal{A}$ and $\mathcal{B}$. Alice’s channel
$\mathcal{A}$ has $A^{\prime}_{I}A_{I}$ as input and $A_{O}$ as output, while
Bob’s channel $\mathcal{B}$ has $B_{I}$ as input and $B_{O}B^{\prime}_{O}$ as
output.

The process matrix $W^{A_{I}A_{O}B_{I}B_{O}}$ acting on these channels forms a
new quantum channel $\mathcal{N}(\mathcal{A},\mathcal{B},W)$ with input
quantum system $A^{\prime}_{I}$ and the output quantum system
$B^{\prime}_{O}$, as shown in Fig. 1. The Choi representation of this new
channel is

$\displaystyle N(\mathcal{A},\mathcal{B},$ $\displaystyle
W)^{A^{\prime}_{I}B^{\prime}_{O}}$ $\displaystyle:=$ $\displaystyle
W^{A_{I}A_{O}B_{I}B_{O}}*(A^{A^{\prime}_{I}A_{I}A_{O}}*B^{B_{I}B_{O}B^{\prime}_{O}})$
$\displaystyle=$ $\displaystyle
W^{A_{I}A_{O}B_{I}B_{O}}*\big{(}A^{A^{\prime}_{I}A_{I}A_{O}}\otimes
B^{B_{I}B_{O}B^{\prime}_{O}}\big{)}.$ (18)

Here, $A$ and $B$ are the Choi representations of the quantum channels
$\mathcal{A}$ and $\mathcal{B}$ respectively.

###  A Asymptotic setting

Similar to the conventional classical communication through quantum channels,
we need to introduce a notion of asymptotic setting for process, namely to
formalise the notion of repeated use of independent copies of a process. The
goal turns out to be non-trivial as one can construct different asymptotic
settings by allowing non-product channels across the different copies [35,
36], resulting in non-trivial constraints on the admissible operations and
processes [37, 38]. For example, Alice could feed the output of her first
channel to her second one. This, however, would require extra knowledge about
the causal relations between the different uses of the process and, for a
process with bidirectional signalling, it would be incompatible with Bob
sending his second output to the first input. As we are investigating causal
structures as communication resources, we assume that all available causal
relations are encoded in the process itself, which leads to the asymptotic
setting, first introduced in Ref. [39], where only product operations across
different parties are allowed.

Our choice of asymptotic setting results in a set of independent channels
$\mathcal{N}_{j}=\mathcal{N}(\mathcal{A}_{j},\mathcal{B}_{j},W)$, as shown in
Fig. 4. Here $\mathcal{A}_{j}$, $\mathcal{B}_{j}$ are the local operations
performed by Alice and Bob respectively. Alice encodes her message $m$ in a
quantum state $\rho_{m}^{(n)}{\in}\otimes_{j=1}^{n}A_{I}^{{}^{\prime}j}$ and
sends the state to Bob through the channels $\\{\mathcal{N}_{j}\\}$. After
receiving the transformed state, Bob performs a POVM on his quantum system
$\otimes_{j=1}^{n}B^{{}^{\prime}j}_{O}$. With this, we conceptualise a
protocol for one way communication from Alice to Bob ($A{\rightarrow}{B}$) in
the following way:

######  Definition 1.

Given a bipartite processes matrix $W^{AB}$, we define an _$A{\rightarrow}B$
protocol with $n$ uses of $W$_ as

  1. 1.

A set of local operations $\\{\mathcal{A}_{j},\mathcal{B}_{j}\\}_{j=1}^{n}$,
where

$\displaystyle\mathcal{A}_{j}$ $\displaystyle:A^{{}^{\prime}j}_{I}\otimes
A^{j}_{I}{\rightarrow}A^{j}_{O},$ $\displaystyle\mathcal{B}_{j}$
$\displaystyle:B^{j}_{I}\rightarrow B^{j}_{O}\otimes B^{{}^{\prime}j}_{O}$

are CPTP maps;

  2. 2.

A state encoding
$m\mapsto\rho^{(n)}_{m}\in\bigotimes_{j=1}^{n}A^{{}^{\prime}j}_{I}$, where
$\rho^{(n)}_{m}\geq 0$ and $\operatorname{Tr}\rho^{(n)}_{m}=1$;

  3. 3.

A decoding POVM $\\{E^{(n)}_{m^{\prime}}\\}_{m^{\prime}}$, where
$E^{(n)}_{m^{\prime}}\geq 0$ and
$\sum_{m^{\prime}}E^{(n)}_{m^{\prime}}=\mathbb{1}$.

Such a protocol produces a classical channel described by the conditional
probabilities

$P(m^{\prime}|m)=\operatorname{Tr}\left[E^{(n)}_{m^{\prime}}\bigotimes_{j=1}^{n}\mathcal{N}_{j}\big{(}\rho^{(n)}_{m}\big{)}\right].$
(19)

We say that two protocols for the same process $W$ are _equivalent_ if they
produce the same conditional probabilities $P(m^{\prime}|m)$.

In general, the ancillary spaces $A^{{}^{\prime}j}_{I}$,
$B^{{}^{\prime}j}_{O}$ need not be isomorphic for different $j$. However, we
can always embed each of them into a space isomorphic to one of the highest
dimension. In the following, we assume that all spaces are of equal dimension
and are identified through a choice of canonical basis.

Note this specific arrangement of channels results in a non-stationary
asymptotic setting. Formulating communication capacity of such a setup poses a
non-trivial challenge [40, 41]. To alleviate this issue, we employ a scheme to
make the channels stationary. Specifically, we replace the local operations
$\\{\mathcal{A}_{j}\\}$ and $\\{\mathcal{B}_{j}\\}$ with fixed local
operations $\\{{\mathcal{A}}\\}$ and $\\{{\mathcal{B}}\\}$ respectively with
support of additional local CPTP maps $\mathcal{E}_{j}$ and $\mathcal{F}_{j}$,
where $\mathcal{A}_{j}{=}{\mathcal{A}}{*}\mathcal{E}_{j}$ and
$\mathcal{B}_{j}{=}\mathcal{F}_{j}{*}{\mathcal{B}}$. Thus we have multiple
independent and identical copies of the channel
${\mathcal{N}}{=}\mathcal{N}({\mathcal{A}},{\mathcal{B}},W)$. Feasibility of
this approach is due to the fact that, in an $A\rightarrow B$ protocol, Bob’s
output can be discarded, i.e., in such a protocol a process matrix $W$ can be
replaced by ${}_{B_{O}}W$, as shown in Fig. 2 and in Refs. [8, 42, 7, 43]. As
we are going to use this fact multiple times, we formulate it as a lemma and
prove it below for completeness:

######  Lemma 1.

If Alice has trivial ancillary output, $\mathcal{A}:A^{\prime}_{I}\otimes
A_{I}\rightarrow A_{O}$, we can replace $W$ with ${}_{B_{O}}W$:

$\mathcal{N}(\mathcal{A},\mathcal{B},W)=\mathcal{N}(\mathcal{A},\mathcal{B},{}_{B_{O}}W).$
(20)

###### Proof.

It is sufficient to show $A{*}W=A{*}{}_{B_{O}}W$. Using condition (16), we can
write $A{*}W=A{*}{}_{A_{O}}W+A{*}{}_{B_{O}}W-A{*}{}_{A_{O}B_{O}}W$. As the
second and third terms are already in the desired form, we only need to look
at the first term:

$A{*}{}_{A_{O}}W=\operatorname{Tr}_{A_{I}A_{O}}\left[A^{A^{\prime}_{I}A_{I}A_{O}}\cdot\left(\frac{\mathbb{1}^{A_{O}}}{d^{A}_{O}}\otimes\operatorname{Tr}_{A_{O}}W\right)\right]\\\
=\frac{1}{d^{A}_{O}}\operatorname{Tr}_{A_{I}}\left[\left(\operatorname{Tr}_{A_{O}}A^{A^{\prime}_{I}A_{I}A_{O}}\right)\cdot\left(\operatorname{Tr}_{A_{O}}W\right)\right]\\\
=\frac{1}{d^{A}_{O}}\operatorname{Tr}_{A_{I}}\left[\mathbb{1}^{A^{\prime}_{I}A_{I}}\cdot\left(\operatorname{Tr}_{A_{O}}W\right)\right]\\\
=\frac{\mathbb{1}^{A^{\prime}_{I}}}{d^{A}_{O}}\otimes\operatorname{Tr}_{A_{I}A_{O}}W=\frac{\mathbb{1}^{A^{\prime}_{I}}}{d^{A}_{O}}\otimes\operatorname{Tr}_{A_{I}A_{O}}\left({}_{B_{O}}W\right),$
(21)

where we used
$\operatorname{Tr}_{A_{O}}A^{A^{\prime}_{I}A_{I}A_{O}}=\mathbb{1}^{A^{\prime}_{I}A_{I}}$
(because $A^{A^{\prime}_{I}A_{I}A_{O}}$ is CPTP) in the third line and Eq.
(15) in the last line. ∎

This lemma allows us to replace Bob’s operation $\mathcal{B}_{j}$ by
$\sigma^{B_{O}}\otimes\big{(}\operatorname{Tr}_{B_{O}}\mathcal{B}_{j}\big{)}^{B_{I}B^{\prime}_{O}}$,
with $\sigma^{B_{O}}$ being an arbitrary state. For the encoding operation
$\mathcal{A}_{j}$, on the other hand, we extend the input system to make it a
controlled operation while treating the control state as Alice’s extended
encoded message. Thus we present the following theorem.

Figure 2: Pictorial depiction of Lemma 1. A one way communication from Alice
to Bob through a channel $\mathcal{N}(\mathcal{A},\mathcal{B},W)$ simplifies
to a channel $\mathcal{N}(\mathcal{A},\mathcal{B},_{B_{O}}W)$. The rightmost
picture shows further simplification to a quantum state
$\Gamma(\mathcal{A}_{m},W)$ with the system $B_{O}$ being discarded, as in Eq.
(39).

######  Theorem 1.

Every $A\rightarrow B$ protocol is equivalent to one with fixed local
operations

$\displaystyle\bar{\mathcal{A}}$
$\displaystyle:A^{{}^{\prime\prime}j}_{I}\otimes A^{j}_{I}\rightarrow
A^{j}_{O},$ (22) $\displaystyle\bar{\mathcal{B}}$
$\displaystyle:B^{j}_{I}\rightarrow B^{j}_{O}\otimes
B^{{}^{\prime\prime}j}_{O},$ (23)

state encoding

$\bar{\rho}^{(n)}_{m}=\bigotimes_{j=1}^{n}\mathcal{E}_{j}\left(\rho^{(n)}_{m}\right),$
(24)

and decoding POVM

$\bar{E}^{(n)}_{m^{\prime}}=\bigotimes_{j=1}^{n}\mathcal{F}_{j}^{{\dagger}}(E^{(n)}_{m^{\prime}}),$
(25)

where
$\mathcal{E}_{j}{:}A^{{}^{\prime}j}_{I}{\rightarrow}A^{{}^{\prime\prime}j}_{I}$,
$\mathcal{F}_{j}{:}B^{{}^{\prime}j}_{O}{\rightarrow}B^{{}^{\prime\prime}j}_{O}$
are CPTP and $\mathcal{F}^{{\dagger}}$ denotes the Hilbert-Schimdt adjoint,
defined through
$\operatorname{Tr}\left[A^{{\dagger}}\mathcal{F}(B)\right]=\operatorname{Tr}\left[\mathcal{F}^{{\dagger}}\left(A^{{\dagger}}\right)B\right]$.

###### Proof.

(See Fig. 3 for a pictorial representation of the proof.) Let us start with
the decoding. Since Alice only performs CPTP maps with no ancillary output, we
can apply Lemma 1 and replace the process matrix $W$ with ${}_{B_{O}}W$, which
is equal to identity on $B_{O}$. This implies that any $A\rightarrow B$
protocol is equivalent to one where we replace the local operations
$\mathcal{B}_{j}$ with
${\sigma}^{B^{j}_{O}}\otimes\operatorname{Tr}_{B^{j}_{O}}\mathcal{B}_{j}$ for
some arbitrary state $\sigma$. Choosing the space $B^{{}^{\prime\prime}j}_{O}$
isomorphic to $B^{j}_{I}$, we see that the original combination of local
operations $\mathcal{B}_{j}$ and decoding POVM is equivalent to performing the
fixed operation
$\bar{\mathcal{B}}={\sigma}^{B^{j}_{O}}\otimes\mathcal{I}^{B^{j}_{I}\rightarrow
B^{{}^{\prime\prime}j}_{O}}$ in each lab, and decoding POVM as in Eq. (25),
with
$\mathcal{F}_{j}=(\operatorname{Tr}_{B^{j}_{O}}\mathcal{B}_{j}\circ\mathcal{I}^{B^{j}_{I}\rightarrow
B^{{}^{\prime\prime}j}_{O}})^{B^{{}^{\prime}j}_{O}}$.

Now for the encoding side: we set
$A^{{}^{\prime\prime}j}_{I}=\mathcal{L}\left(\mathbb{C}^{n}_{j}\right)\otimes
A^{{}^{\prime}j}_{I}$ and define the controlled operation
$\bar{\mathcal{A}}:\mathcal{L}\left(\mathbb{C}^{n}_{j}\right)\otimes
A^{{}^{\prime}j}_{I}\rightarrow A^{j}_{O}$ as

$\bar{\mathcal{A}}\left(\sigma\otimes\rho\right)=\sum_{j=1}^{n}\left\langle
j\right|\sigma\left|j\right\rangle\mathcal{A}_{j}\left(\rho\right)^{A^{j}_{O}},$
(26)

which is manifestly CPTP. For canonical basis states in
$\mathcal{L}\left(\mathbb{C}^{n}_{j}\right)$, this map gives

$\bar{\mathcal{A}}\left(\left|j\middle\rangle\middle\langle
j\right|\otimes\rho\right)=\mathcal{A}_{j}\left(\rho\right),$ (27)

so the choice of local operation can be encoded into a choice of initial
state, expanding the original encoding state as in Eq. (24), with the maps
$\mathcal{E}_{j}:A^{{}^{\prime}j}_{O}\rightarrow A^{{}^{\prime\prime}j}_{O}$
defined as

$\mathcal{E}_{j}\left(\rho^{A^{{}^{\prime}j}_{I}}\right)=\big{(}\left|j\middle\rangle\middle\langle
j\right|\otimes\rho\big{)}^{A^{{}^{\prime\prime}j}_{I}}.$ (28)

∎

The relevance of this theorem is twofold. First, it shows that any protocol
involving a different choice of local operations can be reproduced by fixing
the local operations once and for all. This means that an asymptotic setting
for processes can always be mapped to an asymptotic setting were the same
channel is used $n$ times,
$\mathcal{N}(\bar{\mathcal{A}},\bar{\mathcal{B}},W)^{\otimes n}$. We call a
protocol of this type _stationary_. Second, state encoding and decoding POVM
of an arbitrary protocol transform into those of a stationary one through
product maps, Eqs. (24) and (25). This means that the transformation preserves
the nature of the asymptotic setting, viz. joint/product encoding or decoding.
From now on, we will represent $\bar{\mathcal{A}}$, $\bar{\mathcal{B}}$,
$\bar{\rho}_{m}^{(n)}$ and $\bar{E}_{m^{\prime}}^{(n)}$ without the bar on
top.

Figure 3: Pictorial depiction of Theorem 1. We convert a non-stationary
channel $\mathcal{N}(\mathcal{A}_{j},\mathcal{B}_{j},W)$ to a stationary
channel $\mathcal{N}(\bar{\mathcal{A}},\bar{\mathcal{B}},W)$. Due to Lemma 1,
Bob’s system $B_{O}$ can be set to a fixed state $\sigma$ and corresponding
operation
$\bar{\mathcal{B}}={\sigma}^{B^{j}_{O}}\otimes\mathcal{I}^{B^{j}_{I}\rightarrow
B^{{}^{\prime\prime}j}_{O}}$. Alice’s operation, on the other hand, can be
extended to a controlled CPTP map $\bar{\mathcal{A}}$ as described in Eq.
(27).

###  B Classical capacities of a quantum process

_Holevo quantity for a process:_ Having introduced a stationary protocol with
an asymptotic setting of the channel
$\mathcal{N}({\mathcal{A}},{\mathcal{B}},W)$, as shown in Theorem 1, we can
define the corresponding Holevo quantity for a process $W$ as

$\displaystyle\chi(W)^{A\rightarrow{B}}:=\underset{\mathcal{A},\mathcal{B}}{{\mathrm{max}}}\
{\chi}\left[{\mathcal{N}(\mathcal{A},\mathcal{B},W)}\right].$ (29)

We also introduce the $n$-th extension $\chi(W^{\otimes n})^{A\rightarrow{B}}$
of the above quantity as

$\displaystyle\chi(W^{\otimes
n})^{A\rightarrow{B}}:=\underset{\mathcal{A},\mathcal{B}}{{\mathrm{max}}}\
{\chi}\left[{\mathcal{N}(\mathcal{A},\mathcal{B},W)^{\otimes n}}\right].$ (30)

_Communication capacity for a process:_ We can associate different
communication capacities to an arbitrary process as

$\displaystyle
C^{\sharp}(W)^{A\rightarrow{B}}=\max_{\mathcal{A},\mathcal{B}}C^{\sharp}\left(\mathcal{N}(\mathcal{A},\mathcal{B},W)\right).$
(31)

Where $C^{\sharp}=C^{(1)},C,C^{\textrm{E}}$. Here
$C^{(1)}(W)^{A\rightarrow{B}}$ represents product encoding-product decoding
capacity, as in Eq. (4), $C(W)^{A\rightarrow{B}}$ represents product encoding-
joint decoding capacity, as in Eq. (6) and finally,
$C^{E}(W)^{A\rightarrow{B}}$ represents joint encoding-joint decoding
capacity, as in Eq. (8).

We can relate the Holevo quantity for a process to different
$C^{\sharp}(W)^{A\rightarrow{B}}$ capacities. We show this in the following
lemma.

######  Lemma 2.

Different capacities associated with an arbitrary process $W$ are related to
the Holevo quantity $\chi(W)^{A\rightarrow{B}}$ in the following way.

product encoding-product decoding:

$\displaystyle C^{(1)}(W)^{A\rightarrow{B}}\leq\chi(W)^{A\rightarrow{B}}.$
(32)

product encoding-joint decoding:

$\displaystyle C(W)^{A\rightarrow{B}}=\chi(W)^{A\rightarrow{B}}.$ (33)

Joint encoding-joint decoding:

$\displaystyle
C^{E}(W)^{A\rightarrow{B}}=\lim_{n\rightarrow{\infty}}\frac{\chi(W^{\otimes
n})}{n}.$ (34)

###### Proof.

product encoding-product decoding:

Using Eqs. (31), (5) and (29), we can write

$\displaystyle C^{(1)}(W)^{A\rightarrow{B}}$
$\displaystyle=\max_{{\mathcal{A}},{\mathcal{B}}}C^{(1)}(\mathcal{N}({\mathcal{A}},{\mathcal{B}},W))$
$\displaystyle\leq\max_{{\mathcal{A}},{\mathcal{B}}}\chi(\mathcal{N}({\mathcal{A}},{\mathcal{B}},W))$
$\displaystyle=\chi(W)^{A\rightarrow{B}}.$ (35)

product encoding-joint decoding:

Using Eqs. (31), (6) and (29) we can write

$\displaystyle C(W)^{A\rightarrow{B}}$
$\displaystyle=\max_{{\mathcal{A}},{\mathcal{B}}}C(\mathcal{N}({\mathcal{A}},{\mathcal{B}},W))$
$\displaystyle=\max_{{\mathcal{A}},{\mathcal{B}}}\chi(\mathcal{N}({\mathcal{A}},{\mathcal{B}},W))$
$\displaystyle=\chi(W)^{A\rightarrow{B}}.$ (36)

Joint encoding-joint decoding:

Using Eqs. (31), (7), (8) and (30) we can write

$\displaystyle C^{E}(W)^{A\rightarrow{B}}$
$\displaystyle=\max_{{\mathcal{A}},{\mathcal{B}}}C^{E}(\mathcal{N}({\mathcal{A}},{\mathcal{B}},W))$
$\displaystyle=\max_{{\mathcal{A}},{\mathcal{B}}}\chi_{\mathrm{reg}}(\mathcal{N}({\mathcal{A}},{\mathcal{B}},W))$
$\displaystyle=\max_{{\mathcal{A}},{\mathcal{B}}}\lim_{n\rightarrow{\infty}}\frac{\chi\left[\mathcal{N}({\mathcal{A}},{\mathcal{B}},W)^{\otimes
n}\right]}{n}$
$\displaystyle=\lim_{n\rightarrow{\infty}}\frac{\chi(W^{\otimes{n}})}{n}.$
(37)

∎

###  C Bounds on the classical capacities of a quantum process

Although we have been able to reduce the classical capacities of processes to
that of channels, our results so far do not provide an upper bound on how much
information can be transmitted through a process. This is because the channel
$\mathcal{N}(\mathcal{A},\mathcal{B},W)$ can have arbitrary input and output
dimension.

To establish a bound, we first describe our protocol from a slightly different
point of view. With Alice’s input ensemble $\\{p(m),{\rho_{m}}\\}$, we can
introduce a concatenation of ${\rho_{m}}$ with the channel ${\mathcal{A}}$ as
${A}_{m}^{A_{I}A_{O}}={\rho}_{m}^{A^{\prime\prime}_{I}}*{A}^{A^{\prime\prime}_{I}A_{I}A_{O}}$
with ${A}_{m}$ being the Choi representation of the resulting CPTP map
${\mathcal{A}}_{m}$. Similarly, we can combine Bob’s channel ${\mathcal{B}}$
and POVM operation ${\\{E_{m}\\}}$ to describe a set of CP maps
$\\{{B}_{m^{\prime}}^{B_{I}B_{O}}=B^{B_{I}B_{O}B^{\prime\prime}_{O}}*({E}_{m^{\prime}}^{T})^{B^{\prime\prime}_{O}}\\}_{m^{\prime}}$,
where $\sum_{m^{\prime}}{B}_{m^{\prime}}^{B_{I}B_{O}}$ is a CPTP map and
$({E}_{m^{\prime}}^{T})^{B^{\prime\prime}_{O}}$ is the Choi representation of
${E}_{m^{\prime}}$. The superscript ‘$T$’, denoting the transpose operator, is
due to definition (10), according to which the Choi of a measurement operator
${E}_{m^{\prime}}$ is its transpose ${E}_{m^{\prime}}^{T}$.

With this in mind, we present two theorems, that apply respectively to the
product and joint encoding scenarios.

Figure 4: Encoding and decoding schemes. Here we show two copies of process
$W$. Fig. (a), (b), (c) demonstrate product-encoding product decoding, product
encoding joint decoding and joint encoding-joint decoding respectively.
Product encoding is achieved using the joint state
$\rho_{m}^{(1)}{\otimes}\rho_{m}^{{}^{\prime}(1)}$ and joint encoding is
achieved using the entangled state $\rho_{m}^{(2)}$. Similarly, we use
$E_{m^{\prime}}^{(1)}{\otimes}E_{m^{\prime}}^{{}^{\prime}(1)}$ for product
decoding and $E_{m^{\prime}}^{(2)}$ for joint decoding. Figs. (d), (e), (f)
are the simplifications due to Theorem 1 and Theorem 2. Relevant labelling of
the Hilbert spaces are described in the text.

######  Theorem 2.

In a one-way communication scenario, the optimisation of the Holevo quantity
of a process $W$ can be simplified as

$\displaystyle\chi(W)^{A\rightarrow{B}}=\underset{{\rho}_{m},{\mathcal{A}},p(m)}{{\mathrm{max}}}\
$ $\displaystyle S\left[\sum p(m){\Gamma}({A}_{m},W)\right]-$
$\displaystyle\sum p(m)S\left[{\Gamma}({A}_{m},W)\right].$ (38)

Here the $\Gamma(.)$ is a map that transforms the Choi representation of the
CPTP operation ${\mathcal{A}}_{m}$ and the process matrix $W$, to a quantum
state on Bob’s input space $B_{I}$.

###### Proof.

The reduced process [30] on which Bob applies his CPTP map
${B}_{m^{\prime}}^{B_{I}B_{O}}$ is described by
${A}_{m}^{A_{I}A_{O}}*W^{A_{I}A_{O}B_{I}B_{O}}$. Now, using Lemma 1, we can
write

$\displaystyle{A}_{m}^{A_{I}A_{O}}{*}W^{A_{I}A_{O}B_{I}B_{O}}$
$\displaystyle{=}\mathbb{1}^{B_{O}}{\otimes}\left({A}_{m}^{A_{I}A_{O}}{*}\frac{\operatorname{Tr}_{B_{O}}W}{d_{B_{O}}}^{A_{I}A_{O}B_{I}}\right)$
$\displaystyle=\mathbb{1}^{B_{O}}{\otimes}{\Gamma}({A}_{m},W)^{B_{I}}.$ (39)

Where ${\Gamma}({A}_{m},W){:=}{A}_{m}{*}\operatorname{Tr}_{B_{O}}W/d_{B_{O}}$.
In other words, as shown in Fig. 2, we can simplify Alice’s CPTP map and the
process to a quantum state ${\Gamma}({A}_{m},W)$ in the Hilbert space $B_{I}$,
with Bob’s output at $B_{O}$ being discarded. The maximum classical
information that can be encoded in the ensemble
$\\{p(m),{\Gamma}({A}_{m},W)\\}$ is given by Eq. (38) [3] where we only need
to optimise over the free parameters $p(m)$, ${\rho}_{m}$ and ${\mathcal{A}}$.

This implies one does not need to optimise over Bob’s operation to obtain the
Holevo quantity for the process. ∎

A direct consequence of this theorem is that
$\chi(W)^{A\rightarrow{B}}\leq\log(d_{B_{I}})$, because we have reduced the
Holevo quantity of a process to that of an ensemble of states in $B_{I}$. In
turn, this allows us to establish a bound on the product encoding capacities,
i.e., $C^{(1)}(W)^{A\rightarrow{B}}$ and $C(W)^{A\rightarrow{B}}$, according
to Eq. (35) and Eq. (36), respectively. However, for joint encoding schemes we
need to evaluate the regularised Holevo quantity for the optimum channel
$\mathcal{N}({\mathcal{A}},{\mathcal{B}},W)$, as shown in Eq. (34). In ligth
of this, we introduce the following theorem that bounds the capacity,
$C^{E}(W)^{A\rightarrow{B}}$.

######  Theorem 3.

The joint encoding capacity for a process, $C^{E}(W)^{A\rightarrow{B}}$, is
limited to Alice’s joint CPTP map
${\mathcal{A}}_{m}^{(n)}{=}{\rho}_{m}^{(n)}{*}{\mathcal{A}}^{\otimes n}$ with
$n\rightarrow{\infty}$, and the distribution $p(m)$.

$\displaystyle C^{E}(W)^{A\rightarrow{B}}$ $\displaystyle{=}$
$\displaystyle\lim_{n\rightarrow{\infty}}\underset{{\rho}_{m}^{(n)},{\mathcal{A}},p(m)}{{\mathrm{max}}}\
\frac{1}{n}$ $\displaystyle\bigg{(}S\left[\sum
p(m){\Gamma}({\mathcal{A}}_{m}^{(n)},W)\right]-$ $\displaystyle\sum
p(m)S\left[{\Gamma}({\mathcal{A}}_{m}^{(n)},W)\right]\bigg{)}.$ (40)

Here the map $\Gamma$ transforms the joint CPTP map $A_{m}^{(n)}$ and the
process $W$ to an entangled state at Bob’s input space
$\otimes_{j=1}^{n}B_{I}^{j}$.

###### Proof.

First, we apply Lemma 1 to each copy of the channel
$\mathcal{N}(\mathcal{A},\mathcal{B},W)$ and replace it with
$\mathcal{N}(\mathcal{A},\mathcal{B},\,_{B^{j}_{O}}W)$. Then, in a joint
encoding scheme, we apply
$\otimes_{j}\mathcal{N}(\mathcal{A},\mathcal{B},\,_{B^{j}_{O}}W)$ to a
(possibly entangled) joint state ${\rho}_{m}^{(n)}$. Combining this joint
state with the $n$ copies of Alice’s operation $\mathcal{A}$, we obtain a
joint CPTP map
$\mathcal{A}^{(n)}_{m}:{\otimes}_{j}A^{j}_{I}\rightarrow{\otimes}_{j}A^{j}_{O}$,
with Choi representation $A^{(n)}_{m}=\rho_{m}^{(n)}{*}A^{\otimes n}$.
Plugging $A^{(n)}_{m}$ into the $n$ copies ${}_{B^{j}_{O}}W$, we get
$A^{(n)}_{m}{*}\left({\otimes_{j}}_{B^{j}_{O}}W\right)=\mathbb{1}^{\otimes_{j=1}^{n}B_{O}^{j}}\otimes{\Gamma}({\mathcal{A}}_{m}^{(n)},W)$,
where ${\Gamma}({\mathcal{A}}_{m}^{(n)},W)$ ${\in}\otimes_{j=1}^{n}B_{I}^{j}$
is a (possibly entangled) state, defined as

$\displaystyle{\Gamma}({\mathcal{A}}_{m}^{(n)},W)=\frac{{A}_{m}^{(n)}*\big{(}\operatorname{Tr}_{\otimes_{j=1}^{n}B_{O}^{j}}W^{\otimes{n}}\big{)}}{\Pi_{j=1}^{n}d_{B_{O}^{j}}}.$
(41)

One can extend this setup to $n{\rightarrow}{\infty}$ and achieve a joint
state at Bob’s input Hilbert space $\otimes_{j=1}^{\infty}B_{I}^{j}$. Similar
to Theorem 2, we calculate the maximum amount of classical information encoded
in the ensemble $\\{p(m),{\Gamma}({\mathcal{A}}_{m}^{(n)},W)\\}$ and
regularise it to obtain the joint encoding capacity
$C^{E}(W)^{A\rightarrow{B}}$ where the free parameters are of course, $p(m)$,
${\rho}_{m}^{(n)}$ and ${\mathcal{A}}$. Thus we obtain Eq. (40). ∎

######  Corollary 3.1.

The capacity $C^{E}(W)^{A\rightarrow{B}}$ is upper bounded by the logarithm of
the dimension of Bob’s input Hilbert space, i.e.
$C^{E}(W)^{A\rightarrow{B}}\leq\log(d_{B_{I}})$.

###### Proof.

This is the consequence of Holevo’s theorem [3]. The information content of
the ensemble $\\{p(m),\Gamma({A}_{m}^{(n)},W)\\}$ cannot exceed logarithm of
the dimension of $\Gamma({A}_{m}^{(n)},W)$, i.e., $n\log(d_{B_{I}})$.
Regularising this quantity proves the corollary. ∎

Now we summarise our results. If we consider Alice’s input message $m$ and
Bob’s output message $m^{\prime}$, we can introduce a chain of inequalities
for different classical capacities of the process $W$.

$\displaystyle I(m^{\prime}:m)$ $\displaystyle\leq
C^{(1)}(W)^{A\rightarrow{B}}\leq
C(W)^{A\rightarrow{B}}=\chi(W)^{A\rightarrow{B}}$ $\displaystyle\leq
C^{E}(W)^{A\rightarrow{B}}\leq\log(d_{B_{I}}).$ (42)

One can write down a similar chain of inequalities for a communication
protocol from Bob to Alice. Note that this inequality holds even for a process
$W$ that contains shared entanglement between Alice’s and Bob’s input Hilbert
spaces. This does not contradict the higher capacity achievable in an
entanglement assisted communication protocol, such as super-dense coding [44],
because, when applying the inequalities in Eq. (42), one has to consider the
total dimension of Bob’s input Hilbert space, which consists of the part of
the shared entangled state in Bob’s possession and the quantum state that
Alice communicates to him.

##  V Broadcast communication

Having established the notion of one-way communication through a process, we
proceed to explore scenarios where all communicating parties can transmit and
receive information.

_Two-party communication:_ Let us first consider the two party situation,
where Alice (Bob) sends the message $m(k)$ and Bob (Alice) receives the
message $m^{\prime}(k^{\prime})$. The possibility to violate causal
inequalities indicates that indefinite causal order can indeed provide an
advantage in some two party games [8, 45]; however, it is unclear if this
advantage results in a communication enhancement. To address this question, it
is necessary to find limits on two-way communication for causally separable
processes. In this section we address this question.

There are at least two ways a process can be used as a resource for
bidirectional communication, depending on whether Alice’s and Bob’s
instruments are fixed or if they are chosen depending on the direction of
communication attempted. In the first case, the parties produce a single
probability distribution $P(m^{\prime},k^{\prime}|m,k)$ from the process, and
one looks for communication in the marginals $P(m^{\prime}|m)$,
$P(k^{\prime}|k)$. In the second case, the parties can generate different
probability distributions depending on who is sending and who is receiving.
The one-directional capacities for the first case are upper bounded by those
in the second case, as the best instrument to receive a message might differ
from the best to send a message. In this section, we will be mostly concerned
with the second case.

Let us then consider a scenario where the order between Alice’s and Bob’s
local operations is determined based on a random outcome. We represent a
process where Alice can signal to Bob, but not the other way around, by
$W^{A\prec B}=\,_{B_{O}}W^{A\prec B}$ and the reversed direction of signalling
by $W^{B\prec A}{=}\,_{A_{O}}W^{B\prec A}$. The process matrix
$W_{\mathrm{Sep}}$ in this case is a convex combination of $W^{B\prec A}$ and
$W^{A\prec B}$ [30]:

$\displaystyle W_{\mathrm{sep}}=\lambda W^{B\prec A}+(1-\lambda)W^{A\prec B},$
(43)

where $0\leq\lambda\leq 1$ is the probability for Bob to be first. We call
such a process a _causally separable process_ [8]. We investigate a scenario
where both Alice and Bob are trying to send information to each other through
the background process $W_{\mathrm{Sep}}$. A reasonable attempt to quantify
this bi-directional communication is to evaluate the sum of two one-shot
capacities, $C^{(1)}(W)^{A\rightarrow{B}}$ and $C^{(1)}(W)^{B\rightarrow{A}}$.
We investigate this quantity and evaluate an operationally significant upper
bound from the perspective of the classical capacity of the process.

######  Theorem 4.

For a bi-directional communication protocol through a causally separable
process, defined in Eq. (43), the following inequality holds:

$\displaystyle
C^{(1)}(W_{\mathrm{sep}})^{A{\rightarrow}{B}}{+}C^{(1)}(W_{\mathrm{sep}})^{B{\rightarrow}{A}}$
$\displaystyle{\leq}\lambda\log{(d_{A_{I}})}{+}(1{-}\lambda)\log{(d_{B_{I}})}.$
(44)

###### Proof.

Considering a fixed input probability distribution $P(a)$, the following
linear relationship among marginal conditional probabilities holds for a
causally separable process [8].

$\displaystyle P(a^{\prime}|a)_{W_{\mathrm{sep}}}$ $\displaystyle=\lambda
P(a^{\prime}|a)_{W^{B\prec A}}+(1-\lambda)P(a^{\prime}|a)_{W^{A\prec B}}.$
(45)

With $a{\in}\\{m,k\\}$ and $a^{\prime}{\in}\\{m^{\prime},k^{\prime}\\}$. Let
us consider $A{\rightarrow}{B}$ communication. Consequently we can write:

$\displaystyle C^{(1)}(W_{Sep})^{A\rightarrow{B}}=\max I(m^{\prime}:m)$
$\displaystyle\leq\max\left[\lambda I(m^{\prime}{:}m)_{W^{B\prec
A}}+(1-\lambda)I(m^{\prime}{:}m)_{W^{A\prec B}}\right]$
$\displaystyle=(1-\lambda)\max I(m^{\prime}{:}m)_{W^{A\prec B}}$
$\displaystyle{\leq}(1-\lambda)\log(d_{B_{I}}).$ (46)

Here, the first equation is due to Eqs. (4), and (31). The maximisation is
taken over Alice’s and Bob’s local operations, their message ensembles and the
POVM operations. The first inequality is due to the fact that mutual
information $I(a^{\prime}{:}a)$ is a convex function of $p(a^{\prime}|a)$ for
a fixed input probability distribution $p(a)$ [46]. We obtain the second
equality because, for a definite ordered scenario $B\prec A$, output
$m^{\prime}$ of Bob’s local lab becomes independent of Alice’s input. This
makes $I(m{:}m^{\prime})_{W^{B\prec A}}=0$. The final inequality is due to Eq.
(42). We apply a similar set of reasoning to obtain a bound for
$B\rightarrow{A}$ communication to obtain,

$\displaystyle C^{(1)}(W_{Sep})^{B\rightarrow{A}}\leq\lambda\log(d_{A_{I}}).$
(47)

Adding Eq. (46) and (47), we find

$\displaystyle C^{(1)}(W_{\mathrm{sep}})^{A{\rightarrow}{B}}$
$\displaystyle{+}C^{(1)}(W_{\mathrm{sep}})^{B{\rightarrow}{A}}$
$\displaystyle\leq\lambda\log(d_{A_{I}})+(1-\lambda)\log(d_{B_{I}}).$ (48)

∎

For the particular case $d_{A_{I}}{=}d_{B_{I}}{=}d$, we see that the sum of
two one-shot capacities is upper bounded by $\log(d)$. In other words, the
total communication in causally separable processes can be no more than
maximal one-way communication. We note that a weaker version of this
inequality holds for the scenario where the parties’ instruments are fixed
regardless of the attempted direction of communication. In this case, the
single-shot capacities coincide with the mutual information obtained from a
single conditional probability distribution $P(m^{\prime},k^{\prime}|m,k)$,
resulting in the inequality
$I(m^{\prime}{:}m)+I(k^{\prime}{:}k){\leq}\log(d)$. This is an example of an
_entropic causal inequality_ , first considered in Ref. [47]. Remarkably, no
violation of this inequality is known, and our own numerical search also did
not reveal any violation of Eq. (44). This suggests that the bound on the
total bidirectional communication might hold for general processes.

We note that the bound we established applies to all the quantum processes for
which a physical interpretation is known. For example, in a process with
coherent control of causal order, such as the quantum switch [48], tracing out
the control leads to a separable bipartite process, to which the bound
applies. More generally, it has been shown that any bipartite processes that
admit a unitary extension is causally separable [49, 50].

_Multi-party communication:_ The above-mentioned protocol can be extended to
multiple parties. In that case, each party tries to communicate his/her
information to the remaining parties. Similarly to above, we consider a
process for $N$ parties, $A^{(1)},A^{(2)},...,A^{(N)}$ that can be written as
a probabilistic mixture of permutations of different causal order:

$\displaystyle W^{N}_{\mathrm{sep}}=\sum_{\sigma}{q_{\sigma}}W^{\sigma}.$ (49)

Here, $\sigma$ denotes the different permutations of the communicating parties
and $q_{\sigma}$ denotes the probability of occurrence of each permutation.
Although this is not the most general process with definite causal order [31,
51], it is one of particular interest, as it represents a scenario where the
order among parties can be set by external, random, variables, but is
independent of the parties’ actions.

Motivated by the previous section, we intend to find an upper bound to the
quantity $\sum_{i,j}C^{(1)}(W^{N}_{\mathrm{sep}})^{i{\rightarrow}{j}}$. Here
$i{\rightarrow}{j}$ refers to signalling from the party $A^{(i)}$ to the party
$A^{(j)}$.

######  Theorem 5.

If dimensions of all the input Hilbert spaces of the communicating parties are
equal ($d$), then

$\displaystyle\sum_{i,j}C^{(1)}(W^{N}_{\mathrm{sep}})^{i{\rightarrow}{j}}{\leq}\frac{N(N-1)}{2}\log(d).$
(50)

###### Proof.

we can write the conditional probability
$P(\vec{m}^{\prime}|\vec{m})=\sum_{\sigma}{q_{\sigma}P_{\sigma}(\vec{m}^{\prime}|\vec{m})}$.
We can write down the marginals
$P(m^{\prime}_{j}|m_{i})=\sum_{\sigma}{q_{\sigma}P_{\sigma}(m^{\prime}_{j}|m_{i})}$
$\forall{i,j}$. By the convexity of mutual information and the inequalities
introduced in Eq. (42):

$\displaystyle
C^{(1)}(W^{N}_{\mathrm{sep}})^{i{\rightarrow}{j}}\leq\mathrm{max}$
$\displaystyle\sum_{\sigma}{q_{\sigma}I_{\sigma}(m^{\prime}_{j}:m_{i})}$
$\displaystyle=\mathrm{max}$
$\displaystyle\sum_{\forall{\\{i,j\\}}\,{|}\,\sigma(i)\prec\sigma(j)}{q_{\sigma}I_{\sigma}(m^{\prime}_{j}:m_{i})}$
$\displaystyle\leq$
$\displaystyle\sum_{\forall{\\{i,j\\}}\,{|}\,\sigma(i)\prec\sigma(j)}{q_{\sigma}\log(d_{A^{j}_{I}})}$
$\displaystyle=$
$\displaystyle\sum_{\forall{\\{i,j\\}}\,{|}\,\sigma(i)\prec\sigma(j)}{q_{\sigma}\log(d)}$
(51)

The maximisation is taken over all communicating parties’ local operations,
their message ensembles and the POVM operations. The first inequality is due
to the convexity of mutual information relative to mixtures of conditional
probabilities (as in the bipartite case). The first equality follows from the
fact that if the party $\sigma(j)$ is in the causal past of the party
$\sigma(i)$, then $I(m^{\prime}_{j}{:}m_{i})=0$. $d_{A^{j}_{I}}$ is the
dimension of the input Hilbert space of the party $A^{j}$. The second equality
follows because of our assumption of all the dimensions of the input Hilbert
spaces being equal. Now, it is easy to see that the $n$-th party has total
$n{-}1$ parties in his/her causal past. Therefore, considering each party
trying to communicate with the remaining $N{-}1$ parties, the total number of
available channels are $N(N{-}1)-\sum_{n{=}1}^{N}(n{-}1)=N(N{-}1)/2$. This
results in

$\displaystyle\sum_{i,j}C^{(1)}(W^{N}_{\mathrm{sep}})^{i{\rightarrow}{j}}\leq\frac{N(N-1)}{2}\log(d).$
(52)

∎

The key property that leads to the above bounds is the convexity of mutual
information under probabilistic mixtures of classical channels. With this in
mind, we see that the above results can be extended directly to the product
encoding, joint decoding setting, replacing the one-shot capacity $C^{(1)}$
with the HSW capacity $C$. Indeed, we have seen that $C$ is given by the
(maximised) Holevo quantity $\chi$ of the one-way channel generated by a
process and, just like mutual information, $\chi$ is convex over the
probabilistic mixture of channels. It remains an open question whether higher
total transmission rates can be achieved in a joint encoding setting.

##  VI Conclusion

We have formalised classical communication through a general quantum causal
structure, which may be probabilistic or indefinite. We have defined the
Holevo quantity as well as different classical capacities for an arbitrary
process and established relationships among them. We have found that, for one-
way communication, the various capacities can be reduced to those of ordinary
channels, up to an optimisation over the operations performed in local
laboratories. We have further shown that, for one-way communication, the
classical capacity of a process cannot exceed the Holevo bound—at most one
classical bit per received qubit—even in case of indefinite causal order.

Next, we have quantified bi-directional and more generally broadcast
communication protocols for processes with definite but classically uncertain
causal order. We have demonstrated that the total amount of communication
between two parties cannot exceed the maximal one-way capacity in a fixed
causal order, with a similar bound extending to multipartite broadcast
communication. One can ask whether a process with an indefinite causal
structure can violate these bounds. We have answered this negatively for
coherent control of causal order, as in the quantum switch [48]. It is an open
question whether a more general process can violate the bounds. As we have not
found any violation, it is an interesting possibility that the bounds we have
found might constitute a universal limit to the total communication possible
in any process.

## Acknowledgement

KG thanks the organisers of the Quantum Information Structure of Spacetime
2020 workshop for giving an opportunity to present this talk. We are grateful
to Alastair Abbott, Ding Jia, Nitica Sakharwade, Marco Tomamichel, and
Magdalena Zych and for helpful discussions. This work has been supported by
the Australian Research Council (ARC) by Centre of Excellence for Engineered
Quantum Systems (EQUS, CE170100009), F.C. acknowledges support through an
Australian Research Council Discovery Early Career Researcher Award
(DE170100712). KG is supported by the RTP scholarship from the University of
Queensland. We acknowledge the traditional owners of the land on which the
University of Queensland is situated, the Turrbal and Jagera people.

## References

  * Bennet and Shor [1998] C. H. Bennet and P. Shor, Quantum information theory, IEEE Trans. Inf. Theory 44, 2724 (1998).
  * Wilde [2011] M. M. Wilde, From classical to quantum shannon theory, (2011), arXiv:1106.1445 [quant-ph] .
  * Holevo [1973] A. Holevo, Bounds for the quantity of information transmitted by a quantum communication channel, Problems Inform. Transmission 9, 177 (1973).
  * Schumacher and Westmoreland [1997] B. Schumacher and M. D. Westmoreland, Sending classical information via noisy quantum channels, Phys. Rev. A 56, 131 (1997).
  * Holevo [1998] A. S. Holevo, The capacity of the quantum channel with general signal states, IEEE Trans. Inf. Theory 44, 269 (1998), arXiv:quant-ph/9611023 [quant-ph] .
  * Lamport [1978] L. Lamport, Time, clocks, and the ordering of events in a distributed system, Commun. ACM 21, 558–565 (1978).
  * Chiribella  _et al._ [2013] G. Chiribella, G. M. D’Ariano, P. Perinotti, and B. Valiron, Quantum computations without definite causal structure, Phys. Rev. A 88, 022318 (2013), arXiv:0912.0195 [quant-ph] .
  * Oreshkov  _et al._ [2012] O. Oreshkov, F. Costa, and Č. Brukner, Quantum correlations with no causal order, Nat. Commun. 3, 1092 (2012), arXiv:1105.4464 [quant-ph] .
  * Hardy [2007] L. Hardy, Towards quantum gravity: a framework for probabilistic theories with non-fixed causal structure, J. Phys. A: Math. Gen. 40, 3081 (2007), arXiv:gr-qc/0608043 [gr-qc] .
  * Hardy [2009] L. Hardy, Quantum gravity computers: On the theory of computation with indefinite causal structure, Quantum Reality, Relativistic Causality, and Closing the Epistemic Circle , 379–401 (2009), arXiv:quant-ph/0701019 [quant-ph] .
  * Zych  _et al._ [2019] M. Zych, F. Costa, I. Pikovski, and Č. Brukner, Bell’s theorem for temporal order, Nat. Commun. 10 (2019), arXiv:1708.00248 [quant-ph] .
  * Araújo  _et al._ [2014] M. Araújo, F. Costa, and Č. Brukner, Computational Advantage from Quantum-Controlled Ordering of Gates, Phys. Rev. Lett. 113, 250402 (2014), arXiv:1401.8127 [quant-ph] .
  * Guérin  _et al._ [2016] P. A. Guérin, A. Feix, M. Araújo, and Č. Brukner, Exponential communication complexity advantage from quantum superposition of the direction of communication, Phys. Rev. Lett. 117, 100502 (2016), arXiv:1605.07372 [quant-ph] .
  * Araújo  _et al._ [2017a] M. Araújo, P. A. Guĕrin, and Ä. Baumeler, Quantum computation with indefinite causal structures, Phys. Rev. A 96 (2017a), arXiv:1706.09854 [quant-ph] .
  * Ebler  _et al._ [2018] D. Ebler, S. Salek, and G. Chiribella, Enhanced communication with the assistance of indefinite causal order, Phys. Rev. Lett. 120, 120502 (2018), arXiv:1711.10165 [quant-ph] .
  * Chiribella  _et al._ [2018] G. Chiribella, M. Banik, S. S. Bhattacharya, T. Guha, M. Alimuddin, A. Roy, S. Saha, S. Agrawal, and G. Kar, Indefinite causal order enables perfect quantum communication with zero capacity channel, (2018), arXiv:1810.10457 [quant-ph] .
  * Salek  _et al._ [2018] S. Salek, D. Ebler, and G. Chiribella, Quantum communication in a superposition of causal orders, (2018), arXiv:1809.06655 [quant-ph] .
  * Jia and Costa [2019a] D. Jia and F. Costa, Causal order as a resource for quantum communication, Phys. Rev. A 100, 052319 (2019a), arXiv:1901.09159 [quant-ph] .
  * Caleffi and Cacciapuoti [2020] M. Caleffi and A. S. Cacciapuoti, Quantum switch for the quantum internet: Noiseless communications through noisy channels, IEEE J Sel. Area Comm. 38, 575–588 (2020), arXiv:1907.07432 [quant-ph] .
  * Procopio  _et al._ [2015] L. M. Procopio, A. Moqanaki, M. Araújo, F. Costa, I. Alonso Calafell, E. G. Dowd, D. R. Hamel, L. A. Rozema, Č. Brukner, and P. Walther, Experimental superposition of orders of quantum gates, Nat. Commun. 6 (2015), arXiv:1412.4006 [quant-ph] .
  * Rubino  _et al._ [2017] G. Rubino, L. A. Rozema, A. Feix, M. Araújo, J. M. Zeuner, L. M. Procopio, Č. Brukner, and P. Walther, Experimental verification of an indefinite causal order, Sci. Adv. 3, e1602589 (2017), arXiv:1608.01683 [quant-ph] .
  * Goswami  _et al._ [2018a] K. Goswami, C. Giarmatzi, M. Kewming, F. Costa, C. Branciard, J. Romero, and A. White, Indefinite causal order in a quantum switch, Phys. Rev. Lett. 121 (2018a), arXiv:1803.04302 [quant-ph] .
  * Goswami  _et al._ [2018b] K. Goswami, Y. Cao, G. A. Paz-Silva, J. Romero, and A. G. White, Communicating via ignorance: Increasing communication capacity via superposition of order, (2018b), arXiv:1807.07383 [quant-ph] .
  * Wei  _et al._ [2019] K. Wei, N. Tischler, S.-R. Zhao, Y.-H. Li, J. M. Arrazola, Y. Liu, W. Zhang, H. Li, L. You, Z. Wang, Y.-A. Chen, B. C. Sanders, Q. Zhang, G. J. Pryde, F. Xu, and J.-W. Pan, Experimental quantum switching for exponentially superior quantum communication complexity, Phys. Rev. Lett. 122 (2019), arXiv:1810.10238 [quant-ph] .
  * Guo  _et al._ [2020] Y. Guo, X.-M. Hu, Z.-B. Hou, H. Cao, J.-M. Cui, B.-H. Liu, Y.-F. Huang, C.-F. Li, G.-C. Guo, and G. Chiribella, Experimental transmission of quantum information using a superposition of causal orders, Phys. Rev. Lett. 124 (2020), arXiv:1811.07526 [quant-ph] .
  * Taddei  _et al._ [2020] M. M. Taddei, J. Cariñe, D. Martínez, T. García, N. Guerrero, A. A. Abbott, M. Araújo, C. Branciard, E. S. Gómez, S. P. Walborn, L. Aolita, and G. Lima, Experimental computational advantage from superposition of multiple temporal orders of quantum gates, (2020), arXiv:2002.07817 [quant-ph] .
  * Gyongyosi  _et al._ [2018] L. Gyongyosi, S. Imre, and H. V. Nguyen, A survey on quantum channel capacities, IEEE Commun. Surv 20, 1149 (2018), arXiv:1801.02019 [quant-ph] .
  * Shannon [1948] C. E. Shannon, A mathematical theory of communication, The Bell System Technical Journal 27, 379 (1948).
  * Hastings [2009] M. B. Hastings, Superadditivity of communication capacity using entangled inputs, Nat. Phys. 5, 255–257 (2009), arXiv:0809.3972 [quant-ph] .
  * Araújo  _et al._ [2015] M. Araújo, C. Branciard, F. Costa, A. Feix, C. Giarmatzi, and Č. Brukner, Witnessing causal nonseparability, New J. Phys. 17, 102001 (2015), arXiv:1506.03776 [quant-ph] .
  * Oreshkov and Giarmatzi [2016] O. Oreshkov and C. Giarmatzi, Causal and causally separable processes, New J. Phys. 18, 093020 (2016), arXiv:1506.05449 [quant-ph] .
  * Araújo  _et al._ [2017b] M. Araújo, A. Feix, M. Navascués, and Č. Brukner, A purification postulate for quantum mechanics with indefinite causal order, Quantum 1, 10 (2017b), arXiv:1611.08535 [quant-ph] .
  * Choi [1975] M.-D. Choi, Positive semidefinite biquadratic forms, Linear Algebra Appl. 12, 95 (1975).
  * Chiribella [2012] G. Chiribella, Perfect discrimination of no-signalling channels via quantum superposition of causal structures, Phys. Rev. A 86, 040301 (2012), arXiv:1109.5154 [quant-ph] .
  * Jia and Sakharwade [2018] D. Jia and N. Sakharwade, Tensor products of process matrices with indefinite causal structure, Phys. Rev. A 97 (2018), arXiv:1706.05532 [quant-ph] .
  * Guérin  _et al._ [2019] P. A. Guérin, M. Krumm, C. Budroni, and Č. Brukner, Composition rules for quantum processes: a no-go theorem, New J. Phys. 21, 012001 (2019), arXiv:1806.10374 [quant-ph] .
  * Perinotti [2017] P. Perinotti, Causal structures and the classification of higher order quantum computations, Tutorials, Schools, and Workshops in the Mathematical Sciences , 103–127 (2017), arXiv:1612.05099 [quant-ph] .
  * Kissinger and Uijlen [2019] A. Kissinger and S. Uijlen, A categorical semantics for causal structure, IEEE Symp. Logic Comput. Sci. (LICS) 15 (2019), arXiv:1701.04732 [quant-ph] .
  * Jia and Costa [2019b] D. Jia and F. Costa, Causal order as a resource for quantum communication, Phys. Rev. A 100 (2019b), arXiv:1901.09159 [quant-ph] .
  * Verdu and Te Sun Han [1994] S. Verdu and Te Sun Han, A general formula for channel capacity, IEEE Trans. Inf. Theory 40, 1147 (1994).
  * Hayashi and Nagaoka [2002] M. Hayashi and H. Nagaoka, A general formula for the classical capacity of a general quantum channel, Proc. IEEE Int. Symp. Inf. Theory (2002), arXiv:quant-ph/0206186 [quant-ph] .
  * Chiribella  _et al._ [2008] G. Chiribella, G. M. D’Ariano, and P. Perinotti, Quantum circuit architecture, Phys. Rev. Lett. 101, 060401 (2008), arXiv:0712.1325 [quant-ph] .
  * Morimae [2014] T. Morimae, The process matrix framework for a single-party system (2014), arXiv:1408.1464 [quant-ph] .
  * Bennett and Wiesner [1992] C. H. Bennett and S. J. Wiesner, Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states, Phys. Rev. Lett. 69, 2881 (1992).
  * Branciard  _et al._ [2016] C. Branciard, M. Araújo, A. Feix, F. Costa, and Č. Brukner, The simplest causal inequalities and their violation, New J. Phys. 18, 013008 (2016), arXiv:1508.01704 [quant-ph] .
  * Cover and Thomas [2006] T. M. Cover and J. A. Thomas, Elements of information theory, Wiley-Interscience (2006).
  * Miklin  _et al._ [2017] N. Miklin, A. A. Abbott, C. Branciard, R. Chaves, and C. Budroni, The entropic approach to causal correlations, New J. Phys. 19, 113041 (2017), arXiv:1706.10270 [quant-ph] .
  * Chiribella  _et al._ [2009] G. Chiribella, G. M. D’Ariano, and P. Perinotti, Theoretical framework for quantum networks, Phys. Rev. A 80, 022339 (2009), arXiv:0904.4483 [quant-ph] .
  * [49] J. Barrett, R. Lorenz, and O. Oreshkov, Cyclic quantum causal models, arXiv:2002.12157v1 [quant-ph] .
  * [50] W. Yokojima, M. T. Quintino, A. Soeda, and M. Murao, Consequences of preserving reversibility in quantum superchannels, arXiv:2003.05682v2 [quant-ph] .
  * Wechs  _et al._ [2019] J. Wechs, A. A. Abbott, and C. Branciard, On the definition and characterisation of multipartite causal (non)separability, New J. Phys. 21, 013027 (2019), arXiv:1807.10557 [quant-ph] .