Connecting the marginal problem with the separability problem

The formal definition of the marginal problem is the following: Consider an n-particle Hilbert space $$ \mathcal{H}={⨂}_{i=1}^n{\mathcal{H}}_i$$, and let $$ \mathcal{I}\subset \left\{I\mid I\subset \left[n\right]=\left\{1,2,\dots ,n\right\}\right\}$$ be some subsets of the particles, where the reduced states ρ_I are known marginals. Then, the problem reads

Here, I^c = [n]⧹I denotes the complement of the set I. Before explaining our approach, two facts are worth mentioning: First, if the global state $$ ∣\phi ⟩⟨\phi ∣$$ is not required to be pure, then the quantum marginal problem without purity constraint is already an SDP. Second, if the given marginals are only one-body marginals, that is $$ \mathcal{I}=\left\{\left\{i\right\}\mid i\in \left[n\right]\right\}$$, the marginals are non-overlapping and the problem in Eq. (1) was solved by Klyachko³¹. For overlapping marginals, however, the solution is more complicated, and this is what we want to discuss in this work.

The main idea of our method is to consider, for a given set of marginals, the compatible states and their extensions to two copies. Then, we can formulate the purity constraint using an SDP. First, let us introduce some notation. Let $$ \mathcal{C}$$ be the set of global states (not necessarily pure) that are compatible with the marginals, i.e.,

Then, we define $$ {\mathcal{C}}_2$$ to be the convex hull of two copies of the compatible stateswhere the p_μ form a probability distribution. We denote the two parties as A and B, and each of them owns an n-body quantum system (see Fig. 1).

To impose the purity constraint, we take advantage of the well-known relation³²

where ρ_A and ρ_B are arbitrary quantum states, and V_AB is the swap operator between parties A and B, i.e.,which acts on a state $$ {\mathrm{\Phi }}_{AB}={\sum }_{i,j}{\omega }_{ijkl}∣i,j⟩⟨k,l∣$$ as $$ V_{AB}{\mathrm{\Phi }}_{AB}={\sum }_{i,j}{\omega }_{ijkl}∣j,i⟩⟨k,l∣$$. For a state Φ_AB in $$ {\mathcal{C}}_2$$ this implies thatFurthermore, equality in Eq. (6) is attained if and only if all ρ_μ are pure states. This leads to our first key observation: there exists a pure state in $$ \mathcal{C}$$ if and only if $$ {\max }_{{\mathrm{\Phi }}_{AB}\in {\mathcal{C}}_2}\mathrm{Tr}\left(V_{AB}{\mathrm{\Phi }}_{AB}\right)=1$$.

What remains to be done is the characterization of the set $$ {\mathcal{C}}_2$$, then we can formulate the quantum marginal problem as an optimization problem over this set. This can be done by taking advantage of the separability property³² of the states in $$ {\mathcal{C}}_2$$ with respect to the bipartition (A∣B).

Theorem 1 There exists a pure quantum state $$ ∣\phi ⟩$$ that satisfies $$ {\mathrm{Tr}}_{I^c}\left(∣\phi ⟩⟨\phi ∣\right)={\rho }_I$$ for all $$ I\in \mathcal{I}$$ if, and only if, the solution of the following convex optimization is equal to one,

where SEP denotes the set of separable states w.r.t. the bipartition (A∣B), $$ A_{I^c}$$ denotes all subsystems A_i for i ∈ I^c, and similarly for $$ B_{I^c}$$.

Proof On the one hand, if there exists a pure state $$ ∣\phi ⟩⟨\phi ∣\in \mathcal{C}$$, one can easily verify that $$ {\mathrm{\Phi }}_{AB}=∣\phi ⟩⟨\phi ∣\otimes ∣\phi ⟩⟨\phi ∣$$ satisfies the constraints in Eqs. (8) and (9) as well as $$ \mathrm{Tr}\left(V_{AB}{\mathrm{\Phi }}_{AB}\right)=1$$.

On the other hand, if the solution of Eq. (7) is equal to one, then the separability constraint and Eq. (6) imply that Φ_AB must be of the form³³

