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:quant-ph/0602223 · Physical Review A

Quantum separability and entanglement detection via entanglement-witness search and global optimization

Lawrence M. Ioannou, B. C. Travaglione

Published May 23, 2006• 28 citations
arXivHTMLPDF

Abstract

We focus on determining the separability of an unknown bipartite quantum state $\ensuremath{\rho}$ by invoking a sufficiently large subset of all possible entanglement witnesses given the expected value of each element of a set of mutually orthogonal observables. We review the concept of an entanglement witness from the geometrical point of view and use this geometry to show that the set of separable states is not a polytope and to characterize the class of entanglement witnesses (observables) that detect entangled states on opposite sides of the set of separable states. All this serves to motivate a classical algorithm which, given the expected values of a subset of an orthogonal basis of observables of an otherwise unknown quantum state, searches for an entanglement witness in the span of the subset of observables. The idea of such an algorithm, which is an efficient reduction of the quantum separability problem to a global optimization problem, was introduced by [Ioannou et al., Phys. Rev. A 70, 060303(R)], where it was shown to be an improvement on the naive approach for the quantum separability problem (exhaustive search for a decomposition of the given state into a convex combination of separable states). The last section of the paper discusses in more generality such algorithms, which, in our case, assume a subroutine that computes the global maximum of a real function of several variables. Despite this, we anticipate that such algorithms will perform sufficiently well on small instances that they will render a feasible test for separability in some cases of interest (e.g., in $3\ifmmode\times\else\texttimes\fi{}3$ dimensional systems).

DOI
10.1103/physreva.73.052314

Related papers

Computing finite-dimensional bipartite quantum separability

Lawrence M. Ioannou

Ever since entanglement was identified as a computational and cryptographic resource, effort has been made to find an efficient way to tell whether a given density matrix represents an unentangled, or separable, state. Essentially, this is the quantum separability problem. Chapters 1 to 3 motivate a new interior-point algorithm which, given the expected values of a subset of an orthogonal basis of observables of an otherwise unknown quantum state, searches for an entanglement witness in the span of the subset of observables. When all the expected values are known, the algorithm solves the separability problem. In Chapter 4, I give the motivation for the algorithm and show how it can be used in a particular physical scenario to detect entanglement (or decide separability) of an unknown quantum state using as few quantum resources as possible. I then explain the intuitive idea behind the algorithm and relate it to the standard algorithms of its kind. I end the chapter with a comparison of the complexities of the algorithms surveyed in Chapter 3. Finally, in Chapter 5, I present the details of the algorithm and discuss its performance relative to standard methods.

arXiv:cs/0504110•Apr 29, 2005•4 citations

A Note on Quantum Separability

Lawrence M. Ioannou, B. C. Travaglione

This short note describes a method to tackle the (bipartite) quantum separability problem. The method can be used for solving the separability problem in an experimental setting as well as in the purely mathematical setting. The idea is to invoke the following characterization of entangled states: A state is entangled if and only if there exists an entanglement witness that detects it. The method is basically a search for an entanglement witness that detects the given state.

arXiv:quant-ph/0311184•Nov 26, 2003•0 citations

Detecting quantum entanglement : entanglement witnesses and uncertainty relations

Otfried Gühne

This thesis deals with methods of the detection of entanglement.After recalling some facts and definitions concerning entanglement and separability, we investigate two methods of the detection of entanglement.In the first part of this thesis we consider so-called entanglement witnesses, mainly in view of the detection of multipartite entanglement.Entanglement witnesses are observables for which a negative expectation value indicates entanglement.We first present a simple method to construct these witnesses.Since witnesses are nonlocal observables, they are not easy to measure in a real experiment.However, as we will show, one can circumvent this problem by decomposing the witness into several local observables which can be measured separately.We calculate the local decompositions for several interesting witnesses for two, three and four qubits.Local decompositions can be optimized in the number of measurement settings which are needed for an experimental implementation.We present a method to prove that a given local decomposition is optimal and discuss with this the optimality of our decompositions.Then we present another method of designing witnesses which are by construction measurable with local measurements.Finally, we shortly report on experiments where some of the witnesses derived in this part have been used to detect three-and four-partite entanglement of polarized photons.The second part of this thesis deals with separability criteria which are written in terms of uncertainty relations.There are two different formulations of uncertainty relations since one can measure the uncertainty of an observable by its variance as well as by entropic quantities.We show that both formulations are useful tools for the derivation of separability criteria for finite-dimensional systems and investigate the resulting criteria.Our results in this part exhibit also some more fundamental properties of entanglement: We show how known separability criteria for infinitedimensional systems can be translated to finite-dimensional systems.Furthermore, we prove that any entropic uncertainty relation on one part of the system gives rise to a separability criterion on the composite system.

•Jan 1, 2004•3 citations

Entanglement Detection by Approximate Entanglement Witnesses

