# Directed Redundancy in Time Series

Jan Østergaard  Department of Electronic Systems
Aalborg University
Aalborg, Denmark
Email<EMAIL_ADDRESS>
###### Abstract

We quantify the average amount of redundant information that is transferred
from a subset of relevant random source processes to a target process. To
identify the relevant source processes, we consider those that are connected
to the target process and in addition share a certain proportion of the total
information causally provided to the target. Even if the relevant processes
have no directed information exchange between them, they can still causally
provide redundant information to the target. This makes it difficult to
identify the relevant processes. To solve this issue, we propose the existence
of a hidden redundancy process that governs the shared information among the
relevant processes. We bound the redundancy by the minimal average directed
redundancy from the relevant processes to the target, from the hidden
redundancy process to the target, and from the hidden redundancy process to
the relevant processes.

##  I INTRODUCTION

Mutual information is frequently used when quantifying the amount of
redundancy between random variables [1]. Shannon’s mutual information measure
is only able to quantify the shared information between _two_ sets of
variables [2]. Thus, a naive way to compute the amount of common information
of three or more variables is to use the minimum of their _pairwise_ mutual
informations. Alternative ways of analyzing the intrinsic relationships
between multiple random variables have been considered in e.g., [3, 4, 5, 6,
7, 8, 9, 10, 11].

Consider the case where $Z$ is the target signal and $X$ and $Y$ the source
signals. We are interested in assessing the amount of redundant information in
$Z$ due to $X$ and $Y$, i.e., the amount of shared information that both $X$
and $Y$ convey to $Z$. This was considered for discrete random variables in
[3] as:

$\displaystyle I^{\mathrm{min}}(X;Y;Z)$
$\displaystyle\triangleq\\!\\!\sum_{z\in\mathcal{Z}}p_{Z}(z)\min(I(X;Z=z),I(Y;Z=z)),$
(1) $\displaystyle I(X;Z=z)$
$\displaystyle=\sum_{x\in\mathcal{X}}p_{X|Z}(x|z)\log_{2}\frac{p_{X|Z}(x|z)}{p_{Z}(z)},$
$\displaystyle I(Y;Z=z)$
$\displaystyle=\sum_{y\in\mathcal{Y}}p_{Y|Z}(y|z)\log_{2}\frac{p_{Y|Z}(y|z)}{p_{Z}(z)},$

where $\mathcal{X},\mathcal{Y},\mathcal{Z}$ are the alphabets of $X,Y$, and
$Z$, respectively.

An extension of the redundancy measure in (1) to continuous-alphabet sources
was considered in [12]:

$I^{\mathrm{min}}(X;Y;Z)\\!\triangleq\\!\\!\int_{z\in\mathcal{Z}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!f_{Z}(z)\min(I(X;Z=z),I(Y;Z=z))\,dz.$
(2)

In order to extend (2) to processes, one could use a directed measure for
discrete-time stationary processes $\\{X_{k}\\},\\{Y_{k}\\},$ and
$\\{Z_{k}\\}$; such as transfer entropy $\mathbb{TE}$ [13]:

$\displaystyle\mathbb{TE}(\\{X_{k}\\}\to\\{Z_{k}\\})\triangleq
I(X^{n-1};Z_{n}|Z^{n-1}).$ (3)

We can then form a directed version of the average minimal redundancy measure
for processes as follows:

$\displaystyle
I^{\mathrm{min}}(\\{X_{k}\\};\\{Y_{k}\\};\\{Z_{k}\\})\triangleq\int_{z^{n}\in\mathcal{Z}^{n}}f_{Z}(z_{n}|z^{n-1})\times$
(4)
$\displaystyle\min(\mathbb{TE}(\\{X_{k}\\}\\!\to\\!\\{Z_{k}=z_{k}\\},\mathbb{TE}(\\{Y_{k}\\}\\!\to\\!\\{Z_{k}=z_{k}\\})\,dz^{n}.$

We are, however, facing a number of problems with (4):

  1. _i)_

Computing $\mathbb{TE}(\\{Y_{k}\\}\to\\{Z_{k}=z_{k}\\})$ for every $z^{k}$ is
practically infeasible since $\mathcal{Z}^{n}$ is uncountably infinite.

  2. _ii)_

If there are more than two source processes, the minimum would be taken over
all sources processes. However, perhaps only a few of them are connected to
the target, and hence the minimum transfer entropy over _all_ source processes
and to the target is then always zero.

  3. _iii)_

A positive transfer entropy does not necessarily imply that the processes are
causally related.

Note also that two source processes that have zero causal interaction with
each other, could potentially still causally provide redundant information to
the target.

It was suggested in [12] and further developed in [14] to use the minimum
transfer entropy from the sources to the target as a measure of redundancy.
Such an approach would solve problem _i)_. Moreover, the idea that source
variables can be weakly or even uncorrelated and yet carry redundant
information was discussed in [5] and [12]. Here they suggested to not consider
the mutual information among all the source variables but only between the
sources and the target. We will leverage upon both of these ideas in the
sequel.

In this paper, we propose and analyze a new notion of _directed_ redundancy
that is applicable to both discrete-time _continuous-_ alphabet and _discrete_
-alphabet _processes_. The notion is motivated by the analysis of brain
networks, where it is currently unknown to what degree the human brain relies
upon redundant information for processing [15].

Our main contribution is to quantify the redundant information exchange a set
of _relevant_ source processes each provide to a given target process. This is
complicated by the following problem. Two causally independent sources could
provide different (and hence non-redundant) information to the target. Thus,
if we only measure the _amount_ of causal information exchange from the
sources and to the target, then these sources would wrongly be classified as
providing redundant information transfer to the target. On the other hand, the
causal information exchange between the source processes could be zero even
though they provide redundant information to the target. Thus, it is necessary
but non-trivial to include the dependency between the sources to guarantee
that they actually provide redundant information to the target. To tackle this
problem, we hypothesize the existence of a (perhaps hidden) redundancy
process, $\phi$, which causally affect the source processes. Thus, if we know
$\phi$, we can compute the causal information exchange from $\phi$ to all the
relevant sources, and also to the target. The minimum of these causal
exchanges, would be an upper bound to the redundancy.

###  I-A Notation

We use $\\{X_{k}\\}$ to denote a one-sided scalar random process, i.e.,
$\\{X_{k}\\}=X_{1},X_{2},\dotsc,$ where $X_{k}\in\mathbb{R}$. For brevity, we
will occasionally refer to $\\{X_{k}\\}$ simply by $X$. For example,
$\mathbb{TE}(X\to Z)$ denotes the transfer entropy from $\\{X_{k}\\}$ to
$\\{Z_{k}\\}$.The $i$th element of $\\{X_{k}\\}$ is denoted $X_{i}$, and
$X^{N}=X_{1},\dotsc,X_{N}$. We use the notation $X^{N}(j),j=1,\dots,J,$ to
distinguish between $J$ time-series each of length $N$. If
$X_{k+1}=f_{k}(X^{k},Y^{k}),\forall k$, for a deterministic function $f_{k}$,
then there is a directional (or causal) dependency from $Y$ to $X$.

##  II Redundancy via Minimal Sufficient Statistics

In this section, we motivate the use of minimal sufficient statistics as a
means to bound the common information. Let $A,B$, and $C$ be mutually
independent discrete random variables. Moreover, let $X=(A,B),Y=(A,C)$, and
$Z=(B,C)$. What is the amount of common (redundant) information between $X,Y$,
and $Z$? Using the minimum of their pairwise mutual informations yields:

$\displaystyle\min(I(X;Y),I(X;Z),I(Y;Z))\\!=\\!\min(H(A),H(B),H(C)),$ (5)

since $I(X;Y)=H(X)-H(X|Y)=H(A,B)-H(A,B|A,C)=H(A)+H(B)-H(B|A,C)=H(A)$.
Similarly, $I(X;Z)=H(B)$ and $I(Y;Z)=H(C)$. Thus, if the entropies are
positive the pairwise common information is positively bounded away from zero.
On the other hand, we can define a notion of redundancy based upon sufficient
statistics, which is zero for the above example. Let $T_{XY}$ be a sufficient
statistics of $X$ with respect to $Y$, i.e., $I(X;Y)=I(T_{XY};Y)$ and
$X-T_{XY}-Y$ forms a Markov chain, i.e., $X$ and $Y$ are conditionally
independent of each other given knowledge of $T_{XY}$ [1]. A minimal
sufficient statistics $T^{*}_{XY}$ satisfies [1]:

$T^{*}_{XY}=\arg\min_{T_{XY}}I(T_{XY};X),\quad s.t.\quad I(T_{XY};Y)=I(X;Y).$

For the above example, one may observe that the minimal sufficient statistics
are $T_{XY}=A,T_{XZ}=B$, and $T_{YZ}=C$. Then, clearly
$I(T_{XY};T_{XZ})=I(T_{XZ};T_{YZ})=I(T_{XY};T_{YZ})=0$. Since the minimal
sufficient statistics have no information overlap with each other one could
argue that the triplet $(X,Y,Z)$ therefore should have zero information in
common, which implies zero redundancy. The above example inspire us to
introduce a new notion of redundancy for random variables, which we extend to
processes in the next section:

$\displaystyle\bar{I}^{\mathrm{red}}(X;Y;Z)$ (6)
$\displaystyle\quad\triangleq\min\,(I(T_{XY};T_{XZ}),I(T_{XZ};T_{YZ}),I(T_{XY};T_{YZ})),$

where $T_{XY}$ denotes a minimal sufficient statistics for $X$ with respect to
$Y$, and similarly for $T_{XZ}$ and $T_{YZ}$. Clearly,
$\bar{I}^{\mathrm{red}}(X;Y;Z)\leq\min\,(I(X;Y),I(X;Z),I(Y;Z)).$

##  III Directed Redundancy

In this section, we introduce a hidden redundancy process, and define a notion
of directed redundancy for processes.

###  III-A Hidden redundancy process

The following example illustrates the usefulness of considering a (perhaps
hidden) redundancy process that governs the shared information, which is
exhanged by a set of source processes to a target process. Consider the
following system:

$\displaystyle\psi_{k+1}$ $\displaystyle=a\psi_{k}+W^{\psi}_{k}$ (7)
$\displaystyle\phi_{k+1}$ $\displaystyle=a\phi_{k}+W^{\phi}_{k}$ (8)
$\displaystyle X_{k+1}$ $\displaystyle=bX_{k}+c\phi_{k-1}+W^{X}_{k}$ (9)
$\displaystyle Y_{k+1}$ $\displaystyle=bY_{k}+c\phi_{k-1}+W^{Y}_{k}$ (10)
$\displaystyle Z_{k+1}$
$\displaystyle=bZ_{k}+dX_{k-1}+dY_{k-1}+e\psi_{k-1}+W^{Z}_{k},$ (11)

where $W_{k}^{\varphi}\in\mathbb{R},\forall
k,\forall\varphi\in\\{\phi,\psi,X,Y,Z\\}$, are mutually independent and
standard normally distributed. This set of processes is constructed such that
$\phi$ represents a (hidden) redundancy process which "induces" redundant
information exchanges to $Z$ via $X$ and $Y$ but not via $\psi$. However,
$\psi$ is also causally providing information to the target. Thus, if one
would use a measure like (5), then the redundancy would be estimated as being
zero, since $\psi$ is causally independent of $X$ and $Y$. Even if the mutual
dependency between the sources were left out, the estimate would be the
minimum of $I(\psi;Z),I(\phi;Z),I(X;Z),I(Y;Z)$, which is also wrong, since the
information provided by $(X,Y)$ is independent (and hence not redundant) of
that provided by $\psi$ to the target. Our key idea is to only focus upon the
relevant source processes, $X$ and $Y$, which provide some common directed
information to $Z$ even though they are causally independent of each other.

###  III-B Directed Redundancy for Processes

In the sequel, we will consider the transfer entropy to be our desired measure
of directed (causal) information exchange. Our results are also valid if the
transfer entropy is substituted by, e.g., conditional directed information
[16, 17].

###### Definition 1

_The transfer-entropy measurable causal redundancy provided to the target
$\\{Z_{k}\\}$ via the source processes $\\{X_{k}\\},\\{Y_{k}\\}$, which are
driven by the hidden redundancy process $\\{\phi_{k}\\}$ is defined as:_

