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

International Journal of Quantum Information

Extremal entanglement witnesses

Leif Ove Hansen, Andreas Hauge, Jan Myrheim, Per Øyvind Sollid

Published Dec 1, 2015• 11 citations
Publisher

Abstract

We present a study of extremal entanglement witnesses on a bipartite composite quantum system. We define the cone of witnesses as the dual of the set of separable density matrices, thus [Formula: see text] when [Formula: see text] is a witness and [Formula: see text] is a pure product state, [Formula: see text] with [Formula: see text]. The set of witnesses of unit trace is a compact convex set, uniquely defined by its extremal points. The expectation value [Formula: see text] as a function of vectors [Formula: see text] and [Formula: see text] is a positive semidefinite biquadratic form. Every zero of [Formula: see text] imposes strong real-linear constraints on f and [Formula: see text]. The real and symmetric Hessian matrix at the zero must be positive semidefinite. Its eigenvectors with zero eigenvalue, if such exist, we call Hessian zeros. A zero of [Formula: see text] is quadratic if it has no Hessian zeros, otherwise it is quartic. We call a witness quadratic if it has only quadratic zeros, and quartic if it has at least one quartic zero. A main result we prove is that a witness is extremal if and only if no other witness has the same, or a larger, set of zeros and Hessian zeros. A quadratic extremal witness has a minimum number of isolated zeros depending on dimensions. If a witness is not extremal, then the constraints defined by its zeros and Hessian zeros determine all directions in which we may search for witnesses having more zeros or Hessian zeros. A finite number of iterated searches in random directions, by numerical methods, leads to an extremal witness which is nearly always quadratic and has the minimum number of zeros. We discuss briefly some topics related to extremal witnesses, in particular the relation between the facial structures of the dual sets of witnesses and separable states. We discuss the relation between extremality and optimality of witnesses, and a conjecture of separability of the so-called structural physical approximation (SPA) of an optimal witness. Finally, we discuss how to treat the entanglement witnesses on a complex Hilbert space as a subset of the witnesses on a real Hilbert space.

DOI
10.1142/s0219749915500604

Related papers

Extremal entanglement witnesses

Leif Ove Hansen, Andreas Hauge, Jan Myrheim +1 more

We study extremal entanglement witnesses on a bipartite quantum system. We define the cone of witnesses as the dual of the set of separable density matrices, thus $\textrm{Tr}\,Ωρ\geq 0$ when $Ω$ is a witness and $ρ$ a pure product state, $ρ=ψψ^{\dagger}$ with $ψ=ϕ\otimesχ$. The set of witnesses of unit trace is a compact convex set, defined by its extremal points. The expectation value $f(ϕ,χ)=\mathrm{Tr}\,Ωρ$ as a function of $ϕ$ and $χ$ is a nonnegative biquadratic form. Every zero of $f(ϕ,χ)$ imposes real-linear constraints on $f$ and $Ω$. The Hessian matrix at the zero must be nonnegative. Its eigenvectors with zero eigenvalue, if any, we call Hessian zeros. A zero of $f(ϕ,χ)$ is quadratic if it has no Hessian zeros, otherwise it is quartic. We call a witness quadratic if it has only quadratic zeros, and quartic otherwise. We prove that a witness is extremal if and only if no other witness has the same, or a larger, set of zeros and Hessian zeros. A quadratic extremal witness has a minimum number of isolated zeros depending on dimensions. If a witness is not extremal, the constraints defined by its zeros and Hessian zeros determine all directions in which to search for witnesses having more zeros or Hessian zeros. A finite number of iterated searches in random directions lead to an extremal witness which is usually quadratic with the minimum number of zeros. We discuss some topics related to extremal witnesses, in particular the relation between the facial structures of the dual sets of witnesses and separable states. We discuss the relation between extremality and optimality of witnesses, and a conjecture of separability of the structural physical approximation (SPA) of an optimal witness. We discuss how to treat the entanglement witnesses on a complex Hilbert space as witnesses on a real Hilbert space.

