Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1802.00783 · Journal of Physics A Mathematical and Theoretical

Some Ulam’s reconstruction problems for quantum states

Felix Huber, Simone Severini B

Published Aug 28, 2018• 8 citations
arXivHTMLPDF

Abstract

Abstract Provided a complete set of putative k -body reductions of a multipartite quantum state, can one determine if a joint state exists? We derive necessary conditions for this to be true. In contrast to what is known as the quantum marginal problem, we consider a setting where the labeling of the subsystems is unknown. The problem can be seen in analogy to Ulam’s reconstruction conjecture in graph theory. The conjecture—still unsolved—claims that every graph on at least three vertices can uniquely be reconstructed from the set of its vertex-deleted subgraphs. When considering quantum states, we demonstrate that the non-existence of joint states can, in some cases, already be inferred from a set of marginals having the size of just more than half of the parties. We apply these methods to graph states, where many constraints can be evaluated by knowing the number of stabilizer elements of certain weights that appear in the reductions. This perspective links with constraints that were derived in the context of quantum error-correcting codes and polynomial invariants. Some of these constraints can be interpreted as monogamy-like relations that limit the correlations arising from quantum states. Lastly, we provide an answer to Ulam’s reconstruction problem for generic quantum states.

DOI
10.1088/1751-8121/aadd1e

Related papers

Some Ulam's reconstruction problems for quantum states

Huber, F, Simone Severini B

Provided a complete set of putative k-body reductions of a multipartite quantum state, can one determine if a joint state exists? We derive necessary conditions for this to be true. In contrast to what is known as the quantum marginal problem, we consider a setting where the labeling of the subsystems is unknown. The problem can be seen in analogy to Ulam's reconstruction conjecture in graph theory. The conjecture—still unsolved—claims that every graph on at least three vertices can uniquely be reconstructed from the set of its vertex-deleted subgraphs. When considering quantum states, we demonstrate that the non-existence of joint states can, in some cases, already be inferred from a set of marginals having the size of just more than half of the parties. We apply these methods to graph states, where many constraints can be evaluated by knowing the number of stabilizer elements of certain weights that appear in the reductions. This perspective links with constraints that were derived in the context of quantum error-correcting codes and polynomial invariants. Some of these constraints can be interpreted as monogamy-like relations that limit the correlations arising from quantum states. Lastly, we provide an answer to Ulam's reconstruction problem for generic quantum states.

•Oct 26, 2018•5 citations

Quantum states and their marginals : from multipartite entanglement to quantum error-correcting codes

Felix Huber

At the heart of the curious phenomenon of quantum entanglement lies the relation between the whole and its parts. In my thesis, I explore different aspects of this theme in the multipartite setting by drawing connections to concepts from statistics, graph theory, and quantum error-correcting codes: first, I address the case when joint quantum states are determined by their few-body parts and by Jaynes’ maximum entropy principle. This can be seen as an extension of the notion of entanglement, with less complex states already being determined by their few-body marginals. Second, I address the conditions for certain highly entangled multipartite states to exist. In particular, I present the solution of a long-standing open problem concerning the existence of an absolutely maximally entangled state on seven qubits. This sheds light on the algebraic properties of pure quantum states, and on the conditions that constrain the sharing of entanglement amongst multiple particles. Third, I investigate Ulam’s graph reconstruction problems in the quantum setting, and obtain legitimacy conditions of a set of states to be the reductions of a joint graph state. Lastly, I apply and extend the weight enumerator machinery from quantum error correction to investigate the existence of codes and highly entangled states in higher dimensions. This clarifies the physical interpretation of the weight enumerators and of the quantum MacWilliams identity, leading to novel applications in multipartite entanglement.

•Feb 14, 2018•8 citations

Reconstructing the whole from its parts

Daniel Uzcátegui Contreras, Dardo Goyeneche

The quantum marginal problem consists in deciding whether a given set of marginal reductions is compatible with the existence of a global quantum state or not. In this work, we formulate the problem from the perspective of dynamical systems theory and study its advantages with respect to the standard approach. The introduced formalism allows us to analytically determine global quantum states from a wide class of self-consistent marginal reductions in any multipartite scenario. In particular, we show that any self-consistent set of multipartite marginal reductions is compatible with the existence of a global quantum state, after passing through a depolarizing channel. This result reveals that the complexity associated to the marginal problem can be drastically reduced when restricting the attention to sufficiently mixed marginals. We also formulate the marginal problem in a compressed way, in the sense that the total number of scalar constraints is smaller than the one required by the standard approach. This fact suggests an exponential speedup in runtime when considering semi-definite programming techniques to solve it, in both classical and quantum algorithms. Finally, we reconstruct $n$-qubit quantum states from all the $\binom{n}{k}$ marginal reductions to $k$ parties, generated from randomly chosen mixed states. Numerical simulations reveal that the fraction of cases where we can find a global state equals 1 when $5\leq n\leq12$ and $\lfloor(n-1)/\sqrt{2}\rfloor\leq k\leq n-1$, where $\lfloor\cdot\rfloor$ denotes the floor function.

