Compressing multivariate functions with tree tensor networks

arXiv:2410.03572 · quant-ph, cs.NA, math.NA, physics.comp-ph · Submitted 2024-10-04 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: We're looking at the paper: "Compressing multivariate functions with tree tensor networks".

Mira: Here's the gist of the paper. The gist Tensor networks are increasingly being used as a numerical ansatz for continuum functions by “quantizing” the inputs into discrete binary digits, and this work demonstrates the power of more general tree tensor networks (TTNs) for this purpose.

Kai: Constructing Functions as Tree Tensor Networks The paper provides direct constructions of several elementary functions as generic tree tensor networks and interpolative constructions for more complicated functions via a generalization of the tensor cross interpolation algorithm.

Mira: Direct construction shows that certain elementary functions are factorizable as a product of separate functions for each bit, leading to rank-one tensor networks with local tensors T(i,j) = f(i,j)(xi,j) (Page 4).

Kai: Specifically, three classes of rank-one functions are mentioned: Constant functions where f(x) = c = Qn i=1 QL j=1 c 1 nL (Page 4), Exponential functions where f(x) = cek·x+a = Qn i=1 QL j=1 c 1 nL e ki xi,j2j +a with a,c ∈ C and k = (k1, k2, …, kn) ∈ C n (Page 4), and the Dirac delta function f(x) = δ(x−x˜) = Qn i=1 QL j=1 2δxi,j,x˜i,j where δn,m is the Kronecker delta function and x˜i,j is the setting of digit (i, j) in the binary decomposition of x˜ (Page 4).

Title and authors: Kai: So to wrap up this paper, "Compressing multivariate functions with tree tensor networks," the main point is that we need more than just the standard tensor train method when dealing with multi-dimensional data because it's too inefficient for capturing those complex correlations.

Mira: They are proposing tree tensor networks as a more versatile format that handles these higher dimensions better by allowing for structured connections between the tensors.

Lev: What I see here is they are moving toward a formalism where the structure of the network itself helps solve the compression problem, not just relying on sequential ordering like in tensor trains.

Kai: The authors demonstrate how to construct exact representations of certain elementary functions, like polynomials of degree d, on these general tree tensor networks with a bond dimension that doesn't depend on the specific network topology.

Mira: That's a strong point because it means you don't have to worry about the network shape being perfect if you just want to represent a simple function accurately.

Lev: If we can guarantee that, then the overhead of building the structure itself is less of a limiting factor when we are trying to find an efficient representation.

Kai: They also show how they can use tensor cross interpolation to create interpolative constructions for more complicated functions through a generalization of that algorithm.

Mira: So this isn't just about finding one good function, it’s about having a method to dynamically learn and interpolate the space of possible functions.

Lev: That dynamic learning aspect is what makes it interesting for practical use, especially when we think about real-world data that might have complex dependencies.

Kai: These methods allow them to represent things like exponential functions, where the function form itself has several parameters a and c, as a tensor network with specific indices.

Mira: And they show that they can build even more complex things, like hyperbolic functions, by combining the exponential definition with their addition rules for tensor networks.

Lev: Building things piece by piece like that is exactly how we approach many quantum algorithms where you compose smaller operations into larger ones.

The paper's summary: Kai: The core of the paper is demonstrating that tree tensor networks are a more powerful tool for quantifying inputs into discrete binary digits than just one-dimensional tensor trains or matrix product states.

Mira: They show that by using these general tree tensor networks, you can achieve this quantization with much greater flexibility, which is what they call the power of tree tensor networks (TTNs) for this purpose.

Lev: So they are showing that TTNs offer a more expressive way to map continuous variables onto discrete binary strings than the limited rank-three tensors in a tensor train format.

Kai: They provide direct constructions for several elementary functions, including constants, exponentials, and the Dirac delta function using these tree tensor networks.

Mira: And they also show that they can construct polynomials of degree d on any tree tensor network where the bond dimension is set to d plus one.

Lev: That means we't don't have to worry about the rank being too small for a specific function, as long as we use a TTN structure appropriately.

Kai: They also detail how they handle addition and multiplication of these networks, which defines the space of functions you can realize with this new network format.

Mira: Addition just adds up the bond dimensions, chi = chi(one) + chi(two), and multiplication multiplies them down to chi = chi(one) chi(two) <ref:2410.03572#pg1>.

Lev: That algebraic definition of the space is crucial for understanding how complex functions are built from simpler ones.

Kai: They then introduce the tensor cross interpolation algorithm as a way to dynamically adapt the network ranks while moving through this space.

