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:1504.01029 · Journal of Physics A Mathematical and Theoretical

Relaxations of separability in multipartite systems: Semidefinite programs, witnesses and volumes

Cécilia Lancien, Otfried Gühne, Ritabrata Sengupta, Marcus Huber

Published Nov 24, 2015• 67 citations
arXivHTMLPDF

Abstract

Abstract While entanglement is believed to be an important ingredient in the understanding of quantum many-body physics, the complexity of its characterization scales very unfavorably with the size of the system. Finding super-sets of the set of separable states that admit a simpler description has proven to be a fruitful approach in the bipartite setting. In this paper we discuss a systematic way of characterizing multiparticle entanglement via various relaxations. We furthermore describe an operational witness construction arising from such relaxations that is capable of detecting every entangled state. Finally, we also derive an analytic upper-bound on the volume of biseparable states and show that the volume of the states with a positive partial transpose for any split that rapidly outgrows this volume. This proves that simple semi-definite relaxations in the multiparticle case cannot be an equally good approximation for any scenario.

DOI
10.1088/1751-8113/48/50/505302

Related papers

Entanglement witnesses and semidefinite programming

Pablo A. Parrilo, Andrew C. Doherty, Federico M. Spedalieri

We study the application of sums of squares decompositions and semidefinite programming in the formulation of computational criteria for distinguishing entangled from separable quantum states. A hierarchy of tests is obtained, the simplest of which corresponds to the well-known positive partial transpose (PPT) sufficient criterion, with the more complicated tests being strictly stronger. The duality structure of the problem allows us to provide an explicit construction of the entanglement witnesses corresponding to our tests.

IEEE Conference on Decision and Control (CDC)•Jan 23, 2004•2 citations

Detection of many-body entanglement partitions in a quantum computer

Albert Rico, Dmitry Grinko, Robin Krebs +1 more

We present a method to detect entanglement partitions of multipartite quantum systems, by exploiting their inherent symmetries. Structures like genuinely multipartite entanglement, $m$-separability and entanglement depth are detected as very special cases. This formulation enables us to characterize all the entanglement partitions of all three- and four- partite states and witnesses with unitary and permutation symmetry. In particular, we find and parametrize a complete set of bound entangled states therein. For larger systems, we provide a large family of analytical witnesses detecting many-body states of arbitrary size where none of the parties is separable from the rest. This method relies on weak Schur sampling with projective measurements, and thus can be implemented in a quantum computer. Beyond physics, our results extend to the mathematical literature: we establish new inequalities between matrix immanants, and characterize the set of such inequalities for matrices of size three and four.

quant-pharXiv:2511.13822•Physical Review Letters•Nov 19, 2025•1 citation

Characterizing entanglement in quantum information

Federico M. Spedalieri

Entanglement is a key resource in the emerging field of Quantum Information. The strong correlations between systems described by an entangled state allow us to perform certain tasks more efficiently than it would be possible by using only classical resources. This is why the characterization of entanglement is one of the most important problems in Quantum Information. In this thesis, we analyze several aspects of entanglement. First, we introduce a new family of criteria to determine if a bipartite mixed state is entangled or not. This family consists of a sequence of tests that can be implemented efficiently, and has the property that all entangled states can be detected by some test in the sequence. Each test in the family can be stated as a semidefinite program, which is a class of convex optimization problems. The duality structure of these programs allows us to explicitly construct an entanglement witness that proves entanglement of a state, whenever the state fails one of the tests in the sequence. The entanglement witnesses constructed in this manner have well-defined algebraic properties that can be used to give a characterization of the interior of the set of all possible entanglement witnesses, as well as the set of strictly positive bihermitian forms and the set of strictly positive maps. We also study deterministic transformations of three-qubit pure state when only local operations and classical communication (LOCC) are allowed. We derive strong constraints that the operations and states involved must satisfy, and we apply these results to characterize the set of real states that can be obtained from the GHZ state by LOCC.

•May 22, 2003•0 citations

Entanglement in bipartite X-states: analytical results for the volume of states with positive partial transpose

Yaqing Xy Wang, József Zsolt Bernád

Abstract We provide an analytical formula for the volume ratio between bipartite X-states with positive partial transpose and all bipartite X-states. The result applies to arbitrary m × n-bipartite systems and the volume expressions are derived with respect to the Hilbert–Schmidt measure.

arXiv:2412.20979•Journal of Physics A Mathematical and Theoretical•Apr 2, 2025•0 citations

Complete family of separability criteria

Andrew C. Doherty, Pablo A. Parrilo, Federico M. Spedalieri

We introduce a family of separability criteria that are based on the existence of extensions of a bipartite quantum state \ensuremath{\rho} to a larger number of parties satisfying certain symmetry properties. It can be easily shown that all separable states have the required extensions, so the nonexistence of such an extension for a particular state implies that the state is entangled. One of the main advantages of this approach is that searching for the extension can be cast as a convex optimization problem known as a semidefinite program. Whenever an extension does not exist, the dual optimization constructs an explicit entanglement witness for the particular state. These separability tests can be ordered in a hierarchical structure whose first step corresponds to the well-known positive partial transpose (Peres-Horodecki) criterion, and each test in the hierarchy is at least as powerful as the preceding one. This hierarchy is complete, in the sense that any entangled state is guaranteed to fail a test at some finite point in the hierarchy, thus showing it is entangled. The entanglement witnesses corresponding to each step of the hierarchy have well-defined and very interesting algebraic properties that, in turn, allow for a characterization of the interior of the set of positive maps. Coupled with some recent results on the computational complexity of the separability problem, which has been shown to be NP hard, this hierarchy of tests gives a complete and also computationally and theoretically appealing characterization of mixed bipartite entangled states.

