# Quantum Markov monogamy inequalities

Matheus Capela<EMAIL_ADDRESS>Institute of Physics, Federal University of
Goiás, 74.690-900, Goiânia, Brazil  Lucas C. Céleri<EMAIL_ADDRESS>Institute of Physics, Federal University of Goiás, 74.690-900, Goiânia, Brazil
Rafael Chaves<EMAIL_ADDRESS>International Institute of Physics,
Federal University of Rio Grande do Norte, 59078-970, P. O. Box 1613, Natal,
Brazil  School of Science and Technology, Federal University of Rio Grande do
Norte, Natal, Brazil  Kavan Modi<EMAIL_ADDRESS>School of Physics and
Astronomy, Monash University, Clayton, VIC 3800, Australia

###### Abstract

Markovianity lies at the heart of communication problems. This in turn makes
the information-theoretic characterization of Markov processes worthwhile.
Data processing inequalities are ubiquitous in this sense, assigning necessary
conditions for all Markov processes. We address here the problem of the
information-theoretic analysis of constraints on Markov processes in the
quantum regime. We show the existence of a novel class of quantum data
processing inequalities called here quantum Markov monogamy inequalities. This
new class of necessary conditions on quantum Markov processes is inspired by
its counterpart for classical Markov processes, and thus providing a strong
link between classical and quantum constraints on Markovianity. We go on to
construct a family of multitime quantum Markov monogamy inequalities, based on
the process tensor formalism and that exploits multitime correlations. We then
show, by means of an explicit example, that the Markov monogamy inequalities
can be stronger than the usual quantum data processing inequalities.

##  I Introduction

Markovianity plays a central role in the theory of classical information. This
is enforced by describing the asymptotic encoding-decoding scheme of a
memoryless channel used with no feedback by a Markovian stochastic process
Shannon (1948). This leads to the principal result in information theory, the
channel-coding theorem, stating the maximum rate of classical bits reliably
communicated by a noisy channel to be equal to the mutual information between
the channel’s input and output variables maximized over all input probability
distributions. Furthermore, the mutual information between variables of any
Markovian stochastic process is constrained according to the so-called
classical data processing inequalities (CDPIs). Indeed, a CDPI is directly
used in the proof of the converse statement of the channel-coding theorem,
stating that any encoding-decoding of a noisy channel with communication rate
superior to its capacity is not reliable Yeung (2008). While the classical
data processing theorems are widely studied Arnold (2004); Merhav (2012); Kang
and Ulukus (2010); du Pin Calmon  _et al._ (2017); Kamath and Nair (2015);
Raginsky (2013); Merhav (2011); Anantharam  _et al._ (2014), a wider range of
constraints on classical Markovian processes, the so-called monogamy
inequalities, were only discovered recently Capela  _et al._ (2020) and
conjectured to hold for quantum processes as well.

With rising interest in quantum information theory, classical data processing
inequalities were extended to the regime of quantum processes Schumacher and
Nielsen (1996), setting an appropriate approach to define new constraints on
quantum Markov processes. Indeed, intense research has been undertaken in this
direction since then Buscemi (2014); Buscemi and Datta (2016); Buscemi (2017,
2015); Hayden  _et al._ (2004); Rivas  _et al._ (2014); Ferrie (2014);
Vinjanampathy and Modi (2015); Türkmen  _et al._ (2017). Naturally, the
development of further constraints in terms of information inequalities
imposed by quantum Markovian processes is of great interest in information
theory, and it is the main problem addressed in this paper.

Here, we prove the quantum Markov monogamy inequality (QMMI) constraining any
four-time-steps Markov process. The QMMI is the quantum counterpart of the
classical Markov monogamy inequality (CMMI) Capela  _et al._ (2020), and also
is the main result of this study. The QMMIs valid for six- and eight-time-
steps Markov processes are also provided. This leads to a conjecture on the
Markov monogamy inequalities for arbitrarily long quantum Markov processes.
Furthermore, the results presented here also further enforce the connection
between classical and quantum conditions on Markovianity. Similarly to the
case of classical stochastic processes studied in Capela  _et al._ (2020), we
apply the information inequalities to the problem of witnessing non-
Markovianity in a quantum process. By considering a concrete example, we show
that there are quantum non-Markov processes that can be witnessed by a QMMI,
while not violating any quantum data processing inequalities (QDPI) from
Schumacher and Nielsen (1996). Finally, we construct a larger set of QMMIs
that account for multitime quantum correlations using the process tensor (or
process matrix) formalism Pollock  _et al._ (2018a, b); Costa and Shrapnel
(2016); Milz  _et al._ (2020a); Milz and Modi (2021).

The paper is organized as follows. In Sec. II we review the classical data
processing theorems, and provide the generalized version of the classical
Markov monogamy inequalities. In Sec. III we first review the quantum data
processing inequality from Schumacher and Nielsen (1996). Then we present the
main result of this paper, the Markov monogamy inequality of a four-time-step
quantum Markov process. Furthermore, we provide the conjecture on the general
form of quantum Markov monogamy inequalities. Sec. V deals with the extension
of the quantum data processing theorems, in particular the Markov monogamy
inequalities, to the process tensor formalism. Finally, in Sec. VI we make our
final conclusions and discuss some open problems.

##  II Classical Markov processes and information inequalities

Classically, any discrete stochastic process
$\left\\{X_{1},\dots,X_{n}\right\\}$ is described by a probability
distribution

$\displaystyle p(x_{1},\dots,x_{n}).$ (1)

A particularly important class of processes are those called Markovian, for
which the probability that the random variable $X_{i}$ takes a value $x_{i}$
at time $t_{i}$ is uniquely determined, and not affected by the possible
values of $X$ at previous times to $t_{i-1}$. Mathematically, any Markovian
process must have conditional probability distributions satisfying

$p(x_{i}|x_{i-1},\dots,x_{1})=p(x_{i}|x_{i-1})\quad\forall i.$ (2)

In practice, however, it is often the case that instead of analysing the
probability distribution, one is rather interested in investigating its
Shannon entropy, a fundamental building block in information theory Yeung
(2008), defined for a random variable (or set of variables) $X$ as

$H(X)\coloneqq-\sum_{x}p(x)\log p(x),$ (3)

where the sum is taken over the support of $X$. Entropically, the Markov
condition (2) is expressed as

$H(X_{i}|X_{i-1},\dots,X_{1})=H(X_{i}|X_{i-1})\quad\forall i,$ (4)

which in turn implies the paradigmatic data processing inequalities

$I(X_{r}:X_{s})\geq I(X_{i}:X_{j})\quad{\rm with}\quad i\leq r<s\leq j.$ (5)

Here, $I(X_{i}:X_{j})\coloneqq H(X_{i})+H(X_{j})-H(X_{i}:X_{j})$ is the mutual
information between variables $X_{i}$ and $X_{j}$.

For the simplest Markov chain with $n=3$, the only entropic constraints
implied by Markovianity are the data processing inequalities given by Capela
_et al._ (2020)

$\displaystyle I(X_{1}:X_{2})\geq I(X_{1}:X_{3}),\ I(X_{2}:X_{3})\geq
I(X_{1}:X_{3}),$

that is, we recover the usual data processing inequalities that hold for a
Markov chain.

For $n\geq 4$, however, a new class of inequalities appears, generalizations
of data processing called Markov monogamy inequalities, that implies
constraints on the mutual information between different pairs of variables
along the Markov chain Capela  _et al._ (2020). We present below a generalized
version of the conjecture in Capela  _et al._ (2020), proven to hold for
particular cases of $n$.

######  Conjecture 1 (Classical Markov monogamy inequalities (CMMI)).

Consider the Markovian process $X_{n}\rightarrow\cdots\rightarrow
X_{1}\rightarrow Y_{1}\rightarrow\cdots\rightarrow Y_{n}$. The variables
$X_{1}$ and $Y_{1}$ are to be interpreted as input and output of a given
channel, respectively. The variables $X_{i}$ and $Y_{i}$, with $i=2,\dots,n$,
are interpreted as pre-processed and post-processed variables, respectively.
Then for any bijective function
$f\colon\\{1,\dots,n\\}\rightarrow\\{1,\dots,n\\}$, it holds that

$\sum_{i=1}^{n}I(X_{i}:Y_{i})\geq\sum_{i=1}^{n}I(X_{i}:Y_{f(i)}),$ (6)

where $I(X:Y)$ denotes the mutual information of random variables $X$ and $Y$.

The conjecture above has been checked for $n$ up to 4, that is, Markov chains
with 8 random variables 111Conditions of this type can be tested with a linear
program such as ITIP Yeung and Yan (2016). For the case of $n=2$, we have the
Markov monogamy inequality

$I(X_{1}:Y_{1})+I(X_{2}:Y_{2})\geq I(X_{1}:Y_{2})+I(X_{2}:Y_{1}),$ (7)

associated to the bijection $f\colon\\{1,2\\}\rightarrow\\{1,2\\}$ for which
$f(1)=2$ and $f(2)=1$. The remaining bijection
$g\colon\\{1,2\\}\rightarrow\\{1,2\\}$ for which $g(1)=1$ and $g(2)=2$ leads
to a trivial inequality, nonetheless, a valid one. Note that, independently of
the number of random variables of a stochastic process, the CDPIs and CMMI are
only necessary conditions for Markovianity.

It is worth noting that the result presented in Eq. (7) appeared in Ref. Cover
and Thomas (2005), while in Ref. Capela  _et al._ (2020), we found an extended
class of such inequalities. There we further showed that while all of the
above inequalities are derived for Markov processes, they also hold for
divisible processes that are non-Markovian. We also showed that there are non-
Markovian processes that will also satisfy all of the above inequalities,
i.e., the inequalities are necessary for any Markov process but not
sufficient. Below we will generalize the Markov monogamy inequalities to the
quantum case and for that we will employ the coherent information Schumacher
and Nielsen (1996). Differently from the classical case, however, our approach
will not rely on the Shannon cone construction, mainly because of the non-
negativity of the coherent information and the fact that the classical proof
stands on the marginalization of a joint probability distribution which is not
available on the quantum scenario.

##  III Quantum Markov processes and information inequalities

Central to our purpose are the quantum Markov processes.

######  Definition 1.

A sequence of quantum states $\\{\rho_{1},\cdots,\rho_{n}\\}$ is a quantum
Markov process with respect to the sequence of quantum channels
$\\{\Lambda_{1},\cdots,\Lambda_{n-1}\\}$ if the conditions
$\rho_{i+1}=\Lambda_{i}(\rho_{i})$, with $i=1,\cdots,n-1$ are satisfied. This
situation is denoted by

$\displaystyle\rho_{1}\stackrel{{\scriptstyle\mathclap{\mbox{$\Lambda_{1}$}}}}{{\longrightarrow}}\rho_{2}\stackrel{{\scriptstyle\mathclap{\mbox{$\Lambda_{2}$}}}}{{\longrightarrow}}\rho_{3}\stackrel{{\scriptstyle\mathclap{\mbox{$\Lambda_{3}$}}}}{{\longrightarrow}}\dots\stackrel{{\scriptstyle\mathclap{\mbox{$\Lambda_{n-1}$}}}}{{\longrightarrow}}\rho_{n}.$
(8)

A classical channel $p(Y|X)$ transforms the classical state of the system $X$
into the state of the joint input-output system $XY$, that is, we have
$p(X,Y)=p(Y|X)p(X)$. On the other hand, quantum processes are defined in a
very different way. That is, a quantum channel $\Lambda$ maps the state
$\rho_{1}$ of the input quantum quantum system into the state
$\rho_{2}=\Lambda(\rho_{1})$ of the output quantum system. Therefore, it is
not entirely trivial how one should characterize the temporal correlation in a
quantum process. The development of the quantum data processing inequality
provided great understanding towards this direction. Importantly, it shows we
cannot directly compare classical and quantum information inequalities on
equal footing. In particular, as we have stressed above, the derivation of the
inequalities follow a complete different route. The classical case being based
on the existence of a joint probability distribution followed a
marginalization executed via a Fourier-Motzkin elimination. In turn, the
quantum case combines states and channels, and uses their properties to arrive
at the non-trivial quantum analogue of the information inequalities.

With the goal of deriving conditions on quantum Markov process we define the
coherent information Schumacher and Nielsen (1996). Here, we use Latin letters
to denote both a quantum system and its associated Hilbert space. The coherent
information of the state $\rho$ of a quantum system $\mathsf{S}_{1}$ with
respect to a quantum channel
$\Lambda\colon\mathsf{L}(\mathsf{S}_{1})\rightarrow\mathsf{L}(\mathsf{S}_{2})$
is defined by

$I_{c}(\rho;\Lambda)\coloneqq
H(\Lambda(\rho))-H((\mathrm{id}_{\mathsf{R}}\otimes\Lambda)(\psi)),$ (9)

where $\psi\in\mathsf{L}(\mathsf{R}\otimes\mathsf{S}_{1})$ is a any
purification of $\rho$, and $H(\rho)$ stands for the von Neumann entropy of
the quantum state, defined as

$H(\rho)\coloneqq-\mathrm{Tr}\left[\rho\log{\rho}\right],$ (10)

that reduces to the usual Shannon entropy (3) if we employ the spectral
decomposition $\rho=\sum_{x}\lambda_{x}\ket{x}\bra{x}$ of the density
operator. We will often denote the von Neumann entropy $H(\rho)$ by
$H(\mathsf{S})_{\rho}$, or even by $H(\mathsf{S})$ when it is implicitly known
that the quantum system $\mathsf{S}$ is in the state $\rho$. Generally,
$\mathbb{1}$ denotes the identity operator, and $\mathrm{id}$ denotes the
identity channel.

###  III.1 Quantum data processing inequalities

Importantly, the coherent information replaces the mutual information in the
transition from CDPIs to their quantum counterparts QDPIs Schumacher and
Nielsen (1996). For any quantum state $\rho$ of $\mathsf{S}_{1}$, and for any
quantum channels
$\Lambda_{1}\colon\mathsf{L}(\mathsf{S}_{1})\rightarrow\mathsf{L}(\mathsf{S}_{2})$
and
$\Lambda_{2}\colon\mathsf{L}(\mathsf{S}_{2})\rightarrow\mathsf{L}(\mathsf{S}_{3})$,
it holds that

$I_{c}(\rho_{1};\Lambda_{1})\geq I_{c}(\rho_{1};\Lambda_{2}\circ\Lambda_{1}).$
(11)

For completeness, we refer the reader to our Appendix .1 for the proof
originally presented in Schumacher and Nielsen (1996). Similarly to the
interpretation in the classical case, the quantum data processing theorem
states that coherent information is monotonically decreasing under the action
of noisy operations.

