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

arXiv:2004.10219 · Journal of Mathematical Physics

Approximate tensor decompositions: Disappearance of many separations

Gemma De las Cuevas, Andreas Klingler, Tim Netzer

Published Sep 1, 2021• 9 citations
arXivHTMLPDF

Abstract

It is well known that tensor decompositions show separations, that is, constraints on local terms (such as positivity) may entail an arbitrarily high cost in their representation. Here, we show that many of these separations disappear in the approximate case. Specifically, for every approximation error ɛ and norm, we define the approximate rank as the minimum rank of an element in the ɛ-ball with respect to that norm. For positive semidefinite matrices, we show that the separations between rank, purification rank, and separable rank disappear for a large class of Schatten p-norms. For non-negative tensors, we show that the separations between rank, positive semidefinite rank, and non-negative rank disappear for all ℓp-norms with p > 1. For the trace norm (p = 1), we obtain upper bounds that depend on the ambient dimension. We also provide a deterministic algorithm to obtain the approximate decomposition attaining our bounds. Our main tool is an approximate version of the Carathéodory theorem. Our results imply that many separations are not robust under small perturbations of the tensor, with implications in quantum many-body systems and communication complexity.

DOI
10.1063/5.0033876

Related papers

Border Ranks of Positive and Invariant Tensor Decompositions: Applications to Correlations

Andreas Klingler, Tim Netzer, Gemma De las Cuevas

The matrix rank and its positive versions are robust for small approximations, i.e. they do not decrease under small perturbations. In contrast, the multipartite tensor rank can collapse for arbitrarily small errors, i.e. there may be a gap between rank and border rank, leading to instabilities in the optimization over sets with fixed tensor rank. Can multipartite positive ranks also collapse for small perturbations? In this work, we prove that multipartite positive and invariant tensor decompositions exhibit gaps between rank and border rank, including tensor rank purifications and cyclic separable decompositions. We also prove a correspondence between positive decompositions and membership in certain sets of multipartite probability distributions, and leverage the gaps between rank and border rank to prove that these correlation sets are not closed. It follows that testing membership of probability distributions arising from resources like translational invariant Matrix Product States is impossible in finite time. Overall, this work sheds light on the instability of ranks and the unique behavior of bipartite systems.

arXiv:2304.13478•Quantum•Feb 26, 2025•1 citation

Rank-bmRpositive Hermitian approximation algorithms and positive Hermitian decompositions of Hermitian tensors

Bo Yang, Ying Li, Guyan Ni +1 more

The Hermitian tensor is regarded as an extension of the Hermitian matrix and can be used to represent a quantum mixed state. In quantum information, the problem of separability discrimination and decomposition of a quantum mixed state is still important and hard. In this paper, we deduce the gradient of the approximation function, and propose three algorithms: A negative gradient algorithm and a BFGS algorithm for rank-$R$ positive Hermitian approximation of Hermitian tensors, and a separability discrimination and decomposition algorithm for Hermitian tensors. According to the Taylor formula and the convexity analysis, we prove the effectiveness of the algorithm. Numerical examples also verify the correctness of the theoretical analysis and the effectiveness of algorithms. They show that the BFGS algorithm can be used for the separability discrimination and the positive Hermitian decomposition, as well as to obtain a rank-positive Hermitian decomposition. Compared with the semidefinite relaxation algorithm, the BFGS algorithm has the advantages of less running time and solving the decomposition of higher-order or higher-dimensional Hermitian tensors.

Scientia Sinica Mathematica•May 30, 2023•1 citation

Many-body Approximation for Non-negative Tensors

Kazu Ghalamkari, Mahito Sugiyama, Yoshinobu Kawahara

We present an alternative approach to decompose non-negative tensors, called many-body approximation. Traditional decomposition methods assume low-rankness in the representation, resulting in difficulties in global optimization and target rank selection. We avoid these problems by energy-based modeling of tensors, where a tensor and its mode correspond to a probability distribution and a random variable, respectively. Our model can be globally optimized in terms of the KL divergence minimization by taking the interaction between variables (that is, modes), into account that can be tuned more intuitively than ranks. Furthermore, we visualize interactions between modes as tensor networks and reveal a nontrivial relationship between many-body approximation and low-rank approximation. We demonstrate the effectiveness of our approach in tensor completion and approximation.

