Convex semidefinite tensor optimization and quantum entanglement

Liding Xu, Ye-Chao Liu, Sebastian Pokutta · 2025

Read Convex semidefinite tensor optimization and quantum entanglement by Liding Xu, Ye-Chao Liu, Sebastian Pokutta (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-05258.txt.

Introduction

Liding Xu and co-authors extend semidefinite optimization from matrices to tensors, where the tensor case matches separable quantum states. The matrix cone is a workhorse of convex optimization, but its tensor cousin is far less tame.

The tensor cone can be re-shaped smoothly by factorization, yet it is not self-dual. No fast method is known to test membership or project onto it, and the optimization task, though convex, is NP-hard. The authors develop new ways to compute with this cone, which links convex methods to the study of quantum entanglement.

Catalog record

CREATORLiding Xu, Ye-Chao Liu, Sebastian Pokutta
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE100 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-05258

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Convex semidefinite tensor optimization and quantum entanglement Liding Xu, Ye-Chao Liu, Sebastian Pokutta Abstract The cone of positive-semidefinite (PSD) matrices is fundamental in convex optimization, and we extend this notion to tensors, defining PSD tensors, which correspond to separable quantum states. We study the convex optimization problem over the PSD tensor cone. While this convex cone admits a smooth reparameterization through tensor factorizations (analogous to the matrix case), it is not self-dual. Moreover, there are currently no efficient algorithms for projecting onto or testing membership in this cone, and the semidefinite tensor optimization problem, although convex, is NP-hard. To address these challenges, we develop methods for computing lower and upper bounds on the optimal value of the problem. We propose a general-purpose iterative refinement algorithm that combines a lifted alternating direction method of multipliers with a cutting-plane approach. This algorithm exploits PSD tensor factorizations to produce heuristic solutions and refine the solutions using cutting planes. Since the method requires a linear minimization oracle over PSD tensors, we design a spatial branch-and-bound algorithm based on convex relaxations and valid inequalities. Our framework allows us to study the white-noise mixing threshold, which characterizes the entanglement properties of quantum states. Numerical experiments on benchmark instances demonstrate the effectiveness of the proposed methods. Key words: Tensor Optimization Cutting-Plane Methods Branch-and-Bound Algorithms Quantum Entanglement Convex Relaxations 1 Introduction In quantum information science, a (quantum) state is represented by a density matrix, which is a Hermitian, positive-semidefinite (PSD) matrix with unit trace. The density matrix of a pure state has rank one. A pure state of a multipartite system is separable if and only if its density matrix can be written as a tensor product of rank-one density matrices corresponding to pure states of the individual subsystems. A mixed (non-pure) state is separable if its density matrix is a convex combination of density matrices of separable pure states. States that are not separable are called entangled. Detecting entanglement in mixed states is hard; however, it is central to quantum information science and impacts many areas of physics 29 ; 55 . Mathematically, separability of (quantum) states is closely related to decompositions of tensors. Canonical polyadic decomposition (CPD) is the most well-known tensor decomposition. Given a vector \mathbf{d}=(d_{1},\dots,d_{m}) , an order- m tensor \mathbf{y}\in\mathbb{F}^{d_{1}\times\cdots\times d_{m}} admits a CPD, if \mathbf{y}=\sum_{i\in[r]}\lambda_{i}\mathbf{x}_{i1}\mtens\cdots\mtens\mathbf{x}_{im} , where \mathbb{F} is the field \mathbb{R} of real numbers or the field \mathbb{C} of complex numbers. The minimum r in CPD of \mathbf{y} is its CPD rank. If all modes \mathbf{x}_{ij} ( j\in[m] ) in each component \mathbf{x}_{i1}\mtens\cdots\mtens\mathbf{x}_{im} are identical to a vector \mathbf{x}_{i} and all d_{j}=d , then CPD is symmetric (under permutation of indices). Separable states are tensors that have more restrictive decompositions. We define the following cone of (order- 2m ) PSD tensors: \SOST_{\mathbb{F}}(\mathbf{d})\coloneqq\{\mathbf{y}\in\mathbb{F}^{d_{1}\times d_{1}\cdots\times d_{m}\times d_{m}}\mid\mathbf{y}=\sum_{i\in[r]}\mathbf{x}_{i1}\mtens\mathbf{x}_{i1}^{\dagger}\cdots\mathbf{x}_{im}\mtens\mathbf{x}_{im}^{\dagger}\}, (1) where \mathbf{x}^{\dagger} denotes the conjugate transpose of \mathbf{x} . Any tensor in \SOST_{\mathbb{F}}(\mathbf{d}) , when reshaped as an order-2 tensor, yields a large PSD matrix of size \bar{d}^{2} with \bar{d}=\prod_{j\in[m]}d_{j} . The set \sep(\mathbf{d}) of separable states consists of all unit-trace reshaped tensors in \SOST_{\mathbb{C}}(\mathbf{d}) : \sep(\mathbf{d})\coloneqq\{\mathbf{y}\in\SOST_{\mathbb{C}}(\mathbf{d})\mid\tr(\mathbf{y})=1\}. (2) Identification of separable states is difficult. For unipartite systems ( m=1 ), the set of separable states is simply the set of density matrices. For multipartite systems , however, separable states form a strict subset of density matrices. In addition, the set \sep(\mathbf{d}) is computationally intractable : there are no known efficient algorithms for separation, projection, linear minimization, or even membership testing. The membership testing problem is already strongly NP -hard even for bipartite systems ( m=2 ) 34 . The linear minimization problem \min_{\mathbf{y}\in\sep(\mathbf{d})}\langle\chi,\mathbf{y}\rangle , known as the best separable state (BSS) problem, is also NP -hard 30 . We consider a generalization of semidefinite programming (SDP): semidefinite tensor optimization (SDTO) , a conic optimization problem over the cone of PSD tensors. The SDTO can be written as: \text{opt}\coloneqq\min\{\langle\mathbf{c},\mathbf{z}\rangle:\mathbf{z}\in\mathcal{Z},\;A(\mathbf{z})+\mathbf{a}\in\SOST_{\mathbb{F}}(\mathbf{d})\}, (SDTO) where \mathcal{Z} is a tractable convex cone, A is a linear map, \mathbf{a} is a constant tensor. The intractability of \sep(\mathbf{d}) implies that SDTO is also NP -hard. When m=1 and \mathcal{Z} is a PSD cone, ( SDTO ) becomes an SDP, for which off-the-shelf solvers are available. However, algorithms for tackling the general problem ( SDTO ) are scarce. We adapt established SDP strategies and address the nonconvexity introduced by PSD tensor factorizations. Our first contribution is an iterative refinement (IR) algorithm for ( SDTO ). IR alternates between a heuristic stage – where a lifted alternating direction method of multipliers (LADMM) solves a factorized nonconvex reformulation to find heuristic solutions – and a refinement stage that tightens and certifies bounds via a cutting-plane (CP) algorithm. LADMM and CP warm-start one another: LADMM outputs accelerate CP, while CP polishes the accuracy of heuristic solutions and provides numerically reliable bounds on opt . The IR algorithm produces a non-increasing sequence of upper bounds, and it can also provide lower bounds and certified optima. Our second contribution is a spatial branch-and-bound (sBB) algorithm that serves as a linear minimization oracle (LMO) inside the CP algorithm. The convex relaxations in the sBB algorithm are constructed from the intersections of the following building blocks: • Factorizable DPS constraints obtained by combining the Doherty–Parrilo–Spedalieri (DPS) convex outer approximations of separable bipartite states 26 with McCormick factorization for multilinear monomials 2 ; • SDP McCormick inequalities generated via Kronecker product of two matrix constraints 3 ; • LP McCormick inequalities that support efficient branching rules. We show that these convex sets and inequalities can be derived from a unified framework that generalizes the classical Reformulation–Linearization Technique (RLT) 62 for polynomial optimization. Moreover, the convex outer approximations of separable states also give a convex relaxation of SDTO. We evaluate the proposed algorithms and existing methods on a benchmark problem: determining the white-noise mixing threshold of an entangled state—that is, the minimal amount of white-noise admixture required to make the state separable, or equivalently, its random robustness 70 under a complete depolarizing channel: S(\phi\|\mathbf{Id})=\min\{\mathbf{z}\geq 0:\rho(\mathbf{z};\phi,\mathbf{Id})\coloneqq(\mathbf{Id}/\bar{d}-\phi)\mathbf{z}+\phi\in\sep(\mathbf{d})\}, (Threshold) where the normalized identity matrix \mathbf{Id}/\bar{d} represents the covariance of the white noise. The interpolated state \rho(\mathbf{z};\phi,\mathbf{Id}) lies on the line segment joining \mathbf{Id}/\bar{d} and \phi . The threshold value indicates the separability/entanglement of \phi . 1.1 Related work The problem of certifying entanglement or separability has been studied through several complementary approaches. A well-known example is the positive partial transpose (PPT) criterion 42 ; 57 , which is necessary and sufficient for bipartite systems of \mathbf{d}=(2,2) or (2,3) , but only necessary in higher dimensions. The DPS hierarchy 26 ; 54 extends the PPT criterion and provides nested convex outer approximations of separable states for bipartite systems. From the dual perspective, the DPS hierarchy corresponds to a sum-of-squares hierarchy for a homogeneous Hermitian polynomial over spheres 30 . Although the DPS constraints admit physical interpretations, the hierarchy lacks finite-convergence guarantees 31 . The DPS constraints are primarily used as entanglement certification (YES answers to entanglement). In addition, the DPS hierarchy can produce lower bounds on white-noise mixing thresholds for bipartite states; see an implementation in Ket.jl 4 . The inner approximations of separable states and alternating SDP-based refinement are combined to find separability certification (NO-answer to entanglement) 56 and upper bounds on white-noise mixing thresholds. As

Read the complete text