Equivalently, instead of coherent information, it is also possible to define
the quantum data processing theorem in terms of the quantum mutual
information. For that, let $I(\mathsf{A}:\mathsf{B})_{\rho}\coloneqq
H(\mathsf{A})+H(\mathsf{B})-H(\mathsf{A},\mathsf{B})$ denotes the mutual
information of a bipartite system $\mathsf{A}\otimes\mathsf{B}$ in the state
$\rho$, with $\rho_{A}=\mathrm{Tr}_{B}[\rho]$ and
$\rho_{B}=\mathrm{Tr}_{A}[\rho]$. Then, for any quantum state $\rho$ of the
bipartite system $\mathsf{A}\otimes\mathsf{B}$ and for any quantum channel
$\Lambda\colon\mathsf{L}(\mathsf{B})\rightarrow\mathsf{L}(\mathsf{C})$, it
holds that

$I(\mathsf{A}:\mathsf{B})_{\rho}\geq
I(\mathsf{A}:\mathsf{C})_{(\mathrm{id}_{\mathsf{A}}\otimes\Lambda)(\rho)}.$
(12)

So quantum data processing theorem equivalently states that correlations
between a bipartite quantum system cannot increase under the action of a local
noisy operation. See Ref. Buscemi (2014) for a presentation and application of
the QDPI taking this form. For the sake of completeness, we present a proof of
the equivalence of this two forms of the quantum data processing theorem in
Appendix .1.

Now we move to derive the quantum version of the four-time-steps monogamy
inequality presented in Eq. (7).

###  III.2 Quantum Markov monogamy inequality

In the following we prove a quantum version of the Markov monogamy inequality
(7). This is a crucial step towards extending Conjecture 1, which is valid for
classical variables, also to quantum Markov processes. As such we consider the
four-time-step quantum processes of the form shown in Eq. (8).

$\psi$$\varphi_{1}$$\varphi_{2}$$\varphi_{3}$$U_{1}$$U_{2}$$U_{3}$$\mathsf{R}$$\mathsf{R}$$\mathsf{R}$$\mathsf{R}$$\mathsf{S}_{1}$$\mathsf{S}_{2}$$\mathsf{S}_{3}$$\mathsf{F}_{1}$$\mathsf{E}_{1}$$\mathsf{E}_{1}$$\mathsf{E}_{1}$$\mathsf{F}_{2}$$\mathsf{F}_{2}$$\mathsf{E}_{2}$$\mathsf{E}_{2}$$\mathsf{F}_{3}$$\mathsf{F}_{3}$$\mathsf{F}_{3}$$\mathsf{E}_{3}$$\mathsf{S}_{4}$

Figure 1: Diagram representing the purified process
$\rho_{1}\stackrel{{\scriptstyle\mathclap{\mbox{$\Lambda_{1}$}}}}{{\longrightarrow}}\rho_{2}\stackrel{{\scriptstyle\mathclap{\mbox{$\Lambda_{2}$}}}}{{\longrightarrow}}\rho_{3}\stackrel{{\scriptstyle\mathclap{\mbox{$\Lambda_{3}$}}}}{{\longrightarrow}}\rho_{4}$.
The quantum state $\psi$ is a purification of $\rho_{1}$. Thus, $\rho_{1}$ is
obtained from $\psi$ by tracing out the $\mathsf{R}$ system. The unitary
operator $U_{i}$ and the pure state $\varphi_{i}$ provides a dilation of the
quantum channel $\Lambda_{i}$, with $i=1,2,3,4.$ The remaining quantum states
$\rho_{2},\rho_{3},\rho_{4}$ are obtained by acting the unitary operations and
tracing out the appropriate reference-environment systems.

######  Theorem 1 (Quantum Markov monogamy inequality (QMMI)).

For any quantum state $\rho_{1}$ of a system $\mathsf{S}_{1}$, and for any
quantum channels
$\Lambda_{1}\colon\mathsf{L}(\mathsf{S}_{1})\rightarrow\mathsf{L}(\mathsf{S}_{2})$,
$\Lambda_{2}\colon\mathsf{L}(\mathsf{S}_{2})\rightarrow\mathsf{L}(\mathsf{S}_{3})$
and
$\Lambda_{3}\colon\mathsf{L}(\mathsf{S}_{3})\rightarrow\mathsf{L}(\mathsf{S}_{4})$,
it holds that

$\displaystyle\begin{split}&I_{c}(\rho_{1},\Lambda_{3}\circ\Lambda_{2}\circ\Lambda_{1})+I_{c}(\Lambda_{1}(\rho_{1}),\Lambda_{2})\\\
&\qquad\geq
I_{c}(\rho_{1},\Lambda_{2}\circ\Lambda_{1})+I_{c}(\Lambda_{1}(\rho_{1}),\Lambda_{3}\circ\Lambda_{2}).\end{split}$
(13)

###### Proof.

Define a dilation of each quantum channel $\Lambda_{i}$ —with $i=1,2,3$— by
setting a unitary operator
$U_{i}\colon\mathsf{S}_{i}\otimes\mathsf{F}_{i}\rightarrow\mathsf{S}_{i+1}\otimes\mathsf{E}_{i}$
and a pure quantum state $\varphi_{i}$ for which

$\Lambda_{i}(\rho)=\Tr_{\mathsf{E}_{i}}\left[U_{i}(\rho\otimes\varphi_{i})U_{i}^{\dagger}\right],$
(14)

for any operator $\rho_{1}$ in $\mathsf{L}(\mathsf{S}_{i})$. Fig. 1 provides a
representation of the process for a purification $\psi$ in
$\mathsf{L}(\mathsf{R}\otimes\mathsf{S}_{1})$ of the initial quantum state
$\rho_{1}$.

Now, note the definition of the coherent information terms involved in (13),
and given by

$\displaystyle
I_{c}(\rho_{1};\Lambda_{3}\circ\Lambda_{2}\circ\Lambda_{1})=H(\mathsf{S}_{4})-H(\mathsf{R},\mathsf{S}_{4});$
(15) $\displaystyle
I_{c}(\rho_{2};\Lambda_{2})=H(\mathsf{S}_{3})-H(\mathsf{R},\mathsf{E}_{1},\mathsf{S}_{3});$
(16) $\displaystyle
I_{c}(\rho_{1};\Lambda_{2}\circ\Lambda_{1})=H(\mathsf{S}_{3})-H(\mathsf{R},\mathsf{S}_{3});$
(17) $\displaystyle
I_{c}(\rho_{2};\Lambda_{3}\circ\Lambda_{2})=H(\mathsf{S}_{4})-H(\mathsf{R},\mathsf{E}_{1},\mathsf{S}_{4}),$
(18)

with $\rho_{2}=\Lambda_{1}(\rho_{1})$.

Then, consider the following equality of the entropy terms due to the purity
of the correspondent quantum systems

$\displaystyle
H(\mathsf{R},\mathsf{S}_{4})=H(\mathsf{E}_{1},\mathsf{E}_{2},\mathsf{E}_{3});$
(19) $\displaystyle
H(\mathsf{R},\mathsf{E}_{1},\mathsf{S}_{3})=H(\mathsf{E}_{2});$ (20)
$\displaystyle H(\mathsf{R},\mathsf{S}_{3})=H(\mathsf{E}_{1},\mathsf{E}_{2});$
(21) $\displaystyle
H(\mathsf{R},\mathsf{E}_{1},\mathsf{S}_{4})=H(\mathsf{E}_{2},\mathsf{E}_{3}).$
(22)

Summing Eqs. (19,20,21,22), using the strong subadditivity of quantum entropy
Lieb and Ruskai (1973),

$H(\mathsf{E}_{1},\mathsf{E}_{2},\mathsf{E}_{3})+H(\mathsf{E}_{2})\leq
H(\mathsf{E}_{1},\mathsf{E}_{2})+H(\mathsf{E}_{2},\mathsf{E}_{3}),$ (23)

and solving for (15,16,17,18), we have the desired inequality. ∎

As proven in Appendix .3, the quantum Markov monogamy inequality (QMMI) can
equivalently be cast as the monotonicity of the quantum conditional mutual
information. This is formalized in the theorem below.

######  Theorem 2 (Monotonicity of the quantum conditional mutual information
Wilde (2011)).

For any tripartite quantum state $\rho$ in
$\mathsf{L}(\mathsf{A}\otimes\mathsf{B}\otimes\mathsf{C})$ and for any quantum
channel
$\Lambda\colon\mathsf{L}(\mathsf{B})\rightarrow\mathsf{L}(\mathsf{D})$, it
holds that

$I(\mathsf{A}:\mathsf{B}|\mathsf{C})_{\rho}\geq
I(\mathsf{A}:\mathsf{D}|\mathsf{C})_{(\mathrm{id}_{\mathsf{A}}\otimes\Lambda\otimes\mathrm{id}_{\mathsf{C}})(\rho)}.$
(24)

We remark that our inequalities are completely general and hold for arbitrary
quantum processes (noisy or noiseless). In particular, notice that a necessary
condition for non-Markovianity is the that the process is non-unitary (thus,
coupled to an enviroment). In this sense, the noiseless case is not
interesting from a non-Markovianity point of view.

In any case, classical data processing inequalities are directly associated
with the effect of noise on the processes. For instance, the classical data
processing inequality $I(X_{1}:X_{2})\geq I(X_{1}:X_{3})$ is satisfied with
equality whenever the postprocessing stage $X_{2}\rightarrow X_{3}$ is defined
by a deterministic bijective transformation.

A similar reasoning holds for quantum information inequalities. That is, the
quantum data processing inequality $I_{c}(\rho;\Lambda_{1})\geq
I_{c}(\rho;\Lambda_{2}\circ\Lambda_{1})$ is satisfied with inequality whenever
the channels $\Lambda_{1},\Lambda_{2}$ are deterministic quantum unitary
operations. Moreover, the quantum Markov monogamy inequality in Eq. (13) is
also satisfied with equality whenever the quantum channels
$\Lambda_{1},\Lambda_{2},\Lambda_{3}$ are deterministic unitary quantum
operations. Once again, this enforces non-trivial links between classical and
quantum information processing conditions.

###  III.3 Violation of the quantum Markov monogamy inequality

Our aim here is to show that the QMMI in Eq. (13) can be violated by non-
Markovian processes even in situations where all QDPI (11) continue to hold.
That is, we will prove that the QMMI can witness quantum non-Markovianity
beyond what is possible relying solely on quantum data processing
inequalities.

For a four-time-step quantum Markov process of the form of Eq. (8) the
following quantities are positive semi-definite,

$\displaystyle\mathrm{DP}_{1}\coloneqq$ $\displaystyle
I_{c}(\rho_{1};\Lambda_{1})-I_{c}(\rho_{1};\Lambda_{2}\circ\Lambda_{1});$ (25)
$\displaystyle\mathrm{DP}_{2}\coloneqq$ $\displaystyle
I_{c}(\rho_{1};\Lambda_{1})-I_{c}(\rho_{1};\Lambda_{3}\circ\Lambda_{2}\circ\Lambda_{1});$
(26) $\displaystyle\mathrm{DP}_{3}\coloneqq$ $\displaystyle
I_{c}(\rho_{1};\Lambda_{2}\circ\Lambda_{1})-I_{c}(\rho_{1};\Lambda_{3}\circ\Lambda_{2}\circ\Lambda_{1});$
(27) $\displaystyle\mathrm{DP}_{4}\coloneqq$ $\displaystyle
I_{c}(\rho_{2};\Lambda_{2})-I_{c}(\rho_{2};\Lambda_{3}\circ\Lambda_{2});$ (28)
$\displaystyle\mathrm{M4}\coloneqq$ $\displaystyle
I_{c}(\rho_{1};\Lambda_{3}\circ\Lambda_{2}\circ\Lambda_{1})+I_{c}(\rho_{2};\Lambda_{2})$
$\displaystyle-
I_{c}(\rho_{1};\Lambda_{2}\circ\Lambda_{1})-I_{c}(\rho_{2};\Lambda_{3}\circ\Lambda_{2}),$
(29)

the first four corresponding to QDPIs of the same form as in Eq. (11) and the
last one corresponding QMMI in Eq. (13).

We do not consider the quantum version of all possible CDPIs for a four-time-
step process. For instance, the quantum version of inequalities of the type
$I(X_{2}:X_{3})\geq I(X_{1}:X_{3})$ have not been considered. The reason is
twofold. Firstly, the toolkit related to the proof of the QDPI —presented in
Appendix .1— do not directly applies to this case. Thus we leave it for future
studies. Secondly, considering this type of QDPIs do not add any new
information to our example. That is because inequalities of this form are not
violated for the non-Markovian process examined here. Appendix .2 provides a
discussion on this two claims.

To generate non-Markovian correlations (one that cannot thus be represented by
the process represented in Fig. 1), we exploit an initially correlated
tripartite system $\mathsf{R}\otimes\mathsf{S}\otimes\mathsf{E}$, with each of
its parts consisting of qubit systems, and in the the pure state

$\ket{\psi}=\frac{1}{\sqrt{3}}(\ket{1,0,0}+\ket{0,1,0}+\ket{0,0,1}).$ (30)

The collection $\\{\ket{0},\ket{1}\\}$ corresponds to the computational basis
of the local systems.

Figure 2: Markov monogamy violation. Markov monogamy is the only inequality
being violated in the region $0\leq\lambda\leq 0.15$ (shaded in blue).
Nevertheless, the converse situation is also possible. In the region
$0.85\leq\lambda\leq 1$ (shaded in red), the monogamy inequality is not
violated, while two data processing inequalities witness the non-Markovian
behavior of the evolution.

On the system-environment part of this initial state, we apply in sequence the
unitary operation $U_{\lambda}$, with $0\leq\lambda\leq 1$, that in the
computational basis is given by

$U_{\lambda}=\begin{bmatrix}0&-\sqrt{1-\lambda}&\sqrt{\lambda}&0\\\ 1&0&0&0\\\
0&0&0&1\\\ 0&\sqrt{\lambda}&\sqrt{1-\lambda}&0\end{bmatrix}.$ (31)

Thus, we have the well-defined sequence of states of the tripartite system
$\mathsf{R}\otimes\mathsf{S}\otimes\mathsf{E}$ given by

$\displaystyle\gamma_{1}$ $\displaystyle=$
$\displaystyle\ket{\psi}\bra{\psi};$ (32) $\displaystyle\gamma_{2}$
$\displaystyle=$ $\displaystyle(\mathbb{1}_{\mathsf{R}}\otimes
U_{\lambda})\gamma_{1}(\mathbb{1}_{\mathsf{R}}\otimes U_{\lambda})^{\dagger};$
(33) $\displaystyle\gamma_{3}$ $\displaystyle=$
$\displaystyle(\mathbb{1}_{\mathsf{R}}\otimes
U_{\lambda})\gamma_{2}(\mathbb{1}_{\mathsf{R}}\otimes U_{\lambda})^{\dagger};$
(34) $\displaystyle\gamma_{4}$ $\displaystyle=$
$\displaystyle(\mathbb{1}_{\mathsf{R}}\otimes
U_{\lambda})\gamma_{3}(\mathbb{1}_{\mathsf{R}}\otimes U_{\lambda})^{\dagger}.$
(35)