$\displaystyle
I^{\mathrm{red}}(\\{X_{k}\\};\\{Y_{k}\\};\\{Z_{k}\\})\triangleq$
$\displaystyle\min\ (\mathbb{TE}(\phi\to Z),\mathbb{TE}(\phi\to
T_{XZ}),\mathbb{TE}(\phi\to T_{YZ}),$ $\displaystyle\mathbb{TE}(T_{XZ}\to
Z),\mathbb{TE}(T_{YZ}\to Z),I(\\{T_{XZ}\\};\\{T_{YZ}\\})\ ),$

_where $T_{XZ}$ is a _causal_ minimal sufficient statistics for $X$ with
respect to $Z$, which we define to mean that $T_{XZ}$ satisfies the
conditional Markov chain_

$\vspace{-3mm}X^{n-1}|_{Z^{n-1}}-T_{XZ}^{n-1}|_{Z^{n-1}}-Z_{n}|_{Z^{n-1}},\forall
n,$

where

$\displaystyle T^{n-1}_{XZ}$
$\displaystyle=\arg\min_{S_{XZ}^{n-1}}I(S_{XZ}^{n-1};Z_{n}|Z^{n-1})$
$\displaystyle s.t.\quad
I(S_{XZ}^{n-1};Z_{n}|Z^{n-1})=I(X^{n-1};Z_{n}|Z^{n-1}),\forall n.$

The last quantity $I(\\{T_{XZ}\\};\\{T_{YZ}\\})$ in the definition is a
standard mutual information. This term is necessary to exclude the case where
$X$ and $Y$ would only be providing non-redundant information to $Z$ in which
case $I(\\{T_{XZ}\\};\\{T_{YZ}\\})=0$.

It is non-trivial to find minimal sufficient statistics for general sources,
and below we introduce an upper bound to the redundancy that does not rely on
minimal sufficient statistics.

###### Lemma 1

_Consider the dynamical system in ( 7) – (11). The amount of redundant
transfer entropy communicated via $X$ and $Y$ to $Z$, and contained in $Z$, is
upper bounded by:_

$\displaystyle I^{\mathrm{red}}(\\{X_{k}\\}$
$\displaystyle;\\{Y_{k}\\};\\{Z_{k}\\})\leq\min\,(\mathbb{TE}(\phi\to
Z),\mathbb{TE}(\phi\to X),$ $\displaystyle\mathbb{TE}(\phi\to
Y),\mathbb{TE}(X\to Z),\mathbb{TE}(Y\to Z)).$ (12)

###### Proof:

The proof follows by replacing the minimal sufficient statistics in Definition
1 by their associated random processes. Omitting
$I(\\{T_{XZ}\\};\\{T_{YZ}\\})$ can only increase the estimated redundancy.
$\mathbb{TE}(X\to Z)$ may overestimate the amount of information exchanged
from $X$ to $Z$, since $Z$ also receives information from $Y$. Similarly for
$\mathbb{TE}(Y\to Z)$. Thus, it is necessary to also take into account the
amount of redundant information that is induced into $X$ and $Y$. This is
upper bounded by $\mathbb{TE}(\phi\to X)$ and $\mathbb{TE}(\phi\to Y)$,
respectively. Finally, since $\phi$ is driving the redundancy in the system,
the redundancy can be no greater than $\mathbb{TE}(\phi\to Z)$. ∎

The following lemma demonstrates the existence of systems that are bounded by
the different terms in (12), and thereby showing that all of the terms are
needed.

###### Lemma 2

_Consider the system in ( 7) – (11) and let $a=b=0$, then:_

$\displaystyle\mathbb{TE}(\phi\to X)$ $\displaystyle=\mathbb{TE}(\phi\to
Y)=\frac{1}{2}\log_{2}\big{(}c^{2}\sigma_{\phi}^{2}+1\big{)},$ (13)
$\displaystyle\mathbb{TE}(\phi\to Z)$
$\displaystyle=\frac{1}{2}\log_{2}\bigg{(}\frac{4d^{2}c^{2}\sigma_{\phi}^{2}+2d^{2}+e^{2}+1}{2d^{2}+e^{2}+1}\bigg{)},$
(14) $\displaystyle\mathbb{TE}(X\to Z)$ $\displaystyle=\mathbb{TE}(Y\to Z)$
$\displaystyle=\frac{1}{2}\log_{2}\bigg{(}\frac{4c^{2}d^{2}\sigma_{\phi}^{2}+2d^{2}+e^{2}+1}{\frac{dc^{2}\sigma_{\phi}^{2}}{c^{2}\sigma_{\phi}^{2}+1}+d^{2}+e^{2}+1}\bigg{)},$
(15)

_where $\sigma_{\phi}^{2}$ is the stationary variance of $\phi$, and
$\sigma^{2}_{W^{\varphi}}=1$ for $\varphi\in\\{\psi,X,Y,Z\\}$. Moreover, for
$c=d>0$, and $e=1$, the minimum in (12) is explicitly given by: _

$\displaystyle I^{\mathrm{red}}(\\{X_{k}\\};\\{Y_{k}\\};\\{Z_{k}\\})$ (16)
$\displaystyle\leq\begin{cases}\mathbb{TE}(\phi\to
Z),&0<c<1,\sigma_{\phi}^{2}<4,\\\ \mathbb{TE}(\phi\to X)=\mathbb{TE}(\phi\to
Y),&c\geq 1,\sigma_{\phi}^{2}<4,\\\ \mathbb{TE}(X\to Z)=\mathbb{TE}(Y\to
Z),&\xi_{1}\leq c\leq\xi_{2},\sigma_{\phi}^{2}\geq 4,\end{cases}$

_where
$\xi_{1}=\frac{1}{2}\sigma_{\phi}-\frac{1}{2}\sqrt{\sigma_{\phi}^{2}-4}$ and
$\xi_{2}=\frac{1}{2}\sigma_{\phi}+\frac{1}{2}\sqrt{\sigma_{\phi}^{2}-4}$. _

###### Proof:

We first expand $\mathbb{TE}(\phi\to Z)$ by the chain rule of mutual
information:

$\displaystyle\mathbb{TE}(\phi\to Z)=$ $\displaystyle
I(\phi^{k-1};Z_{k}|Z^{k-1})=I(\phi_{k-4};Z_{k}|Z^{k-1})$
$\displaystyle+I(\phi^{k-1}\backslash\phi_{k-4};Z_{k}|Z^{k-1},\phi_{k-4}).$

The first term can be further written as:

$\displaystyle I(\phi_{k-4};Z_{k}|Z^{k-1})$
$\displaystyle=I(\phi_{k-4};d(X_{k-2}+Y_{k-2})+e\psi_{k-2}+W_{k-1}^{Z}|Z^{k-1})$
$\displaystyle=I(\phi_{k-4};d(2c\phi_{k-4}+W_{k-3}^{X}+W_{k-3}^{Y})+e\psi_{k-2}$
$\displaystyle\quad+W_{k-1}^{Z}|Z^{k-1})$
$\displaystyle\overset{(*)}{=}I(\phi_{k-4};d(2c\phi_{k-4}+W_{k-3}^{X}+W_{k-3}^{Y})+e\psi_{k-2}+W_{k-1}^{Z})$
$\displaystyle=\frac{1}{2}\log_{2}\bigg{(}\frac{4d^{2}c^{2}\sigma_{\phi}^{2}+2d^{2}+e^{2}+1}{2d^{2}+e^{2}+1}\bigg{)}.$

Since $a=b=0$, $(*)$ follows, and it further implies
$I(\phi^{k-1}\backslash\phi_{k-4};Z_{k}|Z^{k-1},\phi_{k-4})=0$. Similarly, we
have that:

$\displaystyle\mathbb{TE}(\phi\to X)=I(\phi^{k-1};X_{k}|X^{k-1})$
$\displaystyle=I(\phi_{k-2};c\phi_{k-2}+W_{k-1}^{X}|X^{k-1})$
$\displaystyle\quad+I(\phi^{k-1}\backslash\phi_{k-2};X_{k}|X^{k-1},\phi_{k-2}).$
$\displaystyle=I(\phi_{k-2};c\phi_{k-2}+W_{k-1}^{X}|X^{k-1})=\frac{1}{2}\log_{2}\big{(}c^{2}\sigma_{\phi}^{2}+1\big{)}$
$\displaystyle=\mathbb{TE}(\phi\to Y).$

Finally, $\mathbb{TE}(Y\to Z)=\mathbb{TE}(X\to Z)$, where:

$\displaystyle\mathbb{TE}(X\to Z)=I(X^{k-1};Z_{k}|Z^{k-1})$
$\displaystyle=I(X_{k-2};dX_{k-2}+dY_{k-2}+e\psi_{k-2}+W_{k-1}^{Z}|Z^{k-1})$
$\displaystyle=\frac{1}{2}\log_{2}\bigg{(}\frac{4c^{2}d^{2}\sigma_{\phi}^{2}+2d^{2}+e^{2}+1}{d\mathrm{var}(c\phi_{k-4}|X_{k-2})+d^{2}+e^{2}+1}\bigg{)},$
$\displaystyle\mathrm{var}(c\phi_{k-4}|X_{k-2})=\frac{c^{2}\sigma_{\phi}^{2}}{c^{2}\sigma_{\phi}^{2}+1}.$

All the arguments of the logarithms in (13), (14), and (15) are convex in
$c=d$, and are having their minima at $c=0$ and maxima at $c=\infty$. Pairwise
equating the arguments of (13), (14), and (15), and solving for $c$, yields
real roots corresponding to the cases provided in (16). The minima can then
readily be verified by evaluating the arguments for any $c$ within the
corresponding regions. ∎

###### Example 1

Let $a=d=e=1/3,b=1/5,c=1/2$, and let the length of the processes in (7) – (11)
be $N=5000$. The transfer entropies between all pairs of processes are shown
in Table I.111The TRENTOOL transfer entropy estimator of [18] was used. It can
be observed that all sources ($\psi,\phi,X,Y$) appears to be coupled to the
target $Z$, and one could therefore wrongly conclude that they all provide a
degree of common (redundant) information, which would be upper bounded by
$\mathbb{TE}(\psi\to Z)\approx 0.03$. This is clearly a false assessment,
since the information provided by $\psi$ to $Z$ is distinct from that provided
by $X$ to $Z$ and hence $\psi$ and $X$ convey zero common information to $Z$.
Let us now ignore $\psi$ and treat $\phi$ as the source that is driving the
redundancy. An upper bound to the amount of common information which $X$ and
$Y$ both relay to $Z$ is then via Lemma 1 estimated as $\mathbb{TE}(\phi\to
Z)\approx 0.04$.

TABLE I: Transfer entropies between the processes in (7) – (11). From/To | $\psi$ | $\phi$ | $X$ | $Y$ | $Z$
---|---|---|---|---|---
$\psi$ | – | 0.00 | 0.00 | 0.00 | 0.03
$\phi$ | 0.00 | – | 0.09 | 0.09 | 0.04
$X$ | 0.00 | 0.00 | – | 0.00 | 0.06
$Y$ | 0.00 | 0.00 | 0.00 | – | 0.06
$Z$ | 0.00 | 0.00 | 0.00 | 0.00 | –

In the above example, we deliberately made the choice of omitting $\psi$, and
focusing on the exchange of redundant information from $\phi$ only via the
sources $X$ and $Y$ to the target $Y$. For larger systems, or for systems with
unknown dynamics, it would be advantageous to use a systematic approach to
select the hidden redundancy process and the associated desired set of
relevant sources. In principle, one could consider all possible subsets of
sources and find the one that maximizes the minimal transfer entropy among
them. This is a problem with exponential complexity in the number of possible
subsets, and equally important, it is known that the amount of redundant
information between variables is decreasing in the number of variables [3].
Thus, such a strategy would potentially be biased towards selecting a minimal
number of sources. We propose an efficient strategy for finding a hidden
redundancy process and selecting its associated relevant sources in Section
IV.

##  IV Selecting relevant source processes

In this section, we consider multiple sources
$\mathcal{S}\triangleq\\{X^{N}(1),X^{N}(2),\dotsc,X^{N}(J)\\},$ and a single
target $Z^{N}$. We will first identify the subset
$\mathcal{T}\subseteq\mathcal{S}$ of sources that are relevant with respect to
the target $Z^{N}$, i.e., we are interested in determining whether they are
"causally" coupled to the target as measured by the strength of the transfer
entropy from $X^{N}(j)$ to $Z^{N}$. Then we identify the hidden process,
$\phi$, and finally identify the subset $\mathcal{R}\subseteq\mathcal{T}$ of
_relevant_ sources, i.e., those that are all governed by the hidden process
$\phi$ and in addition they are all coupled to the target.

