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/0403041 · Physical Review A

Improved algorithm for quantum separability and entanglement detection

Lawrence M. Ioannou, B. C. Travaglione, Donny Cheung, ARTUR K. EKERT

Published Dec 15, 2004• 32 citations
arXivHTMLPDF

Abstract

Determining whether a quantum state is separable or entangled is a problem of fundamental importance in quantum information science. It has recently been shown that this problem is NP-hard, suggesting that an efficient, general solution does not exist. There is a highly inefficient ``basic algorithm'' for solving the quantum separability problem which follows from the definition of a separable state. By exploiting specific properties of the set of separable states, we introduce a classical algorithm that solves the problem significantly faster than the ``basic algorithm,'' allowing a feasible separability test where none previously existed, e.g., in $3\ifmmode\times\else\texttimes\fi{}3$-dimensional systems. Our algorithm also provides a unique tool in the experimental detection of entanglement.

DOI
10.1103/physreva.70.060303

Related papers

A probabilistic approach to detecting quantum entanglement

A. H. McDonald

A key concept in quantum information theory is the notion of separable states; states for which there is no quantum entanglement.Determining if a given state is entangled has been shown to be NP-hard, and so no deterministic and efficient algorithm will likely be created for this purpose.Current tests are either computationally intensive , return false positives or worsen as the dimension of the problem grows larger.These large dimensions arise naturally in quantum computing.It is therefore necessary to develop a reliable test that is naturally scalable to higher dimensions if one wishes to create efficient quantum computers.Using random matrix theory, a new algorithm has been developed that, with high probability, can determine if a quantum state is separable or entangled.The purpose of this research is to implement this algorithm, checking its efficiency through numerical tests, as well as testing the limitations of the theory behind it.

•Apr 14, 2014•0 citations

Separability-entanglement classifier via machine learning

Sirui Lu, Shilin Huang, Keren Li +7 more

The problem of determining whether a given quantum state is entangled lies at the heart of quantum information processing. Despite the many methods---such as the positive partial transpose criterion and the $k$-symmetric extendibility criterion---to tackle this problem, none of them enables a general, practical solution due to the problem's NP-hard complexity. Explicitly, separable states form a high-dimensional convex set of vastly complicated structures. In this work, we build a different separability-entanglement classifier underpinned by machine learning techniques. We use standard tools from machine learning to learn the entanglement feature of arbitrary given quantum states. We perform substantial numerical tests on two-qubit and two-qutrit systems, and the results indicate that our method can outperform the existing methods in generic cases in terms of both speed and accuracy. This opens up avenues to explore quantum entanglement via the machine learning approach.

arXiv:1705.01523•Physical Review A•Jul 13, 2018•117 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

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

Lawrence M. Ioannou, B. C. Travaglione

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).

arXiv:quant-ph/0602223•Physical Review A•May 23, 2006•28 citations

Towards a quantum algorithm deciding the separability problem

Paweł Horodecki, Michał Banacki, Michał Eckstein +1 more

Abstract Determining whether an unknown quantum state is entangled can be approached through quantum tomography and related algorithms. However, these methods are generally inefficient due to the NP-hardness of the problem. An alternative strategy is to treat it as a decision (or estimation) problem with a quantum data structure (Horodecki and Ekert 2002 Phys. Rev. Lett. 89 127902). Over the years, significant progress has been made: the two-qubit case is now fully understood, but for higher-dimensional systems only entanglement detection via negativity has been established. In this work, we propose schemes for measuring upper bounds on bipartite biconcurrence and concurrence, expressed as functions of a fixed (but arbitrary) unitary operation acting on a Hilbert space that is quadratically larger than the original state space. Independently, we provide a scheme for measuring a lower bound for concurrence. In the case of the states proportional to the projectors the schemes are getting significantly simpler and the upper bound on the biconcurrence, as well as the lower bound on the concurrence, become exact (up to experimental and numerical errors). This framework opens the door to tackling the separability problem using methods inspired by the variational quantum eigensolver.

Quantum Science and Technology•May 15, 2026•0 citations

Free versus bound entanglement, a NP-hard problem tackled by machine learning

Beatrix C. Hiesmayr

Entanglement detection in high dimensional systems is a NP-hard problem since it is lacking an efficient way. Given a bipartite quantum state of interest free entanglement can be detected efficiently by the PPT-criterion (Peres-Horodecki criterion), in contrast to detecting bound entanglement, i.e. a curious form of entanglement that can also not be distilled into maximally (free) entangled states. Only a few bound entangled states have been found, typically by constructing dedicated entanglement witnesses, so naturally the question arises how large is the volume of those states. We define a large family of magically symmetric states of bipartite qutrits for which we find [Formula: see text] to be free entangled, [Formula: see text] to be certainly separable and as much as [Formula: see text] to be bound entangled, which shows that this kind of entanglement is not rare. Via various machine learning algorithms we can confirm that the remaining [Formula: see text] of states are more likely to belonging to the set of separable states than bound entangled states. Most important we find via dimension reduction algorithms that there is a strong two-dimensional (linear) sub-structure in the set of bound entangled states. This revealed structure opens a novel path to find and characterize bound entanglement towards solving the long-standing problem of what the existence of bound entanglement is implying.