From the above sequence of states, diagrammatically represented in Fig. 3, we
can compute the QDPIs (denoted as $\mathrm{DP}_{i}$ with $i=1,\cdots,4$) and
QMMI (denoted as $\mathrm{M4}$) witnessing the non-Markovianity of the local
evolution of the system $\mathsf{S}$.

We now follow Equations (15-18), along with Equations (25-29), to compute the
DPIs and QMMI. For the inequality in (25), we need to compute entropies of
states $\Tr_{\mathsf{R},\mathsf{E}}[\gamma_{i}]$ and
$\Tr_{\mathsf{E}}[\gamma_{i}]$ for $i=2,3$. The entropies of the first terms,
in Equations (15-18), are simply the entropies of states
$\Tr_{\mathsf{R},\mathsf{E}}[\gamma_{3}]$ and
$\Tr_{\mathsf{R},\mathsf{E}}[\gamma_{4}]$. The entropies of the second terms
in Equations (15,17) are with respect to $\Tr_{\mathsf{R}}[\gamma_{4}]$ and
$\Tr_{\mathsf{R}}[\gamma_{3}]$, respectively. The fact that $\mathsf{R}$ is
not a purification of the initial state of $\mathsf{S}$, will play a crucial
role in violating the inequalities. In other words, the initial correlations
with $\mathsf{E}$ are a non-Markovian feature. On the other hand, the
entropies of the second terms in Equations (16,18) are with respect to the
total states $\gamma_{3}$ and $\gamma_{4}$, respectively. This is because,
unlike in a Markov process, $\mathsf{E}_{1}$ is the same as $\mathsf{E}$,
i.e., the total environment. This leads coherent interference of $\mathsf{SE}$
correlations throughout the process, which too will play a central role in
violating the inequalities below. This leads to

$\displaystyle\mathrm{DP}_{1}\coloneqq$
$\displaystyle[H(\mathsf{S})-H(\mathsf{R},\mathsf{S})]_{\gamma_{2}}-[H(\mathsf{S})-H(\mathsf{R},\mathsf{S})]_{\gamma_{3}};$
(36) $\displaystyle\mathrm{DP}_{2}\coloneqq$
$\displaystyle[H(\mathsf{S})-H(\mathsf{R},\mathsf{S})]_{\gamma_{2}}-[H(\mathsf{S})-H(\mathsf{R},\mathsf{S})]_{\gamma_{4}};$
(37) $\displaystyle\mathrm{DP}_{3}\coloneqq$
$\displaystyle[H(\mathsf{S})-H(\mathsf{R},\mathsf{S})]_{\gamma_{3}}-[H(\mathsf{S})-H(\mathsf{R},\mathsf{S})]_{\gamma_{4}};$
(38) $\displaystyle\mathrm{DP}_{4}\coloneqq$
$\displaystyle[H(\mathsf{S})-H(\mathsf{R},\mathsf{S},\mathsf{E})]_{\gamma_{3}}$
$\displaystyle-[H(\mathsf{S})-H(\mathsf{R},\mathsf{S},\mathsf{E})]_{\gamma_{4}};$
(39) $\displaystyle\mathrm{M4}\coloneqq$
$\displaystyle[H(\mathsf{R},\mathsf{S},\mathsf{E})-H(\mathsf{R},\mathsf{S})]_{\gamma_{4}}$
$\displaystyle-[H(\mathsf{R},\mathsf{S})-H(\mathsf{R},\mathsf{S},\mathsf{E})]_{\gamma_{3}}.$
(40)

The quantities above are presented in Fig. 2 for the process represented by
Equations (32,33,34,35). We show there are processes for which the Markov
monogamy inequality is violated, and thus witnessing non-Markovianity, while
none of the QDPIs being efficient in this task. We notice that the converse
behavior is also possible.

$\psi$$U_{1}$$U_{2}$$U_{3}$$\mathsf{R}$$\mathsf{R}$$\mathsf{R}$$\mathsf{R}$$\mathsf{S}$$\mathsf{E}$$\mathsf{E}$$\mathsf{S}$$\mathsf{S}$$\mathsf{S}$$\mathsf{E}$$\mathsf{E}$

Figure 3: Non-Markov process. The non-Markovian behavior considered here
consists of initial system-environment correlations, and environmental quantum
memory through the unitary system-environment evolution.

###  III.4 A conjecture on quantum Markov processes

At this stage we are ready to extend Conjecture 1 to the quantum realm. We
take the following notation to simplify its statement. For any quantum Markov
process

$\rho_{1}\stackrel{{\scriptstyle\mathclap{\mbox{$\Lambda_{1}$}}}}{{\longrightarrow}}\rho_{2}\stackrel{{\scriptstyle\mathclap{\mbox{$\Lambda_{2}$}}}}{{\longrightarrow}}\cdots\stackrel{{\scriptstyle\mathclap{\mbox{$\Lambda_{n-1}$}}}}{{\longrightarrow}}\rho_{n}$

we define $I_{c}(\rho_{r}:\rho_{s})=I_{c}(\rho_{s}:\rho_{r})$, with

$I_{c}(\rho_{r}:\rho_{s})\coloneqq
I_{c}(\rho_{r};\bigcirc_{i=r}^{s-1}\Lambda_{i}),$ (41)

for $r<s$, where
$\bigcirc_{i=r}^{s-1}\Lambda_{i}\coloneqq\Lambda_{s-1}\circ\cdots\circ\Lambda_{r}$.

######  Conjecture 2 (Quantum Markov monogamy inequalities).

For any quantum Markov process

$\rho_{n}\rightarrow\cdots\rightarrow\rho_{1}\rightarrow\sigma_{1}\rightarrow\cdots\rightarrow\sigma_{n},$

and for any bijective function
$f:\\{1,\cdots,n\\}\rightarrow\\{1,\cdots,n\\}$, it holds that

$\sum_{i=1}^{n}I_{c}(\rho_{i}:\sigma_{i})\geq\sum_{i=1}^{n}I_{c}(\rho_{i}:\sigma_{f(i)}).$
(42)

In Subsection III.2 we have shown the case $n=2$ to be true. In Appendices .4
and .5 we show that the validity of Conjecture 2 holds for $n=3,4$ as well.

##  IV Comparison to previous results

The witnessing of classical and quantum non-Markovianity is a key application
of the classical and quantum information inequalities presented in the
manuscript. Therefore, this perspective further enforces the relevance and
applicability of the novel quantum Markov monogamy inequalities developed. In
fact, there are many indicators for non-Markovian quantum phenomenon as
discussed in Refs. Rivas  _et al._ (2014); Li  _et al._ (2018); Milz and Modi
(2021). However, all of these indicators, in one manner or another, look for
departures from the divisibility of the process, see Ref. Milz and Modi (2021)
for details. This includes the indicators in Refs. Breuer  _et al._ (2016);
Rivas  _et al._ (2014), as well as the quantum data processing inequalities
(QDPIs).

However, for a concrete comparison we note that it is well-known that the non-
Markovian indicator by Breuer et al. Breuer  _et al._ (2016) is strictly
weaker than that due to Rivas et al. Rivas  _et al._ (2014). However, our
QDPIs already include the non-Markovian indicator of Rivas et al. To see this,
we can rewrite Eq. (11) as

$I_{c}(\rho;\Lambda_{t})\geq I_{c}(\rho;\Lambda_{t+dt}).$ (43)

This inequality may be violated for some non-Markovian processes, i.e.,

$I_{c}(\rho;\Lambda_{t+dt})-I_{c}(\rho;\Lambda_{t})>0\quad\\\
\Rightarrow\quad\mbox{non-Markovianity.}$ (44)

Dividing the above equation by $dt$ tells us that when the derivative of the
coherent information $\partial_{t}{I_{c}}(\rho;\Lambda_{t})$ is positive we
have non-Markovianity. Thus, we can define a measure for non-Markovianity as

$\mathcal{N}_{c}:=\max_{\rho}\int_{0}^{T}n_{c}(t)\ dt$ (45)

where the maximization is over all initial input states $\rho$, and

$n_{c}(t)=\max\\{0,\partial_{t}{I_{c}}(\rho;\Lambda_{t})\\}.$ (46)

This is precisely the definition of non-Markovianity by Rivas et al. As there
may be subtle differences in the choice of metric, a detailed comparison
requires a careful study, which is beyond the scope of the present paper. See
Ref. Chruściński  _et al._ (2011) for a detailed comparison between the works
of Bruer et al. and Rivas et al.

The above results are obtained from only one of our QDPIs. Thus, the QMMIs may
be able to see non-Markovianity where all indicators that are reliant on
divisibility are blind.

We note that a similar reasoning can be applied to the QMMI in order to define
a new measure of non-Markovianity. Similarly, our QMMI implies

$[I_{c}(\rho;\Lambda_{t+dt}\circ\Lambda_{s})-I_{c}(\rho;\Lambda_{t}\circ\Lambda_{s})]\\\
-[I_{c}(\Lambda_{s}(\rho);\Lambda_{t+dt})-I_{c}(\Lambda_{s}(\rho);\Lambda_{t})]>0\quad\\\
\Rightarrow\quad\mbox{non-Markovianity for }t>s.$ (47)

Therefore, we can define the new measure for non-Markovianity

$\mathcal{M}_{c}:=\max_{\rho}\int_{t>s}\int_{0}^{T}m_{c}(t)dsdt,$ (48)

with