arXiv:quant-ph/0308032•Physical Review A•Feb 18, 2004•467 citations

Distinguishing Separable and Entangled States

Andrew C. Doherty, Pablo A. Parrilo, Federico M. Spedalieri

We show how to design families of operational criteria that distinguish entangled from separable quantum states. The simplest of these tests corresponds to the well-known Peres-Horodecki positive partial transpose (PPT) criterion, and the more complicated tests are strictly stronger. The new criteria are tractable due to powerful computational and theoretical methods for the class of convex optimization problems known as semidefinite programs. We successfully applied the results to many low-dimensional states from the literature where the PPT test fails. As a by-product of the criteria, we provide an explicit construction of the corresponding entanglement witnesses.

arXiv:quant-ph/0112007•Physical Review Letters•Apr 23, 2002•366 citations
Abstract While entanglement is believed to be an important ingredient in the understanding of quantum many-body physics, the complexity of its characterization scales very unfavorably with the size of the system. Finding super-sets of the set of separable states that admit a simpler description has proven to be a fruitful approach in the bipartite setting. In this paper we discuss a systematic way of characterizing multiparticle entanglement via various relaxations. We furthermore describe an operational witness construction arising from such relaxations that is capable of detecting every entangled state. Finally, we also derive an analytic upper-bound on the volume of biseparable states and show that the volume of the states with a positive partial transpose for any split that rapidly outgrows this volume. This proves that simple semi-definite relaxations in the multiparticle case cannot be an equally good approximation for any scenario.
We study the application of sums of squares decompositions and semidefinite programming in the formulation of computational criteria for distinguishing entangled from separable quantum states. A hierarchy of tests is obtained, the simplest of which corresponds to the well-known positive partial transpose (PPT) sufficient criterion, with the more complicated tests being strictly stronger. The duality structure of the problem allows us to provide an explicit construction of the entanglement witnesses corresponding to our tests.
We present a method to detect entanglement partitions of multipartite quantum systems, by exploiting their inherent symmetries. Structures like genuinely multipartite entanglement, mmm-separability and entanglement depth are detected as very special cases. This formulation enables us to characterize all the entanglement partitions of all three- and four- partite states and witnesses with unitary and permutation symmetry. In particular, we find and parametrize a complete set of bound entangled states therein. For larger systems, we provide a large family of analytical witnesses detecting many-body states of arbitrary size where none of the parties is separable from the rest. This method relies on weak Schur sampling with projective measurements, and thus can be implemented in a quantum computer. Beyond physics, our results extend to the mathematical literature: we establish new inequalities between matrix immanants, and characterize the set of such inequalities for matrices of size three and four.
Entanglement is a key resource in the emerging field of Quantum Information. The strong correlations between systems described by an entangled state allow us to perform certain tasks more efficiently than it would be possible by using only classical resources. This is why the characterization of entanglement is one of the most important problems in Quantum Information. In this thesis, we analyze several aspects of entanglement. First, we introduce a new family of criteria to determine if a bipartite mixed state is entangled or not. This family consists of a sequence of tests that can be implemented efficiently, and has the property that all entangled states can be detected by some test in the sequence. Each test in the family can be stated as a semidefinite program, which is a class of convex optimization problems. The duality structure of these programs allows us to explicitly construct an entanglement witness that proves entanglement of a state, whenever the state fails one of the tests in the sequence. The entanglement witnesses constructed in this manner have well-defined algebraic properties that can be used to give a characterization of the interior of the set of all possible entanglement witnesses, as well as the set of strictly positive bihermitian forms and the set of strictly positive maps. We also study deterministic transformations of three-qubit pure state when only local operations and classical communication (LOCC) are allowed. We derive strong constraints that the operations and states involved must satisfy, and we apply these results to characterize the set of real states that can be obtained from the GHZ state by LOCC.
We introduce a family of separability criteria that are based on the existence of extensions of a bipartite quantum state \ensuremath{\rho} to a larger number of parties satisfying certain symmetry properties. It can be easily shown that all separable states have the required extensions, so the nonexistence of such an extension for a particular state implies that the state is entangled. One of the main advantages of this approach is that searching for the extension can be cast as a convex optimization problem known as a semidefinite program. Whenever an extension does not exist, the dual optimization constructs an explicit entanglement witness for the particular state. These separability tests can be ordered in a hierarchical structure whose first step corresponds to the well-known positive partial transpose (Peres-Horodecki) criterion, and each test in the hierarchy is at least as powerful as the preceding one. This hierarchy is complete, in the sense that any entangled state is guaranteed to fail a test at some finite point in the hierarchy, thus showing it is entangled. The entanglement witnesses corresponding to each step of the hierarchy have well-defined and very interesting algebraic properties that, in turn, allow for a characterization of the interior of the set of positive maps. Coupled with some recent results on the computational complexity of the separability problem, which has been shown to be NP hard, this hierarchy of tests gives a complete and also computationally and theoretically appealing characterization of mixed bipartite entangled states.
We show how to design families of operational criteria that distinguish entangled from separable quantum states. The simplest of these tests corresponds to the well-known Peres-Horodecki positive partial transpose (PPT) criterion, and the more complicated tests are strictly stronger. The new criteria are tractable due to powerful computational and theoretical methods for the class of convex optimization problems known as semidefinite programs. We successfully applied the results to many low-dimensional states from the literature where the PPT test fails. As a by-product of the criteria, we provide an explicit construction of the corresponding entanglement witnesses.