# Entanglement marginal problems

Miguel Navascués1 Flavio Baccari2 and Antonio Acín3,4 1Institute for Quantum
Optics and Quantum Information (IQOQI) Vienna, Austrian Academy of Sciences
2Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-Straße 1, 85748
Garching, Germany
3ICFO-Institut de Ciencies Fotoniques, The Barcelona Institute of Science and
Technology, 08860 Castelldefels (Barcelona), Spain
4ICREA-Institucio Catalana de Recerca i Estudis Avançats, Lluis Companys 23,
08010 Barcelona, Spain

###### Abstract

We consider the entanglement marginal problem, which consists of deciding
whether a number of reduced density matrices are compatible with an overall
separable quantum state. To tackle this problem, we propose hierarchies of
semidefinite programming relaxations of the set of quantum state marginals
admitting a fully separable extension. We connect the completeness of each
hierarchy to the resolution of an analog classical marginal problem and thus
identify relevant experimental situations where the hierarchies are complete.
For finitely many parties on a star configuration or a chain, we find that we
can achieve an arbitrarily good approximation to the set of nearest-neighbour
marginals of separable states with a time (space) complexity polynomial
(linear) on the system size. Our results even extend to infinite systems, such
as translation-invariant systems in 1D, as well as higher spatial dimensions
with extra symmetries.

##  1 Introduction

Recent quantum experiments with cold atoms and superconducting qubits have
demonstrated different degrees of control over systems of size ranging from
about $50$ [1] to several hundred qubits [2]. Determining whether entanglement
is present in such architectures is a challenging task. To begin with, a full
tomographic reconstruction of the underlying quantum state is out of the
question, since it requires the estimation of a number of parameters that
grows exponentially with the system size. A more realistic goal consists in
estimating a number of parameters that scales polynomially with the system
size, for instance the reduced density matrices of neighboring subsystems.

In that case, however, most general methods for entanglement detection fail,
since they are tailor-made for scenarios where the whole state is available
and therefore require an optimization over an, again, exponential number of
parameters. For instance, the application of the Doherty-Parrilo-Spedalieri
(DPS) hierarchy of relaxations [3] to characterize the set of separable
states, or some entanglement detection methods based on incomplete information
[4] would require solving an optimization problem where one of the variables
corresponds to the full density matrix of the system. The memory cost of such
approaches becomes prohibitive already beyond the case of order of ten qubits.
On the other hand, there exist entanglement detection methods based on two-
point correlation functions [5, 6], but no general construction is known for
them and they are not guaranteed to detect all entangled states. Leaving aside
entanglement detection through indirect methods such as Bell inequality
violations [7, 8], to our knowledge there is no systematic and scalable method
to date to detect entanglement from incomplete information.

In this work, we address this question and consider the _entanglement marginal
problem_ : deciding if an ensemble of density matrices could be the marginal
states of a separable global state $\rho$. We present a framework to construct
hierarchies of tests that are satisfied whenever the ensemble of reduced
states is compatible with a global separable state. The tests amount to
solving a semidefinite program (SDP) [9], a class of convex optimization
problems that can be solved efficiently. If the ensemble fails one of the
tests, then our method will output a linear entanglement witness in terms of
the states in the ensemble that certifies the entanglement of $\rho$. We show
that the convergence of the hierarchy is strongly connected to the classical
marginal problem. For those cases in which the hierarchy is complete, we prove
that any ensemble passing the ${L}^{th}$ test of the hierarchy is
$O(1/{L}^{2})$-close in trace norm to the set of ensembles admitting a
separable extension.

To our surprise, we find that, in many cases of physical interest, the
corresponding hierarchies have a time complexity polynomial on the system
size, and a memory complexity linear on the system size. This allows us to
certify entanglement in systems of hundreds of sites. Our hierarchies also
apply to characterize entanglement in infinite systems, as long as those are
subject to some natural symmetries. More precisely, we propose two SDP
hierarchies that, respectively, characterize entanglement in 1D translation-
invariant (TI) systems and in 2D TI systems in the square lattice that are
also symmetric under horizontal (or vertical) reflections. We test the
practical performance of our approach by working out the critical temperature
beyond which no entanglement is present in the system for a class of solvable
models. We also compute the so-called _separable energy per site_ , the
minimum energy per site achievable by separable states, for some $k$-local
Hamiltonians.

This article is organized as follows: in Section 2 we introduce the notation
and concepts to be used along the text. In Section 3 we define the
entanglement marginal problem, the subject of this work, and we relate it to
the classical marginal problem. In section 4, we present a hierarchy of SDPs
to attack the entanglement marginal problem. We fully characterize, in
Proposition 4, the set of state ensembles to which this hierarchy converges
to. As we argue, this set corresponds to the set of marginals of an overall
separable state iff the classical marginal problem is trivial in the
considered marginal scenario. Otherwise, it is just a strict relaxation. We
then apply our construction to solve the entanglement marginal problem in
scenarios with finitely many parties (section 5) or symmetric systems with
infinitely many parties (section 6). Finally, in section 7 we present our
conclusions.

##  2 Preliminaries

Let ${{\cal A}}=(\alpha,\beta,...)$ be a finite or an infinite countable
alphabet. In the following, each of the letters $\alpha\in{\cal A}$ will
represent either a quantum system with Hilbert space dimension $d_{\alpha}$ or
a classical random variable with finite or infinite cardinality. For finite
systems of $n$ particles, one can take ${{\cal A}}$ to be the set
$\\{1,\ldots,n\\}$, but our considerations also apply to infinite systems,
which motivates the previous notation. Let $I\subset{\cal A}$ be a subset of
all such systems. For any vector or sequence
$\phi\equiv(\phi_{\alpha})_{\alpha\in{\cal A}}$, we call $\phi_{I}$ the vector
or sequence with coefficients $(\phi_{\alpha}:\alpha\in I)$. Similarly, for
any quantum state $\rho:{\cal H}\to{\cal H}$, with ${\cal
H}=\bigotimes_{\alpha\in{\cal A}}{\cal H}_{\alpha}$ being a composite Hilbert
space, the operator $\rho_{I}$ denotes the partial trace $\mbox{tr}_{{\cal
A}\setminus I}(\rho)$. This notation extends to probability distributions:
$p_{I}(\phi_{I})$ denotes the marginal distribution of $p(\phi)$ for variables
$(\phi)_{\alpha\in I}$. The last two sentences do not make much sense
mathematically when $|{\cal A}|=\infty$; in that case, we refer the reader to
Appendix A for a definition of quantum states, probability distributions and
their respective marginalizations.

Let ${\cal I}\subset P({\cal A})$, where $P({\cal A})$ denotes the power set
of ${\cal A}$, that is, the set consisting of all its subsets. By conducting
several tomographic experiments on all the systems in $I\in{\cal I}$, we can
estimate $\rho_{I}$, the density matrix describing the sites at $I$. A
necessary condition for the existence of an overall quantum state $\rho$ for
all systems in ${\cal A}$ compatible with the ensemble
$\\{\rho_{I}\\}_{I\in{\cal I}}$ is that of _local compatibility_ , i.e.,

$\mbox{tr}_{I\setminus J}(\rho_{I})=\mbox{tr}_{J\setminus I}(\rho_{J}),$ (1)

for $I,J\in{\cal I}$.

Local compatibility can also be defined for ensembles of probability
distributions. If $\\{p_{I}(\phi_{I})d\phi_{I}:I\in{\cal I}\\}$ are the
marginals of a global measure $p(\phi)$, defined over all sites in ${\cal A}$,
then $\\{p_{I}(\phi_{I})d\phi_{I}:I\in{\cal I}\\}$ must satisfy the local
compatibility constraints

$\int d\phi_{I\setminus J}p_{I}(\phi_{I})=\int d\phi_{J\setminus
I}p_{J}(\phi_{J}),\forall I,J\in{\cal I}\,$ (2)

for $I,J\in{\cal I}$.

In section 6 we study configurations where the physical systems lie on the
sites of an infinite chain or an infinite hypercubic lattice and the overall
state describing ${\cal A}$ satisfies translation invariance. In those
scenarios, local compatibility admits a very simple form. Consider, for
instance, an infinite translation-invariant 1D system, with ${\cal
A}=\mathbb{Z}$ and $d_{\alpha}=d$ for all $\alpha\in{\cal A}$. Let
$\omega_{\\{1,...,k\\}}$ denote the density matrix (probability distribution)
describing the quantum systems (classical random variables) at sites
$1,...,k$. If $\omega_{\\{1,...,k\\}}$ is the marginal of a translation-
invariant 1D system $\omega$, then $\omega_{\\{1,...,k\\}}$ must also be
subject to the local compatibility relations

$\omega_{\\{1,...,k-1\\}}=\omega_{\\{2,...,k\\}}.$ (3)

This condition is known as local translation invariance (LTI) [10].

In higher spatial dimensions, translation invariance enforces slightly more
complicated local constraints. Think of a 2D infinite square lattice, i.e.,
${\cal A}=\mathbb{Z}^{2}$. A $k\times l$ plaquette is a set of sites of the
form $\hat{I}+z$, for $\hat{I}=\\{(x,y):x=1,...,k;y=1,...,l\\}$,
$z\in\mathbb{Z}^{2}$. If the quantum or classical description
$\omega_{\hat{I}}$ of the sites in $\hat{I}$ is the marginal of a TI quantum
or classical system, then local compatibility implies that

$\displaystyle\omega_{\hat{I}\setminus\\{(1,y):y\\}}=\omega_{\hat{I}\setminus\\{(k,y):y\\}},$
$\displaystyle\omega_{\hat{I}\setminus\\{(x,1):x\\}}=\omega_{\hat{I}\setminus\\{(x,l):x\\}},$
(4)

see Figure 1. These conditions are also dubbed LTI [10].

Figure 1: A $k\times l$ plaquette. Local translation invariance implies that
the marginals (quantum or classical) corresponding to the sites enclosed by
the two dashed lines in each figure are identical.

##  3 The entanglement marginal problem

A multi-partite quantum state $\sigma$, with subsystems labeled by the
elements of ${\cal A}$, is said to be separable if there exists a multi-
variate measure $p(\phi)d\phi$, with $\phi=(\phi_{\alpha})_{\alpha\in{\cal
A}}$, such that

$\sigma=\int p(\phi)d\phi\bigotimes_{\alpha\in{\cal
A}}|\phi_{\alpha}\rangle\\!\langle\phi_{\alpha}|$ (5)

(if $|{\cal A}|=\infty$, we need to marginalize $p$ over finite subsets of
${\cal A}$, see Appendix A). In the following, when we refer to a measure
$p(\phi)$ generating a separable state $\sigma$, we implicitly mean that the
state is defined by Eq. (5).

In this work, we wish to solve what from now on we call the _entanglement
marginal problem_ , stated as follows.

######  Definition 1.

Entanglement marginal problem.

Input: ${\cal A},{\cal I}\subset P({\cal A})$, an ensemble
$\\{\rho_{I}\\}_{I\in{\cal I}}$ of locally compatible states.

Goal: find whether there exists a separable state $\sigma$ such that
$\mbox{tr}_{{\cal A}\setminus I}(\sigma)=\rho_{I}$ for all $I\in{\cal I}$.

As we will see, the entanglement marginal problem is strongly connected to the
_classical marginal problem_ , a very old question that appears in numerous
contexts in physics, such as statistical physics [10, 11] or quantum
nonlocality [12].

######  Definition 2.

Classical marginal problem.

Input: ${\cal A},{\cal I}\subset P({\cal A})$, an ensemble
$\\{p_{I}(\phi_{I})\\}_{I\in{\cal I}}$ of locally compatible probability
distributions.

Goal: find whether there exists a global measure $\tilde{p}$ such that
$\tilde{p}_{I}(\phi_{I})=p_{I}(\phi_{I})$ for all $I\in{\cal I}$.

In general marginal scenarios ${\cal A},{\cal I}\in P({\cal A})$, local
compatibility of classical distributions does not always imply the existence
of a global measure. Consider, for instance, ${\cal A}=\\{1,2,3\\}$, and the
distributions of random variables $a_{1},a_{2},a_{3}\in\\{0,1\\}$ given by
$P_{I}(0,1)=P_{I}(1,0)=\frac{1}{2}$, for $I=\\{1,2\\},\\{1,3\\},\\{2,3\\}$.
These distributions satisfy local compatibility, and yet it is easy to see
that no global distribution $P(a_{1},a_{2},a_{3})$ admits them as marginals.
The classical marginal problem is thus non-trivial, and, in fact, it can be
shown to be NP-hard [13].