Writing $$ {\mathrm{Tr}}_{I^c}\left(\mid {\psi }_{\mu }⟩⟨{\psi }_{\mu }\mid \right)={\sigma }_I^{\left(\mu \right)}$$, the constraint in Eq. (9) implies thatWithout loss of generality, we assume that all p_μ are strictly positive and we want to show that all $$ {\sigma }_I^{\left(\mu \right)}={\rho }_I$$, which will imply that each $$ \mid {\psi }_{\mu }⟩$$ is a pure state with the desired marginals. Let X be any Hermitian matrix such that $$ \mathrm{Tr}\left(X{\rho }_I\right)=0$$, then Eq. (11) and the relation $$ \mathrm{Tr}\left[\left(X\otimes X\right)\left(\sigma \otimes \sigma \right)\right]={\left[\mathrm{Tr}\left(X\sigma \right)\right]}^2$$ imply thatBy noting that $$ \mathrm{Tr}\left(X{\sigma }_I^{\left(\mu \right)}\right)$$ are real numbers, we get that $$ \mathrm{Tr}\left(X{\sigma }_I^{\left(\mu \right)}\right)=0$$, for all μ and all X such that $$ \mathrm{Tr}\left(X{\rho }_I\right)=0$$. Thus, all $$ {\sigma }_I^{\left(\mu \right)}$$ are proportional to ρ_I and, together with $$ \mathrm{Tr}\left({\rho }_I\right)=\mathrm{Tr}\left({\sigma }_I^{\left(\mu \right)}\right)=1$$, this implies that $$ {\sigma }_I^{\left(\mu \right)}={\rho }_I$$ for all μ.

Before proceeding further, we would like to add a few remarks. First, in Theorem 1 the constraint in Eq. (9) can be replaced by a stronger condition

This is because for any (not necessarily separable) quantum state Φ_AB satisfying $$ \mathrm{Tr}\left(V_{AB}{\mathrm{\Phi }}_{AB}\right)=1$$, Eq. (13) implies the validity of Eq. (9). Hence, this replacement will lead to an equivalent result as in Theorem 1. However, when considering relaxations of the optimization in Eq. (7) by replacing the separability constraint in Eq. (8) with some entanglement criteria, Eq. (13) may be strictly stronger for certain marginal problems.

Second, if one finds that $$ \mathrm{Tr}\left(V_{AB}{\mathrm{\Phi }}_{AB}\right)=1$$, this is equivalent to V_ABΦ_AB = Φ_AB, as the largest eigenvalue of V_AB is one. Physically, this means that Φ_AB is a two-party state acting on the symmetric subspace only. Hence, Theorem 1 is also equivalent to the feasibility problem

Furthermore, any feasible state Φ_AB can be used for constructing the global state $$ ∣\phi ⟩$$ with the desired marginals, as the proof of Theorem 1 implies any pure state in the separable decomposition of Φ_AB can give a desired global state.

Third, the separability condition in the optimization Eq. (8) is usually not easy to characterize, hence relaxations of the problem need to be considered. The first candidate is the positive partial transpose (PPT) criterion^34,35, which is an SDP relaxation of the optimization in Eq. (7). The PPT relaxation provides a pretty good approximation when the local dimension and the number of parties are small. In the following, inspired by the symmetric extension criterion³⁶, we propose a multi-party extension method and obtain a complete hierarchy for the marginal problem.

The hierarchy for the marginal problem

In order to generalize Theorem 1, we first need to extend $$ {\mathcal{C}}_2$$ in Eq. (3) from two to an arbitrary number of copies of ρ. That is, we define $$ {\mathcal{C}}_N=\mathrm{conv}\left\{{\rho }^{\otimes N}\mid \rho \in \mathcal{C}\right\}$$. Second, we introduce the notion of the symmetric subspace. We denote the N parties as A, B, …, Z, and each of them owns an n-body quantum system. For any $$ {\mathcal{H}}^{\otimes N}:={\mathcal{H}}_A\otimes {\mathcal{H}}_B\otimes \cdots \otimes {\mathcal{H}}_Z$$, the symmetric subspace is defined as