###  IV-A Target-relevant source processes

We propose to find a tentative set $\mathcal{T}$ of sources, which is a set of
sources that are all coupled to the target. We refer to $\mathcal{T}$ as the
target-relevant set of sources. We choose to define this set as the one with
the minimal number of sources that provides at least an $\eta$-fraction of the
total sum of transfer entropy from all sources to the target. This is akin to
the smallest high-probability sets in [19, Ch.4.3]. This can formally be
stated as the following optimization problem (for $\eta_{T}\in[0,1]$):

$\displaystyle\mathcal{T}=\arg\min_{\mathcal{J}\subseteq\\{1,\dotsc,J\\}}|\mathcal{J}|$
(17) $\displaystyle s.t.\ \sum_{j\in\mathcal{J}}\mathbb{TE}(X^{N}(j)\to
Z^{N})\geq\eta_{T}\sum_{j=1}^{J}\mathbb{TE}(X^{N}(j)\to Z^{N}).$

The constraint in (17) provides an efficient way to omit sources that are only
weakly coupled to the target. The optimization problem can be efficiently
computed by first sorting the transfer entropies in descending order, and then
including the greatest elements one by one until the threshold is breached. If
several elements have equal probability, there could be ambiguous output
unless $\eta_{T}$ is adjusted to either include or exclude all of the equal
probability elements, cf. [19].

###  IV-B Identifying the hidden process

We will now find the hidden redundancy process, which is that particular
source out of all the sources in $\mathcal{S}$, which dominates the redundancy
within a selective group of _relevant_ sources. For each source $X^{N}(i)$,
where $i\in\mathcal{S}$, find the minimal subset $\hat{\mathcal{T}}(i)$ of
$\mathcal{T}$ that provides a given fraction $(\eta_{H}\in[0,1])$ of the total
amount of transfer entropy:

$\displaystyle\hat{\mathcal{T}}(i)=\arg\min_{\mathcal{J}\subseteq\mathcal{T}}|\mathcal{J}|,\quad
s.t.$ (18) $\displaystyle\sum_{j\in\mathcal{J}}\mathbb{TE}(X^{N}(i)\to
X^{N}(j))\geq\eta_{H}\sum_{j\in\mathcal{T}}\mathbb{TE}(X^{N}(i)\to X^{N}(j)).$

The minimal causal information exchange $R(i)$ from the $i$th source and to
its associated processes in $\hat{\mathcal{T}}(i)$ is:

$\displaystyle R(i)=\min_{j\in\hat{\mathcal{T}}(i)}\mathbb{TE}(X^{N}(i)\to
X^{N}(j)).$ (19)

Out of all the $J$ source processes in $\mathcal{S}$, the one that induces the
greatest minimal redundancy within its associated set of sources will be
chosen as the hidden redundancy process:

$\displaystyle i^{*}$ $\displaystyle=\arg\max_{i\in\mathcal{S}}R(i),$ (20)
$\displaystyle\phi^{N}$ $\displaystyle=X^{N}(i^{*}),$ (21)
$\displaystyle\mathcal{R}$ $\displaystyle=\hat{\mathcal{T}}(i^{*}),$ (22)

where $\phi^{N}$ is the hidden redundancy process,
$\mathcal{R}\subseteq\mathcal{T}$ is the set of relevant sources associated
with $\phi^{N}$, and $R(i^{*})$ is an upper bound on the redundancy induced by
$\phi^{N}$ into the set $\mathcal{R}$.

###  IV-C Bounding the minimal redundant information

Inspired by Lemma 1, we formulate the following upper bound to the causal
redundancy defined by Definition 1:

###### Theorem 1

_The minimal redundant information causally exchanged (as measured by the
transfer entropy) to the target via a set of relevant sources, and which is
due to a single hidden redundancy process is upper bounded by:_

$\displaystyle I^{\mathrm{red}}(X^{N}(1);$
$\displaystyle\cdots;X^{N}(J);Z^{N})$ $\displaystyle\leq\min\,(R_{\phi\to
Z},R_{\phi\to\mathcal{R}},R_{\mathcal{R}\to Z}),$ (23)

_where_

$\displaystyle R_{\phi\to Z}=\mathbb{TE}(\phi^{N}\to
Z^{N}),R_{\phi\to\mathcal{R}}=R(i^{*}),$ (24) $\displaystyle R_{\mathcal{R}\to
Z}=\min_{j\in\mathcal{R}}\mathbb{TE}(X^{N}(j)\to Z^{N}).$ (25)

###### Proof:

$R_{\phi\to Z}$ bounds the information exchange from the hidden redundancy
process to the target, $R_{\phi\to\mathcal{R}}$ bounds the information
exchange from the hidden redundancy process and to the relevant sources, and
$R_{\mathcal{R}\to Z}$ bounds the information exchange from the relevant
sources to the target. ∎

##  V Simulation study

We consider 76-channel real-world intracranial EEG recordings obtained from a
patient undergoing 8 periods of seizures. 64 cortical electrodes (referred to
as electrodes 1 – 64) and 12 in-depth electrodes (referred to as electrodes 65
– 76) arranged as two 6 nodes depth-strips were implanted on the subject.
Details about the data can be obtained from [20]222Data available online:
http://math.bu.edu/people/kolaczyk/datasets.html. It was pointed out in [20]
that in particular the depth-strip with electrodes 71 – 76 and the lower left
corner of the cortical grid with electrodes 1 – 4, 9 – 11, and 17 exhibited
strong synchronous neuronal activity during seizures.

In our study, the lower range of cortical electrodes ranging from 1 – 20 will
be considered the targets. The sources will be all the 12 depth electrodes and
the hidden redundancy processes will also be found amongst the 12 depth
electrodes. For each target electrode we first find the set of sources
$\mathcal{T}$ that are coupled to the target using (17). Then we identify the
hidden redundancy process, which is inducing the majority of the redundancy in
the set. This is done using (21). Having identified a potential hidden
redundancy process for a given target electrode, we then use (22) to find the
associated set $\mathcal{R}$ of _relevant_ source processes. From the target,
the hidden redundancy process, and this set of relevant source processes, we
can find the corresponding transfer entropies given by (24). These are plotted
in Fig. 1. The parameters used for the transfer entropy estimator are: a
maximum lag of 5, 10 nearest neighbors, and $\eta_{T}=\eta_{H}=0.8$. A greater
$\eta_{T}$ means less source selected.

From Fig. 1 one can observe that the minimal redundancy mainly follows
$R_{\mathcal{R}\to Z}$, i.e., the minimal transfer entropy from the relevant
sources and to the targets. It is interesting to see that the minimal
redundancy is peaking for target electrodes 6 – 8 and 14 – 16, which are
complementary to the electrodes identified in [20] that were exhibiting strong
synchronous neuronal activity. Moreover, the transfer entropy $R_{\phi\to Z}$
between the hidden redundancy processes and the targets reaches its minima
when $R_{\mathcal{R}\to Z}$ is peaking. This can be explained by the fact that
when $R_{\mathcal{R}\to Z}$ is high, the same information is exchanged via
different sources, and thus the total information about $\phi$ that exists in
the targets is not much greater than that provided by a single source. On the
other hand, when $R_{\mathcal{R}\to Z}$ is low, the different sources could
potentially provide distinct information about $\phi$ to the target, which
would result in an overall greater amount of information about $\phi$ in the
targets. To further explore the cases, where the redundancy is peaking, i.e.,
for target electrodes 6 – 8 and 14 – 16, we have shown the histograms for the
selected hidden redundancy processes, see Fig. 1 (right), and their associated
relevant sources, see Fig. 2 (left). It is interesting to note from Fig. 2
(left) that the redundancy appears to mainly come from within sources on the
same depth-strip (electrodes 65 – 70). Moreover, Fig. 1 (right) shows that the
hidden redundancy process is also mainly belonging to this depth-strip. The
most frequently chosen electrode as the hidden redundancy process is #68. This
one is then selected less as a relevant source, since the hidden redundancy
process is excluded when finding the relevant sources. We have tried to
compare our findings with the graph theoretic analysis of the electrodes
provided in [20], however, we have been unable to explain why electrode 68
appears to be the main driver of redundancy. For comparison, we have in Fig. 2
(right) shown the histogram of the sources $\mathcal{T}$ in (17), i.e., those
having 80% of the entire transfer entropy to the targets. In this case, the
hidden redundancy process is not taken into account, and a more uniform
distribution is obtained compared to Fig. 2, where the hidden redundancy
process is taken into account.

Figure 1: Left: Redundancy (24) – (25) in intracranial EEG data. Right:
Histogram of the sources that are chosen as the hidden redundancy process for
the targets 6 – 8 and 14 – 16.

Figure 2: Left: Histogram of the selected relevant sources using a hidden
redundancy process. Only hidden redundancy processes and relevant source
processes that are causally coupled to the targets 6 – 8 and 14 – 16 are
considered. Right: Histogram of $\mathcal{T}$ in (17), i.e., the 80% greatest
coupled sources to the targets without using a hidden redundancy process.

##  VI Conclusions

We proposed a new methodology for quantifying the causal redundancy provided
by a set of source processes (time series) to a target process. The sources do
not need to be causally dependent upon each other. Instead we motivated the
existence of a hidden redundancy process, which governs the redundancy within
a subset of the source processes. We defined a set of relevant source
processes to be those that are causally coupled to the target, and where the
hidden redundancy process is causally coupled to all of them. We finally
provided an upper bound for the redundancy as the minimal average redundancy
from the relevant sources to the target, from the hidden redundancy process to
the target, and from the hidden redundancy process to the relevant sources.

## References

  * [1] T. Cover and J. Thomas, _Elements of Information Theory_. Wiley-Interscience, 2006.
  * [2] R. Yeung, “A first course in information theory,” _Springer_ , 2002.
  * [3] P. L. Williams and R. D. Beer, “Nonnegative decomposition of multivariate information,” _CoRR_ , vol. abs/1004.2515, 2010.
  * [4] M. Harder, C. Salge, and D. Polani, “Bivariate measure of redundant information,” _Physical Review E_ , vol. 87, no. 1, 2013.
  * [5] N. Bertschinger, J. Rauh, E. Olbrich, J. Jost, and N. Ay, “Quantifying unique information,” _Entropy_ , vol. 16, p. 2161–2183, 2014.
  * [6] R. A. A. Ince, “Measuring multivariate redundant information with pointwise common change in surprisal,” _Entropy_ , vol. 19, no. 7, 2017.
  * [7] R. G. James and J. P. Crutchfield., “Multivariate dependence beyond shannon information,” _Entropy_ , 2017.
  * [8] M. Wibral, V. P. J. Kay, J. Lizier, and W. Philips, “Partial information decomposition as a unified approach to the specification of neural goal functions,” _Brain and Cognition_ , vol. 112, 2017.
  * [9] J. Kunert-Graf, N. Sakhanenko, and D. Galas, “Partial information decomposition and the information delta: A geometric unification disentangling non-pairwise information,” _Entropy_ , vol. 22, no. 1333, 2020\.
  * [10] R. James, J. Emenheiser, and J. Crutchfield, “Unique information and secret key agreement,” _MDPI Entropy_ , vol. 21, no. 1, 2021.
  * [11] P. Mediano, F. Rosas, A. Luppi, R. Carhart-Harris, D. Bor, A. Seth, and A. Barrett, “Towards an extended taxonomy of information dynamics via integrated information decomposition,” _arxiv.org:_ , 2021.
  * [12] A. B. Barrett, “Exploration of synergistic and redundant information sharing in static and dynamical gaussian systems,” _Phys. Rev. E._ , vol. 91, no. 052802, 2015.
  * [13] T. Schreiber, “Measuring information transfer,” _Phys. Rev. Lett._ , vol. 85, 2000.
  * [14] L. Faes, D. Marinazzo, and S. Stramaglia, “Multiscale information decomposition: Exact computation for multivariate gaussian processes,” _Entropy_ , 2017.
  * [15] A. Luppi, P. Mediano, F. Rosas, N. Holland, T. Fryer, J. O’Brien, J. Rowe, D. Menon, D.Bor, and E. Stamatakis, “A synergistic core for human brain evolution and cognition,” _Nature Neuroscience_ , vol. 25, 2022.
  * [16] J. Massey, “Causality, feedback and directed information,” _The International Symposium on Information Theory and Its Applications_ , 1990.
  * [17] G. Kramer, “Capacity results for the discrete memoryless network,” _IEEE Transactions on Information Theory_ , vol. 49, no. 1, pp. 4–21, 2003.
  * [18] M. Lindner, R. Vicente, V. Priesemann, and M. Wibral, “Trentool: a matlab open source toolbox to analyse information flow in time series data with transfer entropy,” _BMC Neurosci._ , vol. 12, p. 119, 2011.
  * [19] D. J. C. MacKay, _Information theory, inference, and learning algorithms_. Cambridge University Press, 2003.
  * [20] M. A. Kramer, E. D. Kolaczyk, and H. E. Kirsch, “Emergent network topology at seizure onset in humans,” _Epilepsy Research_ , vol. 79, no. 173 – 186, 2008\.