In order to understand the connection between the entanglement marginal
problem and its classical counterpart, let us rewrite the reduced states
$\rho_{I}$ as

$\rho_{I}\equiv\int p_{I}(\phi_{I})d\phi_{I}\bigotimes_{\alpha\in
I}|\phi_{\alpha}\rangle\\!\langle\phi_{\alpha}|.$ (6)

for some given probability measures $p_{I}(\phi_{I})$. Notice that one can
assume such a decomposition always to exist, since otherwise some of the
reduced states would be entangled, making the solution to the entanglement
marginal problem trivial. Solving the entanglement marginal problem is
equivalent to determining whether it is possible to find a collection of
distributions $\\{p_{I}(\phi_{I})\\}_{I\in{\cal I}}$ that admits a global
measure and such that eq. (6) holds. Indeed, if such a measure $q(\phi)$
exists, it could be used to generate a separable state $\sigma$ whose reduced
states on each set $I\in{\cal I}$ coincides with $\rho_{I}$, simply because
the corresponding marginal distribution of $q(\phi)$ coincides with
$p_{I}(\phi_{I})$.

The connection between the classical and the entanglement marginal problem
does not make either of them less challenging. First of all, because the
choice of probability measures $p_{I}(\phi_{I})$ in (6) is generally not
unique and there is no guarantee for those measures even to be locally
compatible, in the sense of (2). Moreover, even if we could enforce their
local compatibility, this is generally not enough to guarantee the existence
of a global measure, and hence of an overall separable extension for the
states. We come back to this point below. However, and despite the complexity
of the problems involved, relating the entanglement marginal problem and its
classical counterpart offers a useful interpretation to the hierarchies that
we introduce in the next Section, which will prove crucial to analyze their
convergence properties.

##  4 Semidefinite programming relaxations of the entanglement marginal
problem

To solve the entanglement marginal problem, we follow the ideas of Doherty
Parrilo and Spedalieri (DPS) [3, 14, 15], who provided an algorithm to solve
the entanglement problem in the case where the whole density matrix $\rho$ is
specified, i.e., when ${\cal I}=\\{{\cal A}\\}$. Suppose then that there
exists a probability distribution $p(\phi)$ over pure states $\phi$ such that
the separable state defined by Eq. (5) admits the states $\\{\rho_{I}\\}$ as
marginals. Next, define the states

$\rho^{({L})}_{I}\equiv\int p_{I}(\phi_{I})d\phi_{I}\bigotimes_{\alpha\in
I}|\phi_{\alpha}\rangle\\!\langle\phi_{\alpha}|^{\otimes{L}}.$ (7)

State $\rho^{({L})}_{I}$ thus acts on a composite Hilbert space whose factors
are the ${L}^{th}$ tensor powers of the Hilbert space of each system
$\alpha\in I$. Notice that each of them can be interpreted as a symmetric
extension of $\rho_{I}$ derived from the decomposition (6). Denoting by
$I^{k}$ the first $k$ copies of each system in $I\in{\cal I}$, it is easy to
see that the states $\\{\rho^{({L})}_{I}\\}_{I\in{\cal I}}$ satisfy the
constraints:

  1. (i)

$\mbox{tr}_{I^{{L}-1}}(\rho^{({L})}_{I})=\rho_{I}$.

  2. (ii)

$\rho^{({L})}_{I}$ is Positive under Partial Transposition (PPT) [16] across
all bipartitions of its $|I|{L}$ systems.

  3. (iii)

$\rho^{({L})}_{I}\in B(\bigotimes_{\alpha\in I}{\cal
H}_{\text{sym}}({L},d_{\alpha}))$, where ${\cal H}_{\text{sym}}({L},d)$
denotes the symmetric space of ${L}$ $d$-dimensional particles.

  4. (iv)

$\mbox{tr}_{(I\setminus J)^{L}}(\rho^{({L})}_{I})=\mbox{tr}_{(J\setminus
I)^{L}}(\rho^{({L})}_{J})$ (after appropriately reordering the systems of one
of the sides).

For each ${L}$, we relax the property that $\\{\rho_{I}\\}_{I}$ arise from an
overall separable state by demanding that there exist positive semidefinite
matrices $\\{\rho_{I}^{({L})}\\}_{I}$ satisfying the four conditions above
(note that the last condition is missing in the DPS construction [15]). For
finite ${\cal A}$, the existence of the matrices $\\{\rho_{I}^{({L})}\\}_{I}$
can, in turn, be cast in terms of a semidefinite program (SDP) [9]. As we
increase ${L}$, these conditions lead to the announced SDP _hierarchy_
$\mathbb{H}({\cal I}|\\{\rho_{I}\\}_{I\in{\cal I}})$ ($\mathbb{H}$, for short)
of tests for entanglement detection.

######  Definition 3.

SDP hierarchy $\mathbb{H}$

Given a marginal scenario ${\cal A},{\cal I}\in P({\cal A})$ and
$L\in\mathbb{N}$, $\mathbb{H}^{L}$ is the set of state ensembles
$\\{\rho_{I}\\}_{I\in{\cal I}}$ for which there exist
$\\{\rho^{({L})}_{I}\\}_{I\in{\cal I}}$ such that, for all $I,J\in{\cal I}$,

$\displaystyle\rho^{({L})}_{I}\in B\left(\bigotimes_{\alpha\in I}{\cal
H}_{\text{sym}}({L},d_{\alpha})\right),$
$\displaystyle(\rho^{({L})}_{I})^{T_{S}}\,\succeq\,0,\forall S\subset I^{L},$
$\displaystyle\mbox{tr}_{I^{{L}-1}}(\rho^{({L})}_{I})=\rho_{I},$
$\displaystyle\mbox{tr}_{(I\setminus
J)^{L}}(\rho^{({L})}_{I})=\mbox{tr}_{(J\setminus I)^{L}}(\rho^{({L})}_{J}).$
(8)

If $\\{\rho_{I}\\}_{I\in{\cal I}}\in\mathbb{H}^{L}$, we say that the ensemble
$\\{\rho_{I}\\}_{I\in{\cal I}}$ passes the $L^{th}$ test of hierarchy
$\mathbb{H}$. Otherwise, $\\{\rho_{I}\\}_{I\in{\cal I}}$ is said to fail the
$L^{th}$ test.

Note that the ensemble variables $\\{\rho^{({L})}_{I}\\}_{I\in{\cal I}}$ and
their partial transposes can be embedded, through direct sum, into an overall
positive semidefinite variable, whose diagonal blocks are subject to the
linear/affine constraints above. That way, for each $L$, one arrives at the
canonical form of a semidefinite program [9].

Each level of the hierarchy $\mathbb{H}$ involves matrices acting on
$\bigotimes_{\alpha\in I}{\cal H}_{\text{sym}}({L},d_{\alpha})$, see condition
(iii). Since the dimension of ${\cal H}_{\text{sym}}({L},d)$ is

$d_{\text{sym}}=\left(\begin{array}[]{c}{L}+d-1\\\ d-1\end{array}\right)\sim
O({L}^{d-1})\,,$ (9)

the size of the matrices $\rho^{({L})}_{I}$ scales as $O({L}^{\sum_{\alpha\in
I}(d_{\alpha}-1)})$. Clearly, if the ensemble $\\{\rho_{I}\\}_{I\in{\cal I}}$
fails the ${L}^{\text{th}}$ SDP test of hierarchy $\mathbb{H}$, then it cannot
admit a separable extension. In such a predicament, the dual of the SDP [9]
will return a certificate of infeasibility, i.e., an entanglement witness in
the form of a linear inequality $\sum_{I}\mbox{tr}(W_{I}\rho_{I})\geq 0$ that
is violated by the ensemble $\\{\rho_{I}\\}_{I}$.

In Appendix B, we present also an alternative simplified hierarchy of SDPs
$\bar{\mathbb{H}}({\cal I})$ for those cases in which $I\in{\cal I}$ contains
an index $\alpha_{I}$ that does not appear in any other set $J\in{\cal I}$,
$J\not=I$. One can then provide a hierarchy where the system $\alpha_{I}$ is
not ${L}$-times “extended” in the construction of the matrix variable
$\rho^{({L})}_{I}$. Trivially, any ensemble $\\{\rho_{I}\\}_{I}$ passing the
${L}^{\text{th}}$ test of $\mathbb{H}({\cal I})$ will also pass the
${L}^{\text{th}}$ test of $\bar{\mathbb{H}}({\cal I})$. For some scenarios
${\cal I}$, though, both hierarchies provide a similar approximation to the
set of separable marginals and implementing $\bar{\mathbb{H}}^{L}$ requires
considerably fewer computational resources.

The natural question to ask is whether the SDP hierarchies defined here are
complete, i.e., under which conditions $\\{\rho_{I}\\}_{I}\in\mathbb{H}^{L}$
for all ${L}$ implies that $\\{\rho_{I}\\}_{I}$ admits a separable extension.
To answer it, we exploit the connection to the classical marginal problem
thanks to the following proposition, proven in Appendix C and based on the
linear maps introduced in [17].

######  Proposition 4.

Let $\\{\rho_{I}\\}_{I}\in{\mathbb{H}}^{L}$ or
$\\{\rho_{I}\\}_{I}\in\bar{\mathbb{H}}^{L}$. Then, there exists an ensemble of
fully separable states $\\{\tilde{\rho}_{I}\\}_{I}$, such that, for all
$I\in{\cal I}$,

$\displaystyle\|\rho_{I}-\tilde{\rho}_{I}\|_{1}\leq
2\left\\{1-\prod_{\alpha\in
I,\alpha\not=\alpha_{I}}(1-\epsilon(L,d_{\alpha}))\right\\},$ (10)

where

$\displaystyle\epsilon(L,d)=$ $\displaystyle\frac{d}{2(d-1)}\times$
$\displaystyle\min\\{1-x:P^{d-2,L\pmod{2}}_{\lfloor L/2+1\rfloor}(x)=0\\},$
(11)

and $\\{P^{\beta,\gamma}_{m}(x)\\}_{\beta,\gamma,m}$ denote the Jacobi
polynomials [18].

Moreover, the separable states $\\{\tilde{\rho}_{I}\\}_{I}$ are generated by
an ensemble $\\{\tilde{p}_{I}(\phi_{I})\\}_{I}$ of locally compatible
distributions.

By the properties of the zeros of the Jacobi polynomials [18], it follows
that, for $L\gg d_{\alpha}$, the right-hand side of (10) tends to
$O\left(\frac{\sum_{\alpha\in
I,\alpha\not=\alpha_{I}}d_{\alpha}^{2}}{L^{2}}\right)$. The above proposition
thus shows that the introduced hierarchies are a converging series of
relaxations of the set of reduced states $\\{\rho_{I}\\}_{I}$ admitting a
decomposition (6) generated by locally compatible probability measures.

However, since these compatibility conditions do not necessarily imply a
solution to the classical marginal problem, the proposition is not a proof of
convergence, as the states $\\{\tilde{\rho}_{I}\\}_{I}$ are not necessarily
the marginals of an overall separable state $\sigma$ as in eq. (5). In fact,
suppose that there exists an ensemble $\\{\tilde{p}_{I}(\phi_{I})\\}_{I}$ of
locally compatible distributions which are _not_ generated by an underlying
global measure. Then, for $m$ sufficiently high, one can find a similar
counterexample with an ensemble of probability distributions
$\\{\tilde{P}_{I}(a_{I})\\}$ of random variables
$\\{a_{\alpha}\\}_{\alpha\in{\cal A}}$ taking values in $\\{1,...,m\\}$. In
turn, such distributions can be used to build an ensemble
$\rho^{\text{noext}}_{I}$ of classical states of the form
$\rho^{\text{noext}}_{I}=\sum_{a_{I}}\tilde{P}(a_{I})|a_{I}\rangle\\!\langle
a_{I}|$, where $\\{|a_{I}\rangle:a_{I}\in\\{1,...,m\\}^{|I|}\\}$ is the
computational basis of $({\mathbb{C}}^{m})^{\otimes|I|}$. This ensemble is
generated by locally compatible probability measures and yet there is no
overall quantum state $\sigma$ (separable or not) admitting
$\\{\rho_{I}\\}_{I}$ as reduced density matrices. For these cases, the
hierarchy $\mathbb{H}$ is incomplete.