arXiv:2209.15338•neural information processing systems•Jan 1, 2023•0 citations

Normalized tensor train decomposition

Renfeng Peng, Chengkai Zhu, Bin Gao +2 more

Tensors with unit Frobenius norm are fundamental objects in many fields, including scientific computing and quantum physics, which are able to represent normalized eigenvectors and pure quantum states. While the tensor train decomposition provides a powerful low-rank format for tackling high-dimensional problems, it does not intrinsically enforce the unit-norm constraint. To address this, we introduce the normalized tensor train (NTT) decomposition, which aims to approximate a tensor by unit-norm tensors in tensor train format. The low-rank structure of NTT decomposition not only saves storage and computational cost but also preserves the underlying unit-norm structure. We prove that the set of fixed-rank NTT tensors forms a smooth manifold, and the corresponding Riemannian geometry is derived, paving the way for geometric methods. We propose NTT-based methods for low-rank tensor recovery, high-dimensional eigenvalue problem, estimation of stabilizer rank, and calculation of the minimum output Rényi 2-entropy of quantum channels. Numerical experiments demonstrate the superior efficiency and scalability of the proposed NTT-based methods.

math.NACross-listedarXiv:2511.04369•Nov 7, 2025•0 citations

Counting tensor rank decompositions

Dennis Obster, Naoki Sasakura

The tensor rank decomposition is a useful tool for the geometric interpretation of the tensors in the canonical tensor model (CTM) of quantum gravity. In order to understand the stability of this interpretation, it is important to be able to estimate how many tensor rank decompositions can approximate a given tensor. More precisely, finding an approximate symmetric tensor rank decomposition of a symmetric tensor $Q$ with an error allowance $Δ$ is to find vectors $ϕ^i$ satisfying $\|Q-\sum_{i=1}^R ϕ^i\otimes ϕ^i\cdots \otimes ϕ^i\|^2 \leq Δ$. The volume of all possible such $ϕ^i$ is an interesting quantity which measures the amount of possible decompositions for a tensor $Q$ within an allowance. While it would be difficult to evaluate this quantity for each $Q$, we find an explicit formula for a similar quantity by integrating over all $Q$ of unit norm. The expression as a function of $Δ$ is given by the product of a hypergeometric function and a power function. We also extend the formula to generic decompositions of non-symmetric tensors. The derivation depends on the existence (convergence) of the partition function of a matrix model which appeared in the context of the CTM.

arXiv:2107.10237•Jul 20, 2021•0 citations

Separability of Hermitian tensors and PSD decompositions

Mareike Dressler, Jiawang Nie, Zi Yang

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.

