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

Developing Entanglement Verification for Large Bipartite Systems

Thomas E. Edwards

Published Jan 1, 2012• 0 citations
OpenAlex

Abstract

It is a major problem within the field of Quantum Information whether the state of a system is entangled or separable. Exact methods have been developed for two qubit systems, but for larger systems determining the boundary between separable and entangled states has been shown to be NP-hard. An iterative method has been proposed that creates progressively tighter bounds from each direction, but this method is resource limited, and determining the boundary precisely requires an infinite number of iterations. Further, it is also believed that successive iterations scale badly. Instead, a weighted measure is developed over the delineated subspaces, producing a likelihood function by convex optimization. This presentation describes progress towards understanding and deploying this method in support of experimental work involving entangled states.

Related papers

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

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

Large-Scale Quantum Separability Through a Reproducible Machine Learning Lens

Balthazar Casalé, Giuseppe Di Molfetta, Sandrine Anthoine +1 more

The quantum separability problem consists in deciding whether a bipartite density matrix is entangled or separable. In this work, we propose a machine learning pipeline for finding approximate solutions for this NP-hard problem in large-scale scenarios. We provide an efficient Frank-Wolfe-based algorithm to approximately seek the nearest separable density matrix and derive a systematic way for labeling density matrices as separable or entangled, allowing us to treat quantum separability as a classification problem. Our method is applicable to any two-qudit mixed states. Numerical experiments with quantum states of 3- and 7-dimensional qudits validate the efficiency of the proposed procedure, and demonstrate that it scales up to thousands of density matrices with a high quantum entanglement detection accuracy. This takes a step towards benchmarking quantum separability to support the development of more powerful entanglement detection techniques.

arXiv:2306.09444•Jun 15, 2023•0 citations

Geometric Optimization over Quantum State Spaces: Tight Uncertainty Relations and Resource Certification

Ma-Cheng Yang, Cong-Feng Qiao

Determining the fundamental limits of nonlinear functionals of quantum measurement statistics is a crucial yet generally intractable nonconvex optimization problem. We introduce a generic support-function-based outer-approximation framework for solving concave-minimization (or convex-maximization) problems over the quantum state space. By mapping the problem onto a reduced $\mathcal{Z}$ space, we characterize the exact quantum boundary through supporting half space derived from the largest eigenvalues of effective observables. This yields an effective method that produces tight bounds for general measurements in finite-dimensional quantum systems with preassigned numerical precision. As an initial application, we recover the exact variance-based uncertainty relations of [PRL \textbf{119}, 170404 (2017)] and efficiently compute optimal entropic uncertainty relations (EURs). Our results reveal that standard analytical and majorization-based EUR bounds are fundamentally loose for generic measurements, and we show that the resulting exact bounds directly enhance quantum steering detection under asymmetric settings. We further apply the framework to determine the maximal athermality resource certifiable from a restricted measurement scenario. Our method thus provides a universal computational tool for exploring the boundaries of quantum state space and the limits of quantum resources.

quant-pharXiv:2602.00595•Physical Review Letters•Feb 3, 2026•0 citations

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 NP, NP-completeness, 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 [1, 2, 3]; and the entanglement-witness search (via interior-point algorithms and global optimization) [4, 5]. These two algorithms have the lowest complexity, with the latter being the best under advice of asymptotically optimal point-coverings of the sphere.

Quantum Information and Computation•May 1, 2007•68 citations
It is a major problem within the field of Quantum Information whether the state of a system is entangled or separable. Exact methods have been developed for two qubit systems, but for larger systems determining the boundary between separable and entangled states has been shown to be NP-hard. An iterative method has been proposed that creates progressively tighter bounds from each direction, but this method is resource limited, and determining the boundary precisely requires an infinite number of iterations. Further, it is also believed that successive iterations scale badly. Instead, a weighted measure is developed over the delineated subspaces, producing a likelihood function by convex optimization. This presentation describes progress towards understanding and deploying this method in support of experimental work involving entangled states.
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.
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.
The quantum separability problem consists in deciding whether a bipartite density matrix is entangled or separable. In this work, we propose a machine learning pipeline for finding approximate solutions for this NP-hard problem in large-scale scenarios. We provide an efficient Frank-Wolfe-based algorithm to approximately seek the nearest separable density matrix and derive a systematic way for labeling density matrices as separable or entangled, allowing us to treat quantum separability as a classification problem. Our method is applicable to any two-qudit mixed states. Numerical experiments with quantum states of 3- and 7-dimensional qudits validate the efficiency of the proposed procedure, and demonstrate that it scales up to thousands of density matrices with a high quantum entanglement detection accuracy. This takes a step towards benchmarking quantum separability to support the development of more powerful entanglement detection techniques.
Determining the fundamental limits of nonlinear functionals of quantum measurement statistics is a crucial yet generally intractable nonconvex optimization problem. We introduce a generic support-function-based outer-approximation framework for solving concave-minimization (or convex-maximization) problems over the quantum state space. By mapping the problem onto a reduced Z\mathcal{Z}Z space, we characterize the exact quantum boundary through supporting half space derived from the largest eigenvalues of effective observables. This yields an effective method that produces tight bounds for general measurements in finite-dimensional quantum systems with preassigned numerical precision. As an initial application, we recover the exact variance-based uncertainty relations of [PRL \textbf{119}, 170404 (2017)] and efficiently compute optimal entropic uncertainty relations (EURs). Our results reveal that standard analytical and majorization-based EUR bounds are fundamentally loose for generic measurements, and we show that the resulting exact bounds directly enhance quantum steering detection under asymmetric settings. We further apply the framework to determine the maximal athermality resource certifiable from a restricted measurement scenario. Our method thus provides a universal computational tool for exploring the boundaries of quantum state space and the limits of quantum resources.
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 NP, NP-completeness, 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 [1, 2, 3]; and the entanglement-witness search (via interior-point algorithms and global optimization) [4, 5]. These two algorithms have the lowest complexity, with the latter being the best under advice of asymptotically optimal point-coverings of the sphere.