Conversely, Proposition $1$ guarantees convergence in all those classical
marginal scenarios ${\cal I}$ where global compatibility follows from local
compatibility. In Section 5 and 6 we present several such scenarios for
systems of finite and infinite size, and analyse the corresponding
entanglement marginal problems. These examples illustrate the applicability of
hierarchies $\mathbb{H},\bar{\mathbb{H}}$ to detect entanglement in relevant
experimental situations.

##  5 Finite systems

In this section we present marginal scenarios for finite systems, ${\cal
I}\subset P({\cal A})$, with $|{\cal A}|<\infty$, where the hierarchies
$\mathbb{H},\bar{\mathbb{H}}$ completely solve the entanglement marginal
problem.

First, we need to introduce some graph notation. A graph ${\cal G}=(V,E)$ is
defined by a collection of indices $V$, called vertices, together with a set
$E$ of pairs of vertices $\\{v_{i},v_{j}\\}$, called edges. Two vertices
$v_{i},v_{j}$ are said to be connected if there exists an edge $e\in E$ such
that $v_{i},v_{j}\in e$. A _clique_ is a set of pair-wise connected vertices,
and a _maximal clique_ $C$ is a clique such that, for any $v\in V,v\not\in C$,
$C\cup\\{v\\}$ is not a clique. A _graph cycle_ is a sequence of vertices
$(v_{i})_{i=1}^{m}$ in $V$ such that $v_{1}=v_{m}$ and $v_{i},v_{i+1}$ are
connected for $i=1,...,m-1$. A _chord_ in a graph cycle is an edge that does
not form part of the cycle but nonetheless connects two vertices of it, and a
_chordal graph_ is a graph such that any cycle of length $4$ or higher has a
chord. Chordal graphs find several applications in semidefinite programming
and combinatorial optimization because of their many appealing properties. It
is well known that it is very efficient to find both a perfect elimination
ordering for the vertices of a chordal graph and an arrangement of its maximal
cliques so to fulfil the so-called _running intersection property_. While
these properties are related (see for instance [19]), the second has a clearer
connection to the entanglement marginal problem, as we will show in the
following.

Given ${\cal A},{\cal I}$, define a graph ${\cal G}$ with vertices given by
the letters of ${\cal A}$, and join with an edge every pair of vertices
$\alpha,\beta$ such that $\alpha,\beta\in I$ for some $I\in{\cal I}$. In the
following, we will refer to ${\cal G}$ as the _dependency graph_ of ${\cal
I}$. The following proposition provides a sufficient condition for a marginal
scenario ${\cal A},{\cal I}\in P({\cal A})$ to have a trivial classical
marginal problem.

######  Proposition 5.

Let ${\cal A},{\cal I}\in P({\cal A})$ be a marginal scenario, and let ${\cal
G}$ be its corresponding dependency graph. If ${\cal G}$ is chordal and the
elements of ${\cal I}$ are its maximal cliques, then any ensemble of locally
compatible probability distributions $\\{\tilde{p}_{I}\\}_{I\in{\cal I}}$
admits a global measure.

This proposition is a well-known fact in combinatorial optimization [20] and
relates to the running intersection property mentioned above. For
completeness, we include a proof in Appendix D. Combining Propositions 4 and
5, we arrive at our first main result.

######  Theorem 6.

Let ${\cal A},{\cal I}\in P({\cal A})$ be a marginal scenario such that the
dependency graph of ${\cal I}$ is chordal and each $I\in{\cal I}$ is one of
its maximal cliques. Let $\\{\rho_{I}\\}_{I\in{\cal
I}}\in\bar{\mathbb{H}}^{L}$. Then, there exists a separable state $\sigma$
such that

$\|\sigma_{I}-\rho_{I}\|_{1}\leq O\left(\frac{\sum_{\alpha\in
I,\alpha\not=\alpha_{I}}d_{\alpha}^{2}}{L^{2}}\right),$ (12)

for all $I\in{\cal I}$.

As we argue in the next section, there exist relevant experimental scenarios
with a chordal dependency graph. For those, the above theorem guarantees that
$\bar{\mathbb{H}}$ provides a complete entanglement characterization.

Moreover, Theorem 6 can be useful to characterize the set of separable
ensembles even in marginal scenarios where the dependency graph is not
chordal. Indeed, suppose that we wish to decide whether the ensemble of
density matrices $\\{\rho_{I}\\}_{I\in{\cal I}}$ are the marginals of an
overall separable state, but the dependency graph ${\cal G}$ of ${\cal I}$ is
not chordal. Let $\bar{{\cal G}}$ be a chordal graph with vertices ${\cal A}$
such that ${\cal G}$ is a subgraph of $\bar{{\cal G}}$, and call $\bar{{\cal
I}}$ the set of maximal cliques of $\bar{{\cal G}}$. Since ${\cal G}$ is a
subgraph of $\bar{{\cal G}}$, it follows that there exists a function $c:{\cal
I}\to\bar{{\cal I}}$ such that $I\subset c(I)$, for all $I\in{\cal I}$. Thus,
by Theorem 6, the following hierarchy of SDPs fully characterizes separability
in ${\cal I}$:

$\displaystyle\exists\\{\rho_{I}\\}_{\bar{I}\in\bar{{\cal
I}}}\in\bar{\mathbb{H}}^{L}(\bar{{\cal I}}),$ such that
$\displaystyle\mbox{tr}_{c(I)\setminus I}(\rho_{c(I)})=\rho_{I},\forall
I\in{\cal I}.$ (13)

In graph-theoretic terminology, we would say that $\bar{{\cal G}}$ is a
_chordal completion_ of ${\cal G}$, and, to minimize the time and space
complexity of the hierarchy above, we need that the size of the maximal clique
of $\bar{{\cal G}}$ be as small as possible. Finding the chordal completion of
an arbitrary graph with minimum maximum clique size is known to be an NP-
complete problem [21]. However, for fixed $k\in\mathbb{N}$, deciding whether a
graph admits a chordal completion of maximum clique size $k$ or less is a
problem that can be solved in linear time on $|{\cal A}|$ [22]. Since $k$ is
fixed by our computer memory, it follows that, for any entanglement marginal
problem, we can use the algorithm in [22] to assess if there exists a
tractable SDP hierarchy of the form (13) to tackle it.

Graphs admitting a chordal completion with maximum clique size $k+1$ are
called _partial $k$-trees_, and they have been studied extensively. They
include cactus graphs, pseudoforests, series-parallel graphs, outerplanar
graphs, Halin graphs and Apollonian networks [23]. If the dependency graph of
a given marginal scenario belongs to one of such families, then one can solve
the corresponding entanglement marginal problem efficiently. As we will
analyse in detail next, the above families of graphs comprise some
experimentally relevant scenarios for entanglement detection in many-body
quantum systems.

###  5.1 Particles in a star configuration

Consider first the scenario where we have access to all the two-body reduced
states $\\{\rho_{1j}\\}_{j=2}^{n}$ of particle $1$ and each of the remaining
particles $\\{2,...,n\\}$. Determining whether the overall state of the system
is entangled amounts to solving the entanglement marginal problem for ${\cal
I}=\\{I_{j}:j=2,...,n\\}$, with $I_{j}\equiv\\{1,j\\}$. The corresponding
dependency graph is shown in Figure 2.

Figure 2: The star configuration. The dependency graph consists of the edges
$I_{j}\equiv\\{1,j\\}$, for $j=\\{2,...,n\\}$.

By simple inspection, we notice that the graph is chordal. Moreover, for
$j\not=1$, system $j$ only appears in $I_{j}$. Hence, by Proposition 4, the
hierarchy $\bar{\mathbb{H}}$, with $\alpha_{j}=j$ for $j=2,...,n$, is
convergent. Writing it explicitly, the SDP corresponding to the ${L}$-th level
of $\bar{\mathbb{H}}$ reads as follows

$\displaystyle\exists\,\,$ $\displaystyle\\{\rho_{a_{1}a_{2}\ldots
a_{L}b|j}\in B({\cal H}_{\text{sym}}({L},d_{1})\otimes{\cal
H}_{d_{j}})\\}_{j=2}^{n}\,,$ s.t.
$\displaystyle\forall\,\,j\,\in\,\\{2,\ldots,n\\}:$ (i)
$\displaystyle\rho_{a_{1}a_{2}\ldots a_{L}b|j}\succeq 0\,,$ (ii)
$\displaystyle\mbox{tr}_{(a_{2}\ldots a_{L})}(\rho_{a_{1}a_{2}\ldots
a_{L}b|j})=\rho_{1j}$ (iii) $\displaystyle\rho_{a_{1}a_{2}\ldots
a_{L}b|j}^{T_{a_{1}\ldots a_{k}}}\succeq 0\quad k=1,\ldots,{L}$ and
$\displaystyle\forall\,\,k\,\in\\{3,\ldots n\\}\,:$ (iv)
$\displaystyle\mbox{tr}_{b}(\rho_{a_{1}a_{2}\ldots
a_{L}b|2})=\mbox{tr}_{b}(\rho_{a_{1}a_{2}\ldots a_{L}b|k})$

Note that, in this case, implementing $\mathbb{H}^{L}({\cal I})$ would require
optimizing over positive semidefinite matrix variables $\rho^{({L})}_{I}$ of
size $O({L}^{d_{1}+d_{j}-2})$, each of them acting on the space ${\cal
H}_{\text{sym}}^{{L},d_{1}}\otimes{\cal H}_{\text{sym}}^{{L},d_{j}}$. Running
$\bar{\mathbb{H}}^{L}({\cal I})$, on the contrary, just requires extending
system $1$, and so the corresponding positive semidefinite matrix variables
are of size $O({L}^{d_{1}-1})$.

Let us then see how the hierarchy (5.1) performs in practice. Suppose that all
systems are qubits ($d_{j}=2$ for $j=1,...,n$), and $n=4$. Let $X,Y,Z$ denote
the Pauli matrices, and consider the problem of computing the separable energy
of the Hamiltonian $H=X_{1}X_{2}+Y_{1}Y_{3}+Z_{1}Z_{4}$, i.e., we wish to
minimize the term

$\mbox{tr}(\rho_{I_{2}}X\otimes X)+\mbox{tr}(\rho_{I_{3}}Y\otimes
Y)+\mbox{tr}(\rho_{I_{4}}Z\otimes Z)$ (15)

over all ensembles $\\{\rho_{I}:I\in{\cal I}\\}$ admitting a separable
extension.

An SDP optimization over $\\{\rho_{I}:I\in{\cal I}\\}\in\bar{\mathbb{H}}^{2}$
returns the exact value $-\sqrt{3}\approx-1.7320$, achievable by the product
state

$\sigma=\frac{{\mathbb{I}}+\frac{X+Y+Z}{\sqrt{3}}}{2}\otimes\frac{{\mathbb{I}}-X}{2}\otimes\frac{{\mathbb{I}}-Y}{2}\otimes\frac{{\mathbb{I}}-Z}{2}.$
(16)

This optimization, and all the following ones, was carried out using the
MATLAB optimization package YALMIP [24], in combination with the SDP solver
Mosek [25].

It is interesting to compare the exact value $-\sqrt{3}$ with that obtained by
minimizing $H$ instead over ensembles of separable states
$\\{\rho_{I}:I\in{\cal I}\\}$ satisfying local compatibility. For two-qubit
systems, the PPT condition is equivalent to separability [26]: this allows us
to carry out such an optimization exactly via SDP. The result is $-3$. This
example shows that the set of locally compatible separable states can be a
very bad outer approximation to the set of ensembles admitting a separable
extension. Moreover, as proven in [27, 28, 12], this is so even when one
demands in addition the existence of an overall quantum state for the state
ensemble. The need of constructions like our hierarchies to address the
entanglement marginal problem is thus vindicated.

###  5.2 Particles in a line

