Recoverability from direct quantum correlations
S. Di Giorgio P. Mateus B. Mera



1,2]S. Di Giorgio
1,2]P. Mateus
1,2]B. Mera

[1]Departamento de Matemática, Instituto Superior Técnico, Universidade de Lisboa, Av. Rovisco Pais, 1049-001 Lisboa, Portugal
[2]Instituto de Telecomunicações, 1049-001 Lisboa, Portugal

Recoverability from direct quantum correlations
    [
    December 30, 2023
===============================================



We address the problem of compressing density operators defined on a finite dimensional 	Hilbert space which assumes a tensor product decomposition. In particular, we look for an efficient procedure for learning the most likely density operator, according to Jaynes' principle, given a chosen set of partial information obtained from the unknown quantum system we wish to describe. For complexity reasons, we restrict our analysis to tree-structured sets of bipartite marginals. We focus on the tripartite scenario, where we solve the problem for the couples of measured marginals which are compatible with a quantum Markov chain, providing then an algebraic necessary and sufficient condition for the compatibility to be verified. 
We introduce the generalization of the procedure to the n-partite scenario, giving some preliminary results. In particular, we prove that if the pairwise Markov condition holds between the subparts then the choice of the best set of tree-structured bipartite marginals can be performed efficiently. Moreover, we provide a new characterisation of quantum Markov chains in terms of quantum Bayesian updating processes. 




§ INTRODUCTION



The problem of efficiently compressing density operators can be related to the one addressed by Jaynes <cit.> for probability distributions. We are interested in determining an efficient procedure for inferring the most likely density operator from partial information about the system we wish to describe, with the freedom of choosing the set of partial information to be collected.
With a complete set of measurements, quantum tomography techniques are able to infer with maximum accuracy the density operator that most likely describes the given quantum system, but the needed resources to perform the former increases exponentially with the number of degrees of freedom of the system. A clever choice of a partial set of measurements should optimize the data collection, lead up to an efficient learning procedure and keep a good accuracy. The necessity of dealing with a statistically relevant number of degrees of freedom motivates machine learning <cit.> and quantum machine learning techniques <cit.>.




  
The maximum entropy estimator In his seminal paper <cit.>, Jaynes wrote:

“Information theory provides a constructive criterion for setting up probability distribution on the basis of partial knowledge and leads to a type of statistical inference which is called the maximum-entropy estimate. It is the least biased estimate possible on the given information, i.e. it is maximally noncommittal with regard to missing information.”

Since quantum information theory provides a well-defined generalization the Shannon entropy, the von Neumann entropy, it can be used to state a quantum Jaynes' principle and, therefore, to obtain a maximally noncommittal estimator for density operators with regard to the partial information collected. Moreover, due to the concavity of both Shannon and von Neumann entropy, the maximization problem has a unique solution and the desired estimator is uniquely determined. We choose therefore to infer from the given measurements, the density operators that maximizes the von Neumann entropy. 


  
Learning from direct correlations A common approximation for multipartite physical system description consists in cutting the correlations after the first neighbour. Direct dependencies between random variables are usually less struggling to be measured and it results in a theoretical exponential gain in data collection. Consider a multipartite quantum system, described by a Hilbert space ℋ_X_1,...,X_n=ℋ_X_1⊗…⊗ℋ_X_n, with ℋ_X_i=(d), for all i=1,...,n. To infer the state of the whole system, represented by a density matrix ρ_X_1,...,X_n, one needs an exponential amount of resources, more concretely, (d^2n). However, if one restricts to bipartite correlations only, the amount of resources needed to approximately reproduce the state scales polynomially with n, (n^2 d^4). This approximation restricts the set of learnable states: for pure-multipartite correlated systems, such as the GHZ state, we expect not to be accurately recoverable.


  
Restriction to trees Since density operators generalize classical probability distributions, finding the density operator that maximizes the von Neumann entropy given the complete set of bipartite correlations, would solve the analogous problem for classical probability distributions. To study an efficient learning procedure, the hardness results of the classical problem need to be taken in account.

Given a finite set of classical random variables, the optimization problem of finding the probability distribution that maximizes the Shannon entropy given a general collection of bipartite marginals, can be stated as a graph inference problem. With the provided information, the classical system can be represented by a graph where the vertices represent the random variables and the edges represent the direct dependencies between them. Then, graphical models, such as Bayesian Networks and Markov random fields <cit.>, provide the learning techniques for the maximum entropy estimator. Inferring a general graphical structure is NP-Hard <cit.>, and so is finding an approximate solution <cit.>. The only structures for which a general efficient learning solution is known are trees, as even learning 2-polytrees is NP-Hard <cit.>. Nevertheless, there exists an efficient algorithm to obtain the optimal tree – the Chow-Liu algorithm <cit.>. Then, any set of random variables can be efficiently approximated by the probability distribution describing its most likely tree. It has been an open problem to find richer structures than tree Markov random fields that can be learned efficiently.

Motivated by these classical results, we look for an efficient learning procedure for the maximum von Neumann entropy estimator given a subset of bipartite marginals which is tree-structured. This means that, representing the joint quantum system by a graph where the vertices label the subsystems and where the edges represent the measured bipartite marginals, the resulting graph is a tree. Observe that the problem we are analyzing can be stated also as searching for a subclass of density operators for which the classical results of learning via graphical models can be extended.

The efficiency of the afforementioned learning techniques is mainly due to the factorization of the joint probability distribution that occurs when the conditional independence condition between the interested subparts holds. As we are going to see in detail, also when the system involves quantum correlations, the quantum generalization of conditional independence to quantum states results in an algebraic recovery of the joint in terms of the interested subparts.
However, whereas the graphical structure of a classical system naturally encodes the conditional independence properties between them, the one involving quantum correlations does not. Further conditions, not explicit from the graphical structure, need in general to be verified. Many attempts have been done for developing appropriate generalizations of graphical models for density operators <cit.>, but none of them naturally encodes the required properties which result in a learning simplification without further conditions <cit.>.



 §.§ Problem
 We wish to find an efficient procedure for learning the density operator that maximizes the von Neumann entropy from a subset of (compatible, cf. Definition <ref>) tree-structured bipartite marginals. 


  
Results  We consider the simplest nontrivial tree, i.e. a tripartite quantum system where two marginals are known (Section <ref>). This analysis provides insight for the multipartite scenario (Section <ref>).

Tripartite case: We provide an algebraic recovery procedure of the tripartite density operator given two bipartite marginals when they are compatible with a quantum Markov chain – Definition <ref>. We find that there exists an algebraic recovery procedure, namely the Petz recovery map, for the maximum entropy estimator whenever there exists a quantum Markov chain in the compatibility set of the provided marginals – Theorem <ref>. Indeed, Quantum Markov chains represent the subset of tripartite density operators that strictly contains classical probability distributions, i.e., such that between the two non adjacent quantum states, the (quantum) conditional independence condition holds – Corollary <ref>. Then, we provide a necessary and sufficient condition for efficiently verifying if the given couple of marginals is compatible with a quantum Markov chain –Theorem <ref>. 
Moreover, we give a criterion for determining which couple of possible bipartite marginals, out of the three possible, provides the best maximum entropy estimator, meaning the one that minimizes the relative entropy distance with the unknown density operator. We prove the best estimator to be the one with minimum von Neumann entropy – Theorem <ref>, which, if all the three couple of measured marginals are compatible with a quantum Markov chain, can be obtained by discarding the marginal with minimum quantum mutual information – Theorem <ref>.
Both the conditions of Theorem <ref> and Theorem <ref> are algebraic, allowing the efficiency of the entire learning procedure and, possibly, an easier generalization to the multipartite case.

Furthermore, observing that the problem of entropy maximization can be stated as multiple-step minimum entropy updating (Section <ref>), we give a further characterization of quantum Markov chains as the commutativity of a diagram of quantum Bayesian updating processes – Theorem <ref>.

Multipartite case: We provide some preliminary results about a possible generalization of the notion of the procedure to the multipartite scenario. In particular, we prove that the global Markov condition, properly extended to density operators, is sufficient to have an efficient recovery of the maximum entropy estimator given a tree structured set of bipartite marginals and, additionally, it is sufficient to efficiently choose an optimal tree for the estimator – Proposition <ref>.





§ MAXIMUM ENTROPY ESTIMATOR


Let 𝒳={X_1,...,X_n}, with 0<n<∞, be a set labelling the parts of a multipartite quantum system 𝒳. The physical system 𝒳 can be described by an Hermitian, positive-semidefinite and trace one operator ρ_𝒳, namely a density operator in the Liouville space ℒ(ℋ_𝒳), where ℋ_𝒳 is a separable Hilbert space on its subparts ℋ_𝒳:=⊗_i=1^nℋ_X_i. We denote  by d_X the dimension of the Hilbert space ℋ_X, which is always assumed to be finite in the whole manuscript.
Running several times the same experiment, we can collect many copies of the unknown system; on each of them, we can perform a measurement, obtaining the set of expectation values {⟨Θ_i⟩}_i∈ I, where Θ_i are positive Hermitian operators acting on the full joint Hilbert space ℋ_𝒳.



 The density operator ρ∈ℒ(ℋ_𝒳) that maximizes the von Neumann entropy, denoted S(ρ), is given by 

    ρ_𝒳=1/Zexp(∑_i∈ Iλ_i Θ_i ),  with  Z=[exp(∑_i∈ Iλ_i Θ_i)]

and in which {λ_i}_i∈ I are Lagrange multipliers which are obtained by solving the equations [ρ Θ_i]=⟨Θ_i⟩.


 This follows from taking the variation of the function

    S(ρ) -∑_i∈ Iλ_i([ρ Θ_i]-⟨Θ_i⟩).

By concavity of S the solution is a maximum point and it is unique.

In our case, we are given a set of bipartite marginals {ρ_X_iX_j}, which can be probed by a complete set of observables in the associated bipartite Hilbert spaces. If we are given a Hilbert space ℋ_X, then there exist a set of Hermitian operators {Λ_j^(X): j=0,...,d_X^2-1} which are complete in the sense that any linear operator and, in particular any observable, can be written as a linear combination of the latter. This basis of operators can be chosen to be orthonormal with respect to the Hilbert-Schmidt inner product and, additionally, to be traceless, so that {iΛ_j^(X):j=0,...,d_X^2-1} span a Lie algebra 𝔰𝔲(d_X), where Λ_0^(X):=_X is the identity on ℋ_X and it corresponds to the remaining generator of 𝔲(d_X). For each i∈ I, we denote by {Λ^(X_i)_k:k=0,..,d_X_i^2-1} a chosen complete set of observables for X_i, as before. For each X_iX_j, the set {Λ^(X_i)_k⊗Λ^(X_j)_l: k=0,...,d_X_i^2-1, l=0,...,d_X_j^2-1} forms a complete set of observables for the bipartite system X_iX_j. We extend the operators Λ^(X_i)_k⊗Λ^(X_j)_l acting on ℋ_X_i⊗ℋ_X_j in a natural way to act on the joint Hilbert space ℋ_𝒳 by taking the tensor product with the identity on the relevant factors. By abuse of notation we denote by Λ^(X_i)_kΛ^(X_j)_l the extended operators. As a consequence of Prop. <ref>, the density operator ρ_X_1 ... X_n maximizing the von Neumann entropy assumes the form

    ρ_𝒳=1/Zexp(∑_i,jk^2+l^2≠ 0∑_k=0^d_X_i^2-1∑_l=0^d_X_j^2-1λ^(X_iX_j)_klΛ^(X_i)_kΛ^(X_j)_l),

where, as before, {λ_jk^(X_iX_j)} are the Lagrange multipliers of the optimization problem, constrained by the partial traces on the given marginals. The state of Eq. (<ref>) exists because the set of density operators satisfying the given constraints is convex and non-empty. Indeed, a priori, the set of bipartite marginals is the output of a set of measurements performed on an existing quantum system described by an n-partite density operator. We are than assuming the given set of provided marginals to be compatible.


(Compatibility and Compatibility set) 
Consider a set of density operators 𝒞={ρ_𝒴∈ℒ(ℋ_𝒴) }_𝒴∈𝒦, where 𝒦 is a family of subsystems of 𝒳 which is a cover, i.e., ⋃_𝒴∈𝒦𝒴=𝒳. We say that 𝒞 is a compatible set of marginals if there exists at least one density operator ρ over the joint Hilbert space ℋ_𝒳 such that _𝒴(ρ)=ρ_𝒴 for all ρ_𝒴∈𝒞. Here _𝒴(·) denotes the partial trace over the complementary factors of the Hilbert space 𝒴̅=𝒳\𝒴.

Moreover, we denote by Comp(𝒞) the set of density operators over ℋ_𝒳 s.t. _𝒴(ρ)=ρ_𝒴 for every ρ_𝒴∈𝒞. We say for each ρ∈ Comp(𝒞) that ρ is compatible  with ρ_𝒴, for any 𝒴∈𝒦.  Additionally, we also say that ρ is compatible with 𝒞.

The problem of determining if a given set of density operators is compatible is known as the quantum marginal problem  is  QMA complete <cit.>. This problem reduces to determining the maximum entropy estimator (compatible with the marginals), and therefore, the latter is QMA hard.
In particular, a necessary condition, also sufficient for classical probability distributions, for a set of density operators defined on overlapping Hilbert spaces to be compatible is to coincide on their intersection. Formally, given ρ_𝒴_1,ρ_𝒴_2∈𝒞 compatible, if 𝒴_1∩𝒴_2≠∅ then  _𝒴_1∩𝒴_2(ρ_𝒴_1)=_𝒴_1∩𝒴_2(ρ_𝒴_2). 

Our goal, as stated in the introduction, is to have an efficient recovery of the maximum entropy estimator given a set of bipartite marginals. For that reason and taking into account the results known for the classical case (see the introduction), we restrict to the case where the set of bipartite marginals is tree structured. In the next subsection we consider the tripartite case in detail.

Also in the tripartite case, we are going to restrict the problem to trees where just two marginals out of the three possible are taken in account. This not only to gain some insight about the generalization to the multipartite scenario, but also since the recovery problem for a tripartite probability distribution given all the three possible bipartite marginals is open <cit.>. Moreover, moving to the quantum scenario, also the compatibility problem for just a couple of overlapping marginals is open <cit.>. We are then going to assume the set of the two given marginal density operators compatible.




 §.§ The tripartite case


Let us denote 𝒳={A,B,C}, and assume we are given access to marginals {ρ_AB,ρ_BC}. See the associated graph in Fig. <ref>.

In Eq. (<ref>), we denote by λ_kl:=λ_kl^(AB) and η_kl:=λ_kl^(BC). We then have,

    ρ_ABC=	1/Zexp(k^2+l^2≠ 0∑_k=0^d_A^2-1∑_l=0^d_B^2-1λ_klΛ_k^AΛ_l^B+k^2+l^2≠ 0∑_k=0^d_B^2-1∑_l=0^d_C^2-1η_klΛ_k^BΛ_l^C).

Because for each X_iX_j, the set {Λ^(X_i)_k⊗Λ^(X_j)_l: k=0,...,d_i^2-1, l=0,...,d_j^2-1} forms a complete set of observables for the bipartite system X_iX_j, we can write,

    ρ_AB=1/d_A d_B_AB+	k^2+l^2≠ 0∑_k=0^d_A^2-1∑_l=0^d_B^2-1α_klΛ_k^(A)Λ_l^(B),  ρ_BC=1/d_B d_C_BC+	k^2+l^2≠ 0∑_k=0^d_A^2-1∑_l=0^d_B^2-1β_klΛ_k^(B)Λ_l^(C),

where α_kl, β_kl∈ℝ. Additionally, the constraints imposed by the marginals can be cast in the form

    [Λ_k^(A)Λ_l^(B)(ρ_ABC-ρ_AB⊗C)]=0,  [Λ_k^(B)Λ_l^(C)(ρ_ABC-A⊗ρ_BC)]=0,

where k and l range in the dimensions of the space of linear operators of the appropriate subsystem.

From the partition function Z, one can obtain, by differentiation, a system of equations which allow to solve for the Lagrange multipliers in terms of the known parameters {α_kl} and {β_kl}. This is a standard procedure in statistical mechanics. Determining if the optimization problem described above has an algebraic solution is not trivial: the Lie operators in the exponent of Eq. (<ref>) in general do not commute, which makes the analysis of the constraints imposed in Eq. (<ref>) mathematically hard to manage. Many techniques for overcoming similar problems are object of study, see for example Ref. <cit.> for trace inequalities or Refs. <cit.> for operator inequalities. Instead, here we focus our attention on a well-behaved subset of density operators – quantum Markov chains <cit.>. In the next section, we recall the definition of a quantum Markov chain and prove a necessary and sufficient condition for a given pair of bipartite marginals to be compatible with a quantum Markov chain. 



§ MARGINALS' COMPATIBILITY WITH QUANTUM MARKOV CHAINS



 (Quantum Markov chain <cit.>) A tripartite state ρ_ABC over ℋ_ABC is called a quantum Markov chain (QMC) in order A-B-C if there exists a recovery map ℛ_B→ BC:ℒ(ℋ_B)→ℒ(ℋ_BC) such that

    ρ_ABC=(ℐ_A⊗ℛ_B→ BC)(ρ_AB),
 
where a recovery map is an arbitrary trace-preserving completely positive (CPTP) map, see Ref. <cit.>, and ℐ_A denotes the identity map on ℒ(ℋ_A).


A QMC can be characterized from an information-theoretical point of view due to the following result.



<cit.>
A tripartite state ρ_ABC is a QMC in the order A-B-C if an only if I_ρ(A:C|B)=0, where I_ρ(A:C|B):=S(ρ_AB)+S(ρ_BC)-S(ρ_B)-S(ρ_ABC) is the quantum conditional mutual information.

We recall that in case of classical random variables with finite domains, when we are given two bipartite marginals p(A,B) and p(B,C), the compatibility condition ∑_ap(A=a,B=b)=∑_cp(B=b,C=c) is necessary and sufficient for A and C to be independent conditioned on B, i.e. I(A: C|B)=0. Then, the set of quantum Markov chains includes the set of classical tripartite probability distributions.

Proposition <ref> is equivalent to the statement: a QMC A-B-C is a tripartite quantum state for which the strong subadditivity of the von Neumann entropy,

    S(ρ_AB)+S(ρ_BC)≥ S(ρ_B)+S(ρ_ABC),

holds with equality <cit.>, which trivially results in the fact that a QMC A-B-C maximizes the von Neumann entropy given its two bipartite marginals AB and BC. Furthermore, the quantum systems A and C are said to be quantum conditionally independent given the quantum system B.

A QMC always admits as a recovery channel the rotated Petz recovery map <cit.>:

    𝒫_B→ BC^t(X):=ρ_BC^1+it/2(ρ_B^-1+it/2X ρ_B^-1-it/2)ρ_BC^1-it/2,  for any  X∈ℒ(ℋ_B), t∈ℝ.

In particular, for t=0, the map is known as the Petz recovery map or transpose map:

    𝒫_B→ BC(X):=ρ_BC^1/2ρ_B^-1/2X ρ_B^-1/2ρ_BC^1/2,  for any  X∈ℒ(ℋ_B).

Note that in the previous formulas, ρ_B and X are understood as elements of ℒ(ℋ_BC) by extending it in the natural way, i.e., ρ_B⊗_C. In Ref. <cit.> it is shown that the Petz recovery map is indeed a recovery map, i.e., a CPTP map.

Our first result comes as a natural corollary of the previous stated results.



Given bipartite marginals {ρ_AB,ρ_BC} compatible with a QMC in the order A-B-C, say ρ_ABC, then the solution of the maximum entropy estimator ρ_ABC is precisely equal to ρ_ABC. Moreover, ρ_ABC can be algebraically recovered via the Petz map 𝒫_B→ BC(·), concretely:

    ρ_ABC=ρ_BC^1/2ρ_B^-1/2ρ_ABρ_B^-1/2ρ_BC^1/2.



We can also recover a tripartite density operator from ρ_BC through 𝒫_B→ AB(·):

    ρ_AB^1/2ρ_B^-1/2ρ_BCρ_B^-1/2ρ_AB^1/2,

and by uniqueness, because the von Neumann entropy is concave, they are the same.	


In alternative to the Petz recovery map, in presence of marginals compatible with a QMC, we can solve efficiently the associated optimization problem, i.e., determine the Lagrange multipliers in Eq. (<ref>) due to the following result by Petz <cit.>:


<cit.>
Assume that ρ_ABC is invertible. Then the equality holds in the strong subadditivity inequality (SSA) if and only if logρ_ABC-logρ_AB=logρ_BC-logρ_B.


Our next result, provides a necessary and sufficient condition for the given marginals {ρ_AB,ρ_BC} to be compatible with a QMC. The condition is moreover algebraic, resulting in being easily verifiable.


Two bipartite marginals {ρ_AB,ρ_BC} are compatible with a QMC in ℒ(ℋ_ABC) in the order A-B-C if and only if _A(ρ_AB)=_C(ρ_BC) and the operator Θ_ABC=ρ_BC^1/2ρ_B^-1/2ρ_AB^1/2 is normal.

Before giving the proof of Theorem <ref>, we will need one further result.


<cit.>
A tripartite density operator ρ_ABC∈ℒ(ℋ_ABC) satisfies the SSA with equality, i.e., I_ρ(A:C|B)=0, if and only if there exits a decomposition of the Hilbert space ℋ_B of the form

    ℋ_B=⊕_jℋ_B_j^L⊗ℋ_B_j^R,  such that ρ_ABC=⊕_jp_j ρ_AB_j^L⊗ρ_B_j^R C,

with p_j≥ 0, for all j, ∑_j p_j=1 and the states ρ_AB_j^L∈ℒ(ℋ_A⊗ℋ_B_j^L) and ρ_B_j^RC∈ℒ(ℋ_B_j^R⊗ℋ_C).                 


(⇒) Using compatibility, the following decompositions are a direct consequence of Theorem <ref> 

    ρ_AB   =⊕_jp_j ρ_AB_j^L⊗ρ_B_j^R,  with ρ_B_j^R=_C(ρ_B_j^RC),
    ρ_BC   =⊕_jp_j ρ_B_j^L⊗ρ_B_j^RC,  with ρ_B_j^L=_A(ρ_AB_j^R),
    ρ_B   =⊕_jp_j ρ_B_j^L⊗ρ_B_j^R.

It is now trivial to see that _A(ρ_AB)=_C(ρ_BC), as required. It remains to check that Θ_ABC is normal. Notice that, from the above decompositions, we have

    Θ_ABC   =ρ_BC^1/2ρ_B^-1/2ρ_AB^1/2
       =(⊕_jp_j ρ_B_j^L⊗ρ_B_j^RC)^1/2(⊕_kp_k ρ_B_k^L⊗ρ_B_k^R)^ -1/2(⊕_lp_l ρ_AB_l^L⊗ρ_B_l^R)^1/2
       =⊕_jp_j ρ_AB_j^L^1/2⊗ρ_B_j^RC^1/2.

and also

    Θ_ABC^†=(ρ_BC^1/2ρ_B^-1/2ρ_AB^1/2)^†=ρ_AB^1/2ρ_B^-1/2ρ_BC^1/2=⊕_jp_j ρ_AB_j^L^1/2⊗ρ_B_j^RC^1/2=Θ_ABC,

hence we conclude that Θ_ABC is self-adjoint, therefore normal.

(⇐) Consider the operator 

    ϱ_ABC=Θ_ABC Θ_ABC^†=ρ_BC^1/2ρ_B^-1/2ρ_ABρ_B^-1/2ρ_BC^1/2.

We have:

	
  (i) ϱ_ABC is a density operator over ℋ_ABC. This can be seen from the fact that the map
	
    𝒫_B→ BC:     ℒ(ℋ_B)⟶ℒ(ℋ_BC) 
       σ↦ρ_BC^1/2ρ_B^-1/2σρ_B^-1/2ρ_BC^1/2
 
	is a CPTP map, as mentioned above, and it extends to a CPTP map ℐ_A⊗𝒫_B→ BC which yields, when applied to ρ_AB, ϱ_ABC.
	
  (ii) ϱ_ABC is compatible with {ρ_AB,ρ_BC}. Indeed, we have,
	
    _A(ϱ_ABC)=ρ_BC^1/2ρ_B^-1/2_A(ρ_AB)ρ_B^-1/2ρ_BC^1/2=ρ_BC^1/2ρ_B^-1/2ρ_Bρ_B^-1/2ρ_BC^1/2=ρ_BC,

	where we have used _A(ρ_AB)=ρ_B. Moreover, since Θ_ABC is normal and _C(ρ_BC)=ρ_B, we have,
	
    _C(ϱ_ABC)   =_C(Θ_ABC Θ_ABC^†)=_C(Θ_ABC^† Θ_ABC)=_C(ρ_AB^1/2ρ_B^-1/2ρ_BCρ_B^-1/2ρ_AB^1/2)=ρ_AB.

	
  (iii) By (i) and (ii) and Definition <ref>, ϱ_ABC is a QMC.


From Theorem <ref>, we have the following corollary:

	
The space of pairs of bipartite marginals {ρ_AB,ρ_BC} which is compatible with a QMC is strictly included in the space of pairs of bipartite marginals {ρ_AB,ρ_BC} which are compatible.

The last statement seems rather intuitive, but cannot be seen immediately due to the fact that the quantum marginal problem, also for two overlapping marginals, is open. To provide a counter-example, we numerically generated a random 3-qubit density matrix, from which we obtained two compatible marginals via partial trace. Then, we check the compatibility condition with a quantum Markov chain in Theorem <ref>, given the two marginals. We repeat the process until the latter conditions fails.



§ QUANTUM BAYESIAN UPDATING


The principle of minimum discrimination information <cit.>, is intrinsically related to the maximum entropy principle and it is at the base of inferential updating of probability distributions. Given a prior joint probability distribution q_ X describing the random variables X:={X_1...X_n} and an additional set of new information about the system, the most unbiased posterior p_ X corresponds to the one that minimizes the Kullback-Leibler divergence with the prior distribution under the constraints given by the additional information. If the prior is the most un-informative one, i.e. the  uniform distribution, then the problem is equivalent to finding the probability distribution that maximizes the Shannon entropy with the given constraints. In Ref. <cit.>, the choice of the Kullback-Leibler divergence as a functional for inferential updating is explained in light of the maximum entropy principle and some designed criteria.

The learning problem for multipartite quantum states we are proposing here can be stated a multiple-step inferential updating procedure, where starting from the uniform distribution, i.e. the maximally mixed state, the marginals are the additional information set available at each step.

In Ref. <cit.>, a generalization to the quantum realm of the Bayesian updating procedure is proposed. The Kullback-Leibler divergence is generalized by the von Neumann relative entropy, not by mere replacement, but deriving it from the same designed criteria and the maximum (von Neumann) entropy principle.


(Quantum Bayesian updating) Given a quantum system 𝒳={X_1,...,X_n} described by the joint Hilbert space ℋ_𝒳=⊗_i=1^nℋ_X_i, let ϱ_𝒳∈ℒ(ℋ_𝒳) be our a prior knowledge about it, and {⟨Θ_j ⟩}_j∈ J a set of expectation values corresponding to a set of observables {Θ_j}_j∈ J be the additional set of information. Then, via the principle of minimum updating, the posterior density operator assumes the form

    ρ_𝒳=exp(λ _𝒳 + ∑_j∈ Jα_j  Θ_j +logϱ_𝒳),
 
where the Lagrange multipliers λ and {α_j}_j∈ J are determined by the constraints (ρ)=1 and (ρ Θ_j)=⟨Θ_j⟩, j∈ J. We indicate the updating process of Eq. (<ref>) by the diagram

    ϱ_𝒳ρ_𝒳.


Observing that S(ρ_𝒳)=-S(ρ_𝒳||𝒳), it follows that the maximum entropy density operator of Eq. <ref> is equivalent to the output of the process:

    ABCρ_ABC.

We could split the updating process into two processes, i.e:

    ABCσ'_ABCσ_ABC,

or

    ABCϱ'_ABCϱ_ABC,

and, classically, one can show, all these updating processes, Eq. (<ref>), Eq. (<ref>) and Eq. (<ref>), are equivalent. However, in the quantum scenario, this is not the case due to the non-commutative nature of the observables involved. In Ref. <cit.>, it is shown that, in contrast to the classical case, where the conditional mutual information is always a measure of the distance of a tripartite quantum state to a general Markov chain, in the quantum case it is not. In particular,

    I_ρ(A:C|B)≥ S(ρ_ABC||ℛ_B→ BC(ρ_AB)),

where ℛ_B→ BC(·) is an arbitrary recovery map. Recently, tighter versions of the above inequality have been the object of study by several authors <cit.>. The equality holds when I_ρ(A:C|B)= 0, i.e., for a QMC. 
The fact that the three above processes, Eq. (<ref>), Eq. (<ref>) and Eq. (<ref>), lead to different density operators corresponds to the non-commutativity of a diagram. Moreover, in the next theorem we provide necessary and sufficient conditions for the diagram to commute, which provides a characterization of QMCs in terms of QBU.

	
Given a set of marginals {ρ_AB,ρ_BC}, we then have a commutative diagram of quantum Bayesian updating processes:

    @R+1pc@C+2pcABC[r]^ρ_AB[d]_ρ_BC   σ'_ABC[d]^ρ_BC
    ϱ'_ABC[r]_ρ_AB   ρ_ABC

if and only if they are compatible with a QMC in the order A-B-C.        

To provide a proof of this theorem we will need the following lemma.

<cit.>
Given a tripartite quantum state ρ_ABC∈ℒ(ℋ_ABC) compatible with {ρ_AB,ρ_BC}, the following operator-inequalities hold:

	
  (i) _AB[ρ_ABC(logρ_ABC-logρ_AB+logρ_B-logρ_BC)]≽ 0,
	
  (ii) _AB[ρ_AB(logρ_AB-logρ_ABC-logρ_B+logρ_BC)]≽ 0,

where the equality holds if and only if ρ_ABC is a QMC in the order A-B-C. Above, ≽ 0 stands for positive 	semidefinite.



(⇐) We will now show that if {ρ_AB,ρ_BC} is compatible with a QMC ρ_ABC in the order A-B-C, then σ_ABC=ϱ_ABC=ρ_ABC.

Using the fact that S(ρ)=-S(ρ||ABC), the first step of the updating process is obtained by maximizing the von Neumann entropy, yielding

    σ'_ABC=ρ_AB⊗C   and   ϱ'_ABC=A⊗ρ_BC.

Recalling that (ρ_BC):={ρ_ABC∈ℒ(ℋ_ABC) : _A(ρ_ABC)=ρ_BC}. Then 

    σ_ABC=ρ_ABC∈(ρ_BC)S(ρ_ABC||σ'_ABC).

It then follows that, since ρ_ABC∈(ρ_BC), 

    S(ρ_ABC||ρ_AB⊗C)≥ S(σ_ABC||ρ_AB⊗C).

Analogously, (ρ_AB)={ρ_ABC∈ℒ(ℋ_ABC) : _C(ρ_ABC)=ρ_AB}. Then 

    ϱ_ABC=ρ_ABC∈(ρ_AB)S(ρ_ABC||ϱ'_ABC).

It then follows that, since ρ_ABC∈(ρ_AB), 

    S(ρ_ABC||A⊗ρ_BC)≥ S(ϱ_ABC||A⊗ρ_BC).

The SSA inequality can be obtained as a special case as the contractibility property of the quantum relative entropy under CPTP maps <cit.>:

    S(ρ||σ)≥ S(Φ(ρ)||Φ(σ)),  for all ρ,σ and Φ a CPT map.

Indeed, set ρ=ρ_ABC∈(ρ_AB)∩(ρ_BC), then:

	
  (i) For σ=ρ_AB⊗C and Φ(·)=_A(·), we get
	
    S(ρ_ABC||ρ_AB⊗C)≥ S(ρ_BC||ρ_B⊗C).

	
  (ii) For σ=A⊗ρ_BC and Φ(·)=_C(·), we get
	
    S(ρ_ABC||A⊗ρ_BC)≥ S(ρ_AB||A⊗ρ_B).

 
In both Eq.(<ref>) and Eq. (<ref>) the equality holds for ρ_ABC=ρ_ABC. Using the inequalities (<ref>) and (<ref>) with ρ_ABC=σ_ABC and the Eq.(<ref>) with ρ_ABC=ρ_ABC,

    S(ρ_ABC||ρ_AB⊗C)≥ S(σ_ABC||ρ_AB⊗C)≥ S(ρ_BC||ρ_B⊗C)=S(ρ_ABC||ρ_AB⊗C).

It then follows that ρ_ABC=σ_ABC.

Analogously, using the inequalities (<ref>) and (<ref>) with ρ_ABC=ϱ_ABC and the Eq.(<ref>) with ρ_ABC=ρ_ABC, we get ρ_ABC=ϱ_ABC.

(⇒) We will now show that if σ_ABC=ϱ_ABC then {ρ_AB,ρ_BC} is compatible with a QMC ρ_ABC in the order A-B-C and ρ_ABC=σ_ABC=ϱ_ABC.

To provide explicit representations of σ_ABC and ϱ_ABC as exponentials of some operators we write, using invertibility,

    ρ_AB =exp(∑_i=0^d_A^2-1∑_j=0^d_B^2-1A_ijΛ_i^(A)⊗Λ_j^(B)),  ρ_BC =exp(∑_i=0^d_B^2-1∑_j=0^d_C^2-1C_ijΛ_i^(B)⊗Λ_j^(C)),

for {A_ij} and {B_ij} real coefficients. For convenience, we also define the partition functions

    Z_AB=exp(-A_00)  and  Z_BC=exp(-C_00).

  We then have, using Definition <ref>,

    σ_ABC=exp(∑_i=0^d_B^2-1∑_j=0^d_C^2-1η_ijΛ_i^(B)Λ_j^(C)+logσ'_ABC).

Where {η_ij} are the Lagrange multipliers in the definition. After some algebra, we can write

    logσ_ABC=   (η_00-log Z_BC-log d_C)_ABC+∑_i=0^d^2_B-1∑_j=1^d_C^2-1η_ijΛ_i^(B)Λ_j^(C)
       +∑_i=1^d_A^2-1∑_j=0^d_B^2-1A_ijΛ_i^(A)Λ_j^(B)+∑_i=1^d_B^2-1(A_0i+η_i0)Λ_i^(B).

Similarly,

    ϱ_ABC=exp(∑_i=0^d_A^2-1∑_j=0^d_B^2-1λ_ijΛ_i^(A)Λ_j^(B)+logϱ'_ABC).

Where {λ_ij} are the Lagrange multipliers in the definition. After some algebra, we can write

    logϱ_ABC=   (λ_00-log Z_AB-log d_A)_ABC+∑_i=1^d^2_A-1∑_j=0^d_B^2-1λ_ijΛ_i^(A)Λ_j^(B)
       +∑_i=0^d_B^2-1∑_j=1^d_C^2-1C_ijΛ_i^(B)Λ_j^(C)+∑_i=1^d_B^2-1(C_i0+λ_0i)Λ_i^(B).

Since σ_ABC=ϱ_ABC, by hypothesis, it follows that logσ_ABC=logϱ_ABC and, hence,

    η_00-log Z_BC-log d_C=λ_00-log Z_AB-log d_A,
        A_ij=λ_ij, for  i=1,...,d_A^2-1  and  j=0,...,d_B^2-1,
        C_ij=η_ij, for  i=0,...,d_B^2-1  and    j=1,...,d_C^2-1,
        A_0i+η_i0=C_i0+λ_0i, for   i=1,...,d_B^2-1.

Observing that,

    ∑_i=1^d^2_A-1∑_j=0^d_B^2-1λ_ijΛ_i^(A)Λ_j^(B) =logρ_AB -log Z_AB_AB-∑_i=1^d_B^2-1A_0iΛ_i^(B),
       ∑_i=0^d^2_B-1∑_j=1^d_C^2-1η_ijΛ_i^(B)Λ_j^(C)=logρ_BC -log Z_BC_BC-∑_i=1^d_B^2-1C_i0Λ_i^(B),

it follows that the two reconstructed states can be written as

    logσ_ABC=   logρ_AB +logρ_BC+(η_00-log Z_BC-log d_C)_ABC+∑_i=1^d_B^2-1(η_i0-C_i0)Λ_i^(B),
    logϱ_ABC=   logρ_AB +logρ_BC+(λ_00-log Z_AB-log d_A)_ABC+∑_i=1^d_B^2-1(λ_0i-A_0i)Λ_i^(B).

We now define the Hermitian operator θ_B by the following two equivalent formulas (consequence of logσ_ABC=logϱ_ABC ):

    logθ_B    :=(η_00-log Z_BC-log d_C)_B+∑_i=1^d_B^2-1(η_i0-C_i0)Λ_i^(B)
       =(λ_00-log Z_AB-log d_A)_B+∑_i=1^d_B^2-1(λ_0i-A_0i)Λ_i^(B).

Observe that θ_B can, as usual, be extended by tensoring with the relevant identity maps to the whole Hilbert space ℋ_ABC. We conclude that σ_ABC=ϱ_ABC implies the existence of an Hermitian θ_B such that

    logσ_ABC=logρ_AB +logρ_BC +logθ_B=logϱ_ABC.

Plugging in ρ_ABC=σ_ABC and its logarithm as in Eq. (<ref>), in  Lemma <ref>, we get:


  (i) _B[ρ_BC(logρ_B+logθ_B)]≽ 0,



  (ii) -_B[ρ_B(logρ_B+logθ_B)]_C≽ 0.

The second inequality is equivalent to _B[ρ_B(logρ_B+logθ_B)]≤ 0. By tracing over C the first inequality we get _B[ρ_B(logρ_B+logθ_B)]≥ 0. Therefore,

    _B[ρ_B(logρ_B+logθ_B)]=0.

From this equation, observing that ρ_B=_AC(σ_ABC), we can write

    _B[_AC(σ_ABC)(logρ_B+logθ_B)] =_ABC[σ_ABC _A⊗ (logρ_B+logθ_B)⊗_C]=0.

Adding and subtracting both log(ρ_AB)⊗_C and _A⊗log(ρ_BC), which for simplicity we write without the identity factors, we get

    _ABC[σ_ABC  (logσ_ABC+logρ_B -logρ_AB -logρ_BC)]   =0,

and this equation is equivalent to I_ρ(A:C|B)=0, i.e., equivalent to the statement that the SSA inequality holds with equality.




§ BEST TWO OUT OF THREE


In Section <ref>, we provided a way of efficiently reconstructing a tripartite quantum state given two of its bipartite marginals subject to the compatibility condition – Theorem <ref> and Theorem <ref>. In general, if we are given the three possible bipartite density operators, we still have a residual degree of freedom, namely, the choice of the pair of bipartite density operators from which one will recover the tripartite estimator. We are going to show that the best tripartite maximum von Neumann entropy estimator is the one out of three with minimum von Neumann entropy – Theorem <ref>.

	
	Let ρ∈ℒ(ℋ_ABC) be an unknown quantum state describing a tripartite quantum system ABC. Given the bipartite marginals {ρ_AB,ρ_BC,ρ_AC}, we define 𝒞={ρ_XY,ρ_YZ} with X,Y,Z∈A,B,C to be one of the three possible pairs of marginals, and ρ_𝒞∈(𝒞) to be the maximum von Neumann entropy estimator. Then ρ minimizing the relative entropy with respect to the unknown state ρ_ABC is the one with minimum von Neumann entropy

    ρ= 𝒞 S(ρ_𝒞).



	By linearity of the trace, the von Neumann relative entropy between ρ_ABC and ρ_𝒞:
	
    S(ρ_ABC||ρ_𝒞)=-S(ρ_ABC) -[ρ_ABClogρ_𝒞].

	ρ_𝒞  has the form derived in Eq. (<ref>). Then, there exist Hermitian operators θ_XY∈ℒ(ℋ_XY), θ_YZ∈ℒ(ℋ_YZ) and θ_Y∈ℒ(ℋ_Y) (naturally extended to act on the joint Hilbert space) such that:
	
    logρ_𝒞=θ_XY+θ_YZ+θ_Y.
 
	Plugging in  (<ref>) in  (<ref>) and using the fact that both ρ_ABC and ρ_XYZ are in the compatibility set of 𝒞, it immediately follows that
		
    S(ρ_ABC||ρ_𝒞)=S(ρ_𝒞) -S(ρ_ABC).

	Since the term S(ρ_ABC) is independent on the choice of 𝒞:
	
    ρ=𝒞 S(ρ_ABC||ρ_𝒞)=𝒞 S(ρ_𝒞).


The estimator we are proposing here is then:

    ρ=𝒞 ρ∈(𝒞) S(ρ).


At this level, the efficiency of the choice of the optimal set of marginals is strictly related to the number of possibilities, which makes the direct generalization to the multipartite scenario inefficient.  As we are going to see in detail in Section <ref>, the number of possible choices increases exponentially with the number of variables. The Chow-Liu learning algorithm <cit.>, solves the problem in the case of probability distributions. The next corollary generalizes the Chou-Liu main argument to QMCs., which will give an hint for the possible generalization of the Chow-Liu algorithm to Markov quantum trees (cf. Definition <ref>). Moreover, we are going to see that is sufficient that the compatibility condition with a QMC holds for the estimator obtained via Chow-Liu algorithm to be the optimal one.


	
	Having a tripartite quantum system ABC described by an unknown ρ∈ℒ(ℋ_ABC) and given the bipartite marginals {ρ_AB,ρ_BC,ρ_AC}. If for every pair 𝒞={ρ_XY,ρ_YZ} with X,Y,Z∈{A,B,C}  there exists a QCM in the order X-Y-Z (cf. Theorem <ref>), then the QMC ρ_XYZ minimizing the relative entropy with respect to the unknown state ρ_ABC is the one recovered from the pair
	
    𝒞=𝒞{I_ρ(X:Y) + I_ρ(Y:Z)}.



	Observe that:
	
    S(ρ_ABC||ρ_XYZ)   =[ρ_ABC(logρ_ABC-logρ_XYZ)]
       =-S(ρ_ABC) -[ρ_ABC(logρ_XY +logρ_YZ -logρ_Y)]
       =-S(ρ_ABC) +S(ρ_XY)+S(ρ_YZ)-S(ρ_Y),

	where in the second line we used Lemma <ref>. Now, adding and subtracting S(ρ_X), S(ρ_Y)
	and S(ρ_Z), we immediately get
	
    S(ρ_ABC||ρ_XYZ)=-[I_ρ(X:Y)+I_ρ(Y:Z)]+∑_W∈{A,B,C}S(ρ_W) -S(ρ_ABC).
 
	Since the two last terms are independent on the choice of pair of bipartites, we get the desired result.

Then, in case all the subsets 𝒞 are compatible with a QMC, the min-max estimator is the one obtained excluding from the set of marginals the one with lowest quantum mutual information. The compatibility conditions with QMCs are necessary for this result to hold. Indeed, relaxing the compatibility conditions, now we are going to determine an analoguous form to Eq. (<ref>) for a general maximum entropy estimator Eq (<ref>). 


Take Eq (<ref>) and add and subtract S(ρ_XY), S(ρ_YZ), S(ρ_Y). We then observe that
	
    i)    S(ρ_XY)+S(ρ_YZ)-S(ρ_Y)=-[ I_ρ(X:Y)+I_ρ(Y:Z)] +∑_W∈{A,B,C} S(ρ_W),
    ii)    [ρ_ABClogρ_XYZ]=[ρ_ABC(θ_XY+θ_YZ+θ_Y)]
       =_XY[_Z(ρ_ABC)θ_XY]+_YZ[_X(ρ_ABC)θ_YZ]+_Y[_XZ(ρ_ABC)θ_Y]
       =_XY[_Z(ρ_XYZ)θ_XY]+_YZ[_X(ρ_XYZ)θ_YZ]+_Y[_XZ(ρ_XYZ)θ_Y]
       =-S(ρ_XYZ);
    iii)    S(ρ_XYZ) -S(ρ_XY)-S(ρ_YZ)+S(ρ_Y)= I_ρ(X:Z|Y )


Therefore Eq (<ref>) can be rewritten as it follows

    S(ρ_ABC||ρ_XYZ)=   -[ I_ρ(X:Y)+I_ρ(Y:Z)]-I_ρ(X:Z|Y ) +∑_W∈{A,B,C} S(ρ_W)-S(ρ_ABC).


Comparing Eq. (<ref>) with Eq. (<ref>), we can see that, in general, the choice of the two marginals with maximum mutual informations between the subparts, is not the optimal one for the maximum entropy estimator. Relaxing the compatibility conditions between just one pair with a QMC, the additional term in Eq.(<ref>), namely the quantum conditional mutual information of the constructed maximum entropy estimator, I_ρ(X:Z|Y), is different from zero. The result of Eq (<ref>) does not lead, at first sight, to a simplification of Eq. (<ref>).



§ THE MULTIPARTITE CASE


In the previous sections, while considering the tripartite case, we learned that in order to have an algebraic recovery procedure, we need to have a tree structure and an additional constraint regarding the conditional mutual information. It is then natural to suppose that in the general multipartite case one would need a set of additional constraints, which generalize the one obtained previously, and this motivates the following definitions.


	
	(Quantum graph and quantum tree) A quantum graph is a triple (𝒳,{ℋ_X}_X∈𝒳, ρ,𝒢), where 𝒳={X_1,..,X_n} labels quantum systems described by the associated Hilbert spaces ℋ_X, X∈𝒳, with the n-partite composite system described by ℋ_𝒳=ℋ_X_1⊗ ...⊗ℋ_X_n, ρ∈ℒ(ℋ_𝒳) is an n-partite density operator and 𝒢=(𝒳, E) is an undirected graph.Whenever the underlying graph of a quantum graph is a tree, we call the structure a quantum tree.

 
	Let 𝒢=(V,E) be a undirected graph and let U and W be non overlapping subsets of V. We say that a subset Z, disjoint from U and W, separates U and W if every path connecting a vertex in U and a vertex in W necessarily overlaps with Z. We say that Z is a separator for U and W.


	
	(Markov quantum field and Markov quantum tree) A Markov quantum field is a quantum graph (𝒳,{ℋ_X}_X∈𝒳, ρ,𝒢), where the density operator ρ satisfies the global Markov property: for all U,W⊂𝒳 such that there exists a separator Z for U and W then
	
    I_ρ(U:W|Z)=0.
  	
Whenever the underlying graph of a Markov quantum field is a tree, we call the structure a Markov quantum tree.

Definition <ref> includes the most general Markov property, i.e. the global property. Observe that given a Markov quantum field, then any quantum subtree is a quantum Markov tree.

Let ρ_𝒳∈ℒ(ℋ_𝒳) be an unknown density operator that describes an n-partite physical system labelled by 𝒳. Let 𝒞_𝒯={ρ_X_iX_j, {X_i,X_j}∈ E(𝒯)} a subset of bipartite marginals, graphically representable by one of its spanning trees 𝒯. The quantum state ρ_𝒞_𝒯 that maximizes the von Neumann entropy under the constraints of compatibility with the marginals in 𝒞_𝒯 has the form derived in Eq. (<ref>). Then, there exists a set of Hermitian operators {θ_X_i∈ℒ(ℋ_X_i), X_i∈ V(𝒯)} and {θ_X_iX_j∈ℒ(ℋ_X_iX_j), {X_i,X_j}∈ E(𝒯)}, naturally extended to act on the joint Hilbert space, such that:
	
    logρ_𝒞_𝒯=∑_{X_i,X_j}∈ E(𝒯)θ_X_iX_j+∑_i=1^nθ_X_i,
  
where X_i is the degree of the node X_i, i.e. the number of edges linked to the node. If the quantum tree is a Markov quantum tree, then we have,
	
    logρ_𝒞_𝒯=∑_{X_i,X_j}∈ E(𝒯)logρ_X_iX_j-∑_i=1^n(  X_i-1)logρ_X_i,
 

The combinatorial factor is obtained by considering the spanning Markov quantum tree 𝒯 over 𝒳 as a tripartite one on ABC with A=X_i∈𝒳, B=X_j∈𝒳, C=𝒳\{X_i,X_j}, where X_i and X_j are chosen such that there are no edges between X_i and any vertices in 𝒳\{X_i,X_j}, i.e., A-B-C is a Markov quantum tree, for which we can use Lemma <ref>. 




Then, consider the Markov quantum subtree 𝒳\{X_i,X_j} as a tripartite quantum tree A'-B'-C'  with A=X_k∈𝒳\ X_i, B=X_l∈𝒳\ X_i, C=𝒳\{X_i,X_k,X_l}, apply Lemma <ref>, and iterate the procedure until the remaining subgraph is bipartite. It is then clear that each vertex comes with a factor of its degree minus one.

The construction above allows for an algebraic recovery of the state by iteratively applying the Petz recovery map.
 In the following paragraph, we show that the global Markov condition results in an efficient choice of the best tree.




  
Choosing the best tree Given an unknown n-partite quantum system, its bipartite correlations can be represented by a complete graph. Its number of possible spanning trees, i.e., tree subgraphs which include all vertices in the graph, is given by Cayley's formula <cit.>, n^n-2, which grows exponentially with the number of vertices. Because of this, we can not choose the best tree efficiently. In the classical scenario, one possible solution is to use the Chow-Liu algorithm <cit.>.

Recall that the Chow-Liu algorithm, cf. Appendix, provides an efficient way to find the optimal tree minimizing the Kullback-Leibler divergence between the actual probability distribution, p(X_1=x_1,...,X_n=x_n), and a probability distribution associated to a spanning tree, p^𝒯(X_1=x_1,...,X_n=x_n). In <cit.>, it is shown that the Kullback-Leibler divergence can be written as:

    D_K(p, p^𝒯) =-∑_{X_i,X_j}∈ E(𝒯)I(X_i,X_j)	 +∑_i=1^nH(X_i)-H(X_1,...,X_n),

where H(·) is the Shannon entropy and I(X_i,X_j) is the classical mutual information between X_i and X_j.
The only term that depends on the choice of tree 𝒯=(V(𝒯)=𝒳,E(𝒯)) is the first one, therefore, minimizing the Kullback-Leibler divergence is equivalent to maximizing

    ∑_{X_i,X_j}∈ E(𝒯)I(X_i,X_j),

to which problem the Chow-Liu algorithm provides an efficient solution.


The relative entropy  between the unknown density operator and one of its quantum tree maximum entropy estimators can be written as

    S(ρ_𝒳||ρ_𝒞_𝒯)= -S(ρ_𝒳) +(ρ_𝒳logρ_𝒞_𝒯)=S(ρ_𝒞_𝒯)-S(ρ_𝒳).

Where have used the compatibility conditions to perform a calculation similar to that of Eq. (<ref>). It then follows that Eq. (<ref>) still holds in the n-partite scenario. An alternative form for Eq. (<ref>), which generalizes the one obtained by Chow and Liu for probability distributions Eq. (<ref>), is now derived. Adding and subtracting to Eq. (<ref>) the terms ∑_{X_i,X_j}∈ E(𝒯)S( ρ_X_iX_j) and ∑_i=1^n( degX_i-1) S( ρ_X_i), observing that

    ∑_{X_i,X_j}∈ E(𝒯)S( ρ_X_iX_j)-∑_i=1^n( degX_i-1) S( ρ_X_i)=-∑_{X_i,X_j}∈ E(𝒯)I_ρ(X_i,X_j)+∑_i=1^nS( ρ_X_i),

and setting

    Δ S(ρ_𝒞_𝒯):=∑_{X_i,X_j}∈ E(𝒯)S( ρ_X_iX_j)-∑_i=1^n( degX_i-1) S( ρ_X_i) -S(ρ_𝒞_𝒯),

Eq. (<ref>) assumes the form

    S(ρ_𝒳||ρ_𝒞_𝒯)=-∑_{X_i,X_j}∈ E(𝒯)I_ρ(X_i,X_j)-Δ S(ρ_𝒞_𝒯)+∑_i=1^nS( ρ_X_i) -S(ρ_𝒳).

When Δ S (ρ_𝒞)=0, again the best tree is the one that maximizes the term

    ∑_{X_i,X_j}∈ E(𝒯)I_ρ(X_i,X_j).

This last problem can be efficiently solved using the Chow-Liu algorithm where the mutual information on the bipartite subparts is replaced by its quantum generalization.

Next, we are going to study the conditions the correlations inside the given system have to  satisfy in order to have Δ S (ρ_𝒞_𝒯)=0. Consider the following iterative construction. Since 𝒯 is a tree, there exists a leaf, i.e., a vertex with degree 1 call it X_l_1∈𝒳 and denote by (X_l_1) its adjacent vertex.	 Set 𝒯_1=(V_1,E_1):=𝒯. Now consider the chain X_l_1 - (X_l_1)- V_1\{X_l_1,(X_l_1)}. The associated quantum conditional mutual information reads

    I_ρ(X_l_1: V_1\{X_l_1,(X_l_1)}|(X_l_1))= S(ρ_X_l_1(X_l_1))+S(ρ_V_1\{X_l_1}) -S(ρ_(X_l_1)) -S(ρ_V_1).

Observe that ρ_V_1=ρ_𝒞_𝒯. Set 𝒯_2:=(V_2,E_2), where V_2=V_1\{X_l_1} and E_2 is obtained naturally from E_1 by dropping {X_l_1,(X_l_1)}. It is trivial to see that 𝒯_2 is a tree and, thus, we can find a leaf X_l_2∈ V_2. Consider now the chain X_l_2 - (X_l_2)- V_2\{X_l_2,(X_l_2)}. The associated quantum conditional mutual information reads

    I_ρ(X_l_2: V_2\{X_l_2,(X_l_2)}|(X_l_2))= S(ρ_X_l_2(X_l_2))+S(ρ_V_2\{X_l_2}) -S(ρ_(X_l_2)) -S(ρ_V_2).

It is now clear that S(ρ_V_1\{X_l_1}) in Eq. (<ref>) cancels with S(ρ_V_2) upon summing the two equations. Iteratively, we can build a tree 𝒯_i+1=(V_i+1,E_i+1) from a tree 𝒯_i=(V_i,E_i)  with a chosen leaf X_l_i, by setting V_i+1=V_i\{X_l_i} and dropping the edge {X_l_i,(X_l_i)} from E_i to obtain E_i+1. This construction can be performed until one obtains the last chain X_l_n-2

    ∑_i=1^n-2I_ρ(X_l_i: V_i\{X_l_i,(X_l_i)}|(X_l_i))
       = ∑_i=1^n-2[S(ρ_X_l_i(X_l_i))-S(ρ_(X_l_i))] +S(ρ_V_n-2\{X_l_n-2})-S(ρ_V_1) 
       = ∑_{X_i,X_j}∈ E(𝒯) S(ρ_X_iX_j)-∑_i=1^n((X_i)-1)S(ρ_X_i) -S(ρ_𝒞_𝒯),

where we noticed that V_n-2\{X_l_n-2} is the last edge missing in the sum on the second line and also that ⋃_i=1^n-2{(X_i)} is 𝒳 except two vertices that have degree one. Therefore, we have

    Δ S(ρ_𝒞_𝒯) =∑_i=1^n-2I_ρ(X_l_i: V_i\{X_l_i,(X_l_i)}|(X_l_i)).
 
This equation shows that Δ S(ρ_𝒞_𝒯)≥ 0, because each term in the sum is non-negative. To proceed, we will apply the chain rule for quantum conditional mutual information:

    I_ρ(A:C_1… C_n| B)=   ∑_j=1^n I_ρ(A:C_j|B C_1… C_j-1),
 
where the first term in the sum is defined to be I_ρ(A:C_1|B). Motivated by the order appearing in the Chain rule, we introduce an order in V_i\{ X_l_i,(X_l_i)}={X_w_i(j)}_j=1^n-i, so that

    Δ S(ρ_𝒞_𝒯)    =∑_i=1^n-2 I_ρ(X_l_i: X_w_i(1)… X_w_i(n-i)|(X_l_i))
       =∑_i=1^n-2∑_j=1^n-i I_ρ(X_l_i: X_w_i(j)|(X_l_i)X_w_i(1)… X_w_i(j-1)).

To have Δ S(ρ_𝒞_𝒯) =0 is equivalent to having each term in the sum zero.


The quantity Δ S (ρ_𝒞_𝒯) is always non-negative. It is zero iff

    I_ρ(X_l_i: X_w_i(j)|(X_l_i)X_w_i(1)… X_w_i(j-1))=0,     for all  j=1,...,n-i  and  i=1,...,n-2.


We conclude that if we are given a Markov quantum field, then the choice of the best tree is efficient and the recovery procedure is algebraic. Notice that the set of conditions obtained in Prop. <ref> is polynomial, namely (n^2), and these are in general weaker than the global Markov property. This can perhaps be used as a hint towards relaxing the computationally demanding verification of the global Markov property on the provided marginals. 
                                                                                                              



§ CONCLUSIONS AND OUTLOOK


In this manuscript, we proposed a way to compress a subset of density operators according to a generalization to the quantum realm of the Jaynes' max entropy principle, given a chosen set of partial information. Focusing on the tripartite case, with access to two bipartite marginals, we provided a necessary and sufficient algebraic condition for compatibility with a QMC. The recovery procedure through the Petz map is algebraic and efficient. The recovery procedure goes as follows: 

	
  1. Measure the three bipartite marginals ρ_AB,ρ_BC,ρ_AC;
	
  2. Check for every couple ρ_XY, ρ_YZ with X,Y,Z∈{A,B,C} the compatibility condition with a quantum Markov chain X-Y-Z (Theorem <ref>);
	
  3. If for all the three couples of marginals the compatibility holds, compute the quantum mutual information I(X:Y) and discard the ρ_XY with minimum I(X:Y);
	
  4. From the two remaining marginals, via Petz recovery map, construct the min-max tripartite estimator (Theorem <ref>).


In Theorem <ref>, we provided a new characterisation of QMCs in terms of a commutative diagram of quantum Bayesian updating processes. This hints on a possible category-theoretical characterization of QMCs, which requires further investigation.

Through the notion of a Markov quantum tree, we were able to generalize the Chow-Liu algorithm to density operators. In fact, the results of this manuscript indicate that the classical theory of learning probability distributions via maximum entropy estimation can be extended naturally to Markov quantum trees.

We speculate that, due to the additional term in Eq. (<ref>) (see the paragraph after), it might be possible to extend our results to approximate quantum Markov chains (cf. Ref <cit.>), however, one would have to understand if it is possible to have an efficient compatibility condition, i.e., the analogue of Theorem <ref> for the case of approximate quantum Markov chains. 

We would like to be able to relax the global Markov condition in Definition <ref> and the result of Proposition <ref> provides a hint that such relaxation might be possible. This is desirable because, in general, the global Markov property seems computationally demanding, for a classical computer, to be verified. Another approach, would be to understand if a quantum computer can learn an even wider class of density operators efficiently.

Another possible direction towards extending the space of learnable quantum states is to enlarge the Hilbert space by an ancilla, which would allow to have a QMC, thus, efficiently learnable, however, this ancilla would have to be subject to certain conditions in order not to end up with a state which would be far from the unknown state in the relative entropy sense.



§ ACKNOWLEDGEMENTS


This work was supported by European funds namely via H2020 project SPARTA, national funds through FCT, Fundação para a Ciência e a Tecnologia, under contract IT (UID/EEA/50008/2019), PREDICT (PTDC/CCI-CIF/29877/2017), project QuantMining (POCI-01-0145-FEDER-031826) and internal IT projects QBigData and RAPID. Serena Di Giorgio also acknowledges the FCT PhD grant PD/BD/114332/2016 and the DP-PMI FCT programme.




§ APPENDIX: THE CHOW-LIU ALGORITHM


Given a set of random variables V={X_1,...,X_n} for which we have access to the bipartite correlations described by the joint probability distributions {p_X_iX_j} we can build a weighted complete graph 𝒢 whose vertices label the random variables and the edges correspond to the bipartite probability distributions, p_X_iX_j, weighted by the classical mutual informations I(X_i,X_j), given by 

    I(X_i,X_j)=∑_x_i,x_jp_X_iX_j(x_i,x_j)logp_X_i(x_i)p_X_j(x_j)/p_X_iX_j(x_i,x_j).

The Chow-Liu algorithm allows us to efficiently construct the maximum weighted spanning tree. Explicitly, sort the values {I(X_i,X_j)=I_α}_α=1^N=1/2n(n-1) in descending order, I_1≥ I_2≥ .... ≥ I_N, then the algorithm proceeds to build a tree 𝒯 iteratively as follows:



   [Initialization] 𝒢_0=(V,E_0) where V={X_1,...,X_n} and E_0=∅.

   [Iterative Step] Let {X_i,X_j} be the pair associated to α∈{1,...,N}. Build a graph 𝒢_α=(V,E_α-1), where E_α is obtained as follows

    E_α= 
    E_α-1∪{{X_i,X_j}},  if 𝒢_α=(V,E_α)  is a tree,
    
    E_α-1,  otherwise.



The graph 𝒢_N=𝒯 is the desired maximum weighted tree.

unsrt

