Positive definite Hermitian forms defined on Hilbert spaces \(V_1,\dots,V_k\) naturally extend to an inner product \(\langle \cdot, \cdot \rangle\) defined on the tensor space thereof, \(V_1\otimes \dots \otimes V_k\). Needless to say, this inner product induces a norm \(\| v \| := \sqrt{\langle v, v \rangle}\). Quantum physics characterizes unit norm tensors as pure quantum states; one such state is called separable if it corresponds to a simple tensor \(T=v_1\otimes \dots \otimes v_k\), and entangled if it corresponds to a tensor of higher rank \(\sum_i' v_{i,1}\otimes \dots \otimes v_{i,k}\).
Entanglement has consistently appeared to be a major actor in the qualitative evolution experienced by quantum algorithms. Thus its study, and particularly its measure, is germane to a variety of current fields in the theory of computation. The present paper addresses two such entanglement measures, linked to two mutually dual non-Euclidean norms: the spectral norm \(\| T \|_\sigma := \max_{\| v \|=1} |\langle T, v \rangle|\), and the nuclear norm \(\| T \|_\star := \min_{T=\sum v_i} \|v_i\|\), its defining gamut restricted to simple tensors \(v_i\). The two measures studied here are \(E( T):=-2\log_2(\|T\|_\sigma)\) and \(F( T):=2\log_2(\|T\|_\star)\), but most of the emphasis is placed on the first one.
The paper lays out its specific setting \(V_1=\dots = V_k = \mathbb{C}^n\) in Section 1.1 and states its first main results, namely an upper bound on \(C^2\) (\(C\) being the minimal spectral norm among unit-norm tensors \(T\in (\mathbb{C}^n)^{\otimes k}\)), and an upper bound on the fraction of unit tensors \(T\) in \((\mathbb{C}^n)^{\otimes k}\) satisfying a certain inequality involving \(E(T)\). These improve results from earlier works and help cement the notion that high entanglement is predominant. Such measure-derived predominance, however, does not guarantee the finding of an explicit tensor with high entanglement, and such construction is indeed an extremely testing and mostly unresolved task in a number of well-known open problems.
Once the challenge of constructing explicit tensors with large entanglement is established, one first example is provided, namely the classical determinant tensor, which, while objectively displaying high entanglement itself, falls short of the earlier bound provided by the paper itself. This can also be considered to be a main result, albeit one that is more specific and somehow set apart from those in Section 1.1.
Yet another main result is stated immediately thereafter in the next section, arising from the action of the symmetric group \(\mathfrak{S}_m\) on \(V:=(\mathbb{C}^n)^{\otimes m}\) given by tensor factor permutation and the resulting symmetric product \(\mathrm{Sym}^m(\mathbb{C}^n) \subsetneq (\mathbb{C}^n)^{\otimes m}\). The focus is restricted to symmetric tensors of length one, \(T\in S_1:=\mathrm{Sym}_1^m(\mathbb{C}^n)\), and the maximum entanglement \(E^s_{\max}:=\max \{ E(T) : T\in S_1\}\) is stated to have certain useful lower bounds.
The authors then proceed to pave the ground for the proofs of their main results. On the set of unit-norm tensors in \((\mathbb{C}^n)^{\otimes k}\cong \mathbb{C}^{n^k}\), which is nothing but the Euclidean sphere \(\mathbb{S}^{2n^k-1}\), certain subsets named \(\varepsilon\)-balls are defined in terms of the inner product, and important properties of the volume of said balls are proved. This in turn leads to lower bounds on the inner product as well as an upper bound on the cardinality of any covering of \(\mathbb{S}^{2n^k-1}\) by \(\varepsilon\)-balls, depending solely on \(\varepsilon\) and \(n\).
The aforementioned main results are then proved. The ancillary results leading to them are a lower bound on the inner product of arbitrary \(T\in \mathbb{S}^{2n^k-1}\) with some choice of centers of \(\varepsilon\)-balls in a covering of \(\mathbb{S}^{2n^k-1}\), a proof that said choice suffices for an alternative covering of the same sphere, and an inequality relating all the major constants involved in the problem. Once this is all settled, the main proofs follow in this and the next sections: the proofs of the main bounds, the proof that the determinant tensor shows high entanglement and the proofs of the upper bounds on norms of symmetric tensors of length one.