Figure 3: The 1D case. Left: the dependency graph of a 1D chain with open
boundary conditions, given access to nearest neighbors. Right: the dependency
graphs for the 1D case under closed boundary conditions. The solid lines
indicate the original dependency graph. Adding extra edges (dashed lines), we
obtain a chordal graph, with maximal cliques of the form $\\{1,j,j+1\\}$.

Let us consider next the very natural experimental scenario with particles
${\cal A}=\\{1,...,n\\}$ distributed in a line. We are given access to the
reduced density matrices of the nearest neighbors $\rho_{jj+1}$ for
$j=1,\ldots,n-1$. Namely, ${\cal I}=\\{I_{j}\\}_{j=1}^{n-1}$ with
$I_{j}=\\{j,j+1\\}$. The dependency graph of ${\cal I}$, a linear graph, is
again chordal, and $\\{I_{j}\\}_{j}$ are its maximal cliques. Therefore, the
SDP hierarchies $\mathbb{H}$, $\bar{\mathbb{H}}$ are complete. In this case,
the complexity of implementing one or the other is similar, so from now on, we
will stick to $\mathbb{H}$. For the sake of clarity, let us state explicitly
the SDP corresponding to the ${L}$-th level of such hierarchy, namely

$\displaystyle\exists\,\,$ $\displaystyle\\{\rho_{a_{1}\ldots a_{L}b_{1}\ldots
b_{L}|j}\in B({\cal H}_{j})\\}_{j=1}^{n-1}\,,$ s.t.
$\displaystyle\forall\,\,j\,\in\,\\{1,\ldots,n-1\\}:$ (i)
$\displaystyle\rho_{a_{1}\ldots a_{L}b_{1}\ldots b_{L}|j}\,\succeq\,0$ (ii)
$\displaystyle\mbox{tr}_{(a_{2}\ldots a_{L}b_{2}\ldots
b_{L})}(\rho_{a_{1}\ldots a_{L}b_{1}\ldots b_{L}|j})=\rho_{jj+1}$ (iii)
$\displaystyle\rho_{a_{1}\ldots a_{L}b_{1}\ldots b_{L}|j}^{T_{a_{1}\ldots
a_{k}}T_{b_{1}\ldots b_{l}}}\succeq 0\quad k,l=1,\ldots,{L}$ (iv)
$\displaystyle\mbox{tr}_{(a_{1}\ldots a_{L})}(\rho_{a_{1}\ldots
a_{L}b_{1}\ldots b_{L}|j})$ $\displaystyle=\mbox{tr}_{(b_{1}\ldots
b_{L})}(\rho_{a_{1}\ldots a_{L}b_{1}\ldots b_{L}|j+1})\,,$

where ${\cal H}_{j}\equiv{\cal H}_{\text{sym}}(d_{j},{L})\otimes{\cal
H}_{\text{sym}}(d_{j+1},{L})$.

As in the star configuration, the cost of implementing the ${L}^{th}$ test of
$\mathbb{H}$ on the line, and hence certifying that the ensemble is
$O(1/{L}^{2})$-close to that of a separable state, is just polynomial on the
system size $n$. In fact, even though the number of SDP matrix variables is
linear in $n$, their size is _independent of $n$_. This allows one to tackle
systems of hundreds of sites in a normal desktop, as we see next.

For our example, we take a 1-D Ising-like model, represented by the $2$-local
Hamiltonian $H=-(1/2)\sum_{j=0}^{n-1}X_{j}Y_{j+1}$ with periodic boundary
conditions. As shown in [12], in the limit $n\to\infty$, any quantum state
with support in the (very) degenerate ground state space of this Hamiltonian
is entangled.

The nearest-neighbour reduced density matrices of the thermal state
$\rho_{\beta}=e^{-\beta H}/Z$ can be computed efficiently by performing a
Jordan-Wigner transform and following the methods of [29] (see also [7]). We
wish to determine the critical inverse temperature $\beta_{S}$ for which the
nearest-neighbour two-body marginals of $\rho_{\beta_{S}}$ admit a separable
extension.

Note that there exist quantum systems with more than one critical separability
temperature, i.e., the thermal state of a system can be entangled for very low
temperatures, separable for moderately low temperatures, entangled for
moderately high temperatures and separable for very high temperatures 111A
two-qubit Hamiltonian, generated by random sampling, that exhibits such an
aberrant thermodynamical behavior is given by
$h=\left(\begin{array}[]{cccc}1.3398&0.9526&0.2617&1.8461\\\
0.9526&0.8519&0.2829&-1.1422\\\ 0.2617&0.2829&-2.2228&0.7696\\\
1.8461&-1.1422&0.7696&0.0476\end{array}\right)$.. According to our numerical
tools, though, the Hamiltonian $H$, as well as the Hamiltonians that we will
next introduce in this section, seems to have a single critical temperature.

As shown in Figure 4, implementing the hierarchy (5.2) at level ${L}=2$ allows
us to upper bound the exact value of $\beta_{S}$ for systems of up to few
hundred particles. More specifically, the nearest-neighbor density matrices of
the thermal state of $H$ did not satisfy conditions (5.2) for inverse
temperatures $\beta$ slightly greater than the values plotted in Figure 4.
Curiously, increasing the level to ${L}=3$ does not decrease our upper bounds
on the critical temperature.

Determining (or at least upper-bounding) the critical temperature below which
the thermal state of a many-body system is entangled had already been
considered in several works [30, 5, 31, 32, 33, 34, 35, 36]. Most of the above
methods rely on a specific entanglement witness based on linear or nonlinear
functions of some reduced density matrices of the system. Our technique
encompasses all these methods, at least in the asymptotic limit of convergence
of the hierarchy, when applied to the same marginal scenario. Let us also
mention that most of the previous works focus on translationally invariant
models for which we dedicate a specific comparison in the next Section. A more
interesting comparison can be made with the approach in [5], where the authors
tackle this problem via spin-squeezing inequalities. To do so, they must
assume that all two-body correlators are available, i.e., the authors are
working in the marginal scenario ${\cal I}^{\prime}=\\{\\{j,k\\}:j>k\\}$. Even
though spin-squeezing inequalities do not fully characterize the set of all
separable two-party correlators, it is interesting to see whether they are
advantageous with respect to (complete) methods of entanglement detection via
nearest-neighbor correlations.

In this regard, we find that spin-squeezing inequalities are not able to
detect the entanglement of the thermal state of the Hamiltonian above, not
even at zero temperature. On the other hand, when applied to detect the
entanglement of the thermal state of the Heisenberg model, with
$H=\sum_{i=1}^{n-1}(X_{i}X_{i+1}+Y_{i}Y_{i+1}+Z_{i}Z_{i+1})$, spin-squeezing
inequalities do offer an advantage, as they provide smaller upper bounds on
$\beta_{S}$ than level $L=2$ of hierarchy (5.2) for $n=3,...,8$. Since higher
orders of the hierarchy did not seem to improve the bound on the critical
temperature, we conjecture that, for some range of temperatures where the
thermal state of the Heisenberg Hamiltonian is entangled, there exist
separable states with the same nearest-neighbor correlators (but different
two-body correlators).

The advantages of spin-squeezing inequalities seem to disappear, however, when
the system under consideration is not translation-invariant. To prove this
point, we consider spin-glass systems with a Hamiltonian of the form
$H_{\bar{\alpha}}=\sum_{i}\alpha_{i}(X_{i}X_{i+1}+Y_{i}Y_{i+1}+Z_{i}Z_{i+1})$,
where $(\alpha_{i})_{i}$ are random variables, independently sampled from a
uniform distribution in the interval $[0,1]$. We considered systems of size
$n=3,...,8$. For each system size we generated $600$ such random Hamiltonians
and used spin-squeezing inequalities, as well as the level $L=2$ of hierarchy
(5.2), to ascertain which method produced smaller upper bounds on $\beta_{S}$.
The results are shown in Table 1. As the reader can appreciate, the second
level of the hierarchy (5.2) provides better bounds for $\beta_{S}$ in most of
the cases, and the advantage seems to grow with the system size.

System size | $\eta$
---|---
3 | 0.74
4 | 0.75
5 | 0.78
6 | 0.81
7 | 0.81
8 | 0.83
Table 1: Fraction of times $\eta$ that the second level of the hierarchy (5.2)
produced an upper bound on ${\cal B}_{S}$ (for the random Hamiltonian
$H_{\bar{\alpha}}$) greater than that obtained through spin-squeezing
inequalities.

###  5.3 Particles in a ring

Figure 4: Upper bounds on the critical inverse temperature of separability for
the thermal state of $H=-(1/2)\sum_{j=0}^{n-1}X_{j}Y_{j+1}$, as a function of
the number of particles. The results are obtained by the hierarchy
$\mathbb{H}$ at the level ${L}=2$ for a scenario where all the near-neighbours
two-body reduced states are given. The plot compares the critical $\beta$
between the case where the information of the boundary term $\rho_{1n}$ is
given (red) or not (orange). Although the hierarchy for both cases has a
favourable scaling with $n$, we decided to show only results that require less
than a few hours of computation in a normal laptop.

Let us now complicate our 1D scenario by closing the spin chain, i.e., by
assuming that we are given the knowledge also of $\rho_{1n}$. In the power set
notation, such a scenario corresponds to choosing the sets of indices
$I_{j}=\\{j,j\mbox{ mod }n+1\\}$, for $j=1,...,n$. This example is useful to
illustrate how one can deal with situations in which the dependency graph
${\cal G}$ of ${\cal I}=\\{I_{j}\\}_{j}$ is not chordal, see Figure 3. Hence,
in this scenario local compatibility of marginal probability distributions
does not imply global compatibility. Thus, a modification of (5.2) by simply
introducing an additional symmetric extension $\rho_{a_{1}\ldots
a_{L}b_{1}\ldots b_{L}|n}$ of the reduced density matrix $\rho_{1n}$ would
lead to a sound but not convergent hierarchy of relaxations.

As explained above, one can derive a convergent SDP hierarchy for this
marginal scenario by completing the original dependency graph ${\cal G}$ of
${\cal I}$. In this regard, Figure 3 shows a possible chordal completion
$\bar{{\cal G}}$ for ${\cal G}$, consisting in selecting one of the nodes
(say, node $1$) and adding edges with respect to any other node. The maximal
cliques of the new (chordal) graph are now $\bar{I}_{j}\equiv\\{1,j+1,j+2\\}$,
for $j=1,...,n-2$. Call $\bar{{\cal I}}$ the set of all such sets. Based on
these facts, to solve the 1D entanglement marginal problem for nearest-
neighbour states with closed boundary conditions, we consider a slightly
modified SDP hierarchy whose ${L}^{th}$ level is given by:

$\displaystyle\exists\\{\bar{\rho}_{\bar{I}}\\}_{\bar{I}\in\bar{{\cal
I}}}\in\mathbb{H}^{L}(\bar{{\cal I}})\mbox{ s.t.}$
$\displaystyle\mbox{tr}_{1}\bar{\rho}_{\bar{I}_{j}}=\rho_{j+1j+2},\mbox{ for
}j=1,...,n-2,$
$\displaystyle\mbox{tr}_{3}\bar{\rho}_{\bar{I}_{1}}=\rho_{12},\mbox{tr}_{n-1}\bar{\rho}_{\bar{I}_{n-2}}=\rho_{1n}.$
(18)

This hierarchy is now complete. Moreover, by Theorem 6 and the monotonicity of
the trace distance, it follows that, for any ensemble
$\\{\rho_{I}\\}_{I\in{\cal I}}$ of states passing the $L^{th}$ level, there
exists a separable state $\sigma$ with $\|\rho_{I}-\sigma_{I}\|_{1}\leq
O\left(\frac{3d^{2}}{L^{2}}\right)$, for all $I\in{\cal I}$.

Remarkably, in the 1D case considered here, the polynomial scaling with $n$ of
the computational effort of (5.3) is preserved, since the size of the sets
$\bar{I}_{j}$ is independent of $n$. Thanks to this favourable scaling, we can
use (5.3) to upper bound the critical temperatures for entanglement in the 1D
model defined above for the case of periodic boundary conditions as well, the
results appearing in Figure 4.

