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:0906.2731 · Physical Review A

Power of symmetric extensions for entanglement detection

Miguel Navascués, Masaki Owari, Martin Bodo Plenio

Published Nov 6, 2009• 89 citations
arXivHTMLPDF

Abstract

In this paper, we present progress on the study of the symmetric extension criterion for separability. First, we show that a perturbation of order $O(1/N)$ is sufficient and, in general, necessary to destroy the entanglement of any state admitting an $N$ Bose-symmetric extension. On the other hand, the minimum amount of local noise necessary to induce separability on states arising from $N$ Bose-symmetric extensions with positive partial transpose (PPT) decreases at least as fast as $O(1/{N}^{2})$. From these results, we derive upper bounds on the time and space complexity of the weak membership problem of separability when attacked via algorithms that search for PPT-symmetric extensions. Finally, we show how to estimate the error we incur when we approximate the set of separable states by the set of (PPT) $N$-extendable quantum states in order to compute the maximum average fidelity in pure state estimation problems, the maximal output purity of quantum channels, and the geometric measure of entanglement.

DOI
10.1103/physreva.80.052306

Related papers

Detecting entanglement by pure bosonic extension

Xuanran Zhu, Chao Zhang, Chenfeng Cao +3 more

In the realm of quantum information theory, the detection and quantification of quantum entanglement stand as paramount tasks. The relative entropy of entanglement (REE) serves as a prominent measure of entanglement, with extensive applications spanning numerous related fields. The positive partial transpose (PPT) criterion, while providing an efficient method for the computation of REE, unfortunately, falls short when dealing with bound entanglement. In this study, we propose a method termed “pure bosonic extension” to enhance the practicability of k -bosonic extensions, which approximates the set of separable states from the “outside”, through a hierarchical structure. It enables efficient characterization of the set of k -bosonic extendible states, facilitating the derivation of accurate lower bounds for REE. Compared to the semi-definite programming (SDP) approach, such as the symmetric/bosonic extension function in QETLAB, our algorithm supports much larger dimensions and higher values of extension k . Published by the American Physical Society 2024

arXiv:2209.10934•Physical Review Research•Mar 7, 2024•0 citations

k-Extendibility of high-dimensional bipartite quantum states

Cécilia Lancien

The idea of detecting the entanglement of a given bipartite state by searching for symmetric extensions of this state was first proposed by Doherty et al. The complete family of separability tests it generates, often referred to as the hierarchy of [Formula: see text]-extendibility tests, has already proved to be most promising. The goal of this paper is to try and quantify the efficiency of this separability criterion in typical scenarios. For that, we essentially take two approaches. First, we compute the average width of the set of [Formula: see text]-extendible states, in order to see how it scales with the one of separable states. And second, we characterize when random-induced states are, depending on the ancilla dimension, with high probability violating or not the [Formula: see text]-extendibility test, and compare the obtained result with the corresponding one for entanglement vs separability. The main results can be precisely phrased as follows: on [Formula: see text], when [Formula: see text] grows, the average width of the set of [Formula: see text]-extendible states is equivalent to [Formula: see text], while random states obtained as partial traces over an environment [Formula: see text] of uniformly distributed pure states are violating the [Formula: see text]-extendibility test with probability going to [Formula: see text] if [Formula: see text]. Both statements converge to the conclusion that, if [Formula: see text] is fixed, [Formula: see text]-extendibility is asymptotically a weak approximation of separability, even though any of the other well-studied separability relaxations is outperformed by [Formula: see text]-extendibility as soon as [Formula: see text] is above a certain (dimension independent) value.

arXiv:1504.06459•Random Matrices Theory and Application•Jul 1, 2016•11 citations

Detection of Multiparticle Entanglement: Quantifying the Search for Symmetric Extensions

Fernando G. S. L. Brandão, Matthias Christandl

We provide quantitative bounds on the characterization of multiparticle separable states by states that have locally symmetric extensions. The bounds are derived from two-particle bounds and relate to recent studies on quantum versions of de Finetti's theorem. We discuss algorithmic applications of our results, in particular a quasipolynomial-time algorithm to decide whether a multiparticle quantum state is separable or entangled (for constant number of particles and constant error in the norm induced by one-way local operations and classical communication, or in the Frobenius norm). Our results provide a theoretical justification for the use of the search for symmetric extensions as a test for multiparticle entanglement.