where S_N is the permutation group over N symbols and V_Σ are the corresponding operators on the N parties A, B, …, Z (see Fig. 2). Let $$ P_N^{+}$$ denote the orthogonal projector onto the symmetric subspace of $$ {\mathcal{H}}^{\otimes N}$$. $$ P_N^{+}$$ can be explicitly written asIn particular, for two parties we have the well-known relation $$ P_2^{+}=\left({\mathbb{1}}_{AB}+V_{AB}\right)/2$$, which implies that $$ \mathrm{Tr}\left(V_{AB}{\mathrm{\Phi }}_{AB}\right)=1$$ if and only if $$ \mathrm{Tr}\left(P_2^{+}{\mathrm{\Phi }}_{AB}\right)=1$$. Also, V_ABΦ_AB = Φ_AB is equivalent to $$ P_2^{+}{\mathrm{\Phi }}_{AB}{P}_2^{+}={\mathrm{\Phi }}_{AB}$$. Hereafter, without ambiguity, we will use $$ P_N^{+}$$ to denote both the symmetric subspace and the corresponding orthogonal projector.

Suppose that there exists a pure state $$ \rho \in \mathcal{C}$$. It is easy to see that Φ_AB⋯Z = ρ^⊗N satisfies

Here, the separability can be understood as either full separability or biseparability, since they are equivalent in the symmetric subspace³³. Relaxing Φ_AB⋯Z ∈ SEP, we obtain a complete hierarchy for the quantum marginal problem:

Theorem 2 There exists a pure quantum state $$ ∣\phi ⟩$$ that satisfies $$ {\mathrm{Tr}}_{I^c}\left(∣\phi ⟩⟨\phi ∣\right)={\rho }_I$$ for all $$ I\in \mathcal{I}$$ if and only if for all N ≥ 2 there exists an N-party quantum state Φ_AB⋯Z such that

Each step of this hierarchy is a semidefinite feasibility problem, and the conditions become more restrictive if N increases.

The proof of Theorem 2 is shown in the “Methods” section. Notably, we can add any criterion of full separability, e.g., the PPT criterion for all bipartitions, as extra constraints to the feasibility problem. Then, Theorem 2 still provides a complete hierarchy for the quantum marginal problem. In addition, the quantum marginal problems of practical interest are usually highly symmetric. These symmetries can be utilized to largely simplify the problems in Theorems 1 and 2. Indeed, taking advantage of symmetries is usually necessary for practical applications, because the general quantum marginal problem is QMA-complete^37,38. Notably, even for non-overlapping marginals, despite recent progress in refs. ^39–41, it is still an open problem whether there exists a polynomial-time algorithm. In the following, we illustrate how symmetry can drastically simplify quantum marginal problems with the existence problem of AME states.

Absolutely maximally entangled states

We first recall the definition of AME states. An n-qudit state $$ ∣\psi ⟩$$ is called an AME state, denoted as AME(n, d), if it satisfies

where $$ {\mathcal{I}}_r=\left\{I\subset \left[n\right]\mid ∣I∣=r\right\}$$ and r = ⌊n/2⌋. Thus, Eq. (14) implies that an AME(n, d) exists if and only if the following problem is feasible,Direct evaluation of the problem is usually difficult, because the dimension of Φ_AB is d²ⁿ × d²ⁿ, which is already very large for the simplest cases. For instance, for the 4-qubit case, the size of Φ_AB is 256 × 256.

To resolve this size issue, we investigate the symmetries that can be used to simplify the feasibility problem. Let $$ \mathcal{X}$$ denotes the set of Φ_AB that satisfies the constraints in Eqs. (26), (27), and (28). If we find a unitary group G such that for all g ∈ G and $$ {\mathrm{\Phi }}_{AB}\in \mathcal{X}$$ we have that

Then, the convexity of $$ \mathcal{X}$$ implies that we can add a symmetry constraint to the constraints in Eqs. (26), (27), and (28), namely,

In the following, we will show that the symmetries of the set of AME states (if they exist for given n and d) are restrictive enough to leave only a single unique candidate for Φ_AB, for which separability needs to be checked. The set of AME(n, d) is invariant under local unitaries and permutations on the n particles, so by Theorem 1 (or by direct verification) the following two classes of unitaries satisfy Eq. (29),

where π = π(A₁, A₂, …, A_n) = π(B₁, B₂, …, B_n) denotes the permutation operators on $$ {\mathcal{H}}_A$$ and $$ {\mathcal{H}}_B$$. Note that the U_i in Eq. (31) can be different.

First, let us view V_AB and Φ_AB as V_12…n and Φ_12…n, where i labels the subsystems A_iB_i. Hereafter, without ambiguity, we will omit the subscripts of

