Upper and lower quantum functionals, introduced by Christandl, Vrana and Zuiddam (STOC 2018, J. Amer. Math. Soc. 2023), are families of monotone functions of tensors indexed by a weighting on the set of subsets of the tensor legs. Inspired by quantum information theory, they were crafted as obstructions to asymptotic tensor transformations, relevant in algebraic complexity theory. For tensors of order three, and more generally for weightings on singletons for higher-order tensors, the upper and lower quantum functionals coincide and are spectral points in Strassen's asymptotic spectrum. Moreover, the singleton quantum functionals characterize the asymptotic slice rank, whereas general weightings provide upper bounds on asymptotic partition rank. It has been an open question whether the upper and lower quantum functionals also coincide for other cases, or more generally, how to construct further spectral points, especially for higher-order tensors.
In this work, we show that upper and lower quantum functionals generally do not coincide, but that they anchor new spectral points. With this we mean that there exist new spectral points, which equal the quantum functionals on the set of tensors on which upper and lower coincide. The set is shown to include embedded three-tensors and W-like states and concerns all laminar weightings, significantly extending the singleton case. Moreover, it is shown that these spectral points provide obstructions to asymptotic restriction beyond the previously known spectral points.
Motivated by the problem of constructing fast matrix multiplication algorithms, Strassen (FOCS 1986, Crelle 1987–1991) introduced and developed the theory of asymptotic spectra of tensors. For any sub-semiring X \mathcal {X} of tensors (under direct sum and tensor product), the duality theorem that is at the core of this theory characterizes basic asymptotic properties of the elements of X \mathcal {X} in terms of the asymptotic spectrum of X \mathcal {X} , which is defined as the collection of semiring homomorphisms from X \mathcal {X} to the non-negative reals with a natural monotonicity property. The asymptotic properties characterized by this duality encompass fundamental problems in complexity theory, combinatorics and quantum information. Universal spectral points are elements in the asymptotic spectrum of the semiring of all tensors. Finding all universal spectral points suffices to find the asymptotic spectrum of any sub-semiring. The construction of non-trivial universal spectral points has been an open problem for more than thirty years. We construct, for the first time, a family of non-trivial universal spectral points over the complex numbers, called quantum functionals . We moreover prove that the quantum functionals precisely characterise the asymptotic slice rank of complex tensors. Our construction, which relies on techniques from quantum information theory and representation theory, connects the asymptotic spectrum of tensors to the quantum marginal problem and entanglement polytopes.
Convex optimization on polytopes arises in many areas of science. When the polytope is given implicitly or has exponentially many vertices and facets, standard methods may not apply or be ineffective. This is the case for moment polytopes, such as the entanglement polytopes, which play a foundational role in quantum information and algebraic complexity. They give rise to important entanglement measures and tensor parameters such as the quantum functionals, yet general effective methods for computing these quantities have been elusive.
In this paper we address this challenge. We develop a first-order framework called Hadamard mirror descent to optimize suitable convex functions over moment polytopes and, more generally, the gradient sets of geodesically convex functions. It operates locally and does not rely on any explicit description of the polytope. Our framework extends mirror descent, an effective and widely used framework for convex optimization, from the Euclidean setting to Hadamard manifolds, and is motivated by a recent work by Hirai, which we interpret as a Hadamard version of mirror flow. Applying the framework to entanglement polytopes yields the first efficient first-order algorithms to compute the quantum functionals, the symmetric quantum functional, and the G-stable ranks, as well as a new direct algorithm for the non-commutative rank.
We present a polynomial time algorithm to approximately scale tensors of any format to arbitrary prescribed marginals (whenever possible). This unifies and generalizes a sequence of past works on matrix, operator and tensor scaling. Our algorithm provides an efficient weak membership oracle for the associated moment polytopes, an important family of implicitly-defined convex polytopes with exponentially many facets and a wide range of applications. These include the entanglement polytopes from quantum information theory (in particular, we obtain an efficient solution to the notorious one-body quantum marginal problem) and the Kronecker polytopes from representation theory (which capture the asymptotic support of Kronecker coefficients). Our algorithm can be applied to succinct descriptions of the input tensor whenever the marginals can be efficiently computed, as in the important case of matrix product states or tensor-train decompositions, widely used in computational physics and numerical mathematics. Beyond these applications, the algorithm enriches the arsenal of "numerical" methods for classical problems in invariant theory that are significantly faster than "symbolic" methods which explicitly compute invariants or covariants of the relevant action. We stress that (like almost all past algorithms) our convergence rate is polynomial in the approximation parameter; it is an intriguing question to achieve exponential convergence rate, beating symbolic algorithms exponentially, and providing strong membership and separation oracles for the problems above. We strengthen and generalize the alternating minimization approach of previous papers by introducing the theory of highest weight vectors from representation theory into the numerical optimization framework. We show that highest weight vectors are natural potential functions for scaling algorithms and prove new bounds on their evaluations to obtain polynomial-time convergence. Our techniques are general and we believe that they will be instrumental to obtain efficient algorithms for moment polytopes beyond the ones consider here, and more broadly, for other optimization problems possessing natural symmetries.
We investigate the geometric structure of the set of spectra of bipartite absolute separable states (
ASEPm,n) and absolute positive partial transpose states (
APPTm,n), \emph{i.e.}, bipartite quantum states that remain separable or PPT, respectively, under all global unitary transformations. First, we establish general geometric properties of absolute convex sets of matrices, their spectra and extreme points. Regarding absolute separability, we present a permutation-symmetric reformulation of the absolute PPT criterion and use it to demonstrate that
APPTm,n is a spectrahedron for all
m≤n: in particular, all its faces are exposed. While
ASEP2,n is a spectrahedron, too, for
ASEPm,n we can in general only show that it is a semialgebraic set for all
m,n≥3. Furthermore, we provide a complete characterization of the faces and extreme points of
APPTm,n and demonstrate that the dimension of a face is determined by the rank of a certain matrix, with maximal proper faces having dimension
mn−m−1.
In the quantitative setting, we provide a rigorous lower bound on the maximal attainable purity of
APPTm,n via an inscribed polytope
Pm,n and conjecture that the maximal purity of
APPTm,n (along with its spectra) coincides with the polytope for arbitrary dimensions except when
m=n=2. Additionally, we also provide a rigorous upper bound on the minimal von Neumann entropy of
APPTm,n and demonstrate numerically that the minimum entropy eventually coincides with the polytope
Pm,n as the local system dimension
n increases. Finally, we show that the relative spectral volume of
APPTm,n decays exponentially in
n by a constant multiplicative factor of the relative volume of the inscribed polytope
Pm,n.
We study quantum versions of the Shannon capacity of graphs and non-commutative graphs. We introduce the asymptotic spectrum of graphs with respect to quantum and entanglement-assisted homomorphisms, and we introduce the asymptotic spectrum of non-commutative graphs with respect to entanglement-assisted homomorphisms. We apply Strassen's spectral theorem (J. Reine Angew. Math., 1988) in order to obtain dual characterizations of the corresponding Shannon capacities and asymptotic preorders in terms of their asymptotic spectra. This work extends the study of the asymptotic spectrum of graphs initiated by Zuiddam (Combinatorica, 2019) to the quantum domain. We then exhibit spectral points in the new quantum asymptotic spectra and discuss their relations with the asymptotic spectrum of graphs. In particular, we prove that the (fractional) real and complex Haemers bounds upper bound the quantum Shannon capacity, which is defined as the regularization of the quantum independence number (Mančinska and Roberson, J. Combin. Theory Ser. B, 2016), and that the fractional real and complex Haemers bounds are elements in the quantum asymptotic spectrum of graphs. This is in contrast to the Haemers bounds defined over certain finite fields, which can be strictly smaller than the quantum Shannon capacity. Moreover, since the Haemers bound can be strictly smaller than the Lovász theta function (Haemers, IEEE Trans. Inf. Theory, 1979), we find that the quantum Shannon capacity and the Lovász theta function do not coincide. As a consequence, two well-known conjectures in quantum information theory, namely: 1) the entanglement-assisted zero-error capacity of a classical channel is equal to the Lovász theta function and 2) maximally entangled states and projective measurements are sufficient to achieve the entanglement-assisted zero-error capacity, cannot both be true.