# Certifying Unknown Genuine Multipartite Entanglement by Neural Networks

Zhenyu Chen1 Xiaodie Lin1 Zhaohui Wei2,3, Email<EMAIL_ADDRESS>1Institute for Interdisciplinary Information Sciences, Tsinghua University,
Beijing 100084, China
2Yau Mathematical Sciences Center, Tsinghua University, Beijing 100084, China
3Yanqi Lake Beijing Institute of Mathematical Sciences and Applications,
101407, China

###### Abstract

Suppose we have an unknown multipartite quantum state, how can we
experimentally find out whether it is genuine multipartite entangled or not?
Recall that even for a bipartite quantum state whose density matrix is known,
it is already NP-Hard to determine whether it is entangled or not. Therefore,
it is hard to efficiently solve the above problem generally. However, since
genuine multipartite entanglement is such a fundamental concept that plays a
crucial role in many-body physics and quantum information processing tasks,
finding realistic approaches to certify genuine multipartite entanglement is
undoubtedly necessary. In this work, we show that neural networks can provide
a nice solution to this problem, where measurement statistics data produced by
measuring involved quantum states with local measurement devices serve as
input features of neural networks. By testing our models on many specific
multipartite quantum states, we show that they can certify genuine
multipartite entanglement very accurately, which even include some new results
unknown before. We also exhibit a possible way to improve the efficiency of
our models by reducing the size of features. Lastly, we show that our models
enjoy remarkable robustness against flaws in measurement devices, implying
that they are very experiment-friendly.

††preprint: APS/123-QED

##  I Introduction

Quantum entanglement plays a central role in many quantum information
processing tasks, including quantum communication [1], quantum cryptography
[2] and quantum key distribution [3]. As a consequence, certifying the
existence of quantum entanglement is a fundamental problem.

However, it has been proved that even for a bipartite quantum state that the
density matrix is completely known, to determine whether it is entangled or
not is already NP-Hard [4], implying that it is hard to generally solve this
problem efficiently. Nevertheless, due to its importance, numerous approaches
have been put forward to certify bipartite entanglement [5, 6, 7, 8, 9].

Meanwhile, we often face the situation that the target bipartite quantum state
we would like to characterize is unknown to us, i.e., its density matrix is
not available, making the task even tougher. For this, one may first
reconstruct the density matrix by quantum state tomography [10, 11, 12], and
then try to solve the problem accordingly. However, it is well-known that this
procedure is extremely expensive and can only be implementable when the size
of the target quantum state is small. To overcome this difficulty, some
realistic alternative approaches can be utilized, which include entanglement
witness [13, 14, 15] and device-independent schemes [16, 17, 18, 19]. But they
also suffer from other drawbacks, say being sensitive to operation errors or
being easy to fail in providing valuable outcomes.

When it comes to multipartite quantum states, the problem becomes even more
complicated, as the mathematical structures of multipartite quantum
entanglement are much richer than the bipartite case. Particularly, as a
speical form of multipartite entanglement that is highly valuable, genuine
multipartite entanglement has significant applications in quantum
teleportation [20, 21], quantum state sharing [22], quantum metrology [23,
24], and even chemical and biological processes [25]. To certify it, many
methods have been proposed. For example, when the full information of density
matrices are known, quite a lot of mathematical criteria that can detect
multipartite genuine entanglement have been proposed [26, 27, 28, 29, 30, 31,
32].

Similar to the bipartite case, we also have to handle the case that full
information of target multipartite quantum states is not available, which is
actually an extremely common and realistic problem from the viewpoint of
engineering. For this, known methods such as quantum state tomography,
entanglement witness, and device-independent schemes have been applied to
certify genuine multipartite entanglement [33, 34, 35, 36, 17, 37]. However,
facing similar difficulties as in the bipartite case, it is not hard to
understand that these approaches cannot provide satisfying solutions for this
task. As a result, due to its central role in quantum computing and quantum
engineerings, finding realistic approaches to certify unknown genuine
multipartite entanglement is a challenging yet urgent task, which is also the
main motivation of the current paper.

Recently, machine learning approaches have been employed to characterize
quantum properties [38, 39, 40, 41, 42, 43, 44, 45]. Different from analytic
methods, machine learning is a data-driven approach which aims at making
predictions on unseen data by learning from training data. In these works,
following standard procedures of machine learning tasks, certain features are
extracted from training quantum states, which are then fed into machine
learning models. Then we train these models by adjusting the parameters they
contain such that the models can make predictions on training quantum states
with high accuracy, and if the model details are chosen properly, they can
also make accurate predictions on target quantum states unseen before. Here,
based on the chosen forms of features, different machine learning models can
be designed to detect quantum properties.

In this work, we exploit the possibility that utilizes neural networks to
certify genuine multipartite entanglement for _general_ quantum states, where
the features we choose is measurement statistics data produced by measuring
involved quantum states with local measurement devices. Here each subsystem of
involved multipartite quantum states is measured by at least two devices.
Inspired by Bell experiments, we believe that this kind of measurement
statistics data can reveal nontrivial quantum properties for target quantum
states.

It turns out that our idea works very well. Particularly, we successfully
train a series of neural network models that can certify unknown genuine
multipartite entanglement very accurately, where the target quantum states are
quite diverse. Taking 4-qubit quantum states for example, we first train a
proper model, and then we run the same trained model on four different classes
of 4-qubit quantum states, on each of which our model successfully certify
genuine 4-qubit entanglement with accuracy over 99%. Interestingly, our model
even reports some new results that are unknown before, indicating that machine
learning models can be highly valuable in such a challenging task. We confirm
the high performance of neural networks on many other test quantum states,
which include quantum state sets that are sampled randomly without any
assumptions.

Meanwhile, we also proposed a modified scheme called $k$-correlation to reduce
the cost of our approach, and we show that in some cases where certain
specific prior knowledge is available, the cost of our approach can be sharply
reduced while the prediction accuracy is still comparable.

Lastly, we provide evidence showing that our approach enjoys remarkable
robustness against flaws in measurement devices, which implies that our
approach is very experiment-friendly.

##  II Deep learning and Entanglement structure

In this work, the certification of genuine multipartite entanglement is
formulated as a supervised binary classification task, where the deep learning
method is applied. Deep learning is a powerful machine learning model based on
artificial neural networks. It has great representative ability and has been
widely utilized in a variety of fields such as image recognition [46], natural
language processing [47], recommendation systems [48] and so on.

For our task we apply fully connected neural networks (FNNs) to fit the
training set, for more details one can see Refs.[49, 50]. Following the
standard procedure of machine learning, we need to gather a training dataset
and a test dataset, which have the form of
$\left\\{\left(\bm{x}_{1},y_{1}\right),\ldots,\left(\bm{x}_{N},y_{N}\right)\right\\}$,
where $N$ is the size of the set, $\bm{x}_{i}$ is the feature of the $i$-th
sample, and $y_{i}$ is the label. The labels of training dataset are known to
us, and the mission of the neural network is to predict the labels for the
test dataset. When training the model, we input the features of training
dataset into the model and adjusting its parameters such that it can produce
correct labels for the training dataset. For this, a proper loss function, a
reasonable configuration for the nerual network, and an efficient optimization
method such as gradient-descent have to be chosen. If the model is trained
properly, it can predict accurately the labels of test dataset unseen before.

In this work we apply the deep learning method to certify genuine multipartite
entanglement, which is also a typical binary-classification task. In general,
a multipartite quantum state can involves many subsystems and thus its
entanglement structure can be very complicated. An $n$-partite pure quantum
state $\left|\Psi_{k-sep}\right\rangle$ is called _$k$ -separable_, where
$1\leq k\leq n$, if and only if it can be written as a tensor product of $k$
substates:

$\displaystyle\left|\Psi_{k-sep}\right\rangle=\left|\Psi_{1}\right\rangle\otimes\left|\Psi_{2}\right\rangle\otimes\cdots\otimes\left|\Psi_{k}\right\rangle.$
(1)

Correspondingly, a mixed state is called $k$-separable, if and only if it has
a decomposition into $k$-separable pure states. A multipartite quantum state
is called _genuinely multipartite entangled_ if it can not be written as
$k$-separable for $k=2$, otherwise we call it _biseparable state_. In
addition, a quantum state is said to be of _entanglement intactness $k$_, if
it is $k$-separable but not $(k+1)$-separable.

##  III Detecting Genuine Multipartite Entanglement for Qubit Systems

###  III.1 3-qubit case

####  III.1.1 The setup

As the simplest case, we first try to detect genuine multipartite entanglement
for 3-qubit quantum states. As mentioned above, since our approach is based on
a neural network, we need to prepare a large number of quantum states to train
(and test) the neural network. In this work, we always sample random
$d$-dimensional quantum state $\rho\in\mathcal{H}^{d}$ according to spectral
decomposition

$\displaystyle\rho=\sum_{i=0}^{d-1}\lambda_{i}|u_{i}\rangle\langle u_{i}|.$
(2)

Here we randomly choose nonnegative numbers $\lambda_{i}$’s such that they
satisfy $\sum_{i}\lambda_{i}=1$. Then we generate a $d\times d$ Haar random
unitary $U$, and set $|u_{i}\rangle$ to be the $i$-th column of $U$, which
means that $\\{|u_{i}\rangle\\}$ forms a set of orthonormal basis for
$\mathcal{H}^{d}$. Particularly, if $\lambda_{i}=1$ for some $0\leq i\leq
d-1$, $\rho$ will be a pure state. For now we need to sample 3-qubit quantum
state, so we let $d=8$.

After sampling 3-qubit quantum states, we need to prepare labels for them,
i.e., indicating whether they are genuinely tripartite entangled or not. This
will be done by the result given in Ref.[26], which proves that the following
relation must be satisfied by any biseparable 3-qubit quantum states,

$\begin{split}|\varrho_{2,3}|+&\left|\varrho_{2,5}\right|+\left|\varrho_{3,5}\right|\leqslant\sqrt{\varrho_{1,1}\varrho_{4,4}}+\sqrt{\varrho_{1,1}\varrho_{6,6}}\\\
&+\sqrt{\varrho_{1,1}\varrho_{7,7}}+\frac{1}{2}\left(\varrho_{2,2}+\varrho_{3,3}+\varrho_{5,5}\right),\end{split}$
(3)

where $\varrho_{i,j}$ is the ($i,j$)-th entry of the density matrix.

Therefore, violating Eq.(3) implies the existence of genuine tripartite
entanglement. Utilizing this criterion, we sample 30,000 genuinely tripartite
entangled states. Concretely, we generate a 3-qubit state by Eq.(2), then
substitute the density matrix into Eq.(3). If the equation.(3) does not hold,
we keep this state, otherwise we drop it. Repeat this process until 30,000
genuinely tripartite entangled states are collected. We label each of them
with ‘true’ label.

Next, we construct states with ‘false’ labels by sampling 20,000 biseparable
entangled quantum states and 20,000 fully separable states. When sampling
biseparable entangled quantum states, all 3 possible partitions are included,
that is, these quantum states are sampled according to the form

$\begin{split}p_{1}\rho_{A}\otimes\rho_{BC}+p_{2}\rho_{B}\otimes\rho_{AC}+p_{3}\rho_{C}\otimes\rho_{AB}.\end{split}$
(4)