Before moving on, some comments on related work are in order. In [37] it was
noticed that, for 1D Hamiltonians with closed or open boundary conditions, the
minimum energy achievable via mean field theory (namely, the separable energy)
can be computed up to a fixed error with time complexity polynomial on the
system size using $\epsilon$-nets. The hierarchies introduced here provide a
similar result: by optimizing the energy over the set of marginals compatible
with $\mathbb{H}$, one obtains lower bounds to the mean field energy, whose
distance to the exact results can be controlled by adjusting the hierarchy
level.

##  6 Infinite systems with symmetries

The previous tools can be even applied to solve the entanglement marginal
problem for infinite systems, that is, with $|{\cal A}|=\infty$. Of course,
the most general instance of the problem is out of reach because it requires
specifying an infinite number of reduced states. However, the problem can be
solved in some instances where the global system is supposed to satisfy a
symmetry. The connection to the classical marginal problem plays again an
important role.

###  6.1 Infinite symmetric scenarios where the entanglement marginal problem
is trivial

In section 6.2 we will show how, with minor modifications, hierarchy
$\mathbb{H}$ can be used to fully characterize the marginals of 1D separable
TI quantum states. Before getting there, though, it is worth exploring in
which situations implementing $\mathbb{H}$ would be an overkill. In fact, as
we next prove, if the system under study satisfies certain symmetries present
in most studied models in statistical physics, then the entanglement marginal
problem can be solved with relative ease.

Consider a scenario where physical systems lie on the sites of a two-
dimensional square lattice. That is, ${\cal A}=\mathbb{Z}^{2}$ and
$d_{\alpha}=d$ for all $\alpha\in{\cal A}$. We suppose the overall quantum
state $\rho$ describing the systems in the lattice to be TI and also symmetric
under reflections of the vertical and horizontal axes. This scenario appears
quite frequently in statistical physics. At any temperature, the thermal state
of any lattice Hamiltonian that is both translation and reflection invariant
is described by a lattice state $\rho$ with these two symmetries.

In this context, consider the entanglement marginal problem with ${\cal
I}=\\{(x,y)+\hat{I}:x,y\in\mathbb{Z}\\}$; where $\hat{I}=\\{(x,y):x,y=1,2\\}$,
i.e., we consider all the $2\times 2$ plaquettes. By translation invariance,
we have that $\rho_{I}=\rho_{J}=:\hat{\rho}$, for all $I,J\in{\cal I}$. The
input of the entanglement marginal problem is therefore finite: it suffices to
provide the $4$-partite experimental matrix $\hat{\rho}$, which we take to act
on the sites in $\hat{I}$. Furthermore, by reflection symmetry we have that
$\hat{\rho}$ is invariant under the permutation operators ${\cal P}_{H}$,
${\cal P}_{V}$, where $H$ ($V$) denotes the permutation that exchanges systems
$(x,1)$ and $(x,2)$ for $x=1,2$ ($(1,y)$ and $(2,y)$ for $y=1,2$).

In this scenario, the marginal entanglement problem is trivial, in the
following sense: $\hat{\rho}$ is the marginal of a separable TI reflection
invariant (RI) quantum state iff $\hat{\rho}$ is separable and invariant under
the permutations ${\cal P}_{H},{\cal P}_{V}$. The “only if” implication is
trivial; in the next lines we prove the “if” part.

Let $\hat{\rho}$ be a $4$-partite fully separable quantum state, invariant
under ${\cal P}_{H}$, ${\cal P}_{V}$. Then, there exists a measure
$p_{\hat{I}}(\phi_{\hat{I}})d\phi_{\hat{I}}$ generating $\hat{\rho}$. Consider
now the measure defined by

$\hat{p}_{\hat{I}}(\phi_{\hat{I}})=\frac{1}{4}\sum_{\pi\in\\{{\mathbb{I}},H,V,HV\\}}p_{\hat{I}}(\phi_{\pi(\hat{I})}).$
(19)

This measure is symmetric under the action of $H,V$ on the $4$-dimensional
vector $\phi_{\hat{I}}$. Moreover, it generates the separable state

$\displaystyle\frac{1}{4}\left(\hat{\rho}+{\cal P}_{H}\hat{\rho}{\cal
P}_{H}^{\dagger}+{\cal P}_{V}\hat{\rho}{\cal P}_{V}^{\dagger}+\right.$
$\displaystyle\left.{\cal P}_{V}{\cal P}_{H}\hat{\rho}({\cal P}_{V}{\cal
P}_{H})^{\dagger}\right)=\hat{\rho}.$ (20)

In [38], it is shown that any reflection-invariant distribution
$\hat{p}_{\hat{I}}(\phi_{\hat{I}})$ defined on a $2\times 2$ plaquette admits
an extension $\hat{p}(\phi)$ to the whole square lattice that is also TI and
RI. It follows that $\hat{\rho}$ admits a TI, RI separable extension given by
$\hat{p}(\phi)$.

Unfortunately, this trick cannot be extended to characterize entanglement in,
e.g., $3\times 3$ site plaquettes $I=\\{(x,y):x,y=1,2,3\\}$. The reason is
that there exist LTI distributions $p_{I}(a_{I})$ for the $3\times 3$
plaquette, invariant under reflections and even 90 degree rotations, which
nonetheless do not admit a TI extension [10].

The result in [38] on the classical marginal problem generalizes to square
lattices of all spatial dimensions. We arrive at the following result.

######  Proposition 7.

Let ${\cal A}=\mathbb{Z}^{D}$ and $\hat{I}=\\{1,2\\}^{D}$. A state
$\hat{\rho}$ defined in $\hat{I}$ is the marginal of a translation and
reflection invariant separable state for the whole hypercubic lattice iff
$\hat{\rho}$ is fully separable and symmetric under the reflection of each
orthogonal axis.

In order to characterize such marginals, it is thus enough to impose symmetry
and use any separability criterion, e.g., the DPS hierarchy [15], to enforce
separability.

For the infinite spin chain ($D=1$), the proposition implies that the set of
nearest-neighbor marginals of separable TI and RI states equals the set of
separable bipartite states $\hat{\rho}_{1,2}$, with
$\hat{\rho}_{2,1}=\hat{\rho}_{1,2}$. For $d=2$, the set of such states can be
characterized analytically: it corresponds to the set of bipartite PPT states
with symmetry under reflections. Let us remark that the spin-$1/2$ chain with
translation and reflection invariance comprises the most studied integrable
models in 1D, such as the XY and the Heisenberg models.

On this subject, it is worth noting that in [30] Tóth shows how to compute the
exact separable energy per site of 2-local translation-invariant Hamiltonians
with reflection symmetry. For $D=1$ systems, he observes that the separable
energy can be achieved by states of the form
$...|\psi_{1}\rangle|\psi_{2}\rangle|\psi_{1}\rangle|\psi_{2}\rangle...$. This
can be regarded as the dual of our result, since the extreme points of
symmetric separable bipartite states are of the form
$\hat{\rho}_{12}=\frac{1}{2}(|\psi_{1}\rangle\\!\langle\psi_{1}|\otimes|\psi_{2}\rangle\\!\langle\psi_{2}|+|\psi_{2}\rangle\\!\langle\psi_{2}|\otimes|\psi_{1}\rangle\\!\langle\psi_{1}|)$,
and thus
$\mbox{tr}(\hat{\rho}_{12}H_{12})=\mbox{tr}\\{(|\psi_{1}\rangle\\!\langle\psi_{1}|\otimes|\psi_{2}\rangle\\!\langle\psi_{2}|)H\\}$,
for all operators $H$ such that $H_{12}=H_{21}$. For higher spatial
dimensions, Proposition 7 extends Tóth’s results from Hamiltonians with
nearest-neighbor interactions to Hamiltonians with general (reflection-
symmetric) plaquette operators.

###  6.2 Translation invariance in one dimension

What happens when we care about next-to-nearest neighbor correlations, or lose
invariance under reflections? Then the entanglement marginal problem becomes
non-trivial, and SDP hierarchies such as $\mathbb{H}$ are needed. In this
section, we study how to solve the entanglement marginal problem for infinite
TI 1D chains.

Consider thus a scenario where quantum systems of dimension $d$ rest on the
sites of an infinite spin chain, i.e., ${\cal A}=\mathbb{Z}$. As in the
previous section, we assume that the overall quantum state is TI, but not
necessarily invariant under reflections. The input of the entanglement
marginal problem is $\hat{\rho}$, the reduced density matrix of $k$
consecutive neighbors, i.e., $\hat{\rho}=\rho_{\hat{I}}$, with
$\hat{I}=\\{1,...,k\\}$. We wish to determine whether $\hat{\rho}$ is the
marginal of a separable, TI quantum state.

Suppose, for a moment, that such is the case. In [12] it is shown that, should
there exist an overall TI separable state, the global measure $p(\phi)d\phi$
in eq. (5) can also be chosen TI. Hence the $k$-variate distribution
$p_{\hat{I}}$ generating the separable state $\hat{\rho}$ can be assumed LTI.
This observation implies that $\hat{\rho}^{({L})}$, as defined in (7) is also
LTI, i.e., it satisfies

$\mbox{tr}_{\\{1\\}^{L}}(\hat{\rho}^{({L})})=\mbox{tr}_{\\{k\\}^{L}}(\hat{\rho}^{({L})}).$
(21)

This suggests tackling the entanglement marginal problem with an SDP hierarchy
$\hat{\mathbb{H}}$ whose ${L}^{th}$ level is given by the SDP:

$\displaystyle\exists\hat{\rho}^{({L})}\in B({\cal
H}_{\text{sym}}^{{L},d})^{\otimes k},\hat{\rho}^{({L})}\,\succeq 0\,\,\,\text{
s.t.}$
$\displaystyle\mbox{tr}_{\hat{I}^{{L}-1}}(\hat{\rho}^{({L})})=\hat{\rho},$
$\displaystyle\mbox{tr}_{\\{1\\}^{L}}(\hat{\rho}^{({L})})=\mbox{tr}_{\\{k\\}^{L}}(\hat{\rho}^{({L})}).$
(22)

######  Theorem 8.

Let $\hat{\rho}\in\hat{\mathbb{H}}^{L}$. Then, there exists a translation
invariant separable state $\sigma$ for the infinite spin chain such that

$\|\hat{\rho}-\sigma_{\hat{I}}\|_{1}\leq O\left(\frac{kd^{2}}{L^{2}}\right).$
(23)

###### Proof.

In the proof of Proposition 4 (see Appendix C), we applied the linear maps
defined in [17] to the matrix variables $\\{\rho^{({L})}_{I}\\}_{I}$ appearing
in the definition of $\mathbb{H}$ in order to generate the separable ensemble
$\\{\tilde{\rho}_{I}\\}_{I}$. As explained in Appendix C, these linear maps
have the convenient property of translating linear relations over the matrix
variables $\\{\rho^{({L})}_{I}\\}_{I}$ into analogous linear relations over
the distributions $\\{\tilde{p}_{I}(\phi_{I})\\}_{I}$ generating
$\\{\tilde{\rho}_{I}\\}_{I}$. Consequently, if we apply said maps to
$\hat{\rho}^{({L})}$, we find that, for any
$\hat{\rho}\in\hat{\mathbb{H}}^{L}$, there exists a separable state
$\tilde{\rho}$, with $\|\tilde{\rho}-\hat{\rho}\|_{1}\leq
O\left(\frac{kd^{2}}{{L}^{2}}\right)$ generated by a measure
$\tilde{p}_{\hat{I}}(\phi_{\hat{I}})$ such that

$\int d\varphi\tilde{p}_{\hat{I}}(\varphi,\phi_{2},...,\phi_{k})=\int
d\varphi\tilde{p}_{\hat{I}}(\phi_{1},...,\phi_{k-1},\varphi).$ (24)

That is, the LTI of the variable $\hat{\rho}^{({L})}$, enforced by the last
relation in (22), is inherited by the distribution $\tilde{p}_{\hat{I}}$
generating the separable approximation to $\hat{\rho}$.

It is a well-known result in statistical physics (see, e.g., [12] for a proof)
that every $k$-variate distribution $\tilde{p}_{\hat{I}}$ satisfying 1D LTI
admits a 1D TI extension $\tilde{p}$. Hence, $\tilde{\rho}$ admits a TI
separable extension $\sigma$, and we arrive at the statement of the theorem.