Mira: This allows them to actively minimize the infinity norm error, x f(x) - T(x), by adjusting neighboring pairs of local tensors.

Lev: It’s an active learning approach that lets you "learn general, multi-dimensional target functions f(x) into a TTN format" using pivots determined by the algorithm.

The paper's improvements: Kai: One major improvement is showing that for multivariate functions, structured tree tensor networks offer a significantly more efficient ansatz than the commonly used tensor train.

Mira: And in three dimensions, they found that coupled binary tree tensor networks and comb tree tensor networks are both better ansatzes for the function at hand.

Lev: The comb tree network compresses much more effectively under truncation of internal bonds than tensor trains, which is a key finding for practical applications.

Kai: For instance, the CTTN achieves an error of epsilon around ten-six with a bond dimension of fifteen, whereas tensor trains need thirty to reach that error.

Mira: That difference in rank shows how much better the structured network is at capturing correlations in higher dimensions.

Lev: But they also have to be careful because the paper flags that for real hardware, it's not just about achieving a good theoretical error on a computer; we have to consider the actual physical resources needed.

Kai: And they do address this by showing how the scaling of walltime with bond dimensions follows chi cubed and chi squared respectively for the comb tree and tensor trains.

Mira: That scaling difference in walltime is a concrete way to compare the two methods on physical hardware.

Lev: So, if you're building something, you have to weigh that faster theoretical compression against the practical cost of running it on real hardware.

Conclusion: Kai: To wrap up this paper "Compressing multivariate functions with tree tensor networks," the main implication is that for problems where the solution is a multivariate function with significant inter-dimensional correlations, we should move toward structured tree tensor networks instead of the standard tensor train ansatz.

Mira: The comb tree network seems to be a very effective ansatz for compressing these kinds of functions going forward.

Lev: It sounds like they are pushing us toward using these more structured networks when we think about problems that aren't just simple one-dimensional functions anymore.

Kai: We can use the methods here to build new, more efficient numerical algorithms by leveraging the generality of tensor-network based numerical methods.

Mira: The breadth of what this paper shows is that we can build a wide range of TTN-based numerical algorithms that broaden the potential for these methods significantly.

Lev: It gives us a lot to work with because the tools and methods described in this paper are all contained within the ITensorNumericalAnalysis.jl library, which makes it accessible for building things.

Center for Computational Quantum Physics, Flatiron Institute · PsiQuantum

quant-ph, cs.NA, math.NA, physics.comp-ph

Submitted: 2024-10-04

Updated: 2026-08-17

Comments: Revised Version

Journal ref: SciPost Phys. 21, 095 (2026)

DOI: 10.21468/SciPostPhys.21.4.095

Code: https://github.com/jtindall/ITensorNumericalAnalysis.jl

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 92/100

The gist: The gist Tensor networks are increasingly being used as a numerical ansatz for continuum functions by “quantizing” the inputs into discrete binary digits, and this work demonstrates the power of

Key concepts

Tree Tensor Networks (TTNs): These are a specific type of tensor network used to represent continuous functions by discretizing their inputs into binary digits. They allow for the construction and manipulation of complex functions, moving beyond simpler structures like tensor trains.
Tensor Cross Interpolation (TCI): This is an active learning algorithm that uses an 'interpolative gauge' to iteratively refine a network representation of a function. It dynamically changes the network's structure and ranks by querying the function at strategically chosen points, aiming to minimize the error between the function and its network approximation.
Comb Tree Tensor Network (CTTN): This is a structured tree tensor network topology that is shown to be particularly effective for compressing multivariate functions with strong inter-dimensional correlations. It achieves lower error norms and requires a smaller bond dimension compared to tensor trains for complex 3D problems.

Terminology

Mutual Information — 10× in this paper · explained in 2 episodes
Generalization — 7× in this paper · explained in 13 episodes
Tree Tensor Networks (TTNs) — 6× in this paper · explained in 2 episodes
Active Learning — 4× in this paper · explained in 6 episodes
Benchmark — 3× in this paper · explained in 2 episodes
Matrix Product States (MPS) — 3× in this paper · explained in 2 episodes
Accuracy — 2× in this paper · explained in 1 episode
Direct Numerical Simulation — 2× in this paper
Fixed Point — 2× in this paper · explained in 2 episodes
Quantum Physics — 2× in this paper · explained in 12 episodes
Radiative Transfer — 2× in this paper · explained in 2 episodes
Trace — 2× in this paper · explained in 2 episodes
Clustering — 1× in this paper · explained in 2 episodes
Core — 1× in this paper · explained in 2 episodes
Entanglement — 1× in this paper · explained in 4 episodes
Phase Transition — 1× in this paper · explained in 3 episodes
Phase Transitions — 1× in this paper · explained in 2 episodes
Quantization — 1× in this paper · explained in 15 episodes
Quantum Circuits — 1× in this paper · explained in 2 episodes
Tucker Decomposition — 1× in this paper · explained in 2 episodes