Here $p_{1},p_{2},p_{3}\geq 0$ are randomly picked and satisfy
$\sum_{i=1}^{3}p_{i}=1$. $\rho_{AB},\rho_{AC},\rho_{BC}$ are bipartite
entangled states whose partial transpositions are not positive semi-definite,
implying the existence of partial entanglement [5].

Putting the 30,000 genuinely tripartite entangled states, 20,000 biseparable
entangled states, and 20,000 fully separable states sampled above together, we
obtain the set of training quantum states, for which the correct labels have
been pin down.

Then we extract features for the training quantum states, which is essentially
the measurement outcome statistics data when local quantum measurements are
performed on each qubit. To choose measurement devices, we assign $M$ Haar
random unitary matrices $U_{i1},U_{i2},\cdots U_{iM}\in\mathbb{C}^{2\otimes
2}$ to the $i$-qubit. Let $|u^{k}_{ij}\rangle$ be the $k$-th column of
$U_{ij}$, then the $j$-th measurement device belonging to the $i$-th qubit can
be expressed by the operators $P_{ij}=\\{|u^{k}_{ij}\rangle\langle
u^{k}_{ij}|\\}_{k=1}^{2}$, $j=1,2,\ldots M$. We emphasize that once the
measurement devices are sampled, they remain unchanged during the whole
process extracting features for all the training quantum states. What is more,
when afterward we run the trained model on test quantum states, we also use
the same measurement devices to extract features for the latter.

According to Born’s rule, the possibility that we obtain outcome
$a_{i}\in\\{1,2\\}$ when measuring the $i$-th qubit of $\rho$ with measurement
device $P_{ix_{i}}$ is given by

$\displaystyle p\left(a_{1}a_{2}\ldots a_{n}\mid x_{1}x_{2}\ldots
x_{n}\right)=\operatorname{Tr}\left(\left(\bigotimes_{i=1}^{n}P_{ix_{i}}^{a_{i}}\right)\rho\right),$
(5)

where $x_{i}\in\\{1,2,\ldots M\\}$. All the joint possibility distributions
$p\left(a_{1}a_{2}\ldots a_{n}\mid x_{1}x_{2}\ldots x_{n}\right)$ combined are
called a _correlation_ , which is the input features for our neural networks.

In the 3-qubit case, we assign 2 measurement devices for each qubit, i.e.,
$M=2$, thus the dimension of the input features turns out to be $2^{3}\times
2^{3}=64$.

The FNN we employ in this case has one input layer, one sigmoid output layer,
four hidden layers with $90,60,60,60$ neurons. To avoid overfitting, we add
one drop out layer with a rate of $20\%$ after the first hidden layer. The
loss function adopted for training is the binary crossentropy, which is widely
used in binary classification tasks and can be written as:

$\displaystyle\operatorname{loss}=\frac{1}{N}\left[-\sum_{i=1}^{N}y_{i}\log\hat{y}_{i}+\left(1-y_{i}\right)\log\left(1-\hat{y}_{i}\right)\right],$
(6)

where $N$ is the number of the samples in the training set, $y_{i}$ is the
$i$-th label of the training set, and $\hat{y}_{i}$ is the $i$-th output of
the neural network. In the training process, the parameters of neural networks
are adjusted constantly such that the loss function is optimized. In our
problem, when $\hat{y}_{i}\geq 0.5$ the neural network outputs an outcome
‘true’, meaning that the corresponding quantum state is genuinely tripartite
entangled, otherwise an outcome ‘false’, implying that the neural network
predicts the corresponding quantum state to be biseparable.

####  III.1.2 Performance on GHZ-Werner states and W-Werner states

After training the neural network, we now test its performance in certifying
genuine tripartite entanglement. First, we choose two well-known classes of
quantum states, which are Greenberger-Horne-Zeilinger (GHZ) -Werner states

$\displaystyle\hat{\rho}_{\mathrm{GW}n}\equiv(1-p)\left|\mathrm{GHZ}_{n}\right\rangle\left\langle\mathrm{GHZ}_{n}\right|+pI/2^{n},$
(7)

and W-Werner states

$\displaystyle\hat{\rho}_{\mathrm{WW}n}\equiv(1-p)\left|\mathrm{W}_{n}\right\rangle\left\langle\mathrm{W}_{n}\right|+pI/2^{n},$
(8)

where $|\mathrm{GHZ}_{n}\rangle=(|0\rangle^{\otimes n}+|1\rangle^{\otimes
n})/\sqrt{2}$ and $|\mathrm{W}_{n}\rangle=(|100\ldots 0\rangle+|010\ldots
0\rangle+\ldots+|00\ldots 01\rangle)/\sqrt{n}$. In our case, $n=3$.

In fact, these two classes of quantum states have been well-studied [26, 32].
It turns out that for a GHZ-Werner state $\hat{\rho}_{\mathrm{GW}n}$, it is
genuinely $n$-partite entangled if and only if $0\leqslant
p<1/\left[2\left(1-2^{-n}\right)\right]$, and is biseparable when $p\geq
1/\left[2\left(1-2^{-n}\right)\right]$. For convenience, we call the value
$1/\left[2\left(1-2^{-n}\right)\right]$ the _threshold_ for the GHZ-Werner
state to be genuinely $n$-partite entangled. When $n=3$, the threshold is
$0.571$. Similarly, for a W-Werner state $\hat{\rho}_{\mathrm{WW}3}$, it is
tripartite genuinely entangled if and only if $0\leqslant p<0.521$, thus the
threshold is $0.521$. And the threshold of $\hat{\rho}_{\mathrm{WW}n}$ with
$n\geq 4$ remains open.

The above theoretical results provide us a very nice chance to examine the
performance of the FNN model we have trained. For this, we first extract
features for $\hat{\rho}_{\mathrm{GW}3}$ and $\hat{\rho}_{\mathrm{WW}3}$ by
performing the measurement devices we sampled previously, where $p$ varies
from 0 to 1 at intervals 0.001, and then we input these features into our
neural network.

It turns out that the prediction accuracy of our model on both of the two
classes of test quantum states are over $99\%$. Particularly, the FNN model
predicts that the $\hat{\rho}_{\mathrm{GW}3}$ and $\hat{\rho}_{\mathrm{WW}3}$
are genuinely entangled if and only if $p\leq 0.577$ and $p\leq 0.530$,
respectively (recall that the exact thresholds for these two classes are 0.571
and 0.521 respectively). It is interesting to see that the output of the FNN
model also has a threshold pattern, i.e., it always gives ‘true’ predictions
when $p$ is smaller than certain value, and always gives ‘false’ otherwise.
Our model only makes mistakes near the exact threshold for
$\hat{\rho}_{\mathrm{GW}3}$ and $\hat{\rho}_{\mathrm{WW}3}$. Taking
$\hat{\rho}_{\mathrm{GW}_{3}}$ for example, the neural network provides wrong
predictions only when $p\in(0.572,0.577)$.

####  III.1.3 Performance on random quantum states

In some sense, $\hat{\rho}_{\mathrm{GW}3}$ and $\hat{\rho}_{\mathrm{WW}3}$ are
quite special 3-qubit quantum states. Therefore, to further assess the
performance of the FNN model we have trained, we now test it on more general
3-qubit quantum states.

In Ref.[27], the concept of tripartite entanglement of formation denoted
$E_{f}(\rho)$ was proposed to quantify genuine tripartite entanglement, which
is defined as

$\displaystyle
E_{f}(\rho)\equiv\min_{\left|\psi_{i}\right\rangle}\left(\sum_{i}p_{i}\min\left\\{S_{i}(A),S_{i}(B),S_{i}(C)\right\\}\right),$
(9)

where the first minimum is taken over all pure state decompositions of $\rho$
and $S_{i}(A),S_{i}(B),S_{i}(C)$ are the von Neumann entropies of the
subsystem A, B and C of $|\psi_{i}\rangle$. It turns out that $E_{f}(\rho)$
equals zero for biseparable states [27], and can be lower bounded by
$V_{\rho}$ defined as [51]

$\displaystyle\scriptsize-S(A|BC)-S(B|AC)-S(C|AB)-2\log\left(D_{\max}\right),$
(10)

where $S(A|BC)$ is the von Neumann conditional entropy, and $D_{\max}$ is the
maximum dimension of parties A, B, and C.

$V_{\rho}$ is easy to compute when $\rho$ is given, and can also certify the
existence of genuine tripartite entanglement if its value is positive.
Combining this criterion with the approach that generates random quantum
states given in Eq.(2), we sample 600 genuine tripartite entangled states.
Together with 200 biseparable entangled states and 200 fully separable states,
we construct a set of test quantum states. The features for these test quantum
states are also generated by Eq.(5), where the chosen measurement devices are
the same as those were utilized to prepare training dataset.

We now run the neural network we have trained before on this test dataset. It
turns out that our model again performs very well in this case, and the
prediction accuracy is over $99\%$. Considering that the test dataset is
generated randomly, it is fair to say that our model enjoys a very decent
performance in the 3-qubit case.

###  III.2 $4$-qubit case

Now we apply our approach on larger quantum systems, and turn to certify
genuine 4-partite entanglement. Again, to train the neural network properly,
we need to prepare a lot of training quantum states for which we know
entanglement structure accurately. However, the criteria we utilized to
certify genuine tripartite entanglement can not detect genuine 4-partite
entanglement very well. Instead, we now apply a new criterion provided by
Ref.[28]. Particularly, the concept of concurrence $C(\rho)$ is a genuine
multipartite entanglement measure, and positive concurrence indicates the
existence of genuine multipartite entanglement (see Ref.[28] for more
details). Define

$\displaystyle\begin{split}\mathcal{F}(\rho,\psi)=&\sum_{1\leqslant i\neq
j\leqslant n}\sqrt{\left\langle\Psi_{ij}\left|\rho^{\otimes
2}\Pi\right|\Psi_{ij}\right\rangle}\\\ &-\sum_{1\leqslant i\neq j\leqslant
n}\sqrt{\left\langle\Psi_{ij}\left|\mathcal{P}_{i}^{\dagger}\rho^{\otimes
2}\mathcal{P}_{i}\right|\Psi_{ij}\right\rangle}\\\ &-(n-2)\sum_{1\leqslant
i\leqslant
n}\sqrt{\left\langle\Psi_{ii}\left|\mathcal{P}_{i}^{\dagger}\rho^{\otimes
2}\mathcal{P}_{i}\right|\Psi_{ii}\right\rangle},\end{split}$ (11)

then it holds that $C(\rho)\geq\frac{1}{\sqrt{2}(n-1)}\mathcal{F}(\rho,\psi)$.
Here
$|\psi\rangle=\bigotimes_{i=1}^{n}\left|x_{i}\right\rangle=\left|x_{1}x_{2}\cdots
x_{n}\right\rangle$ is an arbitrary product state in Hilbert space
$\mathcal{H}=\mathcal{H}_{1}\otimes\mathcal{H}_{2}\otimes\cdots\otimes\mathcal{H}_{n}$.
$\left|\psi_{i}\right\rangle=\left|x_{1}x_{2}\cdots
x_{i-1}x_{i}^{\prime}x_{i+1}\cdots x_{n}\right\rangle$ and
$\left|\psi_{j}\right\rangle=\mid x_{1}x_{2}\cdots$
$\left.x_{j-1}x_{j}^{\prime}x_{j+1}\cdots x_{n}\right\rangle$ are the product
states obtained from $|\psi\rangle$ by applying (independently) local
unitaries to $\left|x_{i}\right\rangle\in\mathcal{H}_{i}$ and
$\left|x_{j}\right\rangle\in\mathcal{H}_{j}$, respectively.
$\left|\Psi_{ij}\right\rangle:=\left|\psi_{i}\right\rangle\left|\psi_{j}\right\rangle$
is the tensor product of $\left|\psi_{i}\right\rangle$ and
$\left|\psi_{j}\right\rangle$.
$\Pi=\mathcal{P}_{1}\circ\mathcal{P}_{2}\circ\cdots\circ\mathcal{P}_{n}$,
where $\mathcal{P}_{i}$ is the operator swapping the two copies of
$\mathcal{H}_{i}$ in $\mathcal{H}^{\otimes 2}$, for each $i=1,\ldots,n$.