Linear and Multilinear Algebra•Aug 27, 2021•10 citations
It is well known that tensor decompositions show separations, that is, constraints on local terms (such as positivity) may entail an arbitrarily high cost in their representation. Here, we show that many of these separations disappear in the approximate case. Specifically, for every approximation error ɛ and norm, we define the approximate rank as the minimum rank of an element in the ɛ-ball with respect to that norm. For positive semidefinite matrices, we show that the separations between rank, purification rank, and separable rank disappear for a large class of Schatten p-norms. For non-negative tensors, we show that the separations between rank, positive semidefinite rank, and non-negative rank disappear for all ℓp-norms with p > 1. For the trace norm (p = 1), we obtain upper bounds that depend on the ambient dimension. We also provide a deterministic algorithm to obtain the approximate decomposition attaining our bounds. Our main tool is an approximate version of the Carathéodory theorem. Our results imply that many separations are not robust under small perturbations of the tensor, with implications in quantum many-body systems and communication complexity.
The matrix rank and its positive versions are robust for small approximations, i.e. they do not decrease under small perturbations. In contrast, the multipartite tensor rank can collapse for arbitrarily small errors, i.e. there may be a gap between rank and border rank, leading to instabilities in the optimization over sets with fixed tensor rank. Can multipartite positive ranks also collapse for small perturbations? In this work, we prove that multipartite positive and invariant tensor decompositions exhibit gaps between rank and border rank, including tensor rank purifications and cyclic separable decompositions. We also prove a correspondence between positive decompositions and membership in certain sets of multipartite probability distributions, and leverage the gaps between rank and border rank to prove that these correlation sets are not closed. It follows that testing membership of probability distributions arising from resources like translational invariant Matrix Product States is impossible in finite time. Overall, this work sheds light on the instability of ranks and the unique behavior of bipartite systems.
The Hermitian tensor is regarded as an extension of the Hermitian matrix and can be used to represent a quantum mixed state. In quantum information, the problem of separability discrimination and decomposition of a quantum mixed state is still important and hard. In this paper, we deduce the gradient of the approximation function, and propose three algorithms: A negative gradient algorithm and a BFGS algorithm for rank-RRR positive Hermitian approximation of Hermitian tensors, and a separability discrimination and decomposition algorithm for Hermitian tensors. According to the Taylor formula and the convexity analysis, we prove the effectiveness of the algorithm. Numerical examples also verify the correctness of the theoretical analysis and the effectiveness of algorithms. They show that the BFGS algorithm can be used for the separability discrimination and the positive Hermitian decomposition, as well as to obtain a rank-positive Hermitian decomposition. Compared with the semidefinite relaxation algorithm, the BFGS algorithm has the advantages of less running time and solving the decomposition of higher-order or higher-dimensional Hermitian tensors.
We present an alternative approach to decompose non-negative tensors, called many-body approximation. Traditional decomposition methods assume low-rankness in the representation, resulting in difficulties in global optimization and target rank selection. We avoid these problems by energy-based modeling of tensors, where a tensor and its mode correspond to a probability distribution and a random variable, respectively. Our model can be globally optimized in terms of the KL divergence minimization by taking the interaction between variables (that is, modes), into account that can be tuned more intuitively than ranks. Furthermore, we visualize interactions between modes as tensor networks and reveal a nontrivial relationship between many-body approximation and low-rank approximation. We demonstrate the effectiveness of our approach in tensor completion and approximation.
Tensors with unit Frobenius norm are fundamental objects in many fields, including scientific computing and quantum physics, which are able to represent normalized eigenvectors and pure quantum states. While the tensor train decomposition provides a powerful low-rank format for tackling high-dimensional problems, it does not intrinsically enforce the unit-norm constraint. To address this, we introduce the normalized tensor train (NTT) decomposition, which aims to approximate a tensor by unit-norm tensors in tensor train format. The low-rank structure of NTT decomposition not only saves storage and computational cost but also preserves the underlying unit-norm structure. We prove that the set of fixed-rank NTT tensors forms a smooth manifold, and the corresponding Riemannian geometry is derived, paving the way for geometric methods. We propose NTT-based methods for low-rank tensor recovery, high-dimensional eigenvalue problem, estimation of stabilizer rank, and calculation of the minimum output Rényi 2-entropy of quantum channels. Numerical experiments demonstrate the superior efficiency and scalability of the proposed NTT-based methods.
The tensor rank decomposition is a useful tool for the geometric interpretation of the tensors in the canonical tensor model (CTM) of quantum gravity. In order to understand the stability of this interpretation, it is important to be able to estimate how many tensor rank decompositions can approximate a given tensor. More precisely, finding an approximate symmetric tensor rank decomposition of a symmetric tensor QQQ with an error allowance ΔΔΔ is to find vectors ϕiϕ^iϕi satisfying ∥Q−∑i=1Rϕi⊗ϕi⋯⊗ϕi∥2≤Δ\|Q-\sum_{i=1}^R ϕ^i\otimes ϕ^i\cdots \otimes ϕ^i\|^2 \leq Δ∥Q−∑i=1R​ϕi⊗ϕi⋯⊗ϕi∥2≤Δ. The volume of all possible such ϕiϕ^iϕi is an interesting quantity which measures the amount of possible decompositions for a tensor QQQ within an allowance. While it would be difficult to evaluate this quantity for each QQQ, we find an explicit formula for a similar quantity by integrating over all QQQ of unit norm. The expression as a function of ΔΔΔ is given by the product of a hypergeometric function and a power function. We also extend the formula to generic decompositions of non-symmetric tensors. The derivation depends on the existence (convergence) of the partition function of a matrix model which appeared in the context of the CTM.
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.