Summary

The gist Tensor networks are increasingly being used as a numerical ansatz for continuum functions by “quantizing” the inputs into discrete binary digits, and this work demonstrates the power of more general tree tensor networks (TTNs) for this purpose.

Constructing Functions as Tree Tensor Networks

The paper provides direct constructions of several elementary functions as generic tree tensor networks and interpolative constructions for more complicated functions via a generalization of the tensor cross interpolation algorithm. Direct construction shows that certain elementary functions are factorizable as a product of separate functions for each bit, leading to rank-one tensor networks with local tensors T(i,j) = f(i,j)(xi,j) (Page 4). Specifically, three classes of rank-one functions are mentioned: Constant functions where f(x) = c = Qn i=1 QL j=1 c 1 nL (Page 4), Exponential functions where f(x) = cek·x+a = Qn i=1 QL j=1 c 1 nL e ki xi,j2j +a with a,c ∈ C and k = (k1, k2, …, kn) ∈ C n (Page 4), and the Dirac delta function f(x) = δ(x−x˜) = Qn i=1 QL j=1 2δxi,j,x˜i,j where δn,m is the Kronecker delta function and x˜i,j is the setting of digit (i, j) in the binary decomposition of x˜ (Page 4). For polynomials of degree d on any tree tensor network where the bond dimension will be χ = d + 1, independent of the network (Page 5).

Multiplication and Addition

Rules for multiplying and adding together tensor networks are detailed to expand the space of possible functions which can be realized. Addition is defined as a new tensor network over the same labeled tree T with on-site tensors T˜(i,j) which are defined via T˜(i,j)(xi,j) = T(1)(i,j)(xi,j) ⊕ T(2)(i,j)(xi,j), resulting in a bond dimension of χ = χ(1) + χ(2) (Page 6). Multiplication is defined as a new tensor network over the same labeled tree T with resulting on-site tensors T˜(i,j)(xi,j) = T(1)(i,j)(xi,j)⊗T(2)(i,j)(xi,j), where the bond dimension of the new network is thus χ = χ(1)χ(2) (Page 6). An example provided is for the hyperbolic function f (x) = c cosh(k · x + a) with a,c ∈ C and k = (k1, k2, …, kn) ∈ C n can be built as a tensor network over any labeled tree T with χ = 2 by combining the exponential definition and the rule for addition (Page 6).

Interpolative Construction

The tensor cross interpolation (TCI) algorithm is described as an active learning algorithm which utilizes an “interpolative gauge” to move through the network, changing the gauge centre and updating neighboring pairs of local tensors in order to minimize the infinity norm supx(f(x)—T(x)) while dynamically adapting the ranks of the network (Page 7). The interpolative gauge is obtained by first choosing some tensor to be the root, or gauge center, of the tree, and then computing an interpolative decomposition (ID) of the resulting matrices using prrLU decomposition (Page 8). The algorithm proceeds by contracting these ID matrices towards the root until all of the network consists of interpolating Z tensors surrounding the root/center tensor (Page 8).

Numerical Results for Function Construction

The paper benchmarks different tree tensor network topologies for representing a target function f(x), using error measures ε = 1/g X x∈g f(x) − T(x) and ε∞ = f(x) − T(x)∞ (Page 9). For the Laguerre polynomial, the function can be represented with an error of ε ∼ 10−12 with maximum bond dimension χ = 7 on any of the labeled trees (Page 9). The tensor train ansatz with sequential digit ordering is noticeably more effective than the other labeled trees for typical one-dimensional functions because it captures fundamental correlations at a low cost (Page 9). In three dimensions, the coupled binary tree tensor network (BTTN) and the comb tree tensor network (CTTN) are both better ansatzes for the function at hand and compress much more effectively under truncation of the internal bonds than tensor trains (Page 11). The CTTN performs particularly well, achieving an error ε ∼ 10−6 with a bond dimension of χ = 15 while tensor trains each require a bond dimension of χ = 30 to reach such an error (Page 12).

Solving Fredholm Equations with Tree Tensor Networks