arXiv:1305.2385•May 10, 2013•3 citations

Optimal entanglement criteria from trace invariants

Bivas Mallick, Aabhas Gulati, Ion Nechita

Randomized measurement protocols give experimental access to low-degree polynomial invariants of a quantum state rather than to the state itself, which raises the question of what the best entanglement criterion is that can be built from finitely many such invariants. In this work we answer this question through convex duality. For each degree we introduce the cone of local unitary trace inequalities that are valid for separable bipartite states in all local dimensions, together with its one-matrix counterparts for Hermitian and positive semidefinite matrices. Each cone is the polar dual of a moment cone; we also determine the minimal combinatorial parametrization of the separable cone. The framework organizes the known moment criteria: the PPT criterion using the first three moments of the partial transposition is the image under an embedding of a Hankel determinant from the positive semidefinite cone to the bipartite cone, which we show to be an extremal ray, and we determine the first nontrivial separable cone completely, finding exactly four extremal rays. The framework allows us to analyze the realignment criterion and its centered (or enhanced) variant. We prove that the even singular value moments of the (centered) realignment matrix are trace invariants, associated with explicit fixed-point-free involutions. Extracting the optimal trace-norm bound from $m$ such moments thus becomes a dimension-free truncated moment problem, which we solve in closed form for $m = 2$ and relax to a semidefinite program of size $O(m)$ for arbitrary $m$. The dual solutions are polynomial minorants of $\sqrt{x}$ on $[0,1]$, and two explicit families, binomial and $L^1$-weighted, yield hierarchies of separability inequalities. Finally, we compare the criteria against one another and on PPT entangled states.

quant-pharXiv:2609.29471•Sep 25, 2026•0 citations

Visualizing extremal positive maps in unital and trace-preserving form

Leif Ove Hansen, Jan Myrheim

We define an entanglement witness in a composite quantum system as an observable having a nonnegative expectation value in every separable state. Then a state is entangled if and only if it has a negative expectation value of some entanglement witness. Equivalent representations of entanglement witnesses are nonnegative biquadratic forms or positive linear maps of Hermitian matrices. As reported elsewhere, we have studied extremal entanglement witnesses in dimension $3\ifmmode\times\else\texttimes\fi{}3$ by constructing numerical examples of generic extremal nonnegative forms. These are so complicated that we do not know how to handle them other than by numerical methods. However, the corresponding extremal positive maps can be presented graphically, as we attempt to do in the present paper. We understand that a positive map is extremal when the image of $\mathcal{D}$, the set of density matrices, fills out $\mathcal{D}$ maximally, in a certain sense. For the graphical presentation of a map we transform it to a standard form where it is unital and trace preserving. We present an iterative algorithm for the transformation, which converges rapidly in all our numerical examples and presumably works for any positive map. This standard form of an entanglement witness is unique up to unitary product transformations.

arXiv:1511.02110•Physical Review A•Oct 5, 2015•3 citations

Quantum and Approximation Algorithms for Maximum Witnesses of Boolean Matrix Products

Mirosław Kowaluk, Andrzej Lingas B

The problem of finding maximum (or minimum) witnesses of the Boolean product of two Boolean matrices (MW for short) has a number of important applications, in particular the all-pairs lowest common ancestor (LCA) problem in directed acyclic graphs (dags). The best known upper time-bound on the MW problem for [Formula: see text] Boolean matrices of the form [Formula: see text] has not been substantially improved since 2006. In order to obtain faster algorithms for this problem, we study quantum algorithms for MW and approximation algorithms for MW (in the classical computational model). Some of our quantum algorithms are input or output sensitive. Our fastest quantum algorithm for the MW problem, and consequently for the related problems, runs in time [Formula: see text], where [Formula: see text] satisfies the equation [Formula: see text] and [Formula: see text] is the exponent of the multiplication of an [Formula: see text] matrix by an [Formula: see text] matrix. Next, we consider a relaxed version of the MW problem (in the classical model) asking for reporting a witness of bounded rank (the maximum witness has rank 1) for each non-zero entry of the matrix product. First, by adapting the fastest known algorithm for maximum witnesses, we obtain an algorithm for the relaxed problem that reports for each non-zero entry of the product matrix a witness of rank at most [Formula: see text] in time [Formula: see text] Then, by reducing the relaxed problem to the so called [Formula: see text]-witness problem, we provide an algorithm that reports for each non-zero entry [Formula: see text] of the product matrix [Formula: see text] a witness of rank [Formula: see text], where [Formula: see text] is the number of witnesses for [Formula: see text], with high probability. The algorithm runs in [Formula: see text] time, where [Formula: see text].