Samuel Dai, Ning Bao

The problem of determining whether a given quantum state is separable is known to be computationally difficult. We develop an approach to this problem based on approximations of convex polytopes in high dimensions. By showing that a convex polytope constructed from a finite number of hyperplanes approximates the Euclidean ball arbitrarily well in high dimensions, we find evidence that a finite set of approximate entanglement witnesses is potentially sufficient to determine the entanglement of a state with high probability.

arXiv:2402.14755•Feb 22, 2024•1 citation

Computational complexity of the quantum separability problem

Lawrence M. Ioannou

Ever since entanglement was identified as a computational and cryptographic resource, researchers have sought efficient ways to tell whether a given density matrix represents an unentangled, or separable, state. This paper gives the first systematic and comprehensive treatment of this (bipartite) quantum separability problem, focusing on its deterministic (as opposed to randomized) computational complexity. First, I review the one-sided tests for separability, paying particular attention to the semidefinite programming methods. Then, I discuss various ways of formulating the quantum separability problem, from exact to approximate formulations, the latter of which are the paper's main focus. I then give a thorough treatment of the problem's relationship with the complexity classes NP, NP-complete, and co-NP. I also discuss extensions of Gurvits' NP-hardness result to strong NP-hardness of certain related problems. A major open question is whether the NP-contained formulation (QSEP) of the quantum separability problem is Karp-NP-complete; QSEP may be the first natural example of a problem that is Turing-NP-complete but not Karp-NP-complete. Finally, I survey all the proposed (deterministic) algorithms for the quantum separability problem, including the bounded search for symmetric extensions (via semidefinite programming), based on the recent quantum de Finetti theorem; and the entanglement-witness search (via interior-point algorithms and global optimization). These two algorithms have the lowest complexity, with the latter being the best under advice of asymptotically optimal point-coverings of the sphere.

arXiv:quant-ph/0603199•Mar 22, 2006•0 citations

Internal Boundary Between Entanglement and Separability Within a Quantum State

Bang-Hai Wang

Quantum states are the key mathematical objects in quantum mechanics, and entanglement lies at the heart of the nascent fields of quantum information processing and computation. However, there has not been a general, necessary and sufficient, and operational separability condition to determine whether an arbitrary quantum state is entangled or separable. In this paper, we show that whether a quantum state is entangled or not is determined by a threshold within the quantum state. We first introduce the concept of finer and optimal separable states based on the properties of separable states in the role of higher-level witnesses. Then we show that any bipartite quantum state can be decomposed into a convex mixture of its optimal entangled state and its optimal separable state. Furthermore, we show that whether an arbitrary quantum state is entangled or separable, as well as positive partial transposition (PPT) or not, is determined by the robustness of its optimal entangled state to its optimal separable state with reference to a crucial threshold. Moreover, for an arbitrary quantum state, we provide operational algorithms to obtain its optimal entangled state, its optimal separable state, its best separable approximation (BSA) decomposition, and its best PPT approximation decomposition. And the open question of how to calculate the BSA in high-dimension systems is partially done.

