New paper: Injective norm of random real and complex tensors

Recently, Benjamin McKenna and I put out a paper on the arxiv about the injective norm of random real and complex tensors, and the geometric entanglement of random uniform quantum states (which as the name might not suggest, is directly related to the injective norm¹).

The injective norm is a natural generalization of the operator norm of a matrix. Actually it is really a family of norms as for the operator norms and, in our paper, we are only interested in one instance. Namely, given $\mathcal{H}_i$ $p\in \mathbb{N}$ Hilbert spaces of finite dimensions $d_i$ , the injective norm of an element $T\in \bigotimes \mathcal{H}_i$ is

$\lvert\!\lvert T \rvert\!\rvert_{\text{inj}}=\max_{\lvert\!\lvert x^{(i)} \rvert\!\rvert_2=1}\lvert\langle T, x^{(1)}\otimes \ldots\otimes x^{(p)}\rangle\rvert$

where $x^{(i)}\in \mathcal{H}_i$ . When $p=2$ one recognizes the operator norm (or rather the largest singular value) of $T$ (seeing $T$ as a matrix).

Exemplifying this notion with tensors coming from well known quantum states, we have:

Bell state: $\lvert B\rangle=\frac1{\sqrt{d}}\sum_{i=1}^N\lvert ii\rangle$ , that is the tensor (here matrix) has components $\delta_{ij}/\sqrt{d}$ . Obviously, its injective norm is $\lvert \! \lvert \lvert B\rangle \rvert \!\rvert_{\text{inj}}=1/\sqrt{d}$ .
W state: In this case, $p=3$ and $d_1=d_2=d_3=2$ , one has $\lvert W\rangle:=\frac1{\sqrt{3}}(\lvert 100\rangle+\lvert 010\rangle +\lvert 001\rangle)$ so that the corresponding tensor has non vanishing components $T_{1,0,0}=T_{0,1,0}=T_{0,0,1}=1/\sqrt{3}$ and we compute $\lvert \! \lvert \lvert W\rangle \rvert \!\rvert_{\text{inj}}=2/3$ .

In general, computing the injective norm of a tensor is a difficult problem, in fact, trying to optimize the defining function is NP-hard. This is one of the motivation behind our work. Computing the injective norm of tensors and quantum states is hard, but it has many applications. Indeed, this injective norm is one of the few measures of genuine multipartite entanglement, and as such plays an important role where such measures are useful, namely quantum computing, quantum information theory, phase transitions in topological materials… It also appears naturally in the field of statistical physics: The injective norm is directly related to the ground-state energy of some (spherical) spin glasses. Finally, it’s also studied in data analysis and statistics, for the hidden clique problem or when considering the problem of tensor PCA and independent component analysis.

The main theorem of our paper informally states that with high probability as $d_i=d \to \infty$ a standard gaussian random tensor (real or complex) $T$ has injective norm bounded above by

$\lvert \! \lvert T \rvert \!\rvert_{\text{inj}}\le \sqrt{dp}E_0(p)$

where $E_0(p)$ is the unique positive solution to some explicit equation. One has for instance, $\sqrt{3}E_0(3)\simeq 2.87001$ , while we recover the known random matrix folkore that for $p=2$ and with our conventions one should have with high probability $\lvert \! \lvert T \rvert \!\rvert_{\text{op}}\le 2.$ For a quantum state $\lvert \psi\rangle$ , the normalization results into the high probability bound

$\lvert \! \lvert \lvert \psi\rangle \rvert \!\rvert_{\text{inj}}\le \sqrt{\frac{p}{d^{p-1}}}E_0(p)$

On top of that, we also study the situation $p\to \infty$ and the local dimension $d$ fixed. Again, our main theorem states informally that

$\lvert \! \lvert T \rvert \!\rvert_{\text{inj}}\le \sqrt{p(d-1)}\gamma_d^K(p),$

where $K=\mathbb{R}$ or $\mathbb{C}$ and we can give a quite precise expansion of $\gamma_d^K(p)$ whose dominant behavior as $p\to \infty$ is of the form $\sqrt{\log p}$ .

To prove this theorem we reprove a slightly degenerate version of the Kac-Rice formula, and use the average count of critical point thus obtained to bound the excursion probability of a process of the form $f(x^{(1)},\ldots, x^{(p)})=\text{Re}\langle T, x^{(1)}\otimes\ldots\otimes x^{(p)}\rangle.$ In fact, this is a relatively classical trick in the realm of random fields and spin glasses, but doesn’t seem to appear in the literature on random tensors. It is basically a consequence of Markov inequality, as in fact, if $\max f (x^{(1)},\ldots, x^{(p)})\ge t$ then there should be at least one critical point $x^{(1)}_c,\ldots, x^{(p)}_c$ such that $f (x^{(1)}_c,\ldots, x^{(p)}_c)\in [t, +\infty)$ , and so one has thanks to Markov inequality

$\mathbb{P}(\max f (x^{(1)},\ldots, x^{(p)})\ge t)\le \mathbb{E}(N_0(\nabla f,f, [t, +\infty))).$

As Kac-Rice practitioners are well aware of, the main bottleneck when working with the formula is whether or not the resulting random matrix one has to understand is manageable or not. A lot of the studied cases in the literature are limited to relatively simple random matrices (typically simple modification of GOE random matrices). In our case, we are far from the GOE or relatively integrable random matrices, and so we strongly rely on recent techniques developed by Benjamin McKenna as well as Gérard Ben Arous and Paul Bourgade to understand the asymptotics of our random matrix integrals. However, we have to extend the domain of validity of those techniques, as some of the assumptions they rely on are not satisfied by our random matrices, therefore making them more robust. Furthermore, we also need recent random matrix inequalities that were recently obtained by Afonso S. Bandeira, March T. Boedihardjo, Ramon van Handel and resulting from the interpolation between free probablistic and classical random variables.

Well, now you know that it’s full of beautiful and interesting maths, so if you want to know more, you can read the paper!

It’s also directly related to another measure of entanglement named « Groverian » because of the role it plays in estimating the success probability of (possibly variations of) Grover’s algorithm. All those measures are basically the same, up to choices of conventions.
Note that the injective norm is also often known as the spectral norm of a tensor, or sometimes simply called largest singular value (or, in my opinion, a bit badly but it’s rare, eigenvalue) of a tensor. ↩︎

New paper: Injective norm of random real and complex tensors

Partager :