Separability of Hermitian tensors and PSD decompositions

Mareike Dressler, Jiawang Nie, Zi Yang

TL;DR

This paper introduces highly efficient algorithms for determining if a Hermitian tensor is "separable"—a problem equivalent to identifying whether a quantum state is entangled. By reformulating the task as an optimized truncated moment problem and using tensor "flattening" techniques, the authors provide a framework that is orders of magnitude faster than previous methods and capable of handling much larger systems.

What Problem Does This Paper Address?

Hermitian tensors are the higher-order cousins of Hermitian matrices. A central question in both mathematics and quantum physics is separability: can a given tensor be expressed as a sum of rank-1 positive semidefinite (psd) Hermitian tensors?

In the world of quantum mechanics, this is known as the quantum separability problem. If a quantum state (represented as a tensor) is separable, it is "classical"; if it is not, it is entangled. Because detecting entanglement is NP-hard, researchers need "certificates"—mathematical proofs or efficient algorithms—that can reliably detect separability in practical scenarios. Previous methods often struggled with computational complexity as the size or order of the tensor increased.

Methods

The authors contribute two primary approaches:

  1. Improved Semidefinite Relaxation (SDR): The authors treat separability as a truncated moment problem. They improve upon existing "Lasserre-type" hierarchies by introducing a clever constraint: they require the leading entry of each decomposing vector to be real and nonnegative. This "symmetry breaking" significantly reduces the number of variables the solver has to juggle, leading to tighter relaxations that converge much faster.

  2. Flattening for PSD Decompositions: For tensors that are known to be separable but have a low "psd rank," the authors propose flattening. They transform the high-order tensor into a lower-order (cubic or matrix) form. This allows them to use mature, off-the-shelf tensor decomposition tools (like Tensorlab) to extract the actual psd components. They provide theoretical proofs showing that this method works reliably for "generic" tensors when the rank is sufficiently low.

Datasets

The paper does not use standard machine learning datasets. Instead, it evaluates its algorithms on synthetic benchmarks and known difficult cases from quantum information theory and tensor literature, including:

  • Hankel Tensors: Used to test non-separability detection.
  • Specific Quantum States: Examples of entangled states that are notoriously difficult for traditional algorithms to classify.
  • Randomly Generated Separable Tensors: Used to benchmark the speed and accuracy of computing psd decompositions.

Key Insights and Ideas

  • Phase Fixing: The "aha moment" in their SDR formulation is realizing that because you can multiply decomposing vectors by a complex scalar of magnitude 1 without changing the tensor, the search space is redundant. By fixing the phase (making the first entry real/positive), they eliminate this redundancy, allowing the algorithm to "see" the solution much more clearly and quickly.
  • Flattening preserves structure: The authors show that you don't always need to solve the full, high-order tensor problem. If the rank is low, the "essence" of the decomposition is preserved even when you squash the tensor into a simpler 3rd-order format.
  • Generic Uniqueness: They prove that for most tensors (in a measure-theoretic sense), the low-rank psd decomposition is unique. This provides a theoretical guarantee that their flattening approach isn't just a heuristic—it’s mathematically grounded.

Key Results

The performance gains over previous state-of-the-art methods (specifically the work of Li and Ni, 2020) are dramatic:

  • Speed: In one benchmark (Example 3.10), the new method found a decomposition in 2 seconds, while the previous method took 120 seconds for the same task.
  • Robustness: In a larger test (Example 3.11), the authors' algorithm succeeded in 4.2 seconds, whereas the traditional formulation failed to find a solution even after 6 hours of computation.
  • Scalability: The flattening approach allows the detection of separability for tensors of much larger dimensions than were previously practical to compute.

Limitations and Future Work

  • The "Shortest" Decomposition: While the algorithm can find a positive decomposition, it does not guarantee finding the one with the absolute minimum number of terms (the actual psd rank). The authors explicitly flag this as an open problem (Problem 5.1).
  • High-Rank Tensors: The flattening method relies on the psd rank being relatively low. If the rank is very high, the uniqueness properties vanish, and the method may not be able to recover the decomposition.
  • Numerical Precision: Like all semidefinite programming approaches, the method is subject to the numerical limits of underlying solvers (like SeDuMi), which can be a factor when dealing with extremely high-dimensional quantum systems.

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 the 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 the separability for much larger-sized Hermitian tensors. This method is a good starting point to determine 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