We compute lower bounds for concurrence by randomly sampling a product state
$|\psi\rangle$ and local Haar random unitaries. By this way, we sample
$30,000$ states with positive $\mathcal{F}(\rho,\psi)$ to serve as ‘true’
samples of our training set. Additional $20,000$ states labelled ‘false’ are
constructed for each entanglement intactness of $4,3,2$, where as before all
possible partitions are included for each intactness.

After picking up the quantum states for training, we extract the features by
the similar approach as before, that is, randomly sampling a set of local
measurement devices and fixing them, and then collecting the outcome
statistics data when measuring the training quantum states with these
measurement devices, where the only difference is that we now have four
parties, resulting in that the dimension of the input feature of the neural
network is 256 accordingly.

The neural network we employ here has a similar structure to the one used for
the 3-qubit case, and the concrete configuration is listed in Table.1. The
loss function remains the binary crossentropy.

Table 1: The configuration details of FNNs. In the first column, $n,d$ denotes the number and the dimension of the subsystems, respectively.  System size | Hidden layers
---|---
$n=3,d=2$ | 90 , one drop out layer, 60, 60 , 60
$n=3,d=4$ | 20, one drop out layer, 12, 12, 12
$n=4,d=2$ | 70, one drop out layer, 46, 46 , 46
$n=5,d=2$ | 65, one drop out layer, 42, 42, 42

After training the neural network, we use known analytical results on genuine
4-partite entanglement to evaluate the performance of our model. For this, we
focus on four kinds of 4-qubit quantum states mixed with white noise, which
are $|GHZ_{4}\rangle$, $|W_{4}\rangle$, $\left|Cl_{4}\right\rangle$ and
$\left|D_{24}\right\rangle$. The definition of $|GHZ_{4}\rangle$ and
$|W_{4}\rangle$ have been given in Eq.(7) and Eq.(8), and
$\left|Cl_{4}\right\rangle$ and $\left|D_{24}\right\rangle$ are represented as

$\displaystyle\left|Cl_{4}\right\rangle=$
$\displaystyle(|0000\rangle+|0011\rangle+|1100\rangle-|1111\rangle)/2,$ (12)
$\displaystyle\left|D_{24}\right\rangle=$
$\displaystyle\frac{1}{\sqrt{6}}(|0011\rangle+|1100\rangle+|0101\rangle+|0110\rangle+|1001\rangle.$
$\displaystyle+|1010\rangle)$ (13)

The exact thresholds for $|GHZ_{4}\rangle$ and $\left|Cl_{4}\right\rangle$
with white noise have been found to be 0.533 and 0.614 respectively [32]. That
is to say, $(1-p)\ket{GHZ_{4}}\bra{GHZ_{4}}+pI/16$ is genuine 4-partite
entangled if and only if $0\leq p<0.533$, and similar for $\ket{Cl_{4}}$.
However, to the best of our best knowledge the exact thresholds for
$|W_{4}\rangle$ and $\left|D_{24}\right\rangle$ mixed with white noise are
unknown. And the best-known results for $|W_{4}\rangle$ and
$\left|D_{24}\right\rangle$ mixed with white noise to be genuine 4-partite
entangled is that $p<0.526$ and $p<0.539$ respectively [32].

Similar to the 3-qubit case, we gather one test set of quantum states for each
of the above four classes of 4-qubit quantum states, where $p$ varies at
intervals of 0.001. Again, the features for these test quantum states are
extracted by the same measurement devices as what we utilized in training the
neural network. The labels for these test quantum states are largely known
from the analytical results given in Ref.[32], and we use them to benchmark
our model.

On the four test dataset, the results provided by our neural network are
listed in Table.2. It turns out that on all the instances that analytical
results are known ($0\leq p<1$ for $|GHZ_{4}\rangle$ and
$\left|Cl_{4}\right\rangle$, $0\leq p<0.526$ for $|W_{4}\rangle$, and $0\leq
p<0.539$ for $\left|D_{24}\right\rangle$), overall our model makes excellent
predictions. Interestingly, the results given by the neural network again have
a threshold pattern, which reveals that the thresholds for the $|W_{4}\rangle$
class and the $\left|D_{24}\right\rangle$ class are possibly around $0.635$
and $0.585$ respectively, indicating the potential value of our neural network
again, particularly in quantum engineering areas.

Table 2: Performance of the nerual network for the 4-qubit case. For the classes marked by *, the exact threshold has been known. The last two columns denote the thresholds given by our model and the best-known noise tolerance for the existence of genuine multipartite entanglement. States | Accuracy | Threshold (FNN) | Best-known
---|---|---|---
$|GHZ_{4}\rangle^{*}$ | $99\%$ | 0.523 |  0.533 [32]
$|W_{4}\rangle$ | $100\%$ | 0.635 |  0.526 [32]
$\left|Cl_{4}\right\rangle^{*}$ | $99.7\%$ | 0.611 |  0.614 [32]
$|D_{2,4}\rangle$ | $100\%$ | 0.585 |  0.539 [32]
Random | $99.4\%$ | / | /

To provide more convincing evidence that the neural network we trained works
well, we now test it on more general 4-qubit quantum states. It has been
proven in Ref.[30] that for a 4-qubit quantum state $\rho$, if one of the
inequalities

$\displaystyle\begin{split}\left\|M_{22}\left(T_{i_{1}i_{2}i_{3}i_{4}}\right)\right\|_{k}>\begin{cases}2\sqrt{k}&1\leq
k\leq 3\\\ 1+2k/3&4\leq k\leq 9\end{cases}\end{split}$ (14)

holds, then the state must be genuine multipartite entangled. Here
$T_{i_{1}i_{2}i_{3}i_{4}}={\rm
Tr}(\sigma_{i_{1}}\otimes\cdots\otimes\sigma_{i_{4}}\rho)$, $i_{j}=1,2,3$ for
each $j=1,\cdots,4$ and $\sigma_{1},\sigma_{2},\sigma_{3}$ are the pauli
matrix $X,Y,Z.$
$\left\|M_{22}\left(T_{i_{1}i_{2}i_{3}i_{4}}\right)\right\|_{k}=$
$\left(\left\|T_{\underline{i_{1}}\underline{i_{2}}i_{3}i_{4}}\right\|_{k}+\left\|T_{\underline{i_{1}}i_{2}i_{3}i_{4}}\right\|_{k}+\left\|T_{\underline{i_{1}}i_{2}i_{3}\underline{i_{4}}}\right\|_{k}\right)/3$,
$T_{\underline{i_{1}}i_{2}\underline{i_{3}}i_{4}}=\sum_{i_{1}\cdots
i_{4}}T_{i_{1}i_{2}i_{3}i_{4}}\left|i_{1}i_{3}\right\rangle\left\langle
i_{2}i_{4}\right|$, and $\left\|\cdot\right\|_{k}$ is the Ky Fan k norms
defined as the first $k$ largest singular values of the matrix [52].

Similar as before, we sample 600 genuine 4-partite entangled states by first
randomly generating quantum states by Eq.(2), and then picking up those
satisfying Eq.(14). Together with 600 biseparable states, we construct a nice
test set of quantum states. The experimental result is also listed in Table.2.
As we can see, the prediction accuracy is over $99\%$, indicating a very
decent and stable performance of our model.

##  IV Detecting Genuine Multipartite Entanglement for Qudit States

Next we turn to more general multipartite quantum states, where each subsystem
can be higher-dimensional, and the number of subsystems can also be larger.

We would like to point out that in this case training neural networks is more
challenging. The reason is that after randomly sampling candidate quantum
states for training, it is hard to provide correct labels for them. For
example, if we apply the criteria that we have utilized previously, say
Eq.(10) and Eq.(11), on $5$-qubit quantum states or higher dimensional quantum
states, it is very difficult to certify the existence of genuine multipartite
entanglement. In fact, we also tried to use the technique introduced in
Ref.[32] for the same task, which is actually an optimization approach based
on semi-definite programming, and we find that applying this method is very
time-consuming.

After careful comparisons, we realize that the approach proposed in Ref.[53]
is very suitable to provide labels for candidate training quantum states.
Basically, this approach points out that an ($n+2$)-partite genuinely
entangled state can be obtained by merging two ($n+1$)-partite genuinely
entangled states. Specifically, suppose $\rho_{AC_{1,1}C_{1,2}\cdots C_{1,n}}$
and $\tau_{BC_{2,1}C_{2,2}\cdots C_{2,n}}$ are two $(n+1)$-partite genuinely
entangled states in the Hilbert spaces $\mathcal{H}_{AC_{1,1}C_{1,2}\cdots
C_{1,n}}$ and $\mathcal{H}_{BC_{2,1}C_{2,2}\cdots C_{2,n}}$ respectively. Then
an $(n+2)$-partite genuinely entangled state can be constructed by applying
the operater $\otimes_{K_{c}}$ as follows

$\displaystyle\begin{split}\mathcal{H}_{AC_{1,1}C_{1,2}\cdots
C_{1,n}}\otimes_{K_{c}}\mathcal{H}_{BC_{2,1}C_{2,2}\cdots C_{2,n}}:=\\\
\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes(\mathcal{H}_{C_{1}C_{2}\cdots
C_{n}}),\end{split}$ (15)

where $\mathcal{H}_{C_{j}}=\mathcal{H}_{C_{j,1}}\otimes\mathcal{H}_{C_{j,2}}$,
$1\leq j\leq n$. By definition, $\rho_{AC_{1,1}C_{1,2}\cdots
C_{1,n}}\otimes_{K_{c}}\tau_{BC_{2,1}C_{2,2}\cdots C_{2,n}}$ is an
$(n+2)$-partite state of systems $A,B$, and $C_{j}$ ’s, where
$C_{j}:=\left(C_{1,j}C_{2,j}\right)$ for $1\leqslant j\leqslant n$.

By this method, we can use the small-scale genuine multipartite entangled
states sampled previously to build larger genuine multipartite entangled
states in an iterative manner, which in turn are utilized to train neural
networks customized for large quantum systems.

Meanwhile, note that the entanglement dimension is enlarged after the merging
operation introduced above. For example, if we have two bipartite entangled
quantum states in Hilbert space $\mathcal{H}^{4}\otimes\mathcal{H}^{2}$, after
the merging operation we can obtain a genuine multipartite entangled state in
$\mathcal{H}^{4}\otimes\mathcal{H}^{4}\otimes\mathcal{H}^{4}$.

###  IV.1 Tripartite qudit case

We first apply our approach on tripartite qudit systems. To sample genuine
tripartite entangled quantum states for training, we first generate a lot of
bipartite entangled states, which can be achieved by the positive partial
transpose criterion. Then with the merging operation introduced in Ref.[53] to
generate many desirable genuine tripartite entangled state. In this way, we
eventually collect 20,000 genuine tripartite entangled states in
$\mathcal{H}^{4}\otimes\mathcal{H}^{4}\otimes\mathcal{H}^{4}$. Combining them
with 40,000 biseparable states in the same Hilbert space, we finish preparing
the set of training quantum states.

Next we extract features for the training quantum states, which is again the
measurement statistics data produced by measuring these quantum states
locally. Since the dimensions of subsystems are now larger, we increase the
number of measurement devices for each party from two to three. Accordingly,
we let $M=3$ in Eq.(5), and the feature size of the neural network becomes
$576$. After extracting the features of training quantum states, we input them
into the neural network to train our model. The configuration of the FNN for
this case is also listed in Table. 1.

To test the model we just trained, we first consider the generalized GHZ state
$\left|GHZ_{43}\right\rangle=\frac{1}{2}\sum_{i=0}^{3}|i\rangle^{\otimes 3}$
with white noise:

$\rho=p\left|GHZ_{43}\right\rangle\left\langle
GHZ_{43}\right|+(1-p)\frac{1}{4^{3}}I.$

By running our model on this class of quantum states, we observe that it makes
the ‘true’ prediction when $p>0.161$, while it has been proved analytically
that this class of quantum states is genuine tripartite entangled when
$p>0.157$ [31].

As the second class of test quantum states, we now turn to the qutrit state

$\rho=\frac{1-\alpha-\beta}{27}I+\frac{\alpha}{3}\rho_{\text{bisep
}}+\beta\left|GHZ_{33}\right\rangle\left\langle GHZ_{33}\right|,$

where $\rho_{\text{bisep }}=$ $|0\rangle\langle
0|\otimes(|00\rangle+|11\rangle+|22\rangle)(\langle 00|+\langle 11|+\langle
22|)$. To employ our model for these qutrit states, we embed each qutrit into
a 4-dimensional Hilbert space by padding zeros to the redundant bases to make
these test quantum states have the same dimension with the training quantum
states and the measurement devices that extract features.

