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

A probabilistic approach to detecting quantum entanglement

A. H. McDonald

Published Apr 14, 2014• 0 citations
OpenAlex

Abstract

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.

Related papers

Improved algorithm for quantum separability and entanglement detection

Lawrence M. Ioannou, B. C. Travaglione, Donny Cheung +1 more

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.

arXiv:quant-ph/0403041•Physical Review A•Dec 15, 2004•38 citations

DETERMINISTIC COMPUTATIONAL COMPLEXITY OF THE QUANTUM SEPARABILITY PROBLEM

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. In Section 1, I begin with a brief introduction to separability and entanglement, and a basic formal definition of the quantum separability problem. I conclude with a summary of one-sided tests for separability, including those involving semidefinite programming. In Section 2, I treat the separability problem as a computational decision problem and motivate its approximate formulations. After a review of basic complexity-theoretic notions, I discuss the computational complexity of the separability problem. In Section 3, I give a comprehensive survey of deterministic algorithmic solutions to the (approximate) quantum separability problem. Finally, Section 4 contains a comparison of the complexities of the algorithms surveyed in Section 3. I have attempted to give a comprehensive treatment of the deterministic quantum separability problem from a computational perspective and identify relevant open problems. Features and new results include:

•Mar 22, 2006•4 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•9 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•131 citations

Detection of quantum correlations

Aleksandra Dimić

One of the main foci of modern applied quantum information theory\nis the production of large-scale quantum entanglement involving many\nparticles, to achieve the next-generation quantum technologies. Although a full-scale quantum computer is still far away in time, in the next\nfew years we can expect to have quantum devices composed of up to a\nhundred controllable qubits. The primary challenge in moving towards\nsuch devices lies in the development of reliable and resource-efficient\ndetection techniques to prove genuine quantum advantage. The main\nobjective of this thesis is to investigate novel methods to detect the presence of quantum correlations in such systems, in particular, quantum\nentanglement and quantum nonlocality.\nThe first part of this thesis is dedicated to entanglement detection\nin large-scale quantum systems. Our main goal is to develop a novel\nprobabilistic method in which entanglement is seen as an ability of a\nquantum system to accomplish certain information-processing tasks.\nWe show that for certain classes of large (e.g. few tens of qubits) quantum states, even a single copy of a quantum state suffices to detect\nentanglement with a high confidence. Compared to the standard detection methods, this makes our method exceptionally resource-efficient.\nThe developed probabilistic scheme applies to multiple classes of states, vital for quantum computation, such as cluster states or ground\nstates of local Hamiltonians.\nIn the second part of this thesis, we develop a generic framework\nfor translating any entanglement witness into a resource-efficient probabilistic scheme. We show that the confidence level of entanglement\ndetection grows exponentially fast with the number of detection events,\nwhich makes this ansatz very efficient and reliable. Furthermore, we\npresent the first experimental performance of our method by verifying\nthe presence of entanglement in a photonic six-qubit cluster state.\nThe third part of this thesis describes the extension of our entanglement verification method to quantum nonlocality. Concrete examples\nare presented where we convert Bell’s inequalities into the probabilistic\nprocedure and incorporate our method into self-testing schemes. We\nshow that the performance of our method significantly exceeds the ability of the existing methods for detection of quantum nonlocality and\nself-testing.\nThe last part of this thesis is a study of the weak-convergence properties of random variables generated by quantum measurements. Beginning with a sequence of random variables generated by repeated\nunsharp quantum measurements, we study the limit distribution of\nmeasured relative frequency. We provide the de Finetti-type of representation theorem for all separable states, showing that the measured\ndistribution can be well approximated by a mixture of normal distributions. Additionally, we investigate the convergence rates and show\nthat the relative frequency converges to some constant at the rate of\norder 1=pN for all separable inputs. Finally, we provide an example of\na strictly unsharp quantum measurement where we obtain better scaling by using entangled inputs. We find such behaviour of entangled\nstates relevant for quantum information processing.

•Sep 13, 2019•0 citations

Convex semidefinite tensor optimization and quantum entanglement

Liding Xu, Ye-Chao Liu, Sebastian Pokutta

The cone of positive-semidefinite (PSD) matrices is fundamental in convex optimization, and we extend this notion to tensors, defining PSD tensors, which correspond to separable quantum states. We study the convex optimization problem over the PSD tensor cone. While this convex cone admits a smooth reparameterization through tensor factorizations (analogous to the matrix case), it is not self-dual. Moreover, there are currently no efficient algorithms for projecting onto or testing membership in this cone, and the semidefinite tensor optimization problem, although convex, is NP-hard. To address these challenges, we develop methods for computing lower and upper bounds on the optimal value of the problem. We propose a general-purpose iterative refinement algorithm that combines a lifted alternating direction method of multipliers with a cutting-plane approach. This algorithm exploits PSD tensor factorizations to produce heuristic solutions and refine the solutions using cutting planes. Since the method requires a linear minimization oracle over PSD tensors, we design a spatial branch-and-bound algorithm based on convex relaxations and valid inequalities. Our framework allows us to study the white-noise mixing threshold, which characterizes the entanglement properties of quantum states. Numerical experiments on benchmark instances demonstrate the effectiveness of the proposed methods.