International Journal of Foundations of Computer Science•Nov 10, 2023•2 citations

On a class of entanglement witnesses for multipartite quantum systems

Domenico D’Alessandro

The Hilbert space for [Formula: see text], [Formula: see text]-dimensional, quantum systems, [Formula: see text], contains the subspace of states that are invariant under any permutation, the symmetric sector, [Formula: see text]. Separable states must have a nonzero component on the symmetric sector. More in detail, if [Formula: see text] denotes the orthogonal projection onto [Formula: see text], [Formula: see text], for a bound [Formula: see text] and for any separable state [Formula: see text]. Therefore, if one knows a (lower bound for) [Formula: see text], the operator [Formula: see text] is an entanglement witness for the system. In this paper we calculate sharp bounds [Formula: see text] analytically for the case [Formula: see text] and general [Formula: see text], and numerically for the case of [Formula: see text] qubits ([Formula: see text]). We show with an example that the resulting entanglement witnesses are able to detect entanglement of PPT states.

International Journal of Quantum Information•Jul 10, 2025•0 citations

Entanglement witnesses: construction, analysis and classification

Dariusz Chruściński, Gniewomir Sarbicki

From the physical point of view entanglement witnesses (EWs) define a universal tool for analysis and classification of quantum entangled states. From the mathematical perspective bipartite EWs provide highly non-trivial generalization of positive operators and establish elegant correspondence with the theory of positive maps in matrix algebras. We concentrate on theoretical analysis of various important notions like decomposability, atomicity, optimality, extremality and exposedness. Several methods of construction are provided as well. Our discussion is illustrated by many examples enabling the reader to see the intricate structure of these objects. It is shown that the theory of EWs finds elegant geometric formulation in terms of convex cones and related geometric structures.