$m_{c}(s,t)\\\
:=\max\\{0,\partial_{t}[I_{c}(\rho;\Lambda_{t}\circ\Lambda_{s})-I_{c}(\Lambda_{s}(\rho);\Lambda_{t}]\\}.$
(49)

The conjecture on QMMIs in Sec. III.4 suggests how we can build novel non-
Markovianity measures analogously as above. In fact, there is a necessary and
sufficient condition on divisible processes Buscemi and Datta (2016).

The understanding on the limits on processing information in communication
systems is of primal concern in information theory. In this respect, data
processing inequalities have been shown to be of fundamental relevance in the
development of main results in classical information theory Cover and Thomas
(2005). Precisely, the data processing inequality $I(X_{1}:X_{4})\leq
I(X_{2}:X_{3})$ held by four-time-step classical processes, is the
mathematical result supporting the derivation of the converse part of the
channel-coding theorem: there is no reliable asymptotic encoding-decoding
scheme with communication rate larger than the channel capacity. Clearly, the
channel-coding theorem stems as a fundamental result in information science,
and therefore, makes sure the relevance on the development of further
information inequalities. In turn, the Markov monogamy inequalities appears as
constraints on information processing complementary to data processing
inequalities.

On the other hand, quantum processes differ fundamentally from their classical
counterpart, and thus, demand further understanding and analysis. In this
sense, the quantum data processing inequality is regarded as a highly non-
trivial result, and also as one of the pillars in quantum information theory
Nielsen and Chuang (2002). Therefore, it is not clear beforehand that a given
classical information inequality has a quantum counterpart. The same is true
for the Markov monogamy inequalities. The techniques we had to employ to prove
their quantum analogue are completely different from what is used in the
classical case.

To see why this is the case, we notice that in the classical case the proof of
inequalities rely on the existence of a joint probability distribution
$p(x_{1},\dots,x_{n})$ that marginalizes (via a quantifier elimination
implemented by the Fourier-Motzkin algorithm) to the pairwise distribution
$p(x_{i},x_{j})$ used in the definition of the mutual information. In turn, in
the quantum case, since we are dealing with quantum states at different time
steps, there is a priori no joint description. Instead, we have to rely on a
”mixed” description in terms of channels and states, precisely the reason why
we employ the coherent information. Thus, even though our work is motivated by
the classical monogamy inequality, it is not a trivial or natural extension of
it and thus, develops a fundamental link between classical and quantum
information inequalities.

Furthermore, the quantum Markov monogamy inequalities display novel
constraints on the processing of quantum systems, being capable of witnessing
non-Markovianity in a regime where the paradigmatic data processing
inequalities (widely used in the literature) would simply fail to do so.

Now, we consider multitime correlations indicators based on the process
tensor, which are able to also see non-Markovian features in divisible
processes Milz  _et al._ (2019). In what follows, we show how our quantum
Markov monogamy inequalities (QMMIs) are written in terms of multitime
correlations and thus are stronger indicators for quantum non-Markovian
phenomena than the ones due to Breuer et al. Breuer  _et al._ (2016) and Rivas
et al. Rivas  _et al._ (2014).

##  V Quantum stochastic processes

The CDPI and CMMI stem from a well-defined notion of stochastic process,
namely Eq. (1). The quantum inequalities, in contrast, are derived for family
of quantum channels. This raises the question if there is a quantum equivalent
of Eq. (1)? If so, can we derive a larger family of inequalities than the ones
given in the last section?

In this Section, we will work with the process tensor framework, which is a
natural generalisation of Eq. (1) for quantum processes. With this we will
derive another family of QDPIs and QMMIs. Importantly, the set of inequalities
in the previous section will be satisfied by divisible processes Rivas  _et
al._ (2014), even when the process is non-Markovian. This is because they only
account for two-time correlations, and neglect higher-order correlations in
the process Milz  _et al._ (2019). In contrast, the forthcoming family of
inequalities account for multitime correlations and will be capable of
identifying the non-Markovian features in such processes. We begin by first
reviewing the fundamental elements of this framework.

###  V.1 Process Tensor

We now discuss the structure of multitime correlations in the quantum case by
considering an initial reference-system-environment state $\psi$. Before any
dynamical evolution, an intervention with a control operation $\mathrm{A}_{1}$
can be made on the system alone:
$\mathrm{A}_{1}\colon\mathsf{L}(\mathsf{S}_{1})\rightarrow\mathsf{L}(\mathsf{S}_{1}^{\prime})$.
Next, as before, the system-environment state undergoes an evolution
$\mathrm{U}_{1}:\mathsf{L}(\mathsf{S}_{1}^{\prime}\otimes\mathsf{F}_{1})\to\mathsf{L}(\mathsf{S}_{2}\otimes\mathsf{E}_{2})$
and an intervention $\mathrm{A}_{2}$ is then made on the system $\mathsf{S}$
alone. The process repeats and the total state once again evolves due to
$\mathrm{U}_{2}$, followed by a third intervention $\mathrm{A}_{3}$ on
$\mathsf{S}$ alone, and so on up to a final intervention $\mathrm{A}_{4}$ is
performed following $\mathrm{U}_{3}$, see Fig. 4(a). Here, $\mathsf{S}_{i}$ is
isomorphic to $\mathsf{S}_{i}^{\prime}$ for any interventional time-step
$i=1,2,3$.

The interventions $\\{\mathrm{A}_{j}\\}$ are any physically implementable
operation, which can be thought of a generalised measurement with possible
corresponding outcomes $\\{x_{j}\\}$. Mathematically, these are known as
instruments Davies and Lewis (1970) and represented by a collection of
completely positive maps $\mathcal{J}:=\\{\mathrm{A}_{x_{j}}\\}$ such that
$\sum_{x_{j}}\mathrm{A}_{x_{j}}$ is trace preserving.

Figure 4: Process Tensor. The top panel shows a quantum circuit that accounts
for multitime correlations for observables
$\mathrm{A}_{1},\cdots,\mathrm{A}_{4}$, i.e. Eq. (LABEL:eq:qtocl). The object
in the dotted line is called the process tensor, defined in Eq. (53). It is
drawn in isolation in the bottom panel, uniquely characterised the process.

The above machinery straightforwardly allows for the calculation of the
probability to observe a sequence of quantum events $(x_{k},\dots x_{1})$,
corresponding to a choice of instruments
$\\{\mathcal{J}_{k},\dots,\mathcal{J}_{1}\\}$, as

$\displaystyle\begin{split}&p(x_{k},\dots,x_{1}\,|\,\mathcal{J}_{k},\dots,\mathcal{J}_{1})=\\\
&\qquad\mbox{tr}[\mathrm{A}_{x_{k}}\mathrm{U}_{k-1}\\!\cdots\mathrm{U}_{1}\mathrm{A}_{x_{1}}(\psi)].\end{split}$
(50)

This is depicted in Fig. 4(a). Here, the LHS is akin to a classical joint
probability distribution. We can identify the quantum stochastic process by
rewriting the RHS as

$\displaystyle\mbox{tr}[\mathrm{A}_{x_{k}}\mathrm{U}_{k-1}\\!\cdots\mathrm{U}_{1}\mathrm{A}_{x_{1}}(\psi)]=\mbox{tr}[\Upsilon_{k:1}\mathbf{A}^{\rm
T}_{k:1}]$ (51) with
$\displaystyle\mathbf{A}_{k:1}\\!:=\\!\mathrm{A}_{x_{k}}\\!\otimes\\!\dots\otimes\mathrm{A}_{x_{1}}$
(52) and
$\displaystyle\Upsilon_{k:1}\\!:=\\!\mbox{tr}_{B}[\mathrm{U}_{k}\star\dots\mathrm{U}_{1}\star\psi]$
(53)

where ${\rm T}$ denotes transposition and $\star$ denotes the link product,
defined as a matrix product on the space $E$ and a tensor product on space $S$
Chiribella  _et al._ (2009). Here, $\mathrm{U}$ and $\mathrm{A}$ are the Choi
operators of the corresponding transformations. The important feature here is
the clear separation of the interventions $\mathbf{A}_{k:1}$ from the
influences due to the bath, which are packaged in the process tensor
$\Upsilon_{k:1}$ Pollock  _et al._ (2018a, b); Costa and Shrapnel (2016).

The process tensor is depicted inside the red-dotted line in Fig. 4(b), and
usually denoted by its _Choi state_ $\Upsilon_{k:1}$ Milz and Modi (2021). It
is the quantum generalisation of the joint classical probability distribution
and unambiguously represents a quantum stochastic process Milz  _et al._
(2020a), and reduces to the classical case in the right limits Strasberg and
Díaz (2019); Milz  _et al._ (2020b). It contains all accessible multitime
correlations Ringbauer  _et al._ (2015); White  _et al._ (2020, 2021a).

Figure 5: Markov process tensor. The top panel shows a quantum circuit for a
Markovian process, in presence of interventions. This clearly reduces to what
we posit a Markov process in the previosu section.

An important result that stems from the process tensor formalism is a
necessary and sufficient condition for quantum Markov processes Pollock  _et
al._ (2018b); Costa and Shrapnel (2016). Namely, Markovian processes are those
satisfying the following property: any $k$-time process tensor factorises as

$\displaystyle\Upsilon_{k:1}=\mathrm{L}_{k-1}\otimes\cdots\otimes\mathrm{L}_{2}\otimes\mathrm{L}_{1}\otimes\rho,$
(54)

where $\mathrm{L}_{j}$ are the Choi operators of the CPTP maps $\Lambda_{j}$
as before. See Fig. 5 for a graphical depiction.

It is possible to show that when a quantum process is Markovian, and the
interventions are rank-one projective measurements, then the resulting
distribution in Eq. (LABEL:eq:qtocl) will be a Markovian distribution 222A
coarse (higher-rank projection) measurement can hide memory in the degenerate
subspace, even if the process is Markovian, see Taranto  _et al._ (2019).. We
readily get an infinite family of CDPI and CMMI. We, of course, also get the
QDPIs and QMMI from the last section.

The above Markov condition means that we can deduce a process to be non-
Markovian by looking for correlations. In the last section, the QDPIs and QMMI
are constructed by considering two-time correlations; but in general, we can
certainly look at higher-order correlations. With this in mind, we aim to find
a family of more general inequalities by exploiting the structure of quantum
stochastic processes. In particular, we will show that the inequalities of the
last section cannot differentiate divisible processes from Markovian ones. The
forthcoming inequalities will not have this limitation.

###  V.2 Choi state DPIs

We first consider a family of QDPIs for a four step quantum process as before.
However, we now label the space of the process tensor as
$(\mathsf{R}_{0},\mathsf{S}_{1},\mathsf{R}_{1};\mathsf{S}_{2},\mathsf{R}_{2};\mathsf{S}_{3},\mathsf{R}_{3};\mathsf{S}_{4})$,
see Fig. 4 for an illustration. The advantage we now have is that we can
intervene in a physically allowed form. For instance, at a given time we may
throw away the system, say $\mathsf{S}_{1}$, and replace it with a new system
with its own reference $\mathsf{R}_{1}$. This allows us to construct DPIs on
the future dynamics without worrying about the output states of the past
dynamics.

This is clearly desirable in several situations. For instance, consider a
process where $\Lambda_{1}$ is a fully depolarising process, but the
subsequent process is rich in structure. In such cases, why should we limit
ourselves to only the output of $\Lambda_{1}$? In such instances we would
simply swap out the output of $\Lambda_{1}$ with a more coherent state.

We now construct a family of QDPIs based on the Choi states of a Markov
process. To do so, first note that the mutual information of a bipartite state
$\rho$ can be expressed as a quantum relative entropy

$\displaystyle\begin{split}I(\mathsf{A}:\mathsf{B})_{\rho_{AB}}&=S[\rho_{AB}\|\rho_{A}\otimes\rho_{B}]\\\
&=\Tr[\rho_{AB}\\{\log(\rho_{AB})-\log(\rho_{A}\otimes\rho_{B})\\}].\end{split}$
(55)

Next, note that quantum relative entropy is contractive under the action of
CPTP maps. We can thus derive the following QDPIs when the process is Markov:

$\displaystyle I(\mathsf{R}_{1}:\mathsf{S}_{2})\geq
I(\mathsf{R}_{1}:\mathsf{S}_{3})\geq I(\mathsf{R}_{1}:\mathsf{S}_{4})$ (56)
$\displaystyle I(\mathsf{R}_{2}:\mathsf{S}_{3})\geq
I(\mathsf{R}_{2}:\mathsf{S}_{4}).$ (57)

Here, we have allowed for interventions $\mathrm{A}_{k}$ at the intermediate
times.

The mutual information above is defined on any input state. We now restrict
ourselves to inserting one half of a maximally entangled state in the first
port and computing the quantum mutual information between the other half and
what comes out at the final port. In other words, we are restricting ourselves
to the Choi states of the process. Notice that this reduces to the usual
classical case when we dephase in a local bases and the intermediate operators
$\mathrm{A}_{k}$ become the classical identity channels.

This allows us to derive another set of QDPIs by using the fact that the
quantum relative entropy is contractive under CP maps Petz (2003). Consider
the process from $\mathsf{R}_{1}$ to $\mathsf{S}_{3}$ and compare that to the
process from $\mathsf{R}_{2}$ to $\mathsf{S}_{3}$. The Choi state for the
former is $\Lambda_{2}\circ\mathrm{A}_{2}\circ\Lambda_{1}(\Psi^{+})$.
Graphically we can represent this as top panel in Fig. 6, which we can
transform into the bottom panel by simply sliding the boxes, where we have
added an identity channel $\mathsf{id}_{1}$. Let us compare that to the
process in the third panel, which indeed the Choi state for the process from
$\mathsf{R}_{2}$ to $\mathsf{S}_{3}$. Since the two processes differ by
actions of CP maps on the the bottom leg we have

$\displaystyle I(\mathsf{R}_{2}:\mathsf{S}_{3})\geq
I(\mathsf{R}_{1}:\mathsf{S}_{3}).$ (58)

We have given a graphical proof in Fig. 6, and also see App. .6. By same
argument we can also derive

$\displaystyle I(\mathsf{R}_{3}:\mathsf{S}_{4})\geq
I(\mathsf{R}_{2}:\mathsf{S}_{4})\geq I(\mathsf{R}_{1}:\mathsf{S}_{4}).$ (59)

By choosing the $\mathrm{A}$’s to be rank-one projections we recover classical
processes. For all such processes we can derive the Markov monogamy condition
$\mathrm{M4}$.

Note that for the quantum case we have twice the number of legs than for
classical case. In the classical case we just have $\\{1,2,3,4\\}$, which
means that we have total of six mutual informations and fifteen pairwise
relations between these mutual information. Most of these are not independent,
thus we wind up with four QDPIs and QMMI. In the quantum case we have
$\\{\mathsf{S}_{1},\mathsf{R}_{1};\mathsf{S}_{2},\mathsf{R}_{2};\mathsf{S}_{3},\mathsf{R}_{3};\mathsf{S}_{4}\\}$.
Therefore we have 21 mutual informations. Of these six are vanishing because
of causality, i.e., $I(\mathsf{R}_{y}:\mathsf{S}_{x})=0$ for all $y\geq x$
Milz and Modi (2021). For a Markov process we can require the $\mathsf{R}$
spaces to be independent, leading to three more vanishing constraints,
$I(\mathsf{R}_{x}:\mathsf{R}_{y})=0$. This requirement also means
$I(\mathsf{S}_{x}:\mathsf{S}_{y})=0$, that means six more vanishing mutual
information. We are then left with exactly the same six non-trivial mutual
informations as in the classical case.

Figure 6: Choi state data processing inequalities. We can derive an anaologue
of DPIs from the previous section by using contractivity of quantum relative
entropy and some identities of actions of CPTP maps on the maximally entangled
state $\Psi^{+}$.

###  V.3 Multitime quantum Markov monogamy inequalities

Here, we will present several families of quantum Markov monogamy
inequalities. Their importance is highlighted by the fact that the QDPIs and
the QMMI presented in the last section would all be satisfied for divisible
non-Markovian processes. Here, we allow for interventions onto the process,
which enables the detection temporal correlations that lie in divisible
processes, see Ref. Milz  _et al._ (2019) for explicit examples. To construct
the family of QMMI we will follow the circuits in Fig. 7.

The first family will be defined in terms of the following definition of
coherent information

$\displaystyle
I_{q_{1}}(j;k):=H(\mathsf{S}_{j},\mathsf{R}_{j})-H(\mathsf{S}_{j},\mathsf{R}_{j},\mathsf{S}_{k}).$
(60)

Again, the space relevant for entropies in the last equation are labelled in
Fig. 7.

######  Theorem 3 (Multitime quantum Markov monogamy in equality (MQMMI-1)).

For any Markov process tensor $\Upsilon_{4:1}$, it holds that

$\displaystyle I_{q_{1}}(1;4)+I_{q_{1}}(2;3)\geq
I_{q_{1}}(1;3)+I_{q_{1}}(2;4),$ (61)

with the intervention $\mathrm{A_{j}}$ in $I_{q_{1}}(j;k)$ defined by the
purification of the system $\mathsf{S}_{j}$.

###### Proof.

The above theorem considers a setup that allows for interventions
$\mathrm{A}_{j}$ along the way. For simplicity, let us first consider the
interventions to be identity operations.

For Markov process we have
$H(\mathsf{S}_{j},\mathsf{R}_{j})=H(\mathsf{S}_{j})+H(\mathsf{R}_{j})$ and
$H(\mathsf{S}_{j},\mathsf{R}_{j},\mathsf{S}_{k})=H(\mathsf{S}_{j})+H(\mathsf{R}_{j},\mathsf{S}_{k})$.
Next, we define a dilation of each quantum channel $\Lambda_{i}$ as done in
Eq. (14). Now, note the definition of $I_{q}$ in in Eq. (60) becomes

$\displaystyle
I_{q_{1}}(1;4)=H(\mathsf{R}_{1})-H(\mathsf{E}_{1},\mathsf{E}_{2},\mathsf{E}_{3});$
(62) $\displaystyle I_{q_{1}}(2;3)=H(\mathsf{R}_{2})-H(\mathsf{E}_{2});$ (63)
$\displaystyle
I_{q_{1}}(1;3)=H(\mathsf{R}_{1})-H(\mathsf{E}_{1},\mathsf{E}_{2});$ (64)
$\displaystyle
I_{q_{1}}(2;4)=H(\mathsf{R}_{2})-H(\mathsf{E}_{2},\mathsf{E}_{3}).$ (65)

The rest of the proof then simply follows as before as long as the entropies
in the second terms in each of the above equations comes from an environment
state $\rho_{E_{1},E_{2},E_{3}}$. To ensure this we also require that
$\psi_{i}$ must be purification of $\rho_{i}$, for $i\in\\{1,2\\}$.

Now, let us consider the case where interventions $\mathrm{A}_{j}$ are
arbitrary (CPTP maps). Let $\alpha_{j}$ be the Hilbert space associated with
the environmental system related to the isometric extension of
$\mathrm{A}_{j}$. Then the second terms in the last set of equations becomes

$\displaystyle
H(\mathsf{E}_{1},\alpha_{2},\mathsf{E}_{2},\alpha_{3},\mathsf{E}_{3},\alpha_{4})\to
H(\tilde{\mathsf{E}}_{1},\tilde{\mathsf{E}}_{2},\tilde{\mathsf{E}}_{3});$ (66)
$\displaystyle H(\mathsf{E}_{2},\alpha_{3})\to H(\tilde{\mathsf{E}}_{2});$
(67) $\displaystyle H(\mathsf{E}_{1},\alpha_{2},\mathsf{E}_{2},\alpha_{3})\to
H(\tilde{\mathsf{E}}_{1},\tilde{\mathsf{E}}_{2});$ (68) $\displaystyle
H(\mathsf{E}_{2},\alpha_{3},\mathsf{E}_{3},\alpha_{4})\to
H(\tilde{\mathsf{E}}_{2},\tilde{\mathsf{E}}_{3}).$ (69)

Here, we have redefine
$\tilde{\mathsf{E}}_{1}:=\mathsf{E}_{1}\otimes\alpha_{2}$,
$\tilde{\mathsf{E}}_{2}:=\mathsf{E}_{2}\otimes\alpha_{3}$, and
$\tilde{\mathsf{E}}_{3}:=\mathsf{E}_{3}\otimes\alpha_{4}$. Once we absorbed
$\alpha_{1}$ into the initial state, the rest of the proof then simply follows
as before, using the strong subadditivity of quantum entropy. ∎

Figure 7: Quantum Markov monogamy information with memory. The variations in
coherent information given in Eqs. (60,70,71) account for the memory due to
the past. This figure displays how the spaces that one needs to account for.

One might now wonder, why we had to redefine coherent information in Eq. (60)
to accommodate interventions. The reason is not new. If one wants to
operationally witness QMMI given in Eq. (13), then the state of the system
must be swapped with an identical copy whose purification remains in our
possession. We can of course do the same here to redefine coherent information
as

$\displaystyle
I_{q_{2}}(j;k):=H(\mathsf{S}_{k})-H(\mathsf{S}_{j},\mathsf{R}_{j},\mathsf{S}_{k}).$
(70)

Once again, $\psi_{i}$ must be purification of $\rho_{i}$, for
$i\in\\{1,2\\}$. The big difference is that we now also account for the
entropy of space $\mathsf{S}_{j}$, which, for non-Markovian processes, via
initial correlations plays a non-trivial role. In this sense, the last
equation accounts for not just tripartite correlations Modi (2012);
Vinjanampathy and Modi (2015), as before we only dealt with bipartite
correlations. Yet, another possibility is the following

$\displaystyle
I_{q_{3}}(j;k):=H(\mathsf{S}_{j},\mathsf{S}_{k})-H(\mathsf{S}_{j},\mathsf{R}_{j},\mathsf{S}_{k}).$
(71)

Here, too we must have that $\psi_{i}$ must be purification of $\rho_{i}$, for
$i\in\\{1,2\\}$. And here, again, we account for tripartite correlations thus
this a more powerful version of MQMMI. The proof for the MQMMI for the above
two equations follows the same path as the last two proofs and we omit the
details. Note that we could have kept $\mathsf{R}_{0}$ in the above
definition, and there are many other alternatives.

A couple of remarks are in order at this stage. Firstly, all of these MQMMI
yield the same value for a Markov processes, including the QMMI inequality
from the previous section. All three version of the MQMMI above require that a
state fed into the process at an intermediate stage must be a purification of
the previous output state. This is required so that the strong-subaditivity
inequalities can be applied. While this is the same requirement as the QMMI
inequality in the previous section, the last three version should be able to
account for non-Markovianity even in divisible processes Milz  _et al._
(2019). This is because, they are designed to account for multitime
correlations.

We can just as well construct multitime QDPIs with the three definitions of
coherent information above. In fact, one can also use the above definitions in
the classical case. The key point is that these constructions account for
multitime correlations by allowing for multitime entropies. In contrast to the
classical case, multitime entropies will be stronger indicators of non-
Markovianity when quantum entanglement in time Giarmatzi and Costa (2021);
Milz  _et al._ (2021); White  _et al._ (2021b) is present in the process,
which may serve as an important diagnostic tool.

###  V.4 Violation of the Multitime Quantum Markov monogamy inequalities

Now we consider the interventional approach present in the MQMMIs in order to
witness the non-Markovian beheviour of the process represented in Fig. 3.

Allowing for interventions, the non-Markovian process represented in Fig. 3 is
then described by the process tensor represented in Fig. 4. Furthermore, we
set here a process tensor according to the bottom panel of Fig. 4 by defining
the initial state $\psi$ as in Eq. (30) and joint system-environment
operations
$\mathrm{U}_{i}(\bullet)=U_{\lambda}(\bullet)U_{\lambda}^{\dagger}$, for
$i=1,2,3$, with $U_{\lambda}$ defined in Eq. (31).

The MQMMIs defined with respect to the quantities in Equations (60,70,71) lead
to the definition of the interventional witnesses of non-Markovianity:

$\mathrm{M4}_{q_{i}}\coloneqq
I_{q_{i}}(1;4)+I_{q_{i}}(2;3)-I_{q_{i}}(1;3)-I_{q_{i}}(2;4),$ (72)

with $i=1,2,3$. The quantities defined above are positive semi-definite for
any Markov process tensor, independently of the interventional scheme adopted.
Thus, finding a negative value for any $\mathrm{M4}_{q_{i}}$ (i=1,2,3) implies
the process is non-Markovian. In Fig. 8 we present the plot for the witnesses
in Eq. (72) for the process tensor mentioned above.

Figure 8: Violation of the MQMMIs. Multitime quantum Markov monogamy with
respect to $I_{q_{1}}$ is not violated only for the region
$0.30\leq\lambda\leq 0.55$. The MQMMIs with respect to $I_{q_{2}}$ and
$I_{q_{3}}$ are violated for any value of $\lambda$, thus perfectly witnessing
the non-Markovianity of the process considered.

##  VI Conclusion

Firstly, using the approach introduced in Schumacher and Nielsen (1996) we
have extended the conjecture on classical Markov monogamy inequalities to the
quantum case. We also proved that the Markov monogamy inequalities may be
violated by a non-Markovian quantum process satisfying all the quantum data
processing inequalities. This is done by considering concrete examples.

Secondly, we have also considered how to apply the novel quantum Markov
monogamy inequalities to the process tensor formalism, which accounts for
multitime quantum correlations. This provides an interesting interventional
approach to quantum data processing, and thus adding extra relevance to the
results.

The resources involved within witnessing non-Markovianity with QMMIs and
MQMMIs are not equivalent. Generally, characterizing non-Markov phenomena with
QMMIs involves assessing reference-environment systems. Distinctly, the MQMMIs
do not requires this strong requirement, and only depend upon the system’s
properties. Nevertheless, it requires feeding intermediate steps of the
process with the purification of the previous state of the system. Thus, we
claim it is not fair to compare the results relying this two approaches on an
equal footing.

Quantum data processing theorems have been widely studied in the theory of
quantum information. In particular, the QDPI in Eq. (11) has been shown to
have a relevant interpretation: the local evolution of a quantum system can be
cast as a completely positive and trace preserving operation if and only if
the QDPI is satisfied Buscemi (2014). A stronger operation interpretation for
these new inequalities is still missing so far, and is left for future
studies.

Finally, it is worthy mentioning that the quantum information inequalities we
discovered have the potential to be related with novel recovery operations.
This is supported by the existence of an operational interpretation of the
quantum data processing inequality. In the original formulation in Ref.
Schumacher and Nielsen (1996), the authors used the quantum data processing
inequality to show that, given an initial state $\rho$ and a quantum channel
$\Lambda$, there is a recovery operation $\mathrm{R}$ such that
$\mathrm{R}(\Lambda(\rho))=\rho$ if and only if
$I_{c}(\rho;\mathrm{id})=I_{c}(\rho;\Lambda)$. Therefore, this suggests the
novel QMMIs could be also related to limits on the quantum processing of
information. One possible direction would be providing similar operational
meaning to the quantum Markov monogamy inequalities in terms of memory
strength and quantum recovery procedure Milz  _et al._ (2020b). We leave the
study of operational properties of the Markov monogamy inequalities to future
work.

###### Acknowledgements.

MC and LCC acknowledge the financial support from funding agencies CNPq, FAPEG
and the Brazilian National Institute of Science and Technology of Quantum
Information (INCT- IQ). This study was financed in part by the Coordenação de
Aperfeiçoamento de Pessoal de Nível Superior – Brasil (CAPES) – Finance Code
001. MC also acknowledges the warm hospitality of the School of Mathematics
and Physics at the University of Queensland, where initial part of this study
was developed. Special thanks are expressed to Kaumudibikash Goswami, with
whom MC had inspiring discussions. RC acknowledge the support of the John
Templeton Foundation (grant Q-CAUSAL No 61084), the Serrapilheira Institute
(grant number Serra – 1708-15763), CNPq via the INCT-IQ and Grants No.
406574/2018-9 and 307295/2020-6, the Brazilian agencies MCTIC and MEC. KM is
supported through Australian Research Council Future Fellowship FT160100073,
Discovery Projects DP210100597 & DP220101793, and the International Quantum U
Tech Accelerator award by the US Air Force Research Laboratory.

## Appendix

###  .1 Proof of the data processing theorem and its equivalence with the
monotonicity condition of quantum mutual information

We start by considering the proof of the quantum data processing theorem in
Schumacher and Nielsen (1996).

######  Theorem 4 (Quantum data processing inequality Schumacher and Nielsen
(1996)).