∎

To test how the SDP hierarchy $\hat{\mathbb{H}}$ performs in practice, we take
the entanglement witness for translation-invariant states presented in [12].
There, it is shown that, if $\rho_{1,2}$ is the nearest-neighbor reduced
density matrix of a separable infinite TI state, then it must satisfy
$\mbox{tr}\\{\rho_{12}(X\otimes Z)\\}\geq-\frac{1}{2}$. Moreover, this bound
is tight. We verify that a second order relaxation ${L}=2$ recovers this
bound, up to the solver’s precision. Note that, since $X\otimes Z$ is not
invariant under reflection, we cannot invoke Proposition 7 to solve this
problem. Moreover, as observed in [12], $\mbox{tr}\\{\sigma_{12}(X\otimes
Z)\\}=-1$ for the separable and LTI state
$\sigma_{12}=\frac{1}{2}(|+\rangle\\!\langle+|\otimes|-i\rangle\\!\langle-i|+|-\rangle\\!\langle-|\otimes|+i\rangle\\!\langle+i|)$,
with $X|\pm\rangle=\pm|\pm\rangle,Y|\pm i\rangle=\pm|\pm i\rangle$.

###  6.3 2D translation invariance

Extending the 1D argument for TI systems to the 2D case without further
symmetries is non-trivial. To begin, using the symmetrization technique
introduced in [12], one can prove that the marginal of a 2D separable TI state
admits a separable decomposition generated by a TI measure. Hence, for
$\hat{I}=\\{(x,y):1\leq x\leq k,1\leq y\leq l\\}$, we can assume that the
distribution $p_{\hat{I}}$ in (7) is LTI. Hence the corresponding SDP variable
$\hat{\rho}^{({L})}$ is subject to the LTI conditions:

$\displaystyle\mbox{tr}_{\\{(1,y)^{L}:y\\}}(\hat{\rho}^{({L})})=\mbox{tr}_{\\{(k,y)^{L}:y\\}}(\hat{\rho}^{({L})}),$
$\displaystyle\mbox{tr}_{\\{(x,1)^{L}:x\\}}(\hat{\rho}^{({L})})=\mbox{tr}_{\\{(x,l)^{L}:x\\}}(\hat{\rho}^{({L})}).$
(25)

Applying the linear maps from [17] over any feasible matrix variable
$\hat{\rho}^{({L})}$, we arrive at a separable decomposition for $\hat{\rho}$
generated by a LTI distribution $\tilde{p}(\phi_{\hat{I}})$.

This is the point where problems appear. Unfortunately, in two spatial
dimensions LTI does _not_ imply the existence of a global TI measure [10]. In
fact, the simplest problem of deciding whether a pair of distributions
$P_{h},P_{v}$ are the horizontal and vertical nearest-neighbor distributions
of a 2D translation-invariant model in the square lattice is undecidable [11].
Defining a complete hierarchy of SDPs to characterize entanglement in the 2D
TI case would require considering sequences of extensions
$(\hat{\rho}_{I_{j}}^{({L})})_{j}$ involving an ever-growing number of sites
$I_{j}$.

A compromise between full reflection symmetry and raw TI is a scenario where
the considered system is only symmetric with respect to reflections over the
vertical axis, see Figure 5. Let us then consider an infinite square lattice,
call $\hat{I}$ the $l\times 2$ plaquette $\\{(x,y):x=1,2,y=1,...,l\\}$, and
let $\hat{\rho}$, defined on the sites $\hat{I}$, be the input of an
entanglement marginal problem. We denote by $U,L$ the subsets of $\hat{I}$
given by $\\{(x,y):x=1,2;y=1,...,k-1\\}$, $\\{(x,y):x=1,2;y=2,...,k\\}$,
respectively.

Figure 5: The 2D case. Subsystems (in red) are located at each site of an
infinite square lattice, subject to symmetry under reflections of the blue
axis and translation invariance. The set $\hat{I}$ of sites is circled with
dashed lines.

Acknowledging the LTI and invariance under reflections over the vertical axis
of the underlying distribution $\hat{p}(\phi)$ generating the separable state
$\hat{\rho}$, we arrive, via (7), at a hierarchy of SDP relaxations whose
${L}^{th}$ level is:

$\displaystyle\exists\hat{\rho}^{({L})}\in B({\cal
H}_{\text{sym}}^{{L},d})^{\otimes 2k},\hat{\rho}^{({L})}\succeq 0,$
$\displaystyle\mbox{tr}_{\\{(1,1),(2,1)\\}^{L}}(\hat{\rho}^{({L})})=\mbox{tr}_{\\{(1,k),(2,k)\\}}^{L}(\hat{\rho}^{({L})}),$
$\displaystyle\mbox{SWAP}\hat{\rho}^{({L})}\mbox{SWAP}^{\dagger}=\hat{\rho}^{({L})},$
(26)

where SWAP is the operator permuting the Hilbert spaces of sites $(0,y)$ and
$(1,y)$, for $y=0,...,k-1$. The convergence of this hierarchy follows from the
proof of proposition 4 and the result, proven in [38], that any distribution
$P_{\hat{I}}(a_{\hat{I}})$ satisfying reflection symmetry along the vertical
axis in addition to LTI admits a TI extension that is also symmetric with
respect to vertical reflections.

We arrive at the following theorem.

######  Theorem 9.

Let $\hat{\rho}$ satisfy the $L^{th}$ level of the above hierarchy. Then,
there exists a separable state $\sigma$ for the infinite square lattice,
invariant under translations and vertical reflections, such that

$\|\sigma_{\hat{I}}-\hat{\rho}\|\leq O\left(\frac{kd^{2}}{L^{2}}\right).$ (27)

The characterization of TI distributions with reflection symmetry presented in
[38] can be easily extended to arbitrary spatial dimensions. The general
result would state that any probability distribution $P$ for the variables of
the sites
$\\{(x_{1},x_{1},...,x_{D}):x_{1}\in\\{1,...,k\\},x_{2},...,x_{D}\in\\{1,2\\}\\}$
for a hypercubic lattice admits a TI extension with symmetry under the
reflection of the last $D-1$ axes iff $P$ is LTI along the first axis and
symmetric under the inversion of the rest. Implementing the $2^{nd}$ level of
the corresponding SDP hierarchy to tackle the 3D entanglement marginal problem
is, however, unrealistic in a normal desktop.

##  7 Conclusion

In this work, we have extensively studied the entanglement marginal problem,
namely the problem of detecting the entanglement of an overall quantum state
given access to some ensemble of reduced density matrices. We have presented a
general framework to derive hierarchies of SDP relaxations of the set of
ensembles admitting a separable extension. We related the convergence or
completeness of these hierarchies to the classical marginal problem, and
exploited this connection to solve the entanglement marginal problem for
condensed matter systems of arbitrary size in 1D and also in 2D (under
reflection symmetries). In addition, the introduced tools allowed us to show
that, for some thermodynamical scenarios, the entanglement marginal problem
becomes trivial. In fact, the set of two-qubit nearest-neighbor marginals of a
1D TI, RI separable state can be characterized analytically.

Remarkably, the computational complexity of the methods presented in this work
scales very well with the system size, when it depends on it at all. We are
thus optimistic that our results will find application to assess in a scalable
way the entanglement of the states generated in current and near-term quantum
setups, such as Noisy Intermediate Scale Quantum (NISQ) devices.

_Acknowledgements_

MN was supported by the Austrian Science fund (FWF) stand-alone project P
30947. FB was supported by the Deutsche Forschungsgemeinschaft (DFG, German
Research Foundation) – Project number 414325145 in the framework of the
Austrian Science Fund (FWF): SFB F71. AA was supported by the ERC AdG CERQUTE,
the AXA Chair in Quantum Information Science, the Spanish MINECO (Severo Ochoa
grant SEV-2015-0522), the Generalitat de Catalunya (CERCA Program, QuantumCAT
and SGR 1381) and the Fundació Privada Cellex and Mir-Puig.

## References

  * Arute  _et al._ [2019] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, Nature 574, 505 (2019).
  * Schmied  _et al._ [2016] R. Schmied, J.-D. Bancal, B. Allard, M. Fadel, V. Scarani, P. Treutlein, and N. Sangouard, Science 352, 441 (2016).
  * Doherty  _et al._ [2002] A. C. Doherty, P. A. Parrilo, and F. M. Spedalieri, Phys. Rev. Lett. 88, 187904 (2002).
  * Gühne  _et al._ [2008] O. Gühne, M. Reimpell, and R. F. Werner, Phys. Rev. A 77, 052317 (2008).
  * Tóth  _et al._ [2007] G. Tóth, C. Knapp, O. Gühne, and H. J. Briegel, Physical Review Letters 99 (2007), 10.1103/PhysRevLett.99.250405.
  * Vitagliano  _et al._ [2014] G. Vitagliano, I. Apellaniz, I. L. Egusquiza, and G. Tóth, Physical Review A 89 (2014), 10.1103/PhysRevA.89.032307.
  * Tura  _et al._ [2017] J. Tura, G. De las Cuevas, R. Augusiak, M. Lewenstein, A. Acín, and J. I. Cirac, Physical Review X 7, 021005 (2017).
  * Aloy  _et al._ [2019] A. Aloy, J. Tura, F. Baccari, A. Acín, M. Lewenstein, and R. Augusiak, Physical Review Letters 123 (2019), 10.1103/physrevlett.123.100507.
  * Vandenberghe and Boyd [1996] L. Vandenberghe and S. Boyd, SIAM Review 38, 49 (1996).
  * Goldstein  _et al._ [2017] S. Goldstein, T. Kuna, J. L. Lebowitz, and E. R. Speer, Journal of Statistical Physics 166, 765 (2017).
  * Schlijper [1988] A. G. Schlijper, Journal of Statistical Physics 50, 689 (1988).
  * Wang  _et al._ [2017] Z. Wang, S. Singh, and M. Navascués, Phys. Rev. Lett. 118, 230401 (2017).
  * Pitowsky [1989] I. Pitowsky,  _Quantum Probability and Quantum Logic_, Lecture Notes in Physics (Springer Berlin Heidelberg, 1989).
  * Doherty  _et al._ [2004] A. C. Doherty, P. A. Parrilo, and F. M. Spedalieri, Phys. Rev. A 69, 022308 (2004).
  * Doherty  _et al._ [2005] A. C. Doherty, P. A. Parrilo, and F. M. Spedalieri, Phys. Rev. A 71, 032333 (2005).
  * Peres [1996] S. Peres, Phys. Rev. Lett. 77, 1413–1415 (1996).
  * Navascués  _et al._ [2009] M. Navascués, M. Owari, and M. B. Plenio, Phys. Rev. A 80, 052306 (2009).
  * Abramowitz [1974] M. Abramowitz,  _Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables_ (Dover Publications, Inc., USA, 1974).
  * Vandenberghe and Andersen [2015] L. Vandenberghe and M. S. Andersen, Foundations and Trends in Optimization 1, 241 (2015).
  * Lasserre [2006] J. B. Lasserre, in  _Mathematical Software - ICMS 2006_ , edited by A. Iglesias and N. Takayama (Springer Berlin Heidelberg, Berlin, Heidelberg, 2006) pp. 263–272.
  * Bodlaender  _et al._ [1995] H. L. Bodlaender, J. R. Gilbert, H. Hafsteinsson, and T. Kloks, J. Algorithms 18, 238–255 (1995).
  * Bodlaender [1996] H. L. Bodlaender, SIAM Journal on Computing 25, 1305 (1996).
  * Bodlaender [1998] H. L. Bodlaender, Theoretical Computer Science 209, 1 (1998).
  * Löfberg [2004] J. Löfberg, in  _Proceedings of the CACSD Conference_ (Taipei, Taiwan, 2004).
  * [25] L. Vandenberghe and S. Boyd,  _The MOSEK optimization toolbox for MATLAB manual. Version 7.0 (Revision 140)._ (MOSEK ApS, Denmark.).
  * Horodecki  _et al._ [1996] M. Horodecki, P. Horodecki, and R. Horodecki, Physics Letters A 223, 1–8 (1996).
  * Paraschiv  _et al._ [2018] M. Paraschiv, N. Miklin, T. Moroder, and O. Gühne, Phys. Rev. A 98, 062102 (2018).
  * Miklin  _et al._ [2016] N. Miklin, T. Moroder, and O. Gühne, Phys. Rev. A 93, 020104 (2016).
  * Barouch and McCoy [1971] E. Barouch and B. M. McCoy, Physical Review A 3, 786 (1971).
  * Tóth [2005] G. Tóth, Phys. Rev. A 71, 010301 (2005).
  * Dowling  _et al._ [2004] M. R. Dowling, A. C. Doherty, and S. D. Bartlett, Phys. Rev. A 70, 062113 (2004).
  * Brukner and Vedral [2004] C. Brukner and V. Vedral, arXiv preprint quant-ph/0406040 (2004).
  * Hide  _et al._ [2007] J. Hide, W. Son, I. Lawrie, and V. Vedral, Phys. Rev. A 76, 022319 (2007).
  * Nakata  _et al._ [2009] Y. Nakata, D. Markham, and M. Murao, Phys. Rev. A 79, 042313 (2009).
  * Hauke  _et al._ [2016] P. Hauke, M. Heyl, L. Tagliacozzo, and P. Zoller, Nature Physics 12, 778 (2016).
  * Bose and Tribedi [2005] I. Bose and A. Tribedi, Phys. Rev. A 72, 022314 (2005).
  * Schuch and Cirac [2010] N. Schuch and J. I. Cirac, Phys. Rev. A 82, 012314 (2010).
  * Wang and Navascués [2018] Z. Wang and M. Navascués, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 474, 20170822 (2018).
  * Blair and Peyton [1993] J. R. S. Blair and B. Peyton, in  _Graph Theory and Sparse Matrix Computation_, edited by A. George, J. R. Gilbert, and J. W. H. Liu (Springer New York, New York, NY, 1993) pp. 1–29.

