Separability of Hermitian Tensors and PSD Decompositions

Mareike Dressler, Jiawang Nie, Zi Yang

Abstract

Hermitian tensors are natural generalizations of Hermitian matrices, while possessing rather different properties. A Hermitian tensor is separable if it has a Hermitian decomposition with only positive coefficients, i.e., it is a sum of rank-1 psd Hermitian tensors. This paper studies how to detect separability of Hermitian tensors. It is equivalent to the long-standing quantum separability problem in quantum physics, which asks to tell if a given quantum state is entangled or not. We formulate this as a truncated moment problem and then provide a semidefinite relaxation algorithm to solve it. Moreover, we study psd decompositions of separable Hermitian tensors. When the psd rank is low, we first flatten them into cubic order tensors and then apply tensor decomposition methods to compute psd decompositions. We prove that this method works well if the psd rank is low. In computation, this flattening approach can detect separability for much larger sized Hermitian tensors. This method is a good start on determining psd ranks of separable Hermitian tensors.

1. Introduction

Hermitian tensors serve as a higher-order extension of Hermitian matrices, playing a critical role in fields ranging from multilinear algebra to quantum information theory. A fundamental property of these tensors is separability: a Hermitian tensor is considered separable if it can be expressed as a conic combination of rank-1 positive semidefinite (PSD) Hermitian tensors.

In quantum physics, this mathematical property corresponds directly to the quantum separability problem. A quantum state, represented as a density tensor, is separable if it lacks entanglement. Given that detecting entanglement is known to be NP-hard, the development of efficient "certificates" or algorithms to determine separability is of paramount importance. This paper addresses the computational challenges of detecting separability and computing PSD decompositions, particularly for high-order or large-dimension tensors.

2. Methodology

2.1 Semidefinite Relaxation (SDR) and Phase Fixing

The authors approach the detection of separability by reformulating it as a truncated moment problem. While "Lasserre-type" hierarchies have been used previously to solve such problems, they often suffer from high computational costs due to the redundancy in the search space.

A key contribution of this work is the introduction of a "symmetry breaking" constraint. In a Hermitian decomposition, any decomposing vector can be multiplied by a complex scalar of unit magnitude without altering the resulting tensor. By enforcing that the leading entry of each decomposing vector must be real and non-negative, the authors eliminate this redundancy. This "phase fixing" significantly reduces the number of variables in the semidefinite program, leading to tighter relaxations and faster convergence.

2.2 Flattening for Low-Rank PSD Decompositions

For tensors that are separable and possess a relatively low PSD rank, the authors propose a flattening technique. This method involves transforming a high-order Hermitian tensor into a lower-order form, such as a cubic (3rd-order) tensor or a matrix.

Once flattened, the problem can be solved using mature, off-the-shelf tensor decomposition libraries like Tensorlab. The authors provide theoretical evidence that for "generic" tensors—those that are typical in a measure-theoretic sense—the low-rank PSD decomposition is unique. This ensures that the flattening process preserves the essential structure of the original tensor, allowing for the recovery of the original PSD components.

3. Experimental Evaluation

The proposed algorithms were tested against synthetic benchmarks and notoriously difficult cases from quantum information literature, including Hankel tensors and specific entangled states that challenge traditional classification methods.

The results demonstrate a significant leap in performance compared to previous state-of-the-art methods (e.g., Li and Ni, 2020):

  • Efficiency: In a standard benchmark (Example 3.10), the new SDR method achieved a decomposition in just 2 seconds, compared to the 120 seconds required by previous formulations.
  • Robustness: In more complex scenarios (Example 3.11), the authors' algorithm successfully converged in 4.2 seconds, while the traditional approach failed to produce a solution even after 6 hours of computation.
  • Scalability: The flattening approach effectively extends the reach of separability detection to tensors of dimensions that were previously computationally prohibitive.

4. Discussion and Limitations

While the methods presented offer substantial improvements, certain challenges remain. The current algorithm is designed to find a valid PSD decomposition, but it does not guarantee the discovery of the minimum PSD rank (the smallest number of terms required for the decomposition). This remains an open theoretical and computational problem.

Furthermore, the effectiveness of the flattening method is contingent on the tensor having a relatively low rank. As the rank increases, the uniqueness of the decomposition is no longer guaranteed, and numerical precision issues inherent in semidefinite programming solvers (such as SeDuMi) may become more pronounced.

5. Conclusion

By combining an optimized truncated moment formulation with a novel flattening strategy, this work provides a powerful framework for tackling the quantum separability problem. The introduction of phase-fixing constraints and the utilization of existing tensor decomposition tools represent a significant step forward in making the analysis of high-dimensional Hermitian tensors practical for both mathematicians and physicists.

Summary updated

Abstract

Hermitian tensors are natural generalizations of Hermitian matrices, while possessing rather different properties. A Hermitian tensor is separable if it has a Hermitian decomposition with only positive coefficients, i.e., it is a sum of rank-1 psd Hermitian tensors. This paper studies how to detect separability of Hermitian tensors. It is equivalent to the long-standing quantum separability problem in quantum physics, which asks to tell if a given quantum state is entangled or not. We formulate this as a truncated moment problem and then provide a semidefinite relaxation algorithm to solve it. Moreover, we study psd decompositions of separable Hermitian tensors. When the psd rank is low, we first flatten them into cubic order tensors and then apply tensor decomposition methods to compute psd decompositions. We prove that this method works well if the psd rank is low. In computation, this flattening approach can detect separability for much larger sized Hermitian tensors. This method is a good start on determining psd ranks of separable Hermitian tensors.
BibTeX
@inproceedings{dressler2021separability,
  author = {Mareike Dressler and Jiawang Nie and Zi Yang},
  title = {{Separability of Hermitian Tensors and PSD Decompositions}},
  booktitle = {Linear},
  year = {2021},
  doi = {10.1080/03081087.2021.1965078},
}
Figure