Let $\rho$ be a quantum state of $\mathsf{S}_{1}$, and
$\Lambda_{1}\colon\mathsf{L}(\mathsf{S}_{1})\rightarrow\mathsf{L}(\mathsf{S}_{2}),\Lambda_{2}\colon\mathsf{L}(\mathsf{S}_{2})\rightarrow\mathsf{L}(\mathsf{S}_{3})$
be quantum channels. It holds that

$I_{c}(\rho;\Lambda_{1})\geq I_{c}(\rho;\Lambda_{2}\circ\Lambda_{1}).$ (73)

###### Proof.

Let the state $\rho$ be purified to $\psi$ in
$\mathsf{L}(\mathsf{R}\otimes\mathsf{S}_{1})$. Let the quantum channels be
dilated according to

$\Lambda_{1}(\sigma_{1})=\Tr_{\mathsf{E}_{1}}\left[U_{1}(\sigma_{1}\otimes\varphi_{1})U_{1}^{\dagger}\right]$
(74)

and

$\Lambda_{2}(\sigma_{2})=\Tr_{\mathsf{E}_{2}}\left[U_{2}(\sigma_{2}\otimes\varphi_{2})U_{2}^{\dagger}\right],$
(75)

for any operators $\sigma_{1}$ and $\sigma_{2}$ in
$\mathsf{L}(\mathsf{S}_{1})$ and $\mathsf{L}(\mathsf{S}_{2})$, respectively.
The linear transformations
$U_{1}\colon\mathsf{S}_{1}\otimes\mathsf{F}_{1}\rightarrow\mathsf{S}_{2}\otimes\mathsf{E}_{1}$
and
$U_{2}\colon\mathsf{S}_{2}\otimes\mathsf{F}_{2}\rightarrow\mathsf{S}_{3}\otimes\mathsf{E}_{2}$
are unitary operators, and the pure quantum states $\varphi_{1}$ and
$\varphi_{2}$ are in $\mathsf{L}(\mathsf{F}_{1})$ and
$\mathsf{L}(\mathsf{F}_{2})$, respectively. Consider the following
mathematical assertions with respect to the process represented in Fig. 9.

$\mathsf{R}\otimes\mathsf{E}_{1}\otimes\mathsf{E}_{2}\otimes\mathsf{S}_{3}\,\text{is
pure}\Rightarrow
H(\mathsf{R},\mathsf{E}_{1},\mathsf{E}_{2})=H(\mathsf{S}_{3});$ (76)
$\mathsf{R}\otimes\mathsf{E}_{1}\otimes\mathsf{S}_{2}\,\text{is
pure}\Rightarrow\;H(\mathsf{R},\mathsf{E}_{1})=H(\mathsf{S}_{2});$ (77)
$H(\mathsf{R},\mathsf{S}_{2})=H(\mathsf{E}_{1});$ (78)
$H(\mathsf{R},\mathsf{S}_{3})=H(\mathsf{E}_{1},\mathsf{E}_{2}).$ (79)

$\psi$$\varphi_{1}$$\varphi_{2}$$U_{1}$$U_{2}$$\mathsf{R}$$\mathsf{R}$$\mathsf{R}$$\mathsf{S}_{1}$$\mathsf{S}_{2}$$\mathsf{S}_{3}$$\mathsf{F}_{1}$$\mathsf{E}_{1}$$\mathsf{E}_{1}$$\mathsf{F}_{2}$$\mathsf{F}_{2}$$\mathsf{E}_{2}$

Figure 9: Diagram representing the purified process
$\rho_{1}\stackrel{{\scriptstyle\mathclap{\mbox{$\Lambda_{1}$}}}}{{\longrightarrow}}\rho_{2}\stackrel{{\scriptstyle\mathclap{\mbox{$\Lambda_{2}$}}}}{{\longrightarrow}}\rho_{3}$.
The diagram displays the pure final state obtained by acting successively the
isometric representations $U_{i}(\bullet\otimes\ket{\varphi_{i}})$ of
$\Lambda_{i}$ (with $i=1,2$) on the purification $\psi$ of $\rho$.

Then, we have that the strong subadditivity inequality

$H(\mathsf{R},\mathsf{E}_{1},\mathsf{E}_{2})+H(\mathsf{E}_{1})\leq
H(\mathsf{R},\mathsf{E}_{1})+H(\mathsf{E}_{1},\mathsf{E}_{2})$ (80)

and Equations (76,77,78,79) imply the desired data processing inequality. ∎

Now we are ready to prove the equivalence of Theorem 4 with the monotonicity
of quantum mutual information under local operations. Nevertheless, we state
first a simple result considered in this derivation.

######  Lemma 1 (Proposition 2.29 in Watrous (2018)).

Let $\psi$ be a pure state of $\mathsf{R}\otimes\mathsf{S}_{1}$, and let
$\rho$ be any state of $\mathsf{R}\otimes\mathsf{S}_{2}$ for which
$\Tr_{\mathsf{S}_{1}}[\psi]=\Tr_{\mathsf{S}_{2}}[\rho]$. Then there is a
quantum channel
$\Lambda\colon\mathsf{L}(\mathsf{S}_{1})\rightarrow\mathsf{L}(\mathsf{S}_{2})$
such that $\rho=(\mathrm{id}_{\mathsf{R}}\otimes\Lambda)(\psi)$.

######  Proposition 1.

The following sentences are equivalent:

  1. (A)

The data processing inequality (73) holds for any quantum state $\rho$ of
$\mathsf{S}_{1}$, and for any quantum channels
$\Lambda_{1}\colon\mathsf{L}(\mathsf{S}_{1})\rightarrow\mathsf{L}(\mathsf{S}_{2})$
and
$\Lambda_{2}\colon\mathsf{L}(\mathsf{S}_{2})\rightarrow\mathsf{L}(\mathsf{S}_{3})$;

  2. (B)

For any quantum state $\sigma$ of a bipartite system
$\mathsf{A}\otimes\mathsf{B}$, and for any quantum operation
$\Lambda\colon\mathsf{L}(\mathsf{B})\rightarrow\mathsf{L}(\mathsf{C})$, it
holds that quantum mutual information is monotonically decreasing under the
action of the local operation $\Lambda$. That is,

$I(\mathsf{A}:\mathsf{B})_{\sigma}\geq
I(\mathsf{A}:\mathsf{C})_{(\mathrm{id}\otimes\Lambda)(\sigma)}.$ (81)