arXiv:1105.5720•Physical Review Letters•Oct 17, 2012•28 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

Entanglement and Quantumness - New Numerical Approaches -

Fabian Bohnet-Waldraff

The main topic of this compilation thesis is the investigation of multipartite entanglement of finite dimensional systems. We developed a numerical algorithm that detects if a multipartite state is entangled or separable in a finite number of steps of a semi-definite optimization task. This method is an extension of previously known semi-definite methods, which are inconclusive when the state is separable. In our case, if the state is separable, an explicit decomposition into a mixture of separable states can be extracted. This was achieved by mapping the entanglement problem onto the mathematically well studied truncated moment problem. Additionally, a new way of writing the partially transposed state for symmetric multi-qubit states was developed which simplifies many results previously known in entanglement theory. This new way of writing the partial transpose criterion unifies different interpretations and alternative formulations of the partial transpose criterion and it is also a part in the aforementioned semi-definite algorithm. The geometric properties of entangled symmetric states of two qubits were studied in detail: We could answer the question of how far a given pure state is from the convex hull of symmetric separable states, as measured by the Hilbert-Schmidt distance, by giving an explicit formula for the closest separable symmetric state. For mixed states we could provide a numerical upper and analytical lower bound for this distance. For a larger number of qubits we investigated the ball of absolutely classical states, i.e. symmetric multi-qubit states that stay separable under any unitary transformation. We found an analytical lower bound for the radius of this ball around the maximally mixed symmetric state and gave a numerical upper bound on this radius, by searching for an entangled state as close as possible to the maximally mixed symmetric state. The tensor representation of a symmetric multi-qubit state, or spin-j state, allowed us to study entanglement properties based on the spectrum of the tensor via tensor eigenvalues. The definiteness of this tensor relates to the entanglement of the state it represents and, hence, the smallest tensor eigenvalue can be used to detect entanglement. However, the tensor eigenvalues are more difficult to determine than the familiar matrix eigenvalues which made the investigation computationally more challenging. The relationship between the value of the smallest tensor eigenvalue and the amount of entanglement in the state was also investigated. It turned out that they are strongly correlated for small system sizes, i.e. for up to six qubits. However, to investigate this correlation we needed an independent way to gauge the amount of entanglement of a state and in order to do so we improved existing numerical methods to determine the distance of a state to the set of separable symmetric states, using a combination of linear and quadratic programming. The tensor representation of symmetric multi-qubit states was also used to formally define a new tensor class of regularly decomposable tensors that corresponds to the set of separable symmetric multi-qubit states.

•Sep 29, 2017•0 citations

On the Hardness of the Quantum Separability Problem and the Global Power of Locally Invariant Unitary Operations

Sevag Gharibian

Given a bipartite density matrix ρ of a quantum state, the Quantum Separability \nproblem (QUSEP) asks — is ρ entangled, or separable? In this thesis, we first \nstrengthen Gurvits’ 2003 NP-hardness result for QUSEP by showing that the Weak \nMembership problem over the set of separable bipartite quantum states is strongly \nNP-hard, meaning it is NP-hard even when the error margin is as large as inverse \npolynomial in the dimension, i.e. is “moderately large”. Previously, this NP-hardness was known only to hold in the case of inverse exponential error. We observe \nthe immediate implication of NP-hardness of the Weak Membership problem over the set of entanglement-breaking maps, as well as lower bounds on the maximum (Euclidean) distance possible between a bound entangled state and the separable set of quantum states (assuming P ≠ NP). \n \nWe next investigate the entanglement-detecting capabilities of locally invariant \nunitary operations, as proposed by Fu in 2006. Denoting the subsystems of ρ as \nA and B, such that ρ_B = Tr_A(ρ), a locally invariant unitary operation U^B is one \nwith the property U^B ρ_B (U^B)^† = ρ_B. We investigate the maximum shift (in Euclidean \ndistance) inducible in ρ by applying I⊗U^B, over all locally invariant choices of U^B. \nWe derive closed formulae for this quantity for three cases of interest: (pseudo)pure \nquantum states of arbitrary dimension, Werner states of arbitrary dimension, and \ntwo-qubit states. Surprisingly, similar to recent anomalies detected for non-locality \nmeasures, the first of these formulae demonstrates the existence of non-maximally \nentangled states attaining shifts as large as maximally entangled ones. Using the latter of these formulae, we demonstrate for certain classes of two-qubit states an equivalence between the Fu criterion and the CHSH inequality. Among other results, we investigate the ability of locally invariant unitary operations to detect bound entanglement.