The result given by the neural network is depicted in Fig.1. Particularly,
Area I is the parameter space that has been proved to be genuine tripartite
entangled in Ref.[31], which is strictly smaller than the parameter space that
the neural network reports to be genuine tripartite entangled, as the latter
also contain Area II.

Figure 1: Parameter space for genuine tripartite entanglement certified by
different methods. Area $I$ is given in Ref.[31]. The neural network certifies
both Area $I$ and Area $II$. The $\beta$-coordinate on the lower boundary of
Area $II$ equals 0.14 when $\alpha=0$.

To double check the correctness of the results provided by the neural network,
we perform independent numerical calculations to study the case that
$\alpha=0$. By brute-force search for all possible biseparable decompositions
of $\rho$, we find that $\rho$ is genuine tripartite entangled only when
$\beta$ is larger than 0.13, which is very close to the result given by our
model. We believe that the neural network provides very reliable results in
this case.

###  IV.2 $5$-partite qudit case

As the last demonstration of our approach, we now use it to detect genuine
5-qudit entanglement. Based on the 4-qubit genuinely entangled states sampled
in Sec.III.2, we use the merging technique introduced in Ref.[53] to generate
20,000 5-partite genuinely entangled states in $(\mathcal{H}^{2})^{\otimes
2}\otimes(\mathcal{H}^{4})^{\otimes 3}$. To unify the dimension of subsystems
for simplicity, we embed these quantum states into a larger Hilbert space
$(\mathcal{H}^{4})^{\otimes 5}$ also by padding zeros to the redundant bases.
Together with 60,000 biseparable states with ‘false’ labels, we obtain the
whole set of training quantum states. Then as usual, we extract features for
these states by measuring them with local measurement devices, where each
qudit has three devices. The configuration of the neural network we employ in
this case can be found in Table.1.

We now test the performance of this trained model. Due to that quantum states
which have been certified analytically to be genuine 5-qudit entanglement are
rare, we first test our model with the $|GHZ\rangle_{5}$ with white noise,
which are accordingly embedded into the Hilbert space
$(\mathcal{H}^{4})^{\otimes 5}$. Again, when testing we vary the value of $p$
at intervals 0.001. Recall that the 5-qubit GHZ Werner state has been proved
to be genuinely entangled if and only if $0\leqslant p<0.516$, and it turns
out that our model achieves over $98\%$ prediction accuracy on this class of
quantum states.

In order to further test the power of our model, we construct another test set
composed of more general quantum states. For this, we sample 600 biseparable
states labeled ‘false’, and 600 genuine 5-qudit entangled states labeled
‘true’ with the technique introduced in Eq.(15). Combining these 1200 quantum
states together, we obtain the new test set, on which our model certify
genuine multipartite entanglement with accuracy over 99%.

With the successes of all the models we have trained above, we expect that if
one extends the neural network approach to more complicated cases of target
quantum states, the performance will also be decent.

##  V Reducing the cost of quantum measurements

We have shown the great potential of detecting genuine multipartite
entanglement by machine learning methods, where the features are measurement
statistics data. However, if the number of subsystems goes up, the cost of
quantum measurements (or the size of features) will increase very quickly.
With this in mind, we now propose the so-called _$k$ -correlation_ scheme to
reduce the cost of quantum measurements.

###  V.1 $k$-correlation scheme

Recall that when extracting feature for training and test quantum states, a
set of local quantum measurements are performed on these quantum states to
produce correlation data, where many cross terms are involved. For example,
suppose Alice (Bob) possesses measurement devices $A_{1},A_{2}$
($B_{1},B_{2}$), and she (he) measures the subsystem of a bipartite quantum
state locally. The correlation data they produce comes from four different
combinations of measurement devices, i.e., $A_{1}B_{1}$, $A_{1}B_{2}$,
$A_{2}B_{1}$ and $A_{2}B_{2}$, where $A_{1}B_{2}$, $A_{2}B_{1}$ are called the
cross terms. If we ignore these two cross terms, we can reduce the size of
correlation data by half in this case. By generalizing this idea to
$n$-partite quantum state $\rho$, we define the concept of $k$-correlation
data, which is given by

$\displaystyle p\left(a_{1}a_{2}\ldots a_{n}\mid
x\right)=\operatorname{Tr}\left(\left(\bigotimes_{i=1}^{n}P_{ix}^{a_{i}}\right)\rho\right),$
(16)

where $a_{i}\in[{d_{i}}]\equiv\\{1,\ldots,d_{i}\\}$ represents the outcome for
measurement device $P_{ix}$, here $x\in\\{1,2\ldots k\\}$. In this section, we
will try to certify genuine multipartite entanglement by neural networks with
features being $k$-correlation data, and for convenience, we call this
approach _the $k$-correlation scheme_.

###  V.2 Detecting genuine 4-qubit entanglement using the $k$-correlation
scheme

Since analytical results on genuine 4-qubit entanglement are relatively rich,
we now test the performance of the $k$-correlation scheme in this case. To be
specific, we will reuse the same sets of training and test quantum states as
before, and the only difference between the two models is the forms of
features, which involves both the training and test stages.

After retraining our model based on 5-correlation data, we again test the
model with the four classes of 4-qubit quantum states, i.e.,
$|GHZ_{4}\rangle$, $|W_{4}\rangle$, $|Cl_{4}\rangle$ and $|D_{24}\rangle$
mixed with white noise. The results on prediction accuracy for each class are
listed in Table.3.

Table 3: Performance of the neural network based on $5$-correlation data. States | accuracy
---|---
$|GHZ_{4}\rangle^{*}$ | $86\%$
$|W_{4}\rangle$ | $100\%$
$\left|Cl_{4}\right\rangle^{*}$ | $99.6\%$
$|D_{2,4}\rangle$ | $100\%$

As we can see, the performance of the new model is worse than the original one
based on full correlation data. For example, the prediction accuracy for the
GHZ class is lower compared with the old result. To extract more information
from the training and test quantum states, we offer each party more
measurement devices, and generate $k$-correlations with $k\geq 6$. It turns
out that even if we let $k=16$, which means the features now have the same
size as the original model, the new model still can not certify genuine
4-qubit entanglement for the GHZ-Werner class with accuracy over $90\%$. This
reveals an interesting fact that cross terms in correlation data is very
crucial to extract quantum properties for underlying quantum states.

###  V.3 Detecting genuine multipartite entanglement for graph states

Though the power of the $k$-correlation scheme is weaker than the original
scheme based on full correlation data, we now show that if certain prior
knowledge on target quantum states are known, the $k$-correlation scheme still
enjoys a nice performance.

To demonstrate this fact, in this subsection we utilize the $k$-correlation
scheme to predict whether graph states are genuine multipartite entangled. It
is well-known that graph states have significant applications in quantum
computing and quantum information [54, 55, 56, 57].

The motivation to apply the $k$-correlation scheme on graph states is very
clear. Suppose we have a graph state consisting of $12$ qubits, then if we let
full correlation data serve as features for the neural network, the feature
size will be $2^{24}$ even if each qubit is measured by only two measurement
devices. As a comparison, if we apply the $k$-correlation scheme, the feature
size will be $2^{12}\cdot k$, which can be much smaller. Interestingly, it
turns out that the $k$-correlation scheme works well in this case.

Specifically, we first randomly generate 600 10- (11-, 12-) qubit graph states
to train the neural network, where the corresponding labels (whether the graph
states are genuine multipartite entangled) can be determined by the
connectivity of the underlying graphs [58]. Here the FNN model we choose has 3
hidden layers that contains 50, 25, 10, neurons respectively. After training,
we test the model by running it on another 200 random graph states. The result
is that even $4$-correlation data is already enough to achieve a prediction
accuracy of $97\%$.

It can be seen that the cost of quantum measurement in the $k$-correlation
scheme has been sharply reduced, where the number of measurement device
combinations goes down dramatically. This indicates clearly that prior
knowledge can be very helpful in our approach. In fact, similar result has
also reported in Ref.[41], where a machine learning method is applied to
certify the entanglement structure of pure and noisy generalized GHZ states
based on expectation values of local observables, and a very nice performance
is achieved due to the fact that the training and test quantum states there
have very similar configuration, which is essentially a kind of prior
knowledge. We stress that in the current work our models can handle much more
general quantum states, and as we have pointed out, test quantum states we
choose are often sampled randomly without any assumptions.

We remark that the $k$-correlation scheme and the original scheme based on
full correlation data are two extreme ends to apply our neural network
approach. From the viewpoint of quantum engineering, we believe that there are
many other ways to exploit correlation data with neural network, and a proper
tradeoff between efficiency and prediction accuracy can be found out based on
specific application scenarios.

##  VI Robustness of our models

Recall that in each model we have trained, at the beginning we always randomly
sample a set of measurement devices and fix them, then the features of all
training and test quantum states are extracted based on these devices.
Naturally, one may ask, if we repeat the whole process and sample a different
set of measurement devices, can we obtain better prediction performance?

Interestingly, in all the models we have trained, we do make this kind of
comparisons, and it turns out that measurement devices generated by different
choices of Haar random matrices can only change the prediction performance
very slightly.

Particularly, in the 4-qubit case we also try to extract features with the
observables taken from Ref.[59], which is widely used to witness entanglement
intactness. Specifically, we assign each party the following two observables

$\displaystyle A_{1}=\sigma_{z},$ (17) $\displaystyle A_{2}=A_{+},$ (18)

where $\sigma_{z}$ is the Pauli matrix Z and
$A_{+}=\cos\left(\frac{n+1}{2n}\phi\right)\sigma_{x}+\sin\left(\frac{n+1}{2n}\phi\right)\sigma_{y}$.
In our case, $n=4$ and $\phi=1.1055$. After repeating the training and test
procedures with the new way to extract features, we observe that the accuracy
of detecting genuine 4-qubit entanglement keeps almost unchanged.

To provide further evidence for the above robustness, we also introduce the
mechanism of ‘learnable measurement’ to find out what measurement devices are
optimal in our models. For this, we parameterize involved local measurement
devices, and search for the optimal family of parameters by optimization
approaches [45]. Again, the result shows that even the optimized measurement
devices still provide almost the same prediction accuracy.

We would like to stress that from the point of view of engineering, this kind
of robustness is very valuable. This implies that, even if the quality of the
measurement devices we utilize is poor, as long as their workings keep stable,
our approach can still works very well.

##  VII Conclusion

To summarize, in this work we demonstrate that neural networks can certify
genuine multipartite entanglement very accurately based on the measurement
statistics data produced by measuring involved quantum states with local
measurements. Specifically, we successfully train neural networks to detect
genuine multipartite entanglement for many multipartite qubit and qudit
systems. By testing these trained models on various multipartite quantum
states, we observe that the prediction accuracy is very high. Particularly, in
many cases the test quantum states we choose are sampled randomly, which
provides convincing evidence showing that neural networks can work very well
in such a challenging task.

In addition, to improve the efficiency of our models, we propose the
$k$-correlation scheme to reduce the cost of quantum measurements. We show
that when prior knowledge on target quantum states is known, the performance
of this scheme can still be very good. This indicates that one can adjust
model details to save computational resources according to application
scenarios.

Meanwhile, we remark that our approach can also be combined with the idea of
shadow tomography [60], by which one can generate correlation data based on
classical shadow of involved quantum states, and thus reduce the cost of
quantum operations dramatically.

Lastly, we show that our models enjoy remarkable robustness against flaws in
involved quantum measurements, and this implies that our models are very
experiment-friendly. We expect that in future our neural network approach can
be applied to certify unknown genuine multipartite entanglement, providing a
realistic solution to this fundamental yet difficult problem.

###### Acknowledgements.

We thank Zhangqi Yin for helpful comments. This work was supported by the
National Key R&D Program of China, Grants No. 2018YFA0306703, 2021YFE0113100,
and the National Natural Science Foundation of China, Grant No. 61832015,
62272259.