arXiv:2209.14154•Sep 28, 2022•0 citations

Distribution of entanglement and correlations in all finite dimensions

Christopher Eltschka, Jens Siewert

The physics of a many-particle system is determined by the correlations in its quantum state. Therefore, analyzing these correlations is the foremost task of many-body physics. Any 'a priori' constraint for the properties of the global vs. the local states-the so-called marginals-would help in order to narrow down the wealth of possible solutions for a given many-body problem, however, little is known about such constraints. We derive an equality for correlation-related quantities of any multipartite quantum system composed of finite-dimensional local parties. This relation defines a necessary condition for the compatibility of the marginal properties with those of the joint state. While the equality holds both for pure and mixed states, the pure-state version containing only entanglement measures represents a fully general monogamy relation for entanglement. These findings have interesting implications in terms of conservation laws for correlations, and also with respect to topology.

•May 22, 2018•20 citations

Distribution of entanglement and correlations in all finite dimensions

Christopher Eltschka, Jens Siewert

The physics of a many-particle system is determined by the correlations in its quantum state. Therefore, analyzing these correlations is the foremost task of many-body physics. Any 'a priori' constraint for the properties of the global vs. the local states-the so-called marginals-would help in order to narrow down the wealth of possible solutions for a given many-body problem, however, little is known about such constraints. We derive an equality for correlation-related quantities of any multipartite quantum system composed of finite-dimensional local parties. This relation defines a necessary condition for the compatibility of the marginal properties with those of the joint state. While the equality holds both for pure and mixed states, the pure-state version containing only entanglement measures represents a fully general monogamy relation for entanglement. These findings have interesting implications in terms of conservation laws for correlations, and also with respect to topology.

arXiv:1708.09639•Quantum•May 22, 2018•27 citations

Mixed States Uniquely Determined by Marginals and Additivity

Xinyu Qiu, Lin Chen, Genwei Li +1 more

Identifying whether a mixed quantum state is uniquely determined among all states (UDA) by its local marginals is a basic problem in quantum information theory. We establish necessary and sufficient conditions under which several classes of multipartite mixed states are UDA by their $k$-partite marginals. We also prove structural properties based on ranges and marginals, and formulate a recursive procedure for the determination of UDA states. We show that sufficiently high rank rules out unique determination from fixed-order marginals, implying that almost all multipartite mixed states are not UDA from such marginals. Finally, we completely characterize the additivity of bipartite UDA states, three-qubit and several families of $n$-qubit product UDA states. These results clarify the boundary between UDA and non-UDA mixed states and provide a framework for local-marginal reconstruction and related certification tasks.