###### Proof.

The assertion $(B)\Rightarrow(A)$ is clearly true. Suppose $(A)$ is true. Then
let $\rho$ be the state of an arbitrary quantum system $\mathsf{S}_{1}$, and
$\psi$ be a purification with respect to a bipartite system
$\mathsf{R}\otimes\mathsf{S}_{1}$. Consider also arbitrary quantum channels
$\Lambda_{1}\colon\mathsf{L}(\mathsf{S}_{1})\rightarrow\mathsf{L}(\mathsf{S}_{2})$
and
$\Lambda_{2}\colon\mathsf{L}(\mathsf{S}_{2})\rightarrow\mathsf{L}(\mathsf{S}_{3})$.
Since $(A)$ is true by hypothesis, and
$\sigma\coloneqq(\mathrm{id}_{\mathsf{R}}\otimes\Lambda_{1})(\psi)$ is a state
of the bipartite system $\mathsf{R}\otimes\mathsf{S}_{2}$, we have

$I(\mathsf{R}:\mathsf{S}_{2})_{\sigma}\geq
I(\mathsf{R}:\mathsf{S}_{2})_{(\mathrm{id}_{\mathsf{R}}\otimes\Lambda_{2})(\sigma)}.$
(82)

Thus, subtracting $H(\mathsf{R})$ from both sides of Eq. (82) we have the
desired inequality

$I_{c}(\rho;\Lambda_{1})\geq I_{c}(\rho;\Lambda_{2}\circ\Lambda_{1}),$ (83)

for arbitrary $\rho$, $\Lambda_{1}$ and $\Lambda_{2}$.

Now, let us prove $(A)\Rightarrow(B)$ is true. So suppose $(A)$ is true.
Following the derivation of $(B)\Rightarrow(A)$ we see that in order to prove
its converse statement all we need to do is to prove that all bipartite
quantum states can be written as
$\sigma\coloneqq(\mathrm{id}_{\mathsf{R}}\otimes\Lambda_{2})(\psi)$ for some
pure state $\psi$ of a bipartite system, and quantum channel $\Lambda_{1}$.
Then, we can add $H(\mathsf{R})$ to both sides of Eq. (83) and we are done. So
let $\rho$ be an arbitrary quantum state of any bipartite quantum system
$\mathsf{R}\otimes\mathsf{S}_{2}$. Take its marginal with respect to the
system $\mathsf{R}$, that is, $\tau\coloneqq\Tr_{\mathsf{R}}[\rho]$. Now let
$\psi$ be a purification of $\tau$ with respect to a purification system
$\mathsf{S}_{1}$ such that $\psi\in\mathsf{R}\otimes\mathsf{S}_{1}$. Thus we
have proved the existence of a pure quantum state $\psi$ for which
$\Tr_{\mathsf{S}_{1}}[\psi]=\Tr_{\mathsf{S}_{2}}[\rho]$. Now, using Lemma 1 we
make sure the existence of a quantum channel
$\Lambda_{1}\colon\mathsf{L}(\mathsf{S}_{1})\rightarrow\mathsf{L}(\mathsf{S}_{2})$
fulfilling the desired property. ∎

###  .2 Quantum data processing inequalities for four-time-step Markovian
processes

We argue here on the possible validity of the data processing inequalities not
considered in Subsection III.3. We also show that the DPIs not appearing in
Fig. 2 do not witness the non-Marovianity of our example, and thus are
irrelevant in this case.

One would expect for each DPI to have a valid quantum version in terms of
coherent information. For instance, it is expected that the inequality

$I_{c}(\Lambda_{1}(\rho);\Lambda_{2})\geq
I_{c}(\rho;\Lambda_{2}\circ\Lambda_{1})$ (84)

constrains three-time-step quantum processes. This would be the quantum
version of the CDPI given by $I(X_{2}:X_{3})\geq I(X_{1}:X_{3})$, holding for
any three-time-step classical process. Equation (84) is clearly equivalent to
the condition

$H(\mathsf{E}_{1}|\mathsf{E}_{2})\geq 0,$ (85)

where conditional entropy is computed on any quantum state of the form
presented in Fig. 9.

It is well known that the conditional quantum entropy may be negative, in
contrast to its classical counterpart. This is indeed the case when the
quantum state considered is maximally entangled, for instance. Although, it is
not clear that this behavior may appear from the quantum state arising from a
Markov process. The plot of Fig. 10 shows that taking $U_{1},U_{2}$ to be the
operation of Eq. (31), and quantum states $\psi=\Psi^{+}$,
$\varphi_{1}=\varphi_{2}=\ket{0}$, the condition in Eq. (84) is satisfied for
any value of $0\leq\lambda\leq 1$. That is, the quantity

$\mathrm{DP}_{5}\coloneqq
I_{c}(\Lambda_{1}(\rho);\Lambda_{2})-I_{c}(\rho;\Lambda_{2}\circ\Lambda_{1})$
(86)

is positive for any value of $\lambda$.

We note there is no strong subaditivity solely implying Eq. (85), and we leave
its proof as a future study.

Figure 10: Non-violation of $\mathrm{DP}_{5}$. The quantity defined in Eq.
(86) is non-negative for the Markov process in Fig. 9 with $\psi$ being the
maximally entangled state, and $U_{1},U_{2}$ the operator defined in Eq. (31).

In Appendix .1, we have proved the quantities defined in Equations (25-29) are
non-negative for all four-time-step quantum Markov processes. Now, supposing
every classical DPI has a valid quantum version, we would have the following
extra constraints:

$\displaystyle\mathrm{DP}_{6}\coloneqq$ $\displaystyle
I_{c}(\Lambda_{1}(\rho);\Lambda_{2})-I_{c}(\rho;\Lambda_{3}\circ\Lambda_{2}\circ\Lambda_{1});$
(87) $\displaystyle\mathrm{DP}_{7}\coloneqq$ $\displaystyle
I_{c}(\Lambda_{1}(\rho);\Lambda_{3}\circ\Lambda_{2})-I_{c}(\rho;\Lambda_{3}\circ\Lambda_{2}\circ\Lambda_{1});$
(88) $\displaystyle\mathrm{DP}_{8}\coloneqq$ $\displaystyle
I_{c}(\Lambda_{2}\circ\Lambda_{1}(\rho);\Lambda_{3})-I_{c}(\rho;\Lambda_{3}\circ\Lambda_{2}\circ\Lambda_{1});$
(89) $\displaystyle\mathrm{DP}_{9}\coloneqq$ $\displaystyle
I_{c}(\Lambda_{2}\circ\Lambda_{1}(\rho);\Lambda_{3})-I_{c}(\Lambda_{1}(\rho);\Lambda_{3}\circ\Lambda_{2}).$
(90)

Moreover, for the example considered in Subsection III.3, the DPIs in
Equations (86,87,88) do not witness the non-Markovian behaviour of the
process. See Fig. 11. The remaining inequalities in Equations (89,90) involve
terms related to a bipartite environmental system, and thus cannot be applied
to our example.

Figure 11: Non-violation of $\mathrm{DP_{5}}$, $\mathrm{DP_{6}}$ and
$\mathrm{DP_{7}}$ for the non-Markov process considered in Subsec. III.3. The
quantities defined in Eq.s (86,87,88) are positive for the processes described
by Eq.s (32,33,34,35) and represented in Fig. 3.

###  .3 Quantum Markov monogamy theorem as the monotonicity of conditional
quantum mutual information

Now the Markov monogamy inequalities are subjected to close scrutiny. This
section deals with the monogamy inequality of four-time-step Markovian
processes.

######  Proposition 2.

The following sentences are equivalent:

  1. (A)

The Monogamy inequality (13) holds for any quantum state $\rho$ of
$\mathsf{S}_{1}$, and for any quantum channels
$\Lambda_{1}\colon\mathsf{L}(\mathsf{S}_{1})\rightarrow\mathsf{L}(\mathsf{S}_{2})$,
$\Lambda_{2}\colon\mathsf{L}(\mathsf{S}_{2})\rightarrow\mathsf{L}(\mathsf{S}_{3})$
and
$\Lambda_{3}\colon\mathsf{L}(\mathsf{S}_{3})\rightarrow\mathsf{L}(\mathsf{S}_{4})$;

  2. (B)

For any quantum state $\sigma$ of a tripartite system
$\mathsf{A}\otimes\mathsf{B}\otimes\mathsf{C}$, and for any quantum operation
$\Lambda\colon\mathsf{L}(\mathsf{B})\rightarrow\mathsf{L}(\mathsf{D})$, it
holds that conditional quantum mutual information is monotonically decreasing
under the action of a local operation $\Lambda$. That is,

$I(\mathsf{A}:\mathsf{B}|\mathsf{C})_{\sigma}\geq
I(\mathsf{A}:\mathsf{D}|\mathsf{C})_{(\mathrm{id}\otimes\Lambda\otimes\mathrm{id})(\sigma)}.$
(91)

###### Proof.

The proof is similar to the one of Proposition 1. The sentence
$(B)\Rightarrow(A)$ is trivially true. To prove $(A)\Rightarrow(B)$ we need to
show that any tripartite quantum state $\rho$ can be written as
$\rho=(\mathrm{id}_{\mathsf{A}}\otimes\Lambda\otimes\mathrm{id}_{\mathsf{C}})(\sigma)$,
with $\sigma=(\mathrm{id}_{\mathsf{A}}\otimes\Phi)(\psi\otimes\varphi)$, where
$\psi$ is a state of a bipartite system $\mathsf{A}\otimes\mathsf{D}$,
$\varphi$ is a pure bipartite state of a system $\mathsf{E}$,
$\Phi\colon\mathsf{L}(\mathsf{D}\otimes\mathsf{E})\rightarrow\mathsf{L}(\mathsf{F}\otimes\mathsf{C})$
is a unitary quantum channel, and
$\Lambda\colon\mathsf{L}(\mathsf{F})\rightarrow\mathsf{L}(\mathsf{B})$ is a
quantum channel. It can be done by using Lemma 1 twice as follows.

Let $\tau$ be the tripartite quantum state obtained by swapping the systems
$\mathsf{B}$ and $\mathsf{C}$ of $\rho$. Then define the marginal state with
respect to the bipartite system $\mathsf{A\otimes C}$,
$\omega\coloneqq\Tr_{\mathsf{B}}[\tau]$. By the same reasoning as in the proof
of Proposition 1, we know there are a pure bipartite state
$\psi\in\mathsf{L}(\mathsf{A}\otimes\mathsf{D})$ and a quantum channel
$\Omega\coloneqq\mathsf{L}(\mathsf{D})\rightarrow\mathsf{L}(\mathsf{C})$ for
which $\omega=(\mathrm{id}_{\mathsf{A}}\otimes\Omega)(\psi)$. Let
$U\colon\mathsf{D}\otimes\mathsf{E}\rightarrow\mathsf{C}\otimes\mathsf{F}$ be
a dilation of $\Omega$, such that for some pure state $\varphi$ of the system
$\mathsf{E}$ we have
$\Omega(\bullet)=\Tr_{\mathsf{F}}[U(\bullet\otimes\varphi)U^{\dagger}]$. Then
define the unitary quantum channel
$\widetilde{\Phi}(\bullet)=V(\bullet\otimes\varphi)V^{\dagger}$, where $V$ is
the unitary operator obtained by the action of $U$ followed by the swapping
operation. Define the pure tripartite quantum state
$\eta=(\mathrm{id}_{\mathsf{A}}\otimes\widetilde{\Phi})(\psi\otimes\varphi)$.
The state $\eta$ is a purification of $\omega$. Then we have
$\Tr_{\mathsf{F}}[\eta]=\Tr_{\mathsf{B}}[\tau]$. Thus, by Lemma 1, there is a
quantum channel
$\Lambda\colon\mathsf{L}(\mathsf{F})\rightarrow\mathsf{L}(\mathsf{B})$ for
which
$\tau=(\mathrm{id}_{\mathsf{A}}\otimes\mathrm{id}_{\mathsf{C}}\otimes\Lambda)(\eta)$.
Moreover, take the swapping of systems $\mathsf{C}$ and $\mathsf{B}$ of $\tau$
to recover

$\rho=(\mathrm{id}_{\mathsf{A}}\otimes\Lambda\otimes\mathrm{id}_{\mathsf{C}})(\mathrm{id}_{\mathsf{A}}\otimes\Phi)(\psi\otimes\varphi),$
(92)

with $\Phi(\bullet)=U(\bullet)U^{\dagger}$. ∎

###  .4 Quantum Markov monogamy inequalities for $n=3$

The following results deal with the Markov monogamy conditions for six-time-
step Markov processes.

######  Theorem 5.

For any Markov process

$\rho_{1}\stackrel{{\scriptstyle\mathclap{\mbox{$\Lambda_{1}$}}}}{{\longrightarrow}}\rho_{2}\stackrel{{\scriptstyle\mathclap{\mbox{$\Lambda_{2}$}}}}{{\longrightarrow}}\cdots\stackrel{{\scriptstyle\mathclap{\mbox{$\Lambda_{5}$}}}}{{\longrightarrow}}\rho_{6},$

it holds the following inequalities:

$\displaystyle
I_{c}(\rho_{1}:\rho_{6})+I_{c}(\rho_{2}:\rho_{5})+I_{c}(\rho_{3}:\rho_{4})\geq
I_{c}(\rho_{1}:\rho_{4})+I_{c}(\rho_{2}:\rho_{6})+I_{c}(\rho_{3}:\rho_{5});$
(93) $\displaystyle
I_{c}(\rho_{1}:\rho_{6})+I_{c}(\rho_{2}:\rho_{5})+I_{c}(\rho_{3}:\rho_{4})\geq
I_{c}(\rho_{1}:\rho_{5})+I_{c}(\rho_{2}:\rho_{4})+I_{c}(\rho_{3}:\rho_{6}).$
(94)

###### Proof.

Let the quantum channels
$\Lambda_{i}\colon\mathsf{L}(\mathsf{S}_{i})\rightarrow\mathsf{L}(\mathsf{S}_{i+1})$
– with $i=1,\cdots,5$ – have isometric representation given by
$V_{i}:\mathsf{S}_{i}\rightarrow\mathsf{S}_{i+1}\otimes\mathsf{E}_{i}$. The
proof are given by the strong subadditivity inequalities relating the
environmental systems $\mathsf{E}_{i}$ such that added together imply the
desired Monogamy inequality.

In order to prove Eq. (93) add the strong subadditivity inequalities

$\displaystyle
I(\mathsf{E}_{1}:\mathsf{E}_{5}|\mathsf{E}_{2},\mathsf{E}_{3},\mathsf{E}_{4})$
$\displaystyle\geq$ $\displaystyle 0;$ (95) $\displaystyle
I(\mathsf{E}_{1},\mathsf{E}_{2}:\mathsf{E}_{4}|\mathsf{E}_{3})$
$\displaystyle\geq$ $\displaystyle 0.$ (96)