arXiv:1402.2413•Journal of Physics A Mathematical and Theoretical•Nov 11, 2014•214 citations
We present a study of extremal entanglement witnesses on a bipartite composite quantum system. We define the cone of witnesses as the dual of the set of separable density matrices, thus [Formula: see text] when [Formula: see text] is a witness and [Formula: see text] is a pure product state, [Formula: see text] with [Formula: see text]. The set of witnesses of unit trace is a compact convex set, uniquely defined by its extremal points. The expectation value [Formula: see text] as a function of vectors [Formula: see text] and [Formula: see text] is a positive semidefinite biquadratic form. Every zero of [Formula: see text] imposes strong real-linear constraints on f and [Formula: see text]. The real and symmetric Hessian matrix at the zero must be positive semidefinite. Its eigenvectors with zero eigenvalue, if such exist, we call Hessian zeros. A zero of [Formula: see text] is quadratic if it has no Hessian zeros, otherwise it is quartic. We call a witness quadratic if it has only quadratic zeros, and quartic if it has at least one quartic zero. A main result we prove is that a witness is extremal if and only if no other witness has the same, or a larger, set of zeros and Hessian zeros. A quadratic extremal witness has a minimum number of isolated zeros depending on dimensions. If a witness is not extremal, then the constraints defined by its zeros and Hessian zeros determine all directions in which we may search for witnesses having more zeros or Hessian zeros. A finite number of iterated searches in random directions, by numerical methods, leads to an extremal witness which is nearly always quadratic and has the minimum number of zeros. We discuss briefly some topics related to extremal witnesses, in particular the relation between the facial structures of the dual sets of witnesses and separable states. We discuss the relation between extremality and optimality of witnesses, and a conjecture of separability of the so-called structural physical approximation (SPA) of an optimal witness. Finally, we discuss how to treat the entanglement witnesses on a complex Hilbert space as a subset of the witnesses on a real Hilbert space.
We study extremal entanglement witnesses on a bipartite quantum system. We define the cone of witnesses as the dual of the set of separable density matrices, thus Tr Ωρ≥0\textrm{Tr}\,Ωρ\geq 0TrΩρ≥0 when ΩΩΩ is a witness and ρρρ a pure product state, ρ=ψψ†ρ=ψψ^{\dagger}ρ=ψψ† with ψ=ϕ⊗χψ=ϕ\otimesχψ=ϕ⊗χ. The set of witnesses of unit trace is a compact convex set, defined by its extremal points. The expectation value f(ϕ,χ)=Tr Ωρf(ϕ,χ)=\mathrm{Tr}\,Ωρf(ϕ,χ)=TrΩρ as a function of ϕϕϕ and χχχ is a nonnegative biquadratic form. Every zero of f(ϕ,χ)f(ϕ,χ)f(ϕ,χ) imposes real-linear constraints on fff and ΩΩΩ. The Hessian matrix at the zero must be nonnegative. Its eigenvectors with zero eigenvalue, if any, we call Hessian zeros. A zero of f(ϕ,χ)f(ϕ,χ)f(ϕ,χ) is quadratic if it has no Hessian zeros, otherwise it is quartic. We call a witness quadratic if it has only quadratic zeros, and quartic otherwise. We prove that a witness is extremal if and only if no other witness has the same, or a larger, set of zeros and Hessian zeros. A quadratic extremal witness has a minimum number of isolated zeros depending on dimensions. If a witness is not extremal, the constraints defined by its zeros and Hessian zeros determine all directions in which to search for witnesses having more zeros or Hessian zeros. A finite number of iterated searches in random directions lead to an extremal witness which is usually quadratic with the minimum number of zeros. We discuss some topics related to extremal witnesses, in particular the relation between the facial structures of the dual sets of witnesses and separable states. We discuss the relation between extremality and optimality of witnesses, and a conjecture of separability of the structural physical approximation (SPA) of an optimal witness. We discuss how to treat the entanglement witnesses on a complex Hilbert space as witnesses on a real Hilbert space.
Randomized measurement protocols give experimental access to low-degree polynomial invariants of a quantum state rather than to the state itself, which raises the question of what the best entanglement criterion is that can be built from finitely many such invariants. In this work we answer this question through convex duality. For each degree we introduce the cone of local unitary trace inequalities that are valid for separable bipartite states in all local dimensions, together with its one-matrix counterparts for Hermitian and positive semidefinite matrices. Each cone is the polar dual of a moment cone; we also determine the minimal combinatorial parametrization of the separable cone. The framework organizes the known moment criteria: the PPT criterion using the first three moments of the partial transposition is the image under an embedding of a Hankel determinant from the positive semidefinite cone to the bipartite cone, which we show to be an extremal ray, and we determine the first nontrivial separable cone completely, finding exactly four extremal rays. The framework allows us to analyze the realignment criterion and its centered (or enhanced) variant. We prove that the even singular value moments of the (centered) realignment matrix are trace invariants, associated with explicit fixed-point-free involutions. Extracting the optimal trace-norm bound from mmm such moments thus becomes a dimension-free truncated moment problem, which we solve in closed form for m=2m = 2m=2 and relax to a semidefinite program of size O(m)O(m)O(m) for arbitrary mmm. The dual solutions are polynomial minorants of x\sqrt{x}x​ on [0,1][0,1][0,1], and two explicit families, binomial and L1L^1L1-weighted, yield hierarchies of separability inequalities. Finally, we compare the criteria against one another and on PPT entangled states.
We define an entanglement witness in a composite quantum system as an observable having a nonnegative expectation value in every separable state. Then a state is entangled if and only if it has a negative expectation value of some entanglement witness. Equivalent representations of entanglement witnesses are nonnegative biquadratic forms or positive linear maps of Hermitian matrices. As reported elsewhere, we have studied extremal entanglement witnesses in dimension $3\ifmmode\times\else\texttimes\fi{}3$ by constructing numerical examples of generic extremal nonnegative forms. These are so complicated that we do not know how to handle them other than by numerical methods. However, the corresponding extremal positive maps can be presented graphically, as we attempt to do in the present paper. We understand that a positive map is extremal when the image of D\mathcal{D}D, the set of density matrices, fills out D\mathcal{D}D maximally, in a certain sense. For the graphical presentation of a map we transform it to a standard form where it is unital and trace preserving. We present an iterative algorithm for the transformation, which converges rapidly in all our numerical examples and presumably works for any positive map. This standard form of an entanglement witness is unique up to unitary product transformations.
The problem of finding maximum (or minimum) witnesses of the Boolean product of two Boolean matrices (MW for short) has a number of important applications, in particular the all-pairs lowest common ancestor (LCA) problem in directed acyclic graphs (dags). The best known upper time-bound on the MW problem for [Formula: see text] Boolean matrices of the form [Formula: see text] has not been substantially improved since 2006. In order to obtain faster algorithms for this problem, we study quantum algorithms for MW and approximation algorithms for MW (in the classical computational model). Some of our quantum algorithms are input or output sensitive. Our fastest quantum algorithm for the MW problem, and consequently for the related problems, runs in time [Formula: see text], where [Formula: see text] satisfies the equation [Formula: see text] and [Formula: see text] is the exponent of the multiplication of an [Formula: see text] matrix by an [Formula: see text] matrix. Next, we consider a relaxed version of the MW problem (in the classical model) asking for reporting a witness of bounded rank (the maximum witness has rank 1) for each non-zero entry of the matrix product. First, by adapting the fastest known algorithm for maximum witnesses, we obtain an algorithm for the relaxed problem that reports for each non-zero entry of the product matrix a witness of rank at most [Formula: see text] in time [Formula: see text] Then, by reducing the relaxed problem to the so called [Formula: see text]-witness problem, we provide an algorithm that reports for each non-zero entry [Formula: see text] of the product matrix [Formula: see text] a witness of rank [Formula: see text], where [Formula: see text] is the number of witnesses for [Formula: see text], with high probability. The algorithm runs in [Formula: see text] time, where [Formula: see text].
The Hilbert space for [Formula: see text], [Formula: see text]-dimensional, quantum systems, [Formula: see text], contains the subspace of states that are invariant under any permutation, the symmetric sector, [Formula: see text]. Separable states must have a nonzero component on the symmetric sector. More in detail, if [Formula: see text] denotes the orthogonal projection onto [Formula: see text], [Formula: see text], for a bound [Formula: see text] and for any separable state [Formula: see text]. Therefore, if one knows a (lower bound for) [Formula: see text], the operator [Formula: see text] is an entanglement witness for the system. In this paper we calculate sharp bounds [Formula: see text] analytically for the case [Formula: see text] and general [Formula: see text], and numerically for the case of [Formula: see text] qubits ([Formula: see text]). We show with an example that the resulting entanglement witnesses are able to detect entanglement of PPT states.
From the physical point of view entanglement witnesses (EWs) define a universal tool for analysis and classification of quantum entangled states. From the mathematical perspective bipartite EWs provide highly non-trivial generalization of positive operators and establish elegant correspondence with the theory of positive maps in matrix algebras. We concentrate on theoretical analysis of various important notions like decomposability, atomicity, optimality, extremality and exposedness. Several methods of construction are provided as well. Our discussion is illustrated by many examples enabling the reader to see the intricate structure of these objects. It is shown that the theory of EWs finds elegant geometric formulation in terms of convex cones and related geometric structures.