Herein we study the problem of recovering a density operator from a set of compatible marginals, motivated by limitations of physical observations. Given that the set of compatible density operators is not singular, we adopt Jaynes’ principle and wish to characterize a compatible density operator with maximum entropy. We first show that comparing the entropy of compatible density operators is complete for the quantum computational complexity class QSZK, even for the simplest case of 3-chains. Then, we focus on the particular case of quantum Markov chains and trees and establish that for these cases, there exists a procedure polynomial in the number of subsystems that constructs the maximum entropy compatible density operator. Moreover, we extend the Chow–Liu algorithm to the same subclass of quantum states.
Herein we study the problem of recovering a density operator from a set of compatible marginals, motivated by limitations of physical observations. Given that the set of compatible density operators is not singular, we adopt Jaynes’ principle and wish to characterize a compatible density operator with maximum entropy. We first show that comparing the entropy of compatible density operators is complete for the quantum computational complexity class QSZK, even for the simplest case of 3-chains. Then, we focus on the particular case of quantum Markov chains and trees and establish that for these cases, there exists a procedure polynomial in the number of subsystems that constructs the maximum entropy compatible density operator. Moreover, we extend the Chow–Liu algorithm to the same subclass of quantum states.
Herein we study the problem of recovering a density operator from a set of compatible marginals, motivated by limitations of physical observations. Given that the set of compatible density operators is not singular, we adopt Jaynes’ principle and wish to characterize a compatible density operator with maximum entropy. We first show that comparing the entropy of compatible density operators is complete for the quantum computational complexity class QSZK, even for the simplest case of 3-chains. Then, we focus on the particular case of quantum Markov chains and trees and establish that for these cases, there exists a procedure polynomial in the number of subsystems that constructs the maximum entropy compatible density operator. Moreover, we extend the Chow–Liu algorithm to the same subclass of quantum states.
We address the problem of efficiently and effectively compress density operators (DOs), by providing an efficient procedure for learning the most likely DO, given a chosen set of partial information. We explore, in the context of quantum information theory, the generalisation of the maximum entropy estimator for DOs, when the direct dependencies between the subsystems are provided. As a preliminary analysis, we restrict the problem to tripartite systems when two marginals are known. When the marginals are compatible with the existence of a quantum Markov chain (QMC) we show that there exists a recovery procedure for the maximum entropy estimator, and moreover, that for these states many well-known classical results follow. Furthermore, we notice that, contrary to the classical case, two marginals, compatible with some tripartite state, might not be compatible with a QMC. Finally, we provide a new characterisation of quantum conditional independence in light of maximum entropy updating. At this level, all the Hilbert spaces are considered finite dimensional.
Abstract 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 characterization of quantum Markov chains in terms of quantum Bayesian updating processes .
We study when local reduced density operators, viewed as quantum marginals, can be assembled into a global quantum state with a prescribed Markov structure. The starting point is a canonical logarithmic construction T(R), the noncommutative analogue of the junction-tree formula for decomposable graphical models. Unlike in the classical case, this formal construction may fail: noncommutativity can prevent it from being a normalized state with the prescribed marginals. We prove that this obstruction is captured exactly by a trace condition. For two overlapping marginals, and for clique marginals on a chordal graph, the condition Tr(T(R))=1 is equivalent to the existence of a quantum Markov completion. When it exists, the completion is unique, equal to T(R), and selected by the maximum entropy principle. In the two-clique case, we also give an equivalent conditional reconstruction characterization: the two natural one-sided sandwich reconstructions agree if and only if the trace condition holds. We introduce the global quantum information gI(G)ρ associated with a chordal graph G and show that it is a relative-entropy discrepancy from ρ to the logarithmic candidate, with a trace correction when the candidate is not normalized. We also prove an intersection property for strictly positive quantum conditional independence. Three-qubit Pauli examples illustrate how the quantum obstructions are real: local consistency, feasibility, Markov feasibility, and maximum entropy can all separate.
Abstract Inferring a quantum system from incomplete information is a common problem in many aspects of quantum information science and applications, where the principle of maximum entropy (MaxEnt) plays an important role. The quantum state compatibility problem asks whether there exists a density matrix compatible with some given measurement results. Such a compatibility problem can be naturally formulated as a semidefinite programming (SDP), which searches directly for the existence of a . However, for large system dimensions, it is hard to represent directly, since it requires too many parameters. In this work, MaxEnt is applied to solve various quantum state compatibility problems, including the quantum marginal problem. An immediate advantage of the MaxEnt method is that it only needs to represent via a relatively small number of parameters, which is exactly the number of the operators measured. Furthermore, in case of incompatible measurement results, the method will further return a witness that is a supporting hyperplane of the compatible set. The method has a clear geometric meaning and can be computed effectively with hybrid quantum‐classical algorithms.
We introduce the Markovian matrix product density operator, which is a special subclass of the matrix product density operator. We show that the von Neumann entropy of such ansatz can be computed efficiently on a classical computer. This is possible because one can efficiently certify that the global state forms an approximate quantum Markov chain by verifying a set of inequalities. Each of these inequalities can be verified in time that scales polynomially with the bond dimension and the local Hilbert space dimension. The total number of inequalities scale linearly with the system size. We use this fact to study the complexity of computing the minimum free energy of local Hamiltonians at finite temperature. To this end, we introduce the free energy problem as a generalization of the local Hamiltonian problem, and study its complexity for a class of Hamiltonians that describe quantum spin chains. The corresponding free energy problem at finite temperature is in NP if the Gibbs state of such Hamiltonian forms an approximate quantum Markov chain with an error that decays exponentially with the width of the conditioning subsystem.