math.OCCross-listedarXiv:2511.05258•Nov 10, 2025•1 citation
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.
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.
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. In Section 1, I begin with a brief introduction to separability and entanglement, and a basic formal definition of the quantum separability problem. I conclude with a summary of one-sided tests for separability, including those involving semidefinite programming. In Section 2, I treat the separability problem as a computational decision problem and motivate its approximate formulations. After a review of basic complexity-theoretic notions, I discuss the computational complexity of the separability problem. In Section 3, I give a comprehensive survey of deterministic algorithmic solutions to the (approximate) quantum separability problem. Finally, Section 4 contains a comparison of the complexities of the algorithms surveyed in Section 3. I have attempted to give a comprehensive treatment of the deterministic quantum separability problem from a computational perspective and identify relevant open problems. Features and new results include:
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.
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.
One of the main foci of modern applied quantum information theory\nis the production of large-scale quantum entanglement involving many\nparticles, to achieve the next-generation quantum technologies. Although a full-scale quantum computer is still far away in time, in the next\nfew years we can expect to have quantum devices composed of up to a\nhundred controllable qubits. The primary challenge in moving towards\nsuch devices lies in the development of reliable and resource-efficient\ndetection techniques to prove genuine quantum advantage. The main\nobjective of this thesis is to investigate novel methods to detect the presence of quantum correlations in such systems, in particular, quantum\nentanglement and quantum nonlocality.\nThe first part of this thesis is dedicated to entanglement detection\nin large-scale quantum systems. Our main goal is to develop a novel\nprobabilistic method in which entanglement is seen as an ability of a\nquantum system to accomplish certain information-processing tasks.\nWe show that for certain classes of large (e.g. few tens of qubits) quantum states, even a single copy of a quantum state suffices to detect\nentanglement with a high confidence. Compared to the standard detection methods, this makes our method exceptionally resource-efficient.\nThe developed probabilistic scheme applies to multiple classes of states, vital for quantum computation, such as cluster states or ground\nstates of local Hamiltonians.\nIn the second part of this thesis, we develop a generic framework\nfor translating any entanglement witness into a resource-efficient probabilistic scheme. We show that the confidence level of entanglement\ndetection grows exponentially fast with the number of detection events,\nwhich makes this ansatz very efficient and reliable. Furthermore, we\npresent the first experimental performance of our method by verifying\nthe presence of entanglement in a photonic six-qubit cluster state.\nThe third part of this thesis describes the extension of our entanglement verification method to quantum nonlocality. Concrete examples\nare presented where we convert Bell’s inequalities into the probabilistic\nprocedure and incorporate our method into self-testing schemes. We\nshow that the performance of our method significantly exceeds the ability of the existing methods for detection of quantum nonlocality and\nself-testing.\nThe last part of this thesis is a study of the weak-convergence properties of random variables generated by quantum measurements. Beginning with a sequence of random variables generated by repeated\nunsharp quantum measurements, we study the limit distribution of\nmeasured relative frequency. We provide the de Finetti-type of representation theorem for all separable states, showing that the measured\ndistribution can be well approximated by a mixture of normal distributions. Additionally, we investigate the convergence rates and show\nthat the relative frequency converges to some constant at the rate of\norder 1=pN for all separable inputs. Finally, we provide an example of\na strictly unsharp quantum measurement where we obtain better scaling by using entangled inputs. We find such behaviour of entangled\nstates relevant for quantum information processing.
The cone of positive-semidefinite (PSD) matrices is fundamental in convex optimization, and we extend this notion to tensors, defining PSD tensors, which correspond to separable quantum states. We study the convex optimization problem over the PSD tensor cone. While this convex cone admits a smooth reparameterization through tensor factorizations (analogous to the matrix case), it is not self-dual. Moreover, there are currently no efficient algorithms for projecting onto or testing membership in this cone, and the semidefinite tensor optimization problem, although convex, is NP-hard. To address these challenges, we develop methods for computing lower and upper bounds on the optimal value of the problem. We propose a general-purpose iterative refinement algorithm that combines a lifted alternating direction method of multipliers with a cutting-plane approach. This algorithm exploits PSD tensor factorizations to produce heuristic solutions and refine the solutions using cutting planes. Since the method requires a linear minimization oracle over PSD tensors, we design a spatial branch-and-bound algorithm based on convex relaxations and valid inequalities. Our framework allows us to study the white-noise mixing threshold, which characterizes the entanglement properties of quantum states. Numerical experiments on benchmark instances demonstrate the effectiveness of the proposed methods.