## References

  * Buhrman  _et al._ [2010] H. Buhrman, R. Cleve, S. Massar, and R. De Wolf, Nonlocality and communication complexity, Reviews of modern physics 82, 665 (2010).
  * Ekert [1992] A. K. Ekert, Quantum cryptography and bell’s theorem, in  _Quantum Measurements in Optics_ (Springer, 1992) pp. 413–418.
  * Scarani  _et al._ [2009] V. Scarani, H. Bechmann-Pasquinucci, N. J. Cerf, M. Dušek, N. Lütkenhaus, and M. Peev, The security of practical quantum key distribution, Reviews of modern physics 81, 1301 (2009).
  * Gharibian [2008] S. Gharibian, Strong np-hardness of the quantum separability problem, arXiv preprint arXiv:0810.4507 (2008).
  * Peres [1996] A. Peres, Separability criterion for density matrices, Physical Review Letters 77, 1413 (1996).
  * Horodecki [1997] P. Horodecki, Separability criterion and inseparable mixed states with positive partial transposition, Physics Letters A 232, 333 (1997).
  * Horodecki  _et al._ [1996] R. Horodecki, M. Horodecki, and P. Horodecki, Teleportation, bell’s inequalities and inseparability, Physics Letters A 222, 21 (1996).
  * Gühne and Tóth [2009] O. Gühne and G. Tóth, Entanglement detection, Physics Reports 474, 1 (2009).
  * Doherty  _et al._ [2004] A. C. Doherty, P. A. Parrilo, and F. M. Spedalieri, Complete family of separability criteria, Physical Review A 69, 022308 (2004).
  * Paris and Rehacek [2004] M. Paris and J. Rehacek,  _Quantum state estimation_ , Vol. 649 (Springer Science & Business Media, 2004).
  * Steffen  _et al._ [2006] M. Steffen, M. Ansmann, R. C. Bialczak, N. Katz, E. Lucero, R. McDermott, M. Neeley, E. M. Weig, A. N. Cleland, and J. M. Martinis, Measurement of the entanglement of two superconducting qubits via state tomography, Science 313, 1423 (2006).
  * Poyatos  _et al._ [1997] J. Poyatos, J. I. Cirac, and P. Zoller, Complete characterization of a quantum process: the two-bit quantum gate, Physical Review Letters 78, 390 (1997).
  * Bavaresco  _et al._ [2018] J. Bavaresco, N. Herrera Valencia, C. Klöckl, M. Pivoluska, P. Erker, N. Friis, M. Malik, and M. Huber, Measurements in two bases are sufficient for certifying high-dimensional entanglement, Nature Physics 14, 1032 (2018).
  * Rosset  _et al._ [2012] D. Rosset, R. Ferretti-Schöbitz, J.-D. Bancal, N. Gisin, and Y.-C. Liang, Imperfect measurement settings: Implications for quantum state tomography and entanglement witnesses, Physical Review A 86, 062325 (2012).
  * Friis  _et al._ [2019] N. Friis, G. Vitagliano, M. Malik, and M. Huber, Entanglement certification from theory to experiment, Nature Reviews Physics 1, 72 (2019).
  * Collins  _et al._ [2002] D. Collins, N. Gisin, N. Linden, S. Massar, and S. Popescu, Bell inequalities for arbitrarily high-dimensional systems, Physical review letters 88, 040404 (2002).
  * Moroder  _et al._ [2013] T. Moroder, J.-D. Bancal, Y.-C. Liang, M. Hofmann, and O. Gühne, Device-independent entanglement quantification and related applications, Physical review letters 111, 030501 (2013).
  * Bowles  _et al._ [2018] J. Bowles, I. Šupić, D. Cavalcanti, and A. Acín, Device-independent entanglement certification of all entangled states, Physical review letters 121, 180503 (2018).
  * Xu  _et al._ [2014] P. Xu, X. Yuan, L.-K. Chen, H. Lu, X.-C. Yao, X. Ma, Y.-A. Chen, and J.-W. Pan, Implementation of a measurement-device-independent entanglement witness, Physical review letters 112, 140506 (2014).
  * Yeo and Chua [2006] Y. Yeo and W. K. Chua, Teleportation and dense coding with genuine multipartite entanglement, Physical Review Letters 96, 060502 (2006).
  * Chen  _et al._ [2006] P.-X. Chen, S.-Y. Zhu, and G.-C. Guo, General form of genuine multipartite entanglement quantum channels for teleportation, Physical Review A 74, 032324 (2006).
  * Muralidharan and Panigrahi [2008] S. Muralidharan and P. K. Panigrahi, Perfect teleportation, quantum-state sharing, and superdense coding through a genuinely entangled five-qubit state, Physical Review A 77, 032321 (2008).
  * Tóth [2012] G. Tóth, Multipartite entanglement and high-precision metrology, Physical Review A 85, 022322 (2012).
  * Hyllus  _et al._ [2012] P. Hyllus, W. Laskowski, R. Krischek, C. Schwemmer, W. Wieczorek, H. Weinfurter, L. Pezzé, and A. Smerzi, Fisher information and multiparticle entanglement, Physical Review A 85, 022321 (2012).
  * Sarovar  _et al._ [2010] M. Sarovar, A. Ishizaki, G. R. Fleming, and K. B. Whaley, Quantum entanglement in photosynthetic light-harvesting complexes, Nature Physics 6, 462 (2010).
  * Gühne and Seevinck [2010] O. Gühne and M. Seevinck, Separability criteria for genuine multiparticle entanglement, New Journal of Physics 12, 053002 (2010).
  * Szalay [2015] S. Szalay, Multipartite entanglement measures, Physical Review A 92, 042329 (2015).
  * Ma  _et al._ [2011] Z.-H. Ma, Z.-H. Chen, J.-L. Chen, C. Spengler, A. Gabriel, and M. Huber, Measure of genuine multipartite entanglement with computable lower bounds, Physical Review A 83, 062325 (2011).
  * Chen  _et al._ [2012] Z.-H. Chen, Z.-H. Ma, J.-L. Chen, and S. Severini, Improved lower bounds on genuine-multipartite-entanglement concurrence, Physical Review A 85, 062320 (2012).
  * de Vicente and Huber [2011] J. I. de Vicente and M. Huber, Multipartite entanglement detection from correlation tensors, Physical Review A 84, 062306 (2011).
  * Huber  _et al._ [2010] M. Huber, F. Mintert, A. Gabriel, and B. C. Hiesmayr, Detection of high-dimensional genuine multipartite entanglement of mixed states, Physical review letters 104, 210501 (2010).
  * Jungnitsch  _et al._ [2011] B. Jungnitsch, T. Moroder, and O. Gühne, Taming multiparticle entanglement, Physical review letters 106, 190502 (2011).
  * Bancal  _et al._ [2011] J.-D. Bancal, N. Gisin, Y.-C. Liang, and S. Pironio, Device-independent witnesses of genuine multipartite entanglement, Physical Review Letters 106, 250404 (2011).
  * Tóth and Gühne [2005] G. Tóth and O. Gühne, Detecting genuine multipartite entanglement with two local measurements, Physical review letters 94, 060501 (2005).
  * Bourennane  _et al._ [2004] M. Bourennane, M. Eibl, C. Kurtsiefer, S. Gaertner, H. Weinfurter, O. Gühne, P. Hyllus, D. Bruß, M. Lewenstein, and A. Sanpera, Experimental detection of multipartite entanglement using witness operators, Physical review letters 92, 087902 (2004).
  * Pál and Vértesi [2011] K. F. Pál and T. Vértesi, Multisetting bell-type inequalities for detecting genuine multipartite entanglement, Physical Review A 83, 062123 (2011).
  * Barreiro  _et al._ [2013] J. T. Barreiro, J.-D. Bancal, P. Schindler, D. Nigg, M. Hennrich, T. Monz, N. Gisin, and R. Blatt, Demonstration of genuine multipartite entanglement with device-independent witnesses, Nature Physics 9, 559 (2013).
  * Girardin  _et al._ [2022] A. Girardin, N. Brunner, and T. Kriváchy, Building separable approximations for quantum states via neural networks, Physical Review Research 4, 023238 (2022).
  * Lu  _et al._ [2018a] S. Lu, S. Huang, K. Li, J. Li, J. Chen, D. Lu, Z. Ji, Y. Shen, D. Zhou, and B. Zeng, Separability-entanglement classifier via machine learning, Physical Review A 98, 012315 (2018a).
  * Chen  _et al._ [2021a] Y. Chen, Y. Pan, G. Zhang, and S. Cheng, Detecting quantum entanglement with unsupervised learning, Quantum Science and Technology 7, 015005 (2021a).
  * Chen  _et al._ [2021b] C. Chen, C. Ren, H. Lin, and H. Lu, Entanglement structure detection via machine learning, Quantum Science and Technology (2021b).
  * Ren and Chen [2019] C. Ren and C. Chen, Steerability detection of an arbitrary two-qubit state via machine learning, Physical Review A 100, 022314 (2019).
  * Canabarro  _et al._ [2019] A. Canabarro, S. Brito, and R. Chaves, Machine learning nonlocal correlations, Physical review letters 122, 200401 (2019).
  * Lin  _et al._ [2021] X. Lin, Z. Chen, and Z. Wei, Quantifying unknown entanglement by neural networks, arXiv preprint arXiv:2104.12527 (2021).
  * Lin  _et al._ [2022] X. Lin, Z. Chen, and Z. Wei, Quantifying unknown quantum entanglement via a hybrid quantum-classical machine learning framework, arXiv preprint arXiv:2204.11500 (2022).
  * CireAan  _et al._ [2012] D. CireAan, U. Meier, J. Masci, and J. Schmidhuber, Multi-column deep neural network for traffic sign classification, Neural networks 32, 333 (2012).
  * Gers and Schmidhuber [2001] F. A. Gers and E. Schmidhuber, Lstm recurrent networks learn simple context-free and context-sensitive languages, IEEE Transactions on Neural Networks 12, 1333 (2001).
  * Elkahky  _et al._ [2015] A. M. Elkahky, Y. Song, and X. He, A multi-view deep learning approach for cross domain user modeling in recommendation systems, in  _Proceedings of the 24th international conference on world wide web_ (2015) pp. 278–288.
  * LeCun  _et al._ [1998] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, Gradient-based learning applied to document recognition, Proceedings of the IEEE 86, 2278 (1998).
  * Albawi  _et al._ [2017] S. Albawi, T. A. Mohammed, and S. Al-Zawi, Understanding of a convolutional neural network, in  _2017 International Conference on Engineering and Technology (ICET)_ (Ieee, 2017) pp. 1–6.
  * Schneeloch  _et al._ [2020] J. Schneeloch, C. C. Tison, M. L. Fanto, S. Ray, and P. M. Alsing, Quantifying tripartite entanglement with entropic correlations, Physical Review Research 2, 043152 (2020).
  * Horn and Johnson [2012] R. A. Horn and C. R. Johnson,  _Matrix analysis_ (Cambridge university press, 2012).
  * Shen and Chen [2020] Y. Shen and L. Chen, Construction of genuine multipartite entangled states, Journal of Physics A: Mathematical and Theoretical 53, 125302 (2020).
  * Hein  _et al._ [2004] M. Hein, J. Eisert, and H. J. Briegel, Multiparty entanglement in graph states, Physical Review A 69, 062311 (2004).
  * Hein  _et al._ [2006] M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. Nest, and H.-J. Briegel, Entanglement in graph states and its applications, arXiv preprint quant-ph/0602096 (2006).
  * Keet  _et al._ [2010] A. Keet, B. Fortescue, D. Markham, and B. C. Sanders, Quantum secret sharing with qudit graph states, Physical Review A 82, 062315 (2010).
  * Looi  _et al._ [2008] S. Y. Looi, L. Yu, V. Gheorghiu, and R. B. Griffiths, Quantum-error-correcting codes using qudit graph states, Physical Review A 78, 042303 (2008).
  * West  _et al._ [2001] D. B. West _et al._ ,  _Introduction to graph theory_ , Vol. 2 (Prentice hall Upper Saddle River, 2001).
  * Lu  _et al._ [2018b] H. Lu, Q. Zhao, Z.-D. Li, X.-F. Yin, X. Yuan, J.-C. Hung, L.-K. Chen, L. Li, N.-L. Liu, C.-Z. Peng, _et al._ , Entanglement structure: entanglement partitioning in multipartite systems and its experimental detection using optimizable witnesses, Physical Review X 8, 021072 (2018b).
  * Huang  _et al._ [2020] H.-Y. Huang, R. Kueng, and J. Preskill, Predicting many properties of a quantum system from very few measurements, Nature Physics 16, 1050 (2020).