Now, to prove Eq. (94) consider

$\displaystyle
I(\mathsf{E}_{1}:\mathsf{E}_{5}|\mathsf{E}_{2},\mathsf{E}_{3},\mathsf{E}_{4})$
$\displaystyle\geq$ $\displaystyle 0;$ (97) $\displaystyle
I(\mathsf{E}_{1}:\mathsf{E}_{4},\mathsf{E}_{5}|\mathsf{E}_{3})$
$\displaystyle\geq$ $\displaystyle 0.$ (98)

∎

Now we consider how the Markov monogamy inequalities for six-time-step
processes can be equivalently stated in terms of conditional quantum mutual
information.

######  Proposition 3.

The following sentences are equivalent:

  1. (A)

Theorem 5 holds;

  2. (B)

For any quantum state
$\rho\in\mathsf{L}(\mathsf{R}\otimes\mathsf{E}_{1}\otimes\mathsf{E}_{2}\otimes\mathsf{S}_{4})$,
and for any quantum channels
$\Lambda_{4}\colon\mathsf{L}(\mathsf{S}_{4})\rightarrow\mathsf{L}(\mathsf{S}_{5})$
and
$\Lambda_{5}\colon\mathsf{L}(\mathsf{S}_{5})\rightarrow\mathsf{L}(\mathsf{S}_{6})$,
it holds that

$\displaystyle I(\mathsf{R}:\mathsf{S}_{4}|\mathsf{E}_{1},\mathsf{E}_{2})\geq
I(\mathsf{R},\mathsf{E}_{1}:\mathsf{S}_{5}|\mathsf{E}_{2})+I(\mathsf{R}:\mathsf{S}_{6}|\mathsf{E}_{1});$
(99) $\displaystyle
I(\mathsf{R},\mathsf{E}_{1}:\mathsf{S}_{4}|\mathsf{E}_{2})+I(\mathsf{R}:\mathsf{S}_{5}|\mathsf{E}_{1})\geq
I(\mathsf{R}:\mathsf{S}_{6}|\mathsf{E}_{1},\mathsf{E}_{2}).$ (100)

The proof of Proposition 3 is similar to the one presented for Proposition 2,
so we do not include it here.

###  .5 Quantum Markov monogamy inequalities for $n=4$

The following Theorems deal with the Markov monogamy conditions for eight-
time-step Markov processes.

######  Theorem 6.

It holds that for any Markov process

$\rho_{1}\stackrel{{\scriptstyle\mathclap{\mbox{$\Lambda_{1}$}}}}{{\longrightarrow}}\rho_{2}\stackrel{{\scriptstyle\mathclap{\mbox{$\Lambda_{2}$}}}}{{\longrightarrow}}\cdots\stackrel{{\scriptstyle\mathclap{\mbox{$\Lambda_{7}$}}}}{{\longrightarrow}}\rho_{8},$
$\displaystyle
I_{c}(\rho_{1}:\rho_{8})+I_{c}(\rho_{2}:\rho_{7})+I_{c}(\rho_{3}:\rho_{6})+I_{c}(\rho_{4}:\rho_{5})\geq
I_{c}(\rho_{1}:\rho_{5})+I_{c}(\rho_{2}:\rho_{8})+I_{c}(\rho_{3}:\rho_{7})+I_{c}(\rho_{4}:\rho_{6});$
(101) $\displaystyle
I_{c}(\rho_{1}:\rho_{8})+I_{c}(\rho_{2}:\rho_{7})+I_{c}(\rho_{3}:\rho_{6})+I_{c}(\rho_{4}:\rho_{5})\geq
I_{c}(\rho_{1}:\rho_{7})+I_{c}(\rho_{2}:\rho_{5})+I_{c}(\rho_{3}:\rho_{8})+I_{c}(\rho_{4}:\rho_{6});$
(102) $\displaystyle
I_{c}(\rho_{1}:\rho_{8})+I_{c}(\rho_{2}:\rho_{7})+I_{c}(\rho_{3}:\rho_{6})+I_{c}(\rho_{4}:\rho_{5})\geq
I_{c}(\rho_{1}:\rho_{6})+I_{c}(\rho_{2}:\rho_{8})+I_{c}(\rho_{3}:\rho_{5})+I_{c}(\rho_{4}:\rho_{7});$
(103) $\displaystyle
I_{c}(\rho_{1}:\rho_{8})+I_{c}(\rho_{2}:\rho_{7})+I_{c}(\rho_{3}:\rho_{6})+I_{c}(\rho_{4}:\rho_{5})\geq
I_{c}(\rho_{1}:\rho_{5})+I_{c}(\rho_{2}:\rho_{6})+I_{c}(\rho_{3}:\rho_{8})+I_{c}(\rho_{4}:\rho_{7});$
(104) $\displaystyle
I_{c}(\rho_{1}:\rho_{8})+I_{c}(\rho_{2}:\rho_{7})+I_{c}(\rho_{3}:\rho_{6})+I_{c}(\rho_{4}:\rho_{5})\geq
I_{c}(\rho_{1}:\rho_{7})+I_{c}(\rho_{2}:\rho_{6})+I_{c}(\rho_{3}:\rho_{5})+I_{c}(\rho_{4}:\rho_{8});$
(105) $\displaystyle
I_{c}(\rho_{1}:\rho_{8})+I_{c}(\rho_{2}:\rho_{7})+I_{c}(\rho_{3}:\rho_{6})+I_{c}(\rho_{4}:\rho_{5})\geq
I_{c}(\rho_{1}:\rho_{6})+I_{c}(\rho_{2}:\rho_{5})+I_{c}(\rho_{3}:\rho_{7})+I_{c}(\rho_{4}:\rho_{8});$
(106) $\displaystyle
I_{c}(\rho_{1}:\rho_{8})+I_{c}(\rho_{2}:\rho_{7})+I_{c}(\rho_{3}:\rho_{6})+I_{c}(\rho_{4}:\rho_{5})\geq
I_{c}(\rho_{1}:\rho_{5})+I_{c}(\rho_{2}:\rho_{6})+I_{c}(\rho_{3}:\rho_{7})+I_{c}(\rho_{4}:\rho_{8}).$
(107)

###### Proof.

To prove Eq. (101) add

$\displaystyle
I(\mathsf{E}_{1}:\mathsf{E}_{7}|\mathsf{E}_{2},\mathsf{E}_{3},\mathsf{E}_{4},\mathsf{E}_{5},\mathsf{E}_{6})$
$\displaystyle\geq$ $\displaystyle 0;$ (108) $\displaystyle
I(\mathsf{E}_{1},\mathsf{E}_{2}:\mathsf{E}_{6}|\mathsf{E}_{3},\mathsf{E}_{4},\mathsf{E}_{5})$
$\displaystyle\geq$ $\displaystyle 0;$ (109) $\displaystyle
I(\mathsf{E}_{1},\mathsf{E}_{2},\mathsf{E}_{3}:\mathsf{E}_{5}|\mathsf{E}_{4})$
$\displaystyle\geq$ $\displaystyle 0.$ (110)

To prove Eq. (102) add

$\displaystyle
I(\mathsf{E}_{1}:\mathsf{E}_{7}|\mathsf{E}_{2},\mathsf{E}_{3},\mathsf{E}_{4},\mathsf{E}_{5},\mathsf{E}_{6})$
$\displaystyle\geq$ $\displaystyle 0;$ (111) $\displaystyle
I(\mathsf{E}_{2}:\mathsf{E}_{6},\mathsf{E}_{7}|\mathsf{E}_{3},\mathsf{E}_{4},\mathsf{E}_{5})$
$\displaystyle\geq$ $\displaystyle 0;$ (112) $\displaystyle
I(\mathsf{E}_{2},\mathsf{E}_{3}:\mathsf{E}_{5}|\mathsf{E}_{4})$
$\displaystyle\geq$ $\displaystyle 0.$ (113)

To prove Eq. (103) add

$\displaystyle
I(\mathsf{E}_{1}:\mathsf{E}_{7}|\mathsf{E}_{2},\mathsf{E}_{3},\mathsf{E}_{4},\mathsf{E}_{5},\mathsf{E}_{6})$
$\displaystyle\geq$ $\displaystyle 0;$ (114) $\displaystyle
I(\mathsf{E}_{1},\mathsf{E}_{2}:\mathsf{E}_{6}|\mathsf{E}_{3},\mathsf{E}_{4},\mathsf{E}_{5})$
$\displaystyle\geq$ $\displaystyle 0;$ (115) $\displaystyle
I(\mathsf{E}_{3}:\mathsf{E}_{5},\mathsf{E}_{6}|\mathsf{E}_{4})$
$\displaystyle\geq$ $\displaystyle 0.$ (116)

To prove Eq. (104) add

$\displaystyle
I(\mathsf{E}_{1}:\mathsf{E}_{7}|\mathsf{E}_{2},\mathsf{E}_{3},\mathsf{E}_{4},\mathsf{E}_{5},\mathsf{E}_{6})$
$\displaystyle\geq$ $\displaystyle 0;$ (117) $\displaystyle
I(\mathsf{E}_{2}:\mathsf{E}_{6},\mathsf{E}_{7}|\mathsf{E}_{3},\mathsf{E}_{4},\mathsf{E}_{5})$
$\displaystyle\geq$ $\displaystyle 0;$ (118) $\displaystyle
I(\mathsf{E}_{1},\mathsf{E}_{2},\mathsf{E}_{3}:\mathsf{E}_{5},\mathsf{E}_{6}|\mathsf{E}_{4})$
$\displaystyle\geq$ $\displaystyle 0.$ (119)

To prove Eq. (105) add

$\displaystyle
I(\mathsf{E}_{1}:\mathsf{E}_{7}|\mathsf{E}_{2},\mathsf{E}_{3},\mathsf{E}_{4},\mathsf{E}_{5},\mathsf{E}_{6})$
$\displaystyle\geq$ $\displaystyle 0;$ (120) $\displaystyle
I(\mathsf{E}_{2}:\mathsf{E}_{6},\mathsf{E}_{7}|\mathsf{E}_{3},\mathsf{E}_{4},\mathsf{E}_{5})$
$\displaystyle\geq$ $\displaystyle 0;$ (121) $\displaystyle
I(\mathsf{E}_{3}:\mathsf{E}_{5},\mathsf{E}_{6},\mathsf{E}_{7}|\mathsf{E}_{4})$
$\displaystyle\geq$ $\displaystyle 0.$ (122)

To prove Eq. (106) add

$\displaystyle
I(\mathsf{E}_{1}:\mathsf{E}_{7}|\mathsf{E}_{2},\mathsf{E}_{3},\mathsf{E}_{4},\mathsf{E}_{5},\mathsf{E}_{6})$
$\displaystyle\geq$ $\displaystyle 0;$ (123) $\displaystyle
I(\mathsf{E}_{1},\mathsf{E}_{2}:\mathsf{E}_{6}|\mathsf{E}_{3},\mathsf{E}_{4},\mathsf{E}_{5})$
$\displaystyle\geq$ $\displaystyle 0;$ (124) $\displaystyle
I(\mathsf{E}_{2},\mathsf{E}_{3}:\mathsf{E}_{5},\mathsf{E}_{6},\mathsf{E}_{7}|\mathsf{E}_{4})$
$\displaystyle\geq$ $\displaystyle 0.$ (125)

To prove Eq. (107) add

$\displaystyle
I(\mathsf{E}_{1}:\mathsf{E}_{7}|\mathsf{E}_{2},\mathsf{E}_{3},\mathsf{E}_{4},\mathsf{E}_{5},\mathsf{E}_{6})$
$\displaystyle\geq$ $\displaystyle 0;$ (126) $\displaystyle
I(\mathsf{E}_{1},\mathsf{E}_{2},\mathsf{E}_{3}:\mathsf{E}_{5},\mathsf{E}_{6}|\mathsf{E}_{4})$
$\displaystyle\geq$ $\displaystyle 0;$ (127) $\displaystyle
I(\mathsf{E}_{2}:\mathsf{E}_{6},\mathsf{E}_{7}|\mathsf{E}_{3},\mathsf{E}_{4},\mathsf{E}_{5})$
$\displaystyle\geq$ $\displaystyle 0;$ (128) $\displaystyle
I(\mathsf{E}_{3}:\mathsf{E}_{7}|\mathsf{E}_{4},\mathsf{E}_{5},\mathsf{E}_{6})$
$\displaystyle\geq$ $\displaystyle 0.$ (129)

∎

It follows the Markov monogamy theorems for eight-time-step processes in term
of conditional quantum mutual information. Again, the proof of Proposition 4
below follows the same steps as Proposition 2 and is left absent here.

######  Proposition 4.

The following sentences are equivalent:

  1. (A)

Theorem 6 holds;

  2. (B)

For any quantum state
$\rho\in\mathsf{L}(\mathsf{R}\otimes\mathsf{E}_{1}\otimes\mathsf{E}_{2}\otimes\mathsf{E}_{3}\otimes\mathsf{S}_{5})$,
and for any quantum channels
$\Lambda_{5}\colon\mathsf{L}(\mathsf{S}_{5})\rightarrow\mathsf{L}(\mathsf{S}_{6})$,
$\Lambda_{6}\colon\mathsf{L}(\mathsf{S}_{6})\rightarrow\mathsf{L}(\mathsf{S}_{7})$
and
$\Lambda_{7}\colon\mathsf{L}(\mathsf{S}_{7})\rightarrow\mathsf{L}(\mathsf{S}_{8})$,
it holds that