for simplicity. From this perspective, V_AB can be written as V^⊗n, and the symmetries in Eqs. (31) and (32) can be written as $$ {⨂}_{i=1}^n\left(U_i\otimes U_i\right)$$ for U_i ∈ SU(d) and Π = Π(A₁B₁, A₂B₂, …, A_nB_n) for Π ∈ S_n, respectively. According to Werner’s result³², a (U ⊗ U)-invariant Hermitian operator must be of the form $$ \alpha \mathbb{1}+\beta V$$ with $$ \alpha ,\beta \in \mathbb{R}$$. This implies that a $$ \left[{⨂}_{i=1}^n\left(U_i\otimes U_i\right)\right]$$-invariant state must be a linear combination of operators of the formIn addition, we take advantage of the permutation symmetry under Π ∈ S_n to write any invariant Φ_AB aswhere $$ \mathcal{P}$$ represents the sum over all possible permutations that give different terms, e.g., $$ \mathcal{P}\left\{V\otimes \mathbb{1}\otimes \mathbb{1}\right\}=V\otimes \mathbb{1}\otimes \mathbb{1}+\mathbb{1}\otimes V\otimes \mathbb{1}+\mathbb{1}\otimes \mathbb{1}\otimes V$$.

Inserting this ansatz in Eqs. (27) and (28) one can show by brute force calculation that the x_i are uniquely determined and given by

where we use the convention that $$ \left(\genfrac{}{}{0ex}{}{i}{j}\right)=0$$ when j < 0 or j > i; see Supplementary Note 1 for details. This means that the two-party extension under the symmetries is independent of the specific AME state, which is an interesting structural result considering that there exist even infinite families of AME(n, d) states that are not SLOCC equivalent⁴². Together with Theorem 1, this result implies that an AME state exists if and only if Φ_AB is a separable quantum state.

Theorem 3 An AME(n, d) state exists if and only if the operator Φ_AB defined by Eqs. (35) and (36) is a separable state w.r.t. the bipartition (A∣B) = (A₁A₂…A_n∣B₁B₂…B_n).

To check the separability of Φ_AB, we first consider the positivity condition and the PPT condition. It is easy to see that Φ_AB can be written as

and $$ {\mathrm{\Phi }}_{AB}^{T_B}$$ can be written aswherewith $$ ∣{\varphi }^{+}⟩=\frac{1}{\sqrt{d}}{\sum }_{k=1}^d∣k⟩∣k⟩$$. Here p_i and q_i are the eigenvalues of Φ_AB and $$ {\mathrm{\Phi }}_{AB}^{T_B}$$, respectively. Then, we can simplify the positivity condition Φ_AB ≥ 0 and the PPT condition $$ {\mathrm{\Phi }}_{AB}^{T_B}\ge 0$$ tofor all i = 0, 1, 2, …, n. Note that the latter inequality is trivial for i ≤ r.

The explicit form of p_i and q_i and the proof of the conditions in Eqs. (40) and (41) are shown in Supplementary Note 2. The positivity and PPT conditions can already rule out the existence of many AME states. Actually, they can reproduce all the known nonexistence results³⁰ except AME(7, 2)²⁰. To get a higher-order approximation, we provide a general framework for performing the symmetric extension in Supplementary Notes 3 and 4.

As the open problem of the existence of AME(4, 6) is of particular interest in the quantum information community^28,43, we explicitly express it as the following corollary.

Corollary 1 An AME(4, 6) state exists if and only if the quantum state

is separable, or equivalently,is separable w.r.t. bipartition (A∣B).

At the moment, we are unable to decide separability of these states; in Supplementary Note 5 we provide a short discussion of this problem.

Quantum codes

As another application, we show that our method can also be used to analyze the existence of quantum error-correcting codes. For simplicity, we only consider pure quantum codes⁴⁴ in the text; see “Methods” for the general case. Our starting point is the fact that pure quantum codes are closely related to m-uniform states¹⁸. More precisely, an ((n, K, m+1))_d pure code exists if and only if there exists a K-dimensional subspace $$ \mathcal{Q}$$ of $$ \mathcal{H}={⨂}_{i=1}^n{\mathcal{H}}_i={\left({\mathbb{C}}^d\right)}^{\otimes n}$$ such that all states in $$ \mathcal{Q}$$ are m-uniform, i.e., for all $$ ∣\phi ⟩\in \mathcal{Q}$$