The paper introduces an iterative tree tensor network-based solver for Fredholm integral equations of the second kind, following Algorithm 1 (Page 13). The solution is represented as a TTN and the bond dimension of the solution is boundable in terms of the bond dimension of the kernel (Page 14). The algorithm’s time complexity scales, at worst, as O(NnLr(χz g χz K + χ2z K)) (Page 14). For example, in Example II for a two-dimensional solution f(x1, x2) = 1/(1+x1+x2) squared the TCI can construct g and K on the trees Tx and Tx∪Tt with errors on the order of the grid spacing ε ∼ O(2−L) while using χg,χK = 10, 10 (Page 14). The success of the algorithm relies on finding accurate, low bond dimension representations of K(x,t) and g(x) on the given labeled tree (Page 14). The error on the integration scales as O(exp(−L)) (Page 14).

Conclusion

For problems where the solution is a multivariate function with significant inter-dimensional correlations, our results suggest moving away from the tensor train ansatz and working with more structured tree tensor networks could push the state-of-the-art for problem solving (Page 15). The CTTN is believed to be a very effective ansatz for multivariate function compression going forward (Page 15).

Acknowledgments

The authors thank Matthew Fishman, Ryan Anselm and Marc Ritter for useful discussions, and they are grateful for ongoing support through the Flatiron Institute, a division of the Simons Foundation (Page 16). The tools and methods described in this paper are contained within the ITensorNumericalAnalysis.jl library (Page 16). The authors wish to emphasize that the generality of the work described here means that a wide range of TTN-based numerical algorithms can be built, significantly broadening the scope and potential of tensor-network based numerical methods (Page 16).

Appendix

The proof confirms that a tree tensor network whose local tensors have elements specified by Eq. (2) will contract down to the polynomial f(x) = Pd k=0 ck x k (Page 17). The construction is also shown for higher dimensions, where the virtual indices all of dimension χ = d + 1 (Page 17). Mutual information measurement can be performed efficiently by forming a norm network from two copies of f(x) and contracting over all physical indices other than xA and xB in O(nχz+1L) time (Page 18). The comb tree systematically outperforms the tensor trains for a given covariance matrix M, and the TCI algorithm converges to a value for the infinity norm ε∞ that is orders of magnitude lower for the comb tree than for the tensor trains (Page 19). The scaling of walltime with bond dimensions follows χ3 and χ2 respectively for the comb tree and tensor trains (Page 19).

References

The paper cites numerous foundational works on matrix product states, quantum information, and tensor network algorithms (Page 20). Key references include [1] F. Verstraete et al., [47] ITensorNumericalAnalysis.jl, and [29] Marc K. Ritter et al., which are used to support the methods introduced in this paper (Page 20). The references span areas such as quantum simulation, dimensionality reduction, and numerical linear algebra (Page 20). The work builds upon prior research in tensor train constructions for continuous functions (Page 21). The list of references is extensive, covering topics from quantum systems to large-scale optimization problems (Page 21). The paper's reliance on established methods like the Tensor Cross Interpolation algorithm is noted (Page 23).

Appendix Further Data

Figure S1 shows that the TCI algorithm converges to a value for the infinity norm ε∞ that is orders of magnitude lower for the comb tree than for the tensor trains - despite the train ansatzes utilizing a higher bond dimension and memory (Page 19). The scaling of walltime with bond dimensions follows χ3 and χ2 respectively for the comb tree and tensor trains (Page 19). More efficient caching of the function queries might bring the prefactor down significantly and expose the asymptotic ID scaling sooner (Page 19).

References Continued

The references include works on quantum systems [1], matrix product states [3], and various computational methods for tensor networks [4].

Improvements for AI systems

The improved system can represent multivariate functions using Tree Tensor Networks (TTNs) rather than the commonly used tensor train, allowing for a significantly more effective ansatz than tensor trains for multi-dimensional functions.
The system can construct exact representations of elementary functions, including polynomials of degree d, on arbitrary tree tensor networks with a bond dimension bounded independent of the network topology.
The system can utilize the tensor cross interpolation algorithm to learn general, multi-dimensional target functions f(x) into a TTN format, enabling adaptive learning by querying the function at adaptively determined points known as “pivots.”
The system can solve multi-dimensional, non-linear Fredholm equations using an iterative TTN-based solver where the bond dimension of the solution is therefore boundable in terms of the bond dimension of the kernel.
The system can achieve superior performance for functions with significant inter-dimensional correlations by employing structured tree tensor networks like the comb tree tensor network (CTTN) or coupled binary tree tensor networks (BTTN).