quant-pharXiv:2512.20133•IEEE Transactions on Information Theory•Dec 24, 2025•0 citations
Abstract Provided a complete set of putative k -body reductions of a multipartite quantum state, can one determine if a joint state exists? We derive necessary conditions for this to be true. In contrast to what is known as the quantum marginal problem, we consider a setting where the labeling of the subsystems is unknown. The problem can be seen in analogy to Ulam’s reconstruction conjecture in graph theory. The conjecture—still unsolved—claims that every graph on at least three vertices can uniquely be reconstructed from the set of its vertex-deleted subgraphs. When considering quantum states, we demonstrate that the non-existence of joint states can, in some cases, already be inferred from a set of marginals having the size of just more than half of the parties. We apply these methods to graph states, where many constraints can be evaluated by knowing the number of stabilizer elements of certain weights that appear in the reductions. This perspective links with constraints that were derived in the context of quantum error-correcting codes and polynomial invariants. Some of these constraints can be interpreted as monogamy-like relations that limit the correlations arising from quantum states. Lastly, we provide an answer to Ulam’s reconstruction problem for generic quantum states.
Provided a complete set of putative k-body reductions of a multipartite quantum state, can one determine if a joint state exists? We derive necessary conditions for this to be true. In contrast to what is known as the quantum marginal problem, we consider a setting where the labeling of the subsystems is unknown. The problem can be seen in analogy to Ulam's reconstruction conjecture in graph theory. The conjecture—still unsolved—claims that every graph on at least three vertices can uniquely be reconstructed from the set of its vertex-deleted subgraphs. When considering quantum states, we demonstrate that the non-existence of joint states can, in some cases, already be inferred from a set of marginals having the size of just more than half of the parties. We apply these methods to graph states, where many constraints can be evaluated by knowing the number of stabilizer elements of certain weights that appear in the reductions. This perspective links with constraints that were derived in the context of quantum error-correcting codes and polynomial invariants. Some of these constraints can be interpreted as monogamy-like relations that limit the correlations arising from quantum states. Lastly, we provide an answer to Ulam's reconstruction problem for generic quantum states.
At the heart of the curious phenomenon of quantum entanglement lies the relation between the whole and its parts. In my thesis, I explore different aspects of this theme in the multipartite setting by drawing connections to concepts from statistics, graph theory, and quantum error-correcting codes: first, I address the case when joint quantum states are determined by their few-body parts and by Jaynes’ maximum entropy principle. This can be seen as an extension of the notion of entanglement, with less complex states already being determined by their few-body marginals. Second, I address the conditions for certain highly entangled multipartite states to exist. In particular, I present the solution of a long-standing open problem concerning the existence of an absolutely maximally entangled state on seven qubits. This sheds light on the algebraic properties of pure quantum states, and on the conditions that constrain the sharing of entanglement amongst multiple particles. Third, I investigate Ulam’s graph reconstruction problems in the quantum setting, and obtain legitimacy conditions of a set of states to be the reductions of a joint graph state. Lastly, I apply and extend the weight enumerator machinery from quantum error correction to investigate the existence of codes and highly entangled states in higher dimensions. This clarifies the physical interpretation of the weight enumerators and of the quantum MacWilliams identity, leading to novel applications in multipartite entanglement.
The quantum marginal problem consists in deciding whether a given set of marginal reductions is compatible with the existence of a global quantum state or not. In this work, we formulate the problem from the perspective of dynamical systems theory and study its advantages with respect to the standard approach. The introduced formalism allows us to analytically determine global quantum states from a wide class of self-consistent marginal reductions in any multipartite scenario. In particular, we show that any self-consistent set of multipartite marginal reductions is compatible with the existence of a global quantum state, after passing through a depolarizing channel. This result reveals that the complexity associated to the marginal problem can be drastically reduced when restricting the attention to sufficiently mixed marginals. We also formulate the marginal problem in a compressed way, in the sense that the total number of scalar constraints is smaller than the one required by the standard approach. This fact suggests an exponential speedup in runtime when considering semi-definite programming techniques to solve it, in both classical and quantum algorithms. Finally, we reconstruct nnn-qubit quantum states from all the (nk)\binom{n}{k}(kn​) marginal reductions to kkk parties, generated from randomly chosen mixed states. Numerical simulations reveal that the fraction of cases where we can find a global state equals 1 when 5≤n≤125\leq n\leq125≤n≤12 and ⌊(n−1)/2⌋≤k≤n−1\lfloor(n-1)/\sqrt{2}\rfloor\leq k\leq n-1⌊(n−1)/2​⌋≤k≤n−1, where ⌊⋅⌋\lfloor\cdot\rfloor⌊⋅⌋ denotes the floor function.
The physics of a many-particle system is determined by the correlations in its quantum state. Therefore, analyzing these correlations is the foremost task of many-body physics. Any 'a priori' constraint for the properties of the global vs. the local states-the so-called marginals-would help in order to narrow down the wealth of possible solutions for a given many-body problem, however, little is known about such constraints. We derive an equality for correlation-related quantities of any multipartite quantum system composed of finite-dimensional local parties. This relation defines a necessary condition for the compatibility of the marginal properties with those of the joint state. While the equality holds both for pure and mixed states, the pure-state version containing only entanglement measures represents a fully general monogamy relation for entanglement. These findings have interesting implications in terms of conservation laws for correlations, and also with respect to topology.
The physics of a many-particle system is determined by the correlations in its quantum state. Therefore, analyzing these correlations is the foremost task of many-body physics. Any 'a priori' constraint for the properties of the global vs. the local states-the so-called marginals-would help in order to narrow down the wealth of possible solutions for a given many-body problem, however, little is known about such constraints. We derive an equality for correlation-related quantities of any multipartite quantum system composed of finite-dimensional local parties. This relation defines a necessary condition for the compatibility of the marginal properties with those of the joint state. While the equality holds both for pure and mixed states, the pure-state version containing only entanglement measures represents a fully general monogamy relation for entanglement. These findings have interesting implications in terms of conservation laws for correlations, and also with respect to topology.
Identifying whether a mixed quantum state is uniquely determined among all states (UDA) by its local marginals is a basic problem in quantum information theory. We establish necessary and sufficient conditions under which several classes of multipartite mixed states are UDA by their kkk-partite marginals. We also prove structural properties based on ranges and marginals, and formulate a recursive procedure for the determination of UDA states. We show that sufficiently high rank rules out unique determination from fixed-order marginals, implying that almost all multipartite mixed states are not UDA from such marginals. Finally, we completely characterize the additivity of bipartite UDA states, three-qubit and several families of nnn-qubit product UDA states. These results clarify the boundary between UDA and non-UDA mixed states and provide a framework for local-marginal reconstruction and related certification tasks.