$\displaystyle
I(\mathsf{R}:\mathsf{S}_{5}|\mathsf{E}_{1},\mathsf{E}_{2},\mathsf{E}_{3})\geq
I(\mathsf{R},\mathsf{E}_{1},\mathsf{E}_{2}:\mathsf{S}_{6}|\mathsf{E}_{3})+I(\mathsf{R},\mathsf{E}_{1}:\mathsf{S}_{7}|\mathsf{E}_{2})+I(\mathsf{R}:\mathsf{S}_{8}|\mathsf{E}_{1});$
(130) $\displaystyle
I(\mathsf{R},\mathsf{E}_{1}:\mathsf{S}_{5}|\mathsf{E}_{2},\mathsf{E}_{3})+I(\mathsf{R}:\mathsf{S}_{7}|\mathsf{E}_{1})\geq
I(\mathsf{R},\mathsf{E}_{1},\mathsf{E}_{2}:\mathsf{S}_{8}|\mathsf{E}_{3})+I(\mathsf{R}:\mathsf{S}_{8}|\mathsf{E}_{1},\mathsf{E}_{2});$
(131) $\displaystyle
I(\mathsf{R},\mathsf{E}_{1},\mathsf{E}_{2}:\mathsf{S}_{5}|\mathsf{E}_{3})+I(\mathsf{R}:\mathsf{S}_{6}|\mathsf{E}_{1},\mathsf{E}_{2})\geq
I(\mathsf{R},\mathsf{E}_{1}:\mathsf{S}_{7}|\mathsf{E}_{2},\mathsf{E}_{3})+I(\mathsf{R}:\mathsf{S}_{8}|\mathsf{E}_{1});$
(132) $\displaystyle
I(\mathsf{R}:\mathsf{S}_{5}|\mathsf{E}_{1},\mathsf{E}_{2},\mathsf{E}_{3})+I(\mathsf{R},\mathsf{E}_{1}:\mathsf{S}_{6}|\mathsf{E}_{2})\geq
I(\mathsf{R},\mathsf{E}_{1}:\mathsf{S}_{7}|\mathsf{E}_{2},\mathsf{E}_{3})+I(\mathsf{R}:\mathsf{S}_{8}|\mathsf{E}_{1},\mathsf{E}_{2});$
(133) $\displaystyle
I(\mathsf{R},\mathsf{E}_{1},\mathsf{E}_{2}:\mathsf{S}_{5}|\mathsf{E}_{3})+I(\mathsf{R},\mathsf{E}_{1}:\mathsf{S}_{6}|\mathsf{E}_{2})+I(\mathsf{R}:\mathsf{S}_{7}|\mathsf{E}_{1})\geq
I(\mathsf{R}:\mathsf{S}_{8}|\mathsf{E}_{1},\mathsf{E}_{2},\mathsf{E}_{3});$
(134) $\displaystyle
I(\mathsf{R},\mathsf{E}_{1}:\mathsf{S}_{5}|\mathsf{E}_{2},\mathsf{E}_{3})+I(\mathsf{R}:\mathsf{S}_{6}|\mathsf{E}_{1},\mathsf{E}_{2})\geq
I(\mathsf{R},\mathsf{E}_{1}:\mathsf{S}_{7}|\mathsf{E}_{2})\geq
I(\mathsf{R}:\mathsf{S}_{8}|\mathsf{E}_{1},\mathsf{E}_{2},\mathsf{E}_{3});$
(135) $\displaystyle
I(\mathsf{R}:\mathsf{S}_{5}|\mathsf{E}_{1},\mathsf{E}_{2},\mathsf{E}_{3})+I(\mathsf{R},\mathsf{E}_{1}:\mathsf{S}_{6}|\mathsf{E}_{2})\geq
I(\mathsf{R},\mathsf{E}_{1}:\mathsf{S}_{7}|\mathsf{E}_{2})+I(\mathsf{R}:\mathsf{S}_{8}|\mathsf{E}_{1},\mathsf{E}_{2},\mathsf{E}_{3}).$
(136)

###  .6 Choi state of a CPTP map as an action of a CP map on the adjoint space

Below we show how the Choi state of a CPTP map is identical to the action of a
unital CP on the adjoint space.

$\displaystyle\mathrm{A}\otimes\mathrm{id}(\Psi^{+})=$
$\displaystyle\sum_{ijk}A_{k}\otimes\openone\left|ii\right>\\!\left<jj\right|A_{k}^{\dagger}\otimes\openone$
(137) $\displaystyle=$
$\displaystyle\sum_{ijk}\left(\sum_{mn}a^{(k)}_{nm}\left|n\right>\\!\left<m\right|\otimes\openone\right)\left|ii\right>\\!\left<jj\right|\left(\sum_{rs}a^{(k)*}_{rs}\left|s\right>\\!\left<r\right|\otimes\openone\right)$
$\displaystyle=$
$\displaystyle\sum_{ijk}\left(\openone\otimes\sum_{mn}a^{(k)}_{nm}\left|m\right>\\!\left<n\right|\right)\left|ii\right>\\!\left<jj\right|\left(\openone\otimes\sum_{rs}a^{(k)*}_{rs}\left|r\right>\\!\left<s\right|\right)$
$\displaystyle=$ $\displaystyle\sum_{ijk}\left(\openone\otimes
A_{k}^{\dagger}\left|ii\right>\\!\left<jj\right|A_{k}\otimes\openone\right)^{T}=:\mathrm{id}\otimes\mathrm{A}^{\dagger}(\Psi^{+})$
(138)

The adjoint channel will be unital if the $\mathrm{A}$ is trace preserving.
Both channels are CP.

## References

  * Shannon (1948) Claude E Shannon, “A mathematical theory of communication,” The Bell system technical journal 27, 379–423 (1948).
  * Yeung (2008) Raymond W Yeung,  _Information theory and network coding_ (Springer Science & Business Media, 2008).
  * Arnold (2004) Dieter-Michael Arnold, “On the data-processing inequality in the mismatch case,” in  _International Symposium onInformation Theory, 2004. ISIT 2004. Proceedings._ (IEEE, 2004) p. 266.
  * Merhav (2012) Neri Merhav, “Data-processing inequalities based on a certain structured class of information measures with application to estimation theory,” IEEE transactions on information theory 58, 5287–5301 (2012).
  * Kang and Ulukus (2010) Wei Kang and Sennur Ulukus, “A new data processing inequality and its applications in distributed source and channel coding,” IEEE Transactions on Information Theory 57, 56–69 (2010).
  * du Pin Calmon  _et al._ (2017) Flavio du Pin Calmon, Yury Polyanskiy, and Yihong Wu, “Strong data processing inequalities for input constrained additive noise channels,” IEEE Transactions on Information Theory 64, 1879–1892 (2017).
  * Kamath and Nair (2015) Sudeep Kamath and Chandra Nair, “The strong data processing constant for sums of iid random variables,” in  _2015 IEEE International Symposium on Information Theory (ISIT)_ (IEEE, 2015) pp. 2550–2552.
  * Raginsky (2013) Maxim Raginsky, “Logarithmic sobolev inequalities and strong data processing theorems for discrete channels,” in  _2013 IEEE International Symposium on Information Theory_ (IEEE, 2013) pp. 419–423.
  * Merhav (2011) Neri Merhav, “Data processing theorems and the second law of thermodynamics,” IEEE transactions on information theory 57, 4926–4939 (2011).
  * Anantharam  _et al._ (2014) Venkat Anantharam, Amin Gohari, Sudeep Kamath, and Chandra Nair, “On hypercontractivity and a data processing inequality,” in  _2014 IEEE International Symposium on Information Theory_ (IEEE, 2014) pp. 3022–3026.
  * Capela  _et al._ (2020) Matheus Capela, Lucas C Céleri, Kavan Modi, and Rafael Chaves, “Monogamy of temporal correlations: Witnessing non-markovianity beyond data processing,” Physical Review Research 2, 013350 (2020).
  * Schumacher and Nielsen (1996) Benjamin Schumacher and Michael A Nielsen, “Quantum data processing and error correction,” Physical Review A 54, 2629 (1996).
  * Buscemi (2014) Francesco Buscemi, “Complete positivity, markovianity, and the quantum data-processing inequality, in the presence of initial system-environment correlations,” Physical review letters 113, 140502 (2014).
  * Buscemi and Datta (2016) Francesco Buscemi and Nilanjana Datta, “Equivalence between divisibility and monotonic decrease of information in classical and quantum stochastic processes,” Physical Review A 93, 012101 (2016).
  * Buscemi (2017) Francesco Buscemi, “Comparison of noisy channels and reverse data-processing theorems,” in  _2017 IEEE Information Theory Workshop (ITW)_ (IEEE, 2017) pp. 489–493.
  * Buscemi (2015) Francesco Buscemi, “Reverse data-processing theorems and computational second laws,” in  _Nagoya Winter Workshop: Reality and Measurement in Algebraic Quantum Theory_ (Springer, 2015) pp. 135–159.
  * Hayden  _et al._ (2004) Patrick Hayden, Richard Jozsa, Denes Petz, and Andreas Winter, “Structure of states which satisfy strong subadditivity of quantum entropy with equality,” Communications in mathematical physics 246, 359–374 (2004).
  * Rivas  _et al._ (2014) Angel Rivas, Susana F Huelga, and Martin B Plenio, “Quantum non-markovianity: characterization, quantification and detection,” Reports on Progress in Physics 77, 094001 (2014).
  * Ferrie (2014) Christopher Ferrie, “Data-processing inequalities for quantum metrology,” Physical Review A 90, 014101 (2014).
  * Vinjanampathy and Modi (2015) Sai Vinjanampathy and Kavan Modi, “Entropy bounds for quantum processes with initial correlations,” Phys. Rev. A 92, 052310 (2015).
  * Türkmen  _et al._ (2017) A Türkmen, A Verçin, and S Yılmaz, “Data processing inequality and open quantum systems: Beyond markov states,” Physical Review A 96, 042112 (2017).
  * Pollock  _et al._ (2018a) Felix A Pollock, César Rodríguez-Rosario, Thomas Frauenheim, Mauro Paternostro, and Kavan Modi, “Non-markovian quantum processes: Complete framework and efficient characterization,” Physical Review A 97, 012127 (2018a).
  * Pollock  _et al._ (2018b) Felix A Pollock, César Rodríguez-Rosario, Thomas Frauenheim, Mauro Paternostro, and Kavan Modi, “Operational markov condition for quantum processes,” Physical review letters 120, 040405 (2018b).
  * Costa and Shrapnel (2016) Fabio Costa and Sally Shrapnel, “Quantum causal modelling,” New J. Phys. 18, 063032 (2016).
  * Milz  _et al._ (2020a) Simon Milz, Fattah Sakuldee, Felix A. Pollock, and Kavan Modi, “Kolmogorov extension theorem for (quantum) causal modelling and general probabilistic theories,” Quantum 4, 255 (2020a).
  * Milz and Modi (2021) Simon Milz and Kavan Modi, “Quantum stochastic processes and quantum non-markovian phenomena,” PRX Quantum 2, 030201 (2021).
  * Note (1) Conditions of this type can be tested with a linear program such as ITIP Yeung and Yan (2016).
  * Cover and Thomas (2005) Thomas M. Cover and Joy A. Thomas,  _Elements of Information Theory, Second Edition_ (John Wiley & Sons, 2005).
  * Lieb and Ruskai (1973) Elliott H Lieb and Mary Beth Ruskai, “Proof of the strong subadditivity of quantum-mechanical entropy,” Journal of Mathematical Physics 14, 1938–1941 (1973).
  * Wilde (2011) Mark M Wilde, “From classical to quantum shannon theory,” arXiv preprint arXiv:1106.1445 (2011).
  * Li  _et al._ (2018) Li Li, Michael J.W. Hall, and Howard M. Wiseman, “Concepts of quantum non-markovianity: A hierarchy,” Phys. Rep. 759, 1 (2018).
  * Breuer  _et al._ (2016) Heinz-Peter Breuer, Elsi-Mari Laine, Jyrki Piilo, and Bassano Vacchini, “Colloquium: Non-markovian dynamics in open quantum systems,” Reviews of Modern Physics 88, 021002 (2016).
  * Chruściński  _et al._ (2011) Dariusz Chruściński, Andrzej Kossakowski, and Ángel Rivas, “Measures of non-markovianity: Divisibility versus backflow of information,” Physical Review A 83, 052128 (2011).
  * Nielsen and Chuang (2002) Michael A Nielsen and Isaac Chuang,  _Quantum computation and quantum information_ (Cambridge University Press, 2002).
  * Milz  _et al._ (2019) Simon Milz, M. S. Kim, Felix A. Pollock, and Kavan Modi, “Completely positive divisibility does not mean markovianity,” Phys. Rev. Lett. 123, 040401 (2019).
  * Davies and Lewis (1970) E.B. Davies and J.T. Lewis, “An operational approach to quantum probability,” Commun. Math. Phys. 17, 239 (1970).
  * Chiribella  _et al._ (2009) Giulio Chiribella, Giacomo Mauro D’Ariano, and Paolo Perinotti, “Theoretical framework for quantum networks,” Phys. Rev. A 80, 022339 (2009).
  * Strasberg and Díaz (2019) Philipp Strasberg and María García Díaz, “Classical quantum stochastic processes,” Phys. Rev. A 100, 022120 (2019).
  * Milz  _et al._ (2020b) Simon Milz, Dario Egloff, Philip Taranto, Thomas Theurer, Martin B. Plenio, Andrea Smirne, and Susana F. Huelga, “When Is a Non-Markovian Quantum Process Classical?” Phys. Rev. X 10, 041049 (2020b).
  * Ringbauer  _et al._ (2015) M. Ringbauer, C. J. Wood, K. Modi, A. Gilchrist, A. G. White, and A. Fedrizzi, “Characterizing Quantum Dynamics with Initial System-Environment Correlations,” Phys. Rev. Lett. 114, 090402 (2015).
  * White  _et al._ (2020) Gregory A. L. White, Charles D. Hill, Felix A. Pollock, Lloyd C. L. Hollenberg, and Kavan Modi, “Experimental non-Markovian process characterisation and control on a quantum processor,” Nat. Commun. 11, 6301 (2020).
  * White  _et al._ (2021a) Gregory A. L. White, Felix A. Pollock, Lloyd C. L. Hollenberg, Charles D. Hill, and Kavan Modi, “Non-Markovian Quantum Process Tomography,” arXiv:2106.11722 (2021a).
  * Note (2) A coarse (higher-rank projection) measurement can hide memory in the degenerate subspace, even if the process is Markovian, see Taranto  _et al._ (2019).
  * Petz (2003) Dénes Petz, “Monotonicity of quantum relative entropy revisited,” Rev. Math. Phys. 15, 79–91 (2003).
  * Modi (2012) Kavan Modi, “Operational approach to open dynamics and quantifying initial correlations,” Scientific Reports 2, 581 EP – (2012), article.
  * Giarmatzi and Costa (2021) Christina Giarmatzi and Fabio Costa, “Witnessing quantum memory in non-Markovian processes,” Quantum 5, 440 (2021).
  * Milz  _et al._ (2021) Simon Milz, Cornelia Spee, Zhen-Peng Xu, Felix A. Pollock, Kavan Modi, and Otfried Gühne, “Genuine Multipartite Entanglement in Time,” SciPost Phys. 10, 141 (2021).
  * White  _et al._ (2021b) Gregory A. L. White, Felix A. Pollock, Lloyd C. L. Hollenberg, Charles D. Hill, and Kavan Modi, “Diagnosing temporal quantum correlations with compressed non-Markovian calipers,” arXiv:2107.13934 (2021b).
  * Watrous (2018) John Watrous,  _The theory of quantum information_ (Cambridge University Press, 2018).
  * Yeung and Yan (2016) RW Yeung and YO Yan, “ITIP (Information Theoretic Inequality Prover),”  (2016).
  * Taranto  _et al._ (2019) Philip Taranto, Simon Milz, Felix A Pollock, and Kavan Modi, “Structure of quantum stochastic processes with finite markov order,” Physical Review A 99, 042108 (2019).