arXiv:2106.03977•Scientific Reports•Oct 5, 2021•35 citations
Determining whether a quantum state is separable or entangled is a problem of fundamental importance in quantum information science. It has recently been shown that this problem is NP-hard, suggesting that an efficient, general solution does not exist. There is a highly inefficient basic algorithm'' for solving the quantum separability problem which follows from the definition of a separable state. By exploiting specific properties of the set of separable states, we introduce a classical algorithm that solves the problem significantly faster than the basic algorithm,'' allowing a feasible separability test where none previously existed, e.g., in 3\ifmmode×\else\texttimes\fi33\ifmmode\times\else\texttimes\fi{}33\ifmmode×\else\texttimes\fi3-dimensional systems. Our algorithm also provides a unique tool in the experimental detection of entanglement.
A key concept in quantum information theory is the notion of separable states; states for which there is no quantum entanglement.Determining if a given state is entangled has been shown to be NP-hard, and so no deterministic and efficient algorithm will likely be created for this purpose.Current tests are either computationally intensive , return false positives or worsen as the dimension of the problem grows larger.These large dimensions arise naturally in quantum computing.It is therefore necessary to develop a reliable test that is naturally scalable to higher dimensions if one wishes to create efficient quantum computers.Using random matrix theory, a new algorithm has been developed that, with high probability, can determine if a quantum state is separable or entangled.The purpose of this research is to implement this algorithm, checking its efficiency through numerical tests, as well as testing the limitations of the theory behind it.
The problem of determining whether a given quantum state is entangled lies at the heart of quantum information processing. Despite the many methods---such as the positive partial transpose criterion and the kkk-symmetric extendibility criterion---to tackle this problem, none of them enables a general, practical solution due to the problem's NP-hard complexity. Explicitly, separable states form a high-dimensional convex set of vastly complicated structures. In this work, we build a different separability-entanglement classifier underpinned by machine learning techniques. We use standard tools from machine learning to learn the entanglement feature of arbitrary given quantum states. We perform substantial numerical tests on two-qubit and two-qutrit systems, and the results indicate that our method can outperform the existing methods in generic cases in terms of both speed and accuracy. This opens up avenues to explore quantum entanglement via the machine learning approach.
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).
Abstract Determining whether an unknown quantum state is entangled can be approached through quantum tomography and related algorithms. However, these methods are generally inefficient due to the NP-hardness of the problem. An alternative strategy is to treat it as a decision (or estimation) problem with a quantum data structure (Horodecki and Ekert 2002 Phys. Rev. Lett. 89 127902). Over the years, significant progress has been made: the two-qubit case is now fully understood, but for higher-dimensional systems only entanglement detection via negativity has been established. In this work, we propose schemes for measuring upper bounds on bipartite biconcurrence and concurrence, expressed as functions of a fixed (but arbitrary) unitary operation acting on a Hilbert space that is quadratically larger than the original state space. Independently, we provide a scheme for measuring a lower bound for concurrence. In the case of the states proportional to the projectors the schemes are getting significantly simpler and the upper bound on the biconcurrence, as well as the lower bound on the concurrence, become exact (up to experimental and numerical errors). This framework opens the door to tackling the separability problem using methods inspired by the variational quantum eigensolver.
Entanglement detection in high dimensional systems is a NP-hard problem since it is lacking an efficient way. Given a bipartite quantum state of interest free entanglement can be detected efficiently by the PPT-criterion (Peres-Horodecki criterion), in contrast to detecting bound entanglement, i.e. a curious form of entanglement that can also not be distilled into maximally (free) entangled states. Only a few bound entangled states have been found, typically by constructing dedicated entanglement witnesses, so naturally the question arises how large is the volume of those states. We define a large family of magically symmetric states of bipartite qutrits for which we find [Formula: see text] to be free entangled, [Formula: see text] to be certainly separable and as much as [Formula: see text] to be bound entangled, which shows that this kind of entanglement is not rare. Via various machine learning algorithms we can confirm that the remaining [Formula: see text] of states are more likely to belonging to the set of separable states than bound entangled states. Most important we find via dimension reduction algorithms that there is a strong two-dimensional (linear) sub-structure in the set of bound entangled states. This revealed structure opens a novel path to find and characterize bound entanglement towards solving the long-standing problem of what the existence of bound entanglement is implying.