where $$ {\mathcal{I}}_m=\left\{I\in \left[n\right]\mid ∣I∣=m\right\}$$ and I^c = [n]⧹I. The existence of ((n, 1, m+1))_d pure codes reduces to the existence of m-uniform states, for which the methods from the last section are directly applicable. Here, we show that the existence of ((n, K, m+1))_d pure codes can still be written as a marginal problem if K > 1. To do so, we define an auxiliary system $$ {\mathcal{H}}_0={\mathbb{C}}^K$$ and let $$ \tilde{\mathcal{H}}={\mathcal{H}}_0\otimes \mathcal{H}={⨂}_{i=0}^n{\mathcal{H}}_i={\mathbb{C}}^K\otimes {\left({\mathbb{C}}^d\right)}^{\otimes n}$$. Now, we can write the existence of ((n, K, m+1))_d pure codes as a marginal problem on $$ \tilde{\mathcal{H}}$$.

Lemma 1 A quantum ((n, K, m+1))_d pure code exists if and only if there exists a quantum state $$ ∣Q⟩$$ in $$ \tilde{\mathcal{H}}$$ such that

where I^c is still defined as {1, 2, …, n}⧹I.

Proof We first show the necessity part. Suppose that a ((n, K, m+1))_d code with corresponding subspace $$ \mathcal{Q}$$ exists. We define an entangled state $$ ∣Q⟩$$ in $$ {\mathcal{H}}_0\otimes \mathcal{Q}\subset \tilde{\mathcal{H}}$$ as

where $$ {\left\{∣k⟩\right\}}_{k=1}^K$$ and $$ {\left\{∣k_L⟩\right\}}_{k=1}^K$$ are orthonormal bases for $$ {\mathcal{H}}_0$$ and $$ \mathcal{Q}$$, respectively. Then for any pure state $$ ∣a⟩$$ in $$ {\mathcal{H}}_0$$, $$ \sqrt{K}⟨a\mid Q⟩\in \mathcal{Q}$$. Hence, Eq. (44) implies thatfor all $$ ∣a⟩$$ in $$ {\mathcal{H}}_0$$, which in turn implies Eq. (45).

To prove the sufficiency part, let $$ \mathcal{Q}$$ be the space generated by the pure states $$ ∣{\phi }_a⟩=\sqrt{K}⟨a\mid Q⟩$$ for all $$ ∣a⟩$$ in $$ {\mathcal{H}}_0$$. Then, Eq. (45) implies that all $$ ∣{\phi }_a⟩$$ are m-uniform states. Furthermore, from $$ \mathrm{rank}\left({\mathrm{Tr}}_0\left(∣Q⟩⟨Q∣\right)\right)=\mathrm{rank}\left({\mathrm{Tr}}_{12\cdots n}\left(∣Q⟩⟨Q∣\right)\right)=\mathrm{rank}\left({\mathbb{1}}_K/K\right)=K$$ it follows that $$ \mathcal{Q}$$ is a K-dimensional subspace.

Thus, Theorem 1 gives a necessary and sufficient condition for the existence of ((n, K, m+1))_d pure codes.

Proposition 1 A quantum ((n, K, m+1))_d pure code exists if and only if there exists Φ_AB in $$ {\tilde{\mathcal{H}}}_A\otimes {\tilde{\mathcal{H}}}_B={\left[{\mathbb{C}}^K\otimes {\left({\mathbb{C}}^d\right)}^{\otimes n}\right]}^{\otimes 2}$$ such that

where SEP denotes the set of separable states w.r.t. the bipartition (A∣B) = (A₀A₁ ⋯ A_n∣B₀B₁ ⋯ B_n), V_AB is the swap operator between $$ {\tilde{\mathcal{H}}}_A$$ and $$ {\tilde{\mathcal{H}}}_B$$, and $$ A_{I^c}$$ denotes all subsystems A_i for i ∈ I^c.

