In this paper, we present a technically simple method to establish upper bounds on the expected injective norm of real and complex random tensors. Our approach is somewhat analogous to the moment method in random matrix theory, and is based on a deterministic upper bound on the injective norm of a tensor which might be of independent interest. Compared to previous approaches to these problems (spin-glass methods, epsilon-net techniques, Sudakov-Fernique arguments, and PAC-Bayesian proofs), our method has the benefit of being nonasymptotic, relatively elementary, and applicable to non-Gaussian models. We illustrate our approach on various models of random tensors, recovering some previously known (and conjecturally tight) bounds with simpler arguments, and presenting new bounds, some of which are provably tight. From the perspective of statistical physics, our results yield rigorous estimates on the ground-state energy of real and complex, possibly non-Gaussian, spin glass models. From the perspective of quantum information, they establish bounds on the geometric entanglement of random bosonic states and of random states with bounded multipartite Schmidt rank, both in the thermodynamic limits as well as the regimes of large local dimensions.
In this paper, we present a technically simple method to establish upper bounds on the expected injective norm of real and complex random tensors. Our approach is somewhat analogous to the moment method in random matrix theory, and is based on a deterministic upper bound on the injective norm of a tensor which might be of independent interest. Compared to previous approaches to these problems (spin-glass methods, epsilon-net techniques, Sudakov-Fernique arguments, and PAC-Bayesian proofs), our method has the benefit of being nonasymptotic, relatively elementary, and applicable to non-Gaussian models. We illustrate our approach on various models of random tensors, recovering some previously known (and conjecturally tight) bounds with simpler arguments, and presenting new bounds, some of which are provably tight. From the perspective of statistical physics, our results yield rigorous estimates on the ground-state energy of real and complex, possibly non-Gaussian, spin glass models. From the perspective of quantum information, they establish bounds on the geometric entanglement of random bosonic states and of random states with bounded multipartite Schmidt rank, both in the thermodynamic limits as well as the regimes of large local dimensions.
The injective norm is a natural generalization to tensors of the operator norm of a matrix. In quantum information, the injective norm is one important measure of genuine multipartite entanglement of quantum states, where it is known as the geometric entanglement. In this paper, we give a high-probability upper bound on the injective norm of real and complex Gaussian random tensors, corresponding to a lower bound on the geometric entanglement of random quantum states, and to a bound on the ground-state energy of a particular multispecies spherical spin glass model. For some cases of our model, previous work used ε-net techniques to identify the correct order of magnitude; in the present work, we use the Kac--Rice formula to give a one-sided bound on the constant which we believe to be tight.
It was recently proven that, in contrast to their matrix analogues, the moments of a real Gaussian tensor of size N do not in general factorize over their connected components in the asymptotic large N limit. While the original proof of this rather surprising result was not constructive, explicit examples of non-factorizing moments, which are expectation values of trace-invariants, have since then been discovered. We explore further aspects of this problem, with a focus on Haar-distributed (or Gaussian) complex random tensors, which are more directly relevant to quantum information. We start out by exhibiting an explicit example of non-factorizing trace-invariant, thereby filling a gap in the recent literature. We then turn to the opposite question: that of finding interesting families of trace-invariants that do in fact factorize at large N. We establish three main theorems in this regard. The first one provides a sufficient combinatorial bound ensuring large N factorization, that is also simple enough to be applicable to various cases of practical relevance. Our second main result shows that the expectation value of any compatible trace-invariant is dominated by certain tree-like combinatorial structures at large N, which we refer to as tree-like dominant pairings. Our third main theorem establishes that any trace-invariant admitting tree-like dominant pairings does actually factorize at large N. In this way, we are able to prove that various families of trace-invariants that have been previously studied in the literature do factorize at large N. We apply our findings to the theory of multipartite quantum entanglement: to any trace-invariant is associated a multipartite generalization of Rényi entanglement entropy, whose typical expectation value in the uniform random quantum state can be explicitly computed assuming large N factorization.
Genuine multipartite entanglement of a given multipartite pure quantum state can be quantified through its geometric measure of entanglement, which, up to logarithms, is simply the maximum overlap of the corresponding unit tensor with product unit tensors, a quantity that is also known as the injective norm of the tensor. Our general goal in this work is to estimate this injective norm of randomly sampled tensors. To this end, we study and compare various algorithms, based either on the widely used alternating least squares method or on a novel normalized gradient descent approach, and suited to either symmetrized or non-symmetrized random tensors. We first benchmark their respective performances on the case of symmetrized real Gaussian tensors, whose asymptotic average injective norm is known analytically. Having established that our proposed normalized gradient descent algorithm generally performs best, we then use it to obtain numerical estimates for the average injective norm of complex Gaussian tensors (i.e., up to normalization, uniformly distributed multipartite pure quantum states), with or without permutation-invariance. We also estimate the average injective norm of random matrix product states constructed from Gaussian local tensors, with or without translation-invariance. All these results constitute the first numerical estimates on the amount of genuinely multipartite entanglement typically present in various models of random multipartite pure states. Finally, motivated by our numerical results, we posit two conjectures on the injective norms of random Gaussian tensors (real and complex) and Gaussian MPS in the asymptotic limit of the physical dimension.
A bstract The largest eigenvalue of random tensors is an important feature of systems involving disorder, equivalent to the ground state energy of glassy systems or to the injective norm of quantum states. For symmetric Gaussian random tensors of order 3 and of size N , in the presence of a Gaussian noise, continuing the work [1], we compute the genuine and signed eigenvalue distributions, using field theoretic methods at large N combined with earlier rigorous results of [2]. We characterize the behaviour of the edge of the two distributions as the variance of the noise increases. We find two critical values of the variance, the first of which corresponding to the emergence of an outlier from the main part of the spectrum and the second where this outlier merges with the corresponding largest eigenvalue and they both become complex. We support our claims with Monte Carlo simulations. We believe that our results set the ground for a definition of pseudospectrum of random tensors based on Z-eigenvalues.
Abstract Random tensor models have applications in a variety of fields, such as quantum gravity, quantum information theory, mathematics of modern technologies, etc., and studying their statistical properties, e.g. tensor eigenvalue/vector distributions, is interesting and useful. Recently some tensor eigenvalue/vector distributions have been computed by expressing them as partition functions of 0D quantum field theories. In this paper, using this method, we compute three cases of complex eigenvalue/vector distributions of symmetric order-three random tensors, where the three cases can be characterized by the Lie-group invariances, O(N,R), O(N,C), and U(N,C), respectively. Exact closed-form expressions of the distributions are obtained by computing partition functions of four-fermi theories, where the last case is of the “signed” distribution, which counts the distribution with a sign factor coming from a Hessian matrix. As an application, we compute the injective norm of the complex symmetric order-three random tensor in the large-N limit by computing the edge of the last signed distribution, obtaining agreement with an earlier numerical result in the literature.
Abstract We define and study XOR games in the framework of general probabilistic theories, which encompasses all physical models whose predictive power obeys minimal requirements. The bias of an XOR game under local or global strategies is shown to be given by a certain injective or projective tensor norm, respectively. The intrinsic (i.e. model-independent) advantage of global over local strategies is thus connected to a universal functionr(n, m) called ‘projective–injective ratio’. This is defined as the minimal constant ρ ρ such that ∥⋅∥X⊗πY⩽ρ∥⋅∥X⊗εY ‖·‖X⊗πY⩽ρ‖·‖X⊗εY holds for all Banach spaces of dimensions dimX=n dimX=n and dimY=m dimY=m , where X⊗πY X⊗πY and X⊗εY X⊗εY are the projective and injective tensor products. By requiring that X=Y X=Y , one obtains a symmetrised version of the above ratio, denoted by rs(n) rs(n) . We prove that r(n,m)⩾19/18 r(n,m)⩾19/18 for all n,m⩾2 n,m⩾2 , implying that injective and projective tensor products are never isometric. We then study the asymptotic behaviour ofr(n, m) and rs(n) rs(n) , showing that, up to log factors: rs(n) rs(n) is of the order n n (which is sharp);r(n, n) is at least of the order n1/6 n1/6 ; andr(n, m) grows at least as min{n,m}1/8 min{n,m}1/8 . These results constitute our main contribution to the theory of tensor norms. In our proof, a crucial role is played by an ‘ ℓ1/ℓ2/ℓ∞ ℓ1/ℓ2/ℓ∞ trichotomy theorem’ based on ideas by Pisier, Rudelson, Szarek, and Tomczak-Jaegermann. The main operational consequence we draw is that there is a universal gap between local and global strategies in general XOR games, and that this grows as a power of the minimal local dimension. In the quantum case, we are able to determine this gap up to universal constants. As a corollary, we obtain an improved bound on the scaling of the maximal quantum data hiding efficiency against local measurements.