##  Appendix A Infinite systems

In this section, we provide simple operational definitions for classical
distributions, quantum states and separable quantum states describing physical
systems with a countable set of subsystems ${\cal A}$, finite or infinite.

######  Definition 10.

Quantum states

Let ${\cal A}$ be a countable alphabet, and, for each $\alpha\in{\cal A}$, let
$d_{\alpha}\in\mathbb{N}$ denote the Hilbert space dimension of system
$\alpha$. Let $\rho$ be a function mapping every finite subset ${\cal
B}\subset{\cal A}$ into a trace-one positive semidefinite matrix $\rho_{{\cal
B}}\in\bigotimes_{\beta\in{\cal B}}B({\mathbb{C}}^{d_{\beta}})$, with the
property

$\mbox{tr}_{{\cal B}\setminus{\cal C}}(\rho_{{\cal B}})=\mbox{tr}_{{\cal
C}\setminus{\cal B}}(\rho_{{\cal C}}),$ (28)

for all finite ${\cal B},{\cal C}\subset{\cal A}$.

We say that $\rho$ is a _quantum state_ for system ${\cal A}$.

For finite ${\cal A}$, this definition coincides with the standard definition
of a quantum state. For infinite alphabets, though, we regard a quantum state
as an infinite set of reduced density matrices, each acting on finitely many
systems. One can construct an analogous definition for classical probability
distributions, by replacing positive semidefinite matrices with classical
measures and partial traces with integrals over finite sets of random
variables.

The definition of separability in infinite dimensional systems follows similar
lines.

######  Definition 11.

Separable quantum states

Let ${\cal A}$ be a countable alphabet, and let $\rho$ be a state of ${\cal
A}$. If, for all finite subsets ${\cal B}\subset{\cal A}$, $\rho_{{\cal B}}$
is a separable state, then we say that $\rho$ is separable.

Using a Cantor-like argument, one can see that $\rho$ is a separable state iff
there exists a distribution $p$ such that, for all finite ${\cal
B}\subset{\cal A}$,

$\rho_{{\cal B}}=\int d\phi_{{\cal B}}p_{{\cal B}}(\phi_{{\cal
B}})\bigotimes_{\beta\in{\cal B}}|\phi_{\beta}\rangle\\!\langle\phi_{\beta}|.$
(29)

This is evident if ${\cal A}$ is finite. To construct such a distribution in
the $|{\cal A}|=\infty$ case (more specifically: a function $p$ mapping any
finite subset ${\cal B}\subset{\cal A}$ into a distribution $p_{{\cal
B}}(\phi_{{\cal B}})$ such that eq. (29) holds and such that, for any finite
${\cal B},{\cal C}\subset{\cal A}$, $p_{\cal B},p_{\cal C}$ are locally
compatible), we start from the premise that all states $\rho_{{\cal B}}$ are
separable. Consequently, for all finite ${\cal B}\subset{\cal A}$, there exist
(not necessarily locally compatible) distributions $\tilde{p}_{\cal B}$
satisfying

$\rho_{{\cal B}}=\int d\phi_{{\cal B}}\tilde{p}_{{\cal B}}(\phi_{{\cal
B}})\bigotimes_{\beta\in{\cal B}}|\phi_{\beta}\rangle\\!\langle\phi_{\beta}|.$
(30)

Next we consider an increasing sequence $({\cal B}^{i})_{i}$ of finite subsets
of ${\cal A}$ such that $\cup_{i}{\cal B}^{i}={\cal A}$, as well as the
sequence of distributions $\tilde{p}_{i}=\tilde{p}_{{\cal B}_{i}}$, and
partition the measure space of the variables $\phi_{{\cal B}_{i}}$ into a
finite set of measurable subsets ${\cal F}_{i}$, with ${\cal F}_{i}={\cal
F}_{i-1}\times{\cal F}^{\prime}_{i}$. By the Bolzano-Weierstrass theorem,
there exists a subsequence $(s^{1}_{j})_{j}$ of $(i)_{i}$ such that the limit

$p_{{\cal B}_{1}}(\Phi):=\lim_{j\to\infty}\int_{\Phi}d_{\phi_{{\cal
B}_{1}}}\int d\phi_{{\cal B}_{s^{1}_{j}}\setminus{\cal
B}_{1}}\tilde{p}_{s^{1}_{j}}(\phi_{{\cal B}_{s^{1}_{j}}})$ (31)

exists, for all $\Phi\in{\cal F}_{1}$. Now, starting from the sequence
$(s^{1}_{j})_{j}$, we invoke the Bolzano-Weierstrass theorem again to show
that there exists a subsequence $(s^{2}_{j})_{j}$ of $(s^{1}_{j})_{j}$ with
the property that

$\displaystyle p_{{\cal
B}_{2}}(\Phi)=\lim_{j\to\infty}\int_{\Phi_{1}\times\Phi^{\prime}_{2}}d_{\phi_{{\cal
B}_{2}}}\int d\phi_{{\cal B}_{s^{2}_{j}}\setminus{\cal
B}_{2}}\tilde{p}_{s^{2}_{j}}(\phi_{{\cal B}_{s^{2}_{j}}})$
$\displaystyle=:p_{{\cal B}_{2}}(\Phi_{1}\times\Phi_{2}^{\prime})$ (32)

exists for all $\Phi_{1}\times\Phi_{2}^{\prime}\in{\cal F}_{2}$. Moreover,
since $(s^{2}_{j})_{j}$ is a subsequence of $(s^{1}_{j})_{j}$, we have that

$\sum_{\Phi_{2}^{\prime}}p_{{\cal
B}_{2}}(\Phi_{1}\times\Phi_{2}^{\prime})=p_{{\cal B}_{1}}(\Phi_{1}).$ (33)

That is, within the coarse-graining given by ${\cal F}^{2}$, the distributions
$p_{{\cal B}_{1}}$ and $p_{{\cal B}_{2}}$ so defined are locally compatible.

Iterating this argument, we arrive at a sequence of nested subsequences with
the property that, for the $k^{th}$ subsequence $(s^{k}_{j})_{j}$, the limit

$\lim_{j\to\infty}\int_{\Phi}d\phi_{{\cal B}_{k}}\int_{{\cal
B}_{s^{k}_{j}}\setminus{\cal B}_{k}}\tilde{p}_{{\cal
B}_{s^{k}_{j}}}(\phi_{{\cal B}_{s^{k}_{j}}})=:p_{{\cal B}_{k}}(\Phi)$ (34)