Furthermore, the multi-party extension and symmetrization techniques that we developed for AME states can be easily adapted to the quantum error-correcting codes. For instance, the PPT relaxation can be written as a linear program and the symmetric extensions can be written as SDPs. An important difference is that the symmetrized Φ_AB for quantum error-correcting codes is no longer uniquely determined by the marginals in general. Finally, we would like to mention that Lemma 5 is of independent interest on its own. For example, Eq. (45) implies that $$ K{d}^m\le \sqrt{K{d}^n}$$, as $$ \mathrm{rank}\left({\mathrm{Tr}}_{I^c}\left(∣Q⟩⟨Q∣\right)\right)\le \sqrt{\dim \left(\tilde{\mathcal{H}}\right)}$$. This provides a simple proof for the quantum Singleton bound^44,45 K ≤ d^n−2m for pure codes.

General quantum codes

In general, a quantum ((n, K, m+1))_d code exists if and only if there exists a K-dimensional subspace $$ \mathcal{Q}$$ of $$ \mathcal{H}={⨂}_{i=1}^n{\mathcal{H}}_i={\left({\mathbb{C}}^d\right)}^{\otimes n}$$ such that for all $$ ∣\phi ⟩\in \mathcal{Q}$$

where ρ_I are marginals that are arbitrary but independent of $$ ∣\phi ⟩$$, $$ {\mathcal{I}}_m=\left\{I\in \left[n\right]\mid ∣I∣=m\right\}$$, and I^c = [n]⧹I = {1, 2, …, n}⧹I. Similar to the case of pure codes, we can prove the following lemma.

Lemma 3 A quantum ((n, K, m+1))_d code exists if and only if there exists a quantum state $$ ∣Q⟩$$ in $$ \tilde{\mathcal{H}}$$ and marginal states ρ_I such that

where $$ \tilde{\mathcal{H}}={\mathcal{H}}_0\otimes \mathcal{H}={⨂}_{i=0}^n{\mathcal{H}}_i={\mathbb{C}}^K\otimes {\left({\mathbb{C}}^d\right)}^{\otimes n}$$ and I^c is defined as [n]⧹I = {1, 2, …, n}⧹I.

If the marginals ρ_I are given like in the case of pure codes, the problem reduces to a marginal problem. However, to ensure the existence of ((n, K, m+1))_d codes, an arbitrary set of marginals is sufficient. This makes the problem no longer a marginal problem, however, we can circumvent this issue by observing that Eq. (57) is equivalent to

for all M₀ such that $$ \mathrm{Tr}\left(M_0\right)=0$$. Moreover, we can choose an arbitrary basis $$ \mathcal{B}$$ for $$ \left\{M_0\mid \mathrm{Tr}\left(M_0\right)=0,M_0^{†}=M_0\right\}$$. Then, with the general result on rank-constrained optimization from ref. ⁴⁷, we obtain the following theorem, and similar to the AME existence problem, a complete hierarchy can be constructed using the symmetric extension technique.

Proposition 2 A quantum ((n, K, m+1))_d code exists if and only if there exists Φ_AB in $$ {\tilde{\mathcal{H}}}_A\otimes {\tilde{\mathcal{H}}}_B={\left[{\mathbb{C}}^K\otimes {\left({\mathbb{C}}^d\right)}^{\otimes n}\right]}^{\otimes 2}$$ such that

for all $$ I\in {\mathcal{I}}_m$$ and $$ M_{A_0}\in \mathcal{B}$$, where the SEP means the separability with respect to the bipartition (A∣B) = (A₀A₁ ⋯ A_n∣B₀B₁ ⋯ B_n), V_AB is the swap operator between $$ {\tilde{\mathcal{H}}}_A$$ and $$ {\tilde{\mathcal{H}}}_B$$, $$ A_{I^c}$$ denotes all subsystems A_i for i ∈ I^c, and $$ {\mathbb{1}}_{A_0^c}$$ denote the identity operator on AB⧹A₀ = A₁A₂ ⋯ A_nB₀B₁B₂ ⋯ B_n.

By noticing that the set of ((n, K, m+1))_d (pure or general) codes, or rather, the set of states $$ ∣Q⟩$$, is invariant under local unitaries and permutations on the bodies 123 ⋯ n, we can assume that Φ_AB is invariant under the following two classes of unitaries

for all U₀ ∈ SU(K), U_i ∈ SU(d), and π ∈ S_n. Thus, the symmetrized Φ_AB is of the formfor $$ x_i,y_i\in \mathbb{R}$$. Hence, all the techniques we developed for AME states can be easily adapted to the quantum error-correcting codes. For example, the PPT relaxation can be written as a linear program and the symmetric extension can be written as SDPs.