•Sep 18, 2008•0 citations
In this paper, we present progress on the study of the symmetric extension criterion for separability. First, we show that a perturbation of order O(1/N)O(1/N)O(1/N) is sufficient and, in general, necessary to destroy the entanglement of any state admitting an NNN Bose-symmetric extension. On the other hand, the minimum amount of local noise necessary to induce separability on states arising from NNN Bose-symmetric extensions with positive partial transpose (PPT) decreases at least as fast as O(1/N2)O(1/{N}^{2})O(1/N2). From these results, we derive upper bounds on the time and space complexity of the weak membership problem of separability when attacked via algorithms that search for PPT-symmetric extensions. Finally, we show how to estimate the error we incur when we approximate the set of separable states by the set of (PPT) NNN-extendable quantum states in order to compute the maximum average fidelity in pure state estimation problems, the maximal output purity of quantum channels, and the geometric measure of entanglement.
In the realm of quantum information theory, the detection and quantification of quantum entanglement stand as paramount tasks. The relative entropy of entanglement (REE) serves as a prominent measure of entanglement, with extensive applications spanning numerous related fields. The positive partial transpose (PPT) criterion, while providing an efficient method for the computation of REE, unfortunately, falls short when dealing with bound entanglement. In this study, we propose a method termed “pure bosonic extension” to enhance the practicability of k -bosonic extensions, which approximates the set of separable states from the “outside”, through a hierarchical structure. It enables efficient characterization of the set of k -bosonic extendible states, facilitating the derivation of accurate lower bounds for REE. Compared to the semi-definite programming (SDP) approach, such as the symmetric/bosonic extension function in QETLAB, our algorithm supports much larger dimensions and higher values of extension k . Published by the American Physical Society 2024
The idea of detecting the entanglement of a given bipartite state by searching for symmetric extensions of this state was first proposed by Doherty et al. The complete family of separability tests it generates, often referred to as the hierarchy of [Formula: see text]-extendibility tests, has already proved to be most promising. The goal of this paper is to try and quantify the efficiency of this separability criterion in typical scenarios. For that, we essentially take two approaches. First, we compute the average width of the set of [Formula: see text]-extendible states, in order to see how it scales with the one of separable states. And second, we characterize when random-induced states are, depending on the ancilla dimension, with high probability violating or not the [Formula: see text]-extendibility test, and compare the obtained result with the corresponding one for entanglement vs separability. The main results can be precisely phrased as follows: on [Formula: see text], when [Formula: see text] grows, the average width of the set of [Formula: see text]-extendible states is equivalent to [Formula: see text], while random states obtained as partial traces over an environment [Formula: see text] of uniformly distributed pure states are violating the [Formula: see text]-extendibility test with probability going to [Formula: see text] if [Formula: see text]. Both statements converge to the conclusion that, if [Formula: see text] is fixed, [Formula: see text]-extendibility is asymptotically a weak approximation of separability, even though any of the other well-studied separability relaxations is outperformed by [Formula: see text]-extendibility as soon as [Formula: see text] is above a certain (dimension independent) value.
We provide quantitative bounds on the characterization of multiparticle separable states by states that have locally symmetric extensions. The bounds are derived from two-particle bounds and relate to recent studies on quantum versions of de Finetti's theorem. We discuss algorithmic applications of our results, in particular a quasipolynomial-time algorithm to decide whether a multiparticle quantum state is separable or entangled (for constant number of particles and constant error in the norm induced by one-way local operations and classical communication, or in the Frobenius norm). Our results provide a theoretical justification for the use of the search for symmetric extensions as a test for multiparticle entanglement.
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.
The main topic of this compilation thesis is the investigation of multipartite entanglement of finite dimensional systems. We developed a numerical algorithm that detects if a multipartite state is entangled or separable in a finite number of steps of a semi-definite optimization task. This method is an extension of previously known semi-definite methods, which are inconclusive when the state is separable. In our case, if the state is separable, an explicit decomposition into a mixture of separable states can be extracted. This was achieved by mapping the entanglement problem onto the mathematically well studied truncated moment problem. Additionally, a new way of writing the partially transposed state for symmetric multi-qubit states was developed which simplifies many results previously known in entanglement theory. This new way of writing the partial transpose criterion unifies different interpretations and alternative formulations of the partial transpose criterion and it is also a part in the aforementioned semi-definite algorithm. The geometric properties of entangled symmetric states of two qubits were studied in detail: We could answer the question of how far a given pure state is from the convex hull of symmetric separable states, as measured by the Hilbert-Schmidt distance, by giving an explicit formula for the closest separable symmetric state. For mixed states we could provide a numerical upper and analytical lower bound for this distance. For a larger number of qubits we investigated the ball of absolutely classical states, i.e. symmetric multi-qubit states that stay separable under any unitary transformation. We found an analytical lower bound for the radius of this ball around the maximally mixed symmetric state and gave a numerical upper bound on this radius, by searching for an entangled state as close as possible to the maximally mixed symmetric state. The tensor representation of a symmetric multi-qubit state, or spin-j state, allowed us to study entanglement properties based on the spectrum of the tensor via tensor eigenvalues. The definiteness of this tensor relates to the entanglement of the state it represents and, hence, the smallest tensor eigenvalue can be used to detect entanglement. However, the tensor eigenvalues are more difficult to determine than the familiar matrix eigenvalues which made the investigation computationally more challenging. The relationship between the value of the smallest tensor eigenvalue and the amount of entanglement in the state was also investigated. It turned out that they are strongly correlated for small system sizes, i.e. for up to six qubits. However, to investigate this correlation we needed an independent way to gauge the amount of entanglement of a state and in order to do so we improved existing numerical methods to determine the distance of a state to the set of separable symmetric states, using a combination of linear and quadratic programming. The tensor representation of symmetric multi-qubit states was also used to formally define a new tensor class of regularly decomposable tensors that corresponds to the set of separable symmetric multi-qubit states.
Given a bipartite density matrix ρ of a quantum state, the Quantum Separability \nproblem (QUSEP) asks — is ρ entangled, or separable? In this thesis, we first \nstrengthen Gurvits’ 2003 NP-hardness result for QUSEP by showing that the Weak \nMembership problem over the set of separable bipartite quantum states is strongly \nNP-hard, meaning it is NP-hard even when the error margin is as large as inverse \npolynomial in the dimension, i.e. is “moderately large”. Previously, this NP-hardness was known only to hold in the case of inverse exponential error. We observe \nthe immediate implication of NP-hardness of the Weak Membership problem over the set of entanglement-breaking maps, as well as lower bounds on the maximum (Euclidean) distance possible between a bound entangled state and the separable set of quantum states (assuming P ≠ NP). \n \nWe next investigate the entanglement-detecting capabilities of locally invariant \nunitary operations, as proposed by Fu in 2006. Denoting the subsystems of ρ as \nA and B, such that ρ_B = Tr_A(ρ), a locally invariant unitary operation U^B is one \nwith the property U^B ρ_B (U^B)^† = ρ_B. We investigate the maximum shift (in Euclidean \ndistance) inducible in ρ by applying I⊗U^B, over all locally invariant choices of U^B. \nWe derive closed formulae for this quantity for three cases of interest: (pseudo)pure \nquantum states of arbitrary dimension, Werner states of arbitrary dimension, and \ntwo-qubit states. Surprisingly, similar to recent anomalies detected for non-locality \nmeasures, the first of these formulae demonstrates the existence of non-maximally \nentangled states attaining shifts as large as maximally entangled ones. Using the latter of these formulae, we demonstrate for certain classes of two-qubit states an equivalence between the Fu criterion and the CHSH inequality. Among other results, we investigate the ability of locally invariant unitary operations to detect bound entanglement.