exists for all $\Phi\in{\cal F}_{k}$, and all so-generated coarse-grained
probability distributions $\\{p_{{\cal B}_{k}}(\Phi):\Phi\in{\cal F}_{k}$ are
locally compatible. Moreover, if we consider the sequence
$(s_{j})_{j}\equiv(s^{j}_{j})_{j}$, we have that, for all $k$,

$\lim_{j\to\infty}\int_{\Phi}d\phi_{{\cal B}_{k}}\int_{{\cal
B}_{s_{j}}\setminus{\cal B}_{k}}\tilde{p}_{{\cal B}_{s_{j}}}(\phi_{{\cal
B}_{s_{j}}})=p_{{\cal B}_{k}}(\Phi).$ (35)

Within the coarse-grainings ${\cal F}^{k}$, we hence arrive at a global
definition of $p$. To arrive at a more fine-grained description of $p$, we
consider sub-partitions $\bar{{\cal F}}_{k}$ of ${\cal F}_{k}$ such that
$\bar{{\cal F}}_{k}=\hat{{\cal F}}_{k-1}\times\hat{{\cal F}}_{k}^{\prime}$ and
apply the same argument as before over the sequence $(s_{j})_{j}$. Iterating
the argument over and over, we find that there exists a sequence
$(\hat{s}_{j})_{j}$ such that

$\lim_{j\to\infty}\int_{\Phi}d\phi_{{\cal B}_{k}}\int_{{\cal
B}_{\hat{s}_{j}}\setminus{\cal B}_{k}}\tilde{p}_{{\cal
B}_{\hat{s}_{j}}}(\phi_{{\cal B}_{\hat{s}_{j}}})=:p_{{\cal B}_{k}}(\Phi)$ (36)

exists for any measurable set $\Phi$. $(p_{{\cal B}_{j}})_{j}$ are, by
construction, locally compatible. Moreover, since $(\tilde{p}_{{\cal
B}_{j}})_{j}$ satisfy eq. (30), it follows that $p$ satisfies (29).

##  Appendix B A simplified hierarchy for the entanglement marginal problem

Suppose that there exists a subset ${\cal I}_{+}$ of ${\cal I}$ such that any
$I\in{\cal I}_{+}$ contains a letter $\alpha_{I}$ that is not present in any
other set $J\in{\cal I}$. Define $\bar{I}$ as $I\setminus\\{\alpha_{I}\\}$ for
$I\in{\cal I}_{+}$ or $I$, otherwise, and, for any $I\not\in{\cal I}_{+}$, let
$\alpha_{I}\not\in{\cal A}$ denote a 1-dimensional Hilbert space. This
notation will become clear below.

Let $\\{\rho_{I}\\}_{I}$ admit a separable extension generated by the measure
$p(\phi)$, and define the states

$\bar{\rho}^{({L})}_{I}\equiv\int
p_{I}(\phi_{I})d\phi_{I}\bigotimes_{\alpha\in\bar{I}}|\phi_{\alpha}\rangle\\!\langle\phi_{\alpha}|^{\otimes{L}}\otimes|\phi_{\alpha_{I}}\rangle\\!\langle\phi_{\alpha_{I}}|.$
(37)

Note that whenever $I\not\in{\cal I}_{+}$, the last element $\alpha_{I}$ in
the previous equation corresponds to a one-dimensional Hilbert space and can
in practice be removed. It is however convenient to write it to have a unified
notation for the two cases $I\in{\cal I}_{+}$ and $I\not\in{\cal I}_{+}$. Then
the states $\\{\bar{\rho}^{({L})}_{I}\\}$ satisfy the conditions

  1. (i)

$\mbox{tr}_{\bar{I}^{{L}-1}}(\bar{\rho}^{({L})}_{I})=\rho_{I}$.

  2. (ii)

$\bar{\rho}^{({L})}_{I}$ is Positive under Partial Transposition (PPT) across
all bipartitions.

  3. (iii)

$\bar{\rho}^{({L})}_{I}\in B(\bigotimes_{\alpha\in\bar{I}}{\cal
H}_{\text{sym}}({L},d_{\alpha})\otimes{\cal H}_{\alpha_{I}})$.

  4. (iv)

$\mbox{tr}_{(I\setminus
J)^{L},\alpha_{I}}(\bar{\rho}^{({L})}_{I})=\mbox{tr}_{(J\setminus
I)^{L},\alpha_{J}}(\bar{\rho}^{({L})}_{J})$ (after appropriately reordering
the systems of one of the sides).

As in the definition of $\mathbb{H}$, we relax the property that
$\\{\rho_{I}\\}_{I}$ admit a separable extension by demanding that there exist
positive semidefinite matrices $\\{\bar{\rho}^{({L})}_{I}\\}_{I}$ satisfying
conditions (i)-(iv). The resulting SDP hierarchy $\bar{\mathbb{H}}({\cal
I}|\\{\rho_{I}\\}_{I})$ is weaker than $\mathbb{H}({\cal
I}|\\{\rho_{I}\\}_{I})$, in the sense that
$\\{\rho_{I}\\}_{I}\in\mathbb{H}^{L}$ implies
$\\{\rho_{I}\\}_{I}\in\bar{\mathbb{H}}^{L}$. However, for some configurations
of ${\cal I}$, verifying that $\\{\rho_{I}\\}_{I}\in\bar{\mathbb{H}}^{L}({\cal
I})$ requires considerably less computational resources. This is because, as
said, the index $\alpha_{I}$ is not extended in this hierarchy.

##  Appendix C From matrix variables to separable states and probability
distributions

In this Appendix, we prove Proposition 4. We also show that linear relations
over the matrix variables in the hierarchy $\mathbb{H}$ described in the main
text are inherited by the measure generating the separable approximation to
$\\{\rho_{I}\\}_{I}$. For simplicity, we first prove that Proposition 4 holds
for any ensemble $\\{\rho_{I}\\}_{I}\in\mathbb{H}^{L}$. The extension to the
weaker condition $\\{\rho_{I}\\}_{I}\in\bar{\mathbb{H}}^{L}$, defined in
Appendix B, will follow easily.

To analyze the speed of convergence of the DPS hierarchy [3, 14, 15], one of
us introduced in [17] a family of linear maps $\Omega^{d,{L}}_{\phi}:B({\cal
H}_{\text{sym}}^{{L},d})\to B({\mathbb{C}}^{d})$ with the property that, for
all Hilbert spaces ${\cal H}$ and all states $\omega_{1^{L}A}\in B({\cal
H}_{\text{sym}}({L},d)\otimes{\cal H})$ positive semidefinite under the
transposition of $\lfloor\frac{{L}}{2}\rfloor$ of the ${L}$ symmetric systems,
the following inequality holds:

$(\Omega^{d,{L}}_{\phi}\otimes{\mathbb{I}}_{B({\cal
H})})(\omega_{1^{L}A})=|\phi\rangle\\!\langle\phi|_{1}\otimes(\omega_{\phi})_{A}\geq
0.$ (38)

Furthermore, the map $\Omega^{d,{L}}\equiv\int d\phi\Omega^{d,{L}}_{\phi}$
satisfies

$\displaystyle(\Omega^{d,{L}}\otimes{\mathbb{I}}_{B({\cal
H})})(\omega_{1^{L}A})=$ $\displaystyle(1-\epsilon(L,d))\omega_{1^{L}A}+$
$\displaystyle\epsilon(L,d)\frac{{\mathbb{I}}_{1}}{d}\otimes\omega_{A},$ (39)

with $\epsilon(L,d)$ defined as in (11).

Now, suppose that the ensemble $\\{\rho_{I}\\}_{I}$ admits extensions
$\\{\rho_{I}^{({L})}\\}$ satisfying the conditions (i)-(iv) in the main text.
We simultaneously apply the maps $\int d\phi\Omega^{d_{\alpha},{L}}_{\phi}$,
for $\alpha\in{\cal A}$, to each of the states $\\{\rho_{I}^{({L})}\\}$. This
results in the states $\tilde{\rho}_{I}=\int
d\phi_{I}\tilde{p}(\phi_{I})\bigotimes_{\alpha\in
I}|\phi_{\alpha}\rangle\\!\langle\phi_{\alpha}|$, with
$\tilde{p}(\phi_{I})=\mbox{tr}(\bigotimes_{\alpha\in
I}\Omega^{d_{\alpha},{L}}_{\phi_{i}}\rho_{I}^{({L})})$. Note that, if
$\\{\rho^{({L})}_{I}\\}_{I}$ satisfies linear constraints of the form

$\sum_{I\in{\cal I},J\subset I}c_{IJ}\mbox{tr}_{(I/J)^{L}}\rho^{({L})}_{I}=0,$
(40)

such as local compatibility, or relations (21), (25), then so will the
ensemble of measures $\\{\tilde{p}_{I}\\}_{I}$. Finally, due to eq. (39),

$\displaystyle\tilde{\rho}_{I}=\prod_{\alpha\in
I}(1-\epsilon(d_{\alpha},L))\rho_{I}+$ $\displaystyle\left(1-\prod_{\alpha\in
I}(1-\epsilon(d_{\alpha},L))\right)\sigma_{I},$ (41)

for some normalized state $\sigma_{I}$. Subtracting $\rho_{I}$ and invoking
the triangle inequality, we arrive at equation (10) in Proposition 4.

To see that Proposition 4 also applies to the simplified hierarchy
$\bar{\mathbb{H}}$ with no linear constraints on $\\{\rho_{I}^{({L})}\\}_{I}$
besides local compatibility, just apply to each variable
$\bar{\rho}^{({L})}_{I}$ the maps $\int d\phi\Omega^{d_{\alpha},{L}}_{\phi}$,
for $\alpha\in\bar{I}$. The result will be a separable state of the form

$\tilde{\rho}_{I}=\int
p_{\bar{I}}(\phi_{\bar{I}})\left(\bigotimes_{\alpha\in\bar{I}}|\phi_{\alpha}\rangle\\!\langle\phi_{\alpha}|\right)\otimes\sigma(\phi_{\bar{I}}),$
(42)

where $\sigma(\phi_{\bar{I}})$ is the state of system $\alpha_{I}$ after we
subject systems in $\bar{I}$ to the map
$\bigotimes_{\alpha\in\bar{I}}\Omega^{d_{\alpha},{L}}_{\phi_{\alpha}}$.
Writing

$\sigma(\phi_{\bar{I}})=\int
d\phi_{\alpha_{I}}\tilde{p}(\phi_{\alpha_{I}}|\phi_{\bar{I}})|\phi_{\alpha_{I}}\rangle\\!\langle\phi_{\alpha_{I}}|,$
(43)

we find that the separable state $\tilde{\rho}_{I}$ is generated by the
distribution
$\tilde{p}(\phi_{I})\equiv\tilde{p}_{\bar{I}}(\phi_{\bar{I}})\tilde{p}(\phi_{\alpha_{I}}|\phi_{\bar{I}})$,
with

$\tilde{p}_{\bar{I}}(\phi_{\bar{I}})=\mbox{tr}\left(\bigotimes_{\alpha\in\bar{I}}\Omega^{d_{\alpha},{L}}_{\phi_{\alpha}}(\bar{\rho}^{({L})})\right).$
(44)

Since, by assumption, system $\alpha_{I}$ does not belong to any other
$J\in{\cal I},J\not=I$, local compatibility of
$\\{\bar{\rho}^{({L})}_{I}\\}_{I}$ implies local compatibility of the
distributions $\\{\tilde{p}_{I}\\}_{I}$.

##  Appendix D Global compatibility for chordal graphs

The purpose of this section is to prove that, if the dependency graph ${\cal
G}$ of ${\cal I}$ is chordal and the elements of ${\cal I}$ correspond to its
maximal cliques, then local compatibility of distributions
$\\{p_{I}(\phi_{I})\\}_{I\in{\cal I}}$ implies global compatibility.

It is a standard result in combinatorics [39] that the maximal cliques of a
chordal graph can be ordered as $I_{1},...,I_{m}$ in such a way that, for all
$j\in\\{1,...,m-1\\}$,

$I_{j+1}\cap\left(\bigcup_{k=1}^{j}I_{k}\right)\subset I_{s},$ (45)

for some $s\leq j$. This condition is known as the _running intersection
property_.

We next prove that the running intersection property, together with local
compatibility, implies the existence of a global distribution $p(\phi)$. Call
$V,\Lambda$ the union and intersection of the sets $I_{1},I_{2}$,
respectively. Note that, given the sets $\\{p_{I}(\phi^{I})\\}_{I}$,
$p(\phi_{\Lambda})$ is well defined by local compatibility. Now, define
$p_{V}(\phi_{V}):=p(\phi_{I_{1}})p(\phi_{I_{2}})/p(\phi_{\Lambda})$.
Summing/integrating over the variables $\phi_{i}$, with $i\in
I_{2}\setminus\Lambda$, we obtain $p(\phi_{I_{1}})$. Similarly,
summing/integrating over $\phi_{i}$, with $i\in I_{1}\setminus\Lambda$, we
obtain $p_{I_{2}}(\phi_{I_{2}})$. Hence $p_{V}$ admits $p_{I_{1}},p_{I_{2}}$
as marginals. Furthermore, consider any set $I_{j}$, with $j>2$. By the
running intersection property, either $I_{j}\cap V\subset I_{1}$ or $I_{j}\cap
V\subset I_{2}$, and so $p_{I_{j}\cap V}(\phi_{I_{j}\cap V})$ is well defined.
It thus follows that the sets of indices $\\{V\\}\cup\\{I_{j}\\}_{j=2}^{m}$
and the distributions $\\{p_{V}\\}\cup\\{p_{I_{j}}\\}_{j=3}^{m}$ satisfy,
respectively, the running intersection property and local compatibility.
Iterating this procedure $m-2$ times, we arrive at a global probability
distribution.

We next illustrate the construction of the overall distribution with an
example. Think of the open spin chain discussed in Section 5.2, where ${\cal
I}=\\{I_{j}:j=1,...,n-1\\}$, with $I_{j}=\\{j,j+1\\}$. It can be verified that
the sequence of sets $(I_{j})_{j}$ satisfies the running intersection property
(45). Now, let $\\{p_{\\{j,j+1\\}}(\phi_{j},\phi_{j+1})\\}_{j=1}^{n-1}$ be a
set of locally compatible distributions. Following the procedure sketched
above, a global distribution for the variables at sites $1,2,3$ is given by

$p_{\\{1,2,3\\}}(\phi_{1},\phi_{2},\phi_{3})=\frac{p_{\\{1,2\\}}(\phi_{1},\phi_{2})p_{\\{2,3\\}}(\phi_{2},\phi_{3})}{p_{2}(\phi_{2})},$
(46)

where

$\displaystyle p_{2}(\phi_{2}):=$ $\displaystyle\int
d\phi_{1}p_{\\{1,2\\}}(\phi_{1},\phi_{2})=$ $\displaystyle\int
d\phi_{3}p_{\\{2,3\\}}(\phi_{2},\phi_{3}).$ (47)

Note that the last relation holds by local compatibility.

To see why (46) is an extension of $p_{\\{1,2\\}},p_{\\{2,3\\}}$, integrate
$\phi_{1}$ in both sides of (46). We find, by (47), that

$\int
d\phi_{1}p_{\\{1,2,3\\}}(\phi_{1},\phi_{2},\phi_{3})=p_{\\{2,3\\}}(\phi_{2},\phi_{3}).$
(48)

Similarly, integrating $\phi_{3}$ we arrive at

$\int
d\phi_{3}p_{\\{1,2,3\\}}(\phi_{1},\phi_{2},\phi_{3})=p_{\\{1,2\\}}(\phi_{1},\phi_{2}).$
(49)

By increasing the number of variables of the overall probability distribution
in this fashion, we find that

$p(\phi):=p_{\\{1,2\\}}(\phi_{1},\phi_{2})\prod_{j=2}^{n-1}\frac{p_{\\{j,j+1\\}}(\phi_{j},\phi_{j+1})}{p_{j}(\phi_{j})}$
(50)

is an extension of the ensemble $\\{p_{\\{j,j+1\\}}:j=1,...,n-1\\}$.