arXiv:2003.00607•IEEE Transactions on Information Theory•Sep 8, 2022•7 citations
We focus on determining the separability of an unknown bipartite quantum state \ensuremathρ\ensuremath{\rho}\ensuremathρ by invoking a sufficiently large subset of all possible entanglement witnesses given the expected value of each element of a set of mutually orthogonal observables. We review the concept of an entanglement witness from the geometrical point of view and use this geometry to show that the set of separable states is not a polytope and to characterize the class of entanglement witnesses (observables) that detect entangled states on opposite sides of the set of separable states. All this serves to motivate a classical algorithm which, given the expected values of a subset of an orthogonal basis of observables of an otherwise unknown quantum state, searches for an entanglement witness in the span of the subset of observables. The idea of such an algorithm, which is an efficient reduction of the quantum separability problem to a global optimization problem, was introduced by [Ioannou et al., Phys. Rev. A 70, 060303(R)], where it was shown to be an improvement on the naive approach for the quantum separability problem (exhaustive search for a decomposition of the given state into a convex combination of separable states). The last section of the paper discusses in more generality such algorithms, which, in our case, assume a subroutine that computes the global maximum of a real function of several variables. Despite this, we anticipate that such algorithms will perform sufficiently well on small instances that they will render a feasible test for separability in some cases of interest (e.g., in 3\ifmmode×\else\texttimes\fi33\ifmmode\times\else\texttimes\fi{}33\ifmmode×\else\texttimes\fi3 dimensional systems).
Ever since entanglement was identified as a computational and cryptographic resource, effort has been made to find an efficient way to tell whether a given density matrix represents an unentangled, or separable, state. Essentially, this is the quantum separability problem. Chapters 1 to 3 motivate a new interior-point algorithm which, given the expected values of a subset of an orthogonal basis of observables of an otherwise unknown quantum state, searches for an entanglement witness in the span of the subset of observables. When all the expected values are known, the algorithm solves the separability problem. In Chapter 4, I give the motivation for the algorithm and show how it can be used in a particular physical scenario to detect entanglement (or decide separability) of an unknown quantum state using as few quantum resources as possible. I then explain the intuitive idea behind the algorithm and relate it to the standard algorithms of its kind. I end the chapter with a comparison of the complexities of the algorithms surveyed in Chapter 3. Finally, in Chapter 5, I present the details of the algorithm and discuss its performance relative to standard methods.
This thesis deals with methods of the detection of entanglement.After recalling some facts and definitions concerning entanglement and separability, we investigate two methods of the detection of entanglement.In the first part of this thesis we consider so-called entanglement witnesses, mainly in view of the detection of multipartite entanglement.Entanglement witnesses are observables for which a negative expectation value indicates entanglement.We first present a simple method to construct these witnesses.Since witnesses are nonlocal observables, they are not easy to measure in a real experiment.However, as we will show, one can circumvent this problem by decomposing the witness into several local observables which can be measured separately.We calculate the local decompositions for several interesting witnesses for two, three and four qubits.Local decompositions can be optimized in the number of measurement settings which are needed for an experimental implementation.We present a method to prove that a given local decomposition is optimal and discuss with this the optimality of our decompositions.Then we present another method of designing witnesses which are by construction measurable with local measurements.Finally, we shortly report on experiments where some of the witnesses derived in this part have been used to detect three-and four-partite entanglement of polarized photons.The second part of this thesis deals with separability criteria which are written in terms of uncertainty relations.There are two different formulations of uncertainty relations since one can measure the uncertainty of an observable by its variance as well as by entropic quantities.We show that both formulations are useful tools for the derivation of separability criteria for finite-dimensional systems and investigate the resulting criteria.Our results in this part exhibit also some more fundamental properties of entanglement: We show how known separability criteria for infinitedimensional systems can be translated to finite-dimensional systems.Furthermore, we prove that any entropic uncertainty relation on one part of the system gives rise to a separability criterion on the composite system.
The problem of determining whether a given quantum state is separable is known to be computationally difficult. We develop an approach to this problem based on approximations of convex polytopes in high dimensions. By showing that a convex polytope constructed from a finite number of hyperplanes approximates the Euclidean ball arbitrarily well in high dimensions, we find evidence that a finite set of approximate entanglement witnesses is potentially sufficient to determine the entanglement of a state with high probability.
Ever since entanglement was identified as a computational and cryptographic resource, researchers have sought efficient ways to tell whether a given density matrix represents an unentangled, or separable, state. This paper gives the first systematic and comprehensive treatment of this (bipartite) quantum separability problem, focusing on its deterministic (as opposed to randomized) computational complexity. First, I review the one-sided tests for separability, paying particular attention to the semidefinite programming methods. Then, I discuss various ways of formulating the quantum separability problem, from exact to approximate formulations, the latter of which are the paper's main focus. I then give a thorough treatment of the problem's relationship with the complexity classes NP, NP-complete, and co-NP. I also discuss extensions of Gurvits' NP-hardness result to strong NP-hardness of certain related problems. A major open question is whether the NP-contained formulation (QSEP) of the quantum separability problem is Karp-NP-complete; QSEP may be the first natural example of a problem that is Turing-NP-complete but not Karp-NP-complete. Finally, I survey all the proposed (deterministic) algorithms for the quantum separability problem, including the bounded search for symmetric extensions (via semidefinite programming), based on the recent quantum de Finetti theorem; and the entanglement-witness search (via interior-point algorithms and global optimization). These two algorithms have the lowest complexity, with the latter being the best under advice of asymptotically optimal point-coverings of the sphere.
Quantum states are the key mathematical objects in quantum mechanics, and entanglement lies at the heart of the nascent fields of quantum information processing and computation. However, there has not been a general, necessary and sufficient, and operational separability condition to determine whether an arbitrary quantum state is entangled or separable. In this paper, we show that whether a quantum state is entangled or not is determined by a threshold within the quantum state. We first introduce the concept of finer and optimal separable states based on the properties of separable states in the role of higher-level witnesses. Then we show that any bipartite quantum state can be decomposed into a convex mixture of its optimal entangled state and its optimal separable state. Furthermore, we show that whether an arbitrary quantum state is entangled or separable, as well as positive partial transposition (PPT) or not, is determined by the robustness of its optimal entangled state to its optimal separable state with reference to a crucial threshold. Moreover, for an arbitrary quantum state, we provide operational algorithms to obtain its optimal entangled state, its optimal separable state, its best separable approximation (BSA) decomposition, and its best PPT approximation decomposition. And the open question of how to calculate the BSA in high-dimension systems is partially done.