PaperlayerView exact revision on arXiv

Source-linked AI summary

Iterative tensor network transformations for element-wise evaluation of elementary and filtering functions

Xiao Wang, Tomohiro Hashizume, Pia Siegl, Dieter Jaksch

arXiv:2608.17135v1cs.LGcond-mat.stat-mechcs.AIphysics.comp-phquant-ph

TL;DR

Tensor trains lack direct implementations for generic element-wise nonlinear functions, limiting their use in general data processing. This paper introduces ITNT, an iterative framework for evaluating such functions in compressed TT form, and reports order-of-magnitude higher reaction-rate fidelity than interpolation alongside near-optimal discrete-optimization results.

  • Problem

    Although tensor trains support only a limited set of rank-controlled operations, generic element-wise nonlinear functions lack a direct TT implementation.

    Source: §I · p. 1

  • Method

    ITNT iteratively combines efficient TT operations to evaluate arbitrary element-wise functions directly on TT-encoded data.

    Source: §I · pp. 1–2

  • Results

    ITNT produced higher-fidelity reaction-rate estimates and found near-optimal discrete-optimization configurations, with reaction-rate fidelity an order of magnitude higher than interpolation.

    Source: §I · p. 2, §II · p. 7

  • Takeaways & Limitations

    ITNT broadens tensor-network applications to nonlinear field processing and global optimization over exponentially large configuration subspaces.

    Source: §III · p. 7

    For the sign-function transformation, inputs outside its stable convergence domain can cause oscillatory behavior and divergence, necessitating global rescaling.

    Source: D. Accelerating element-wise sign… · p. 10

Abstract

from arXiv · show

Tensor networks are powerful formats for compressing large-scale data. However, their application to general data processing has been limited by the difficulty of performing nonlinear operations. Here, we introduce iterative tensor network transformations (ITNTs), a general algorithmic framework for the element-wise evaluation of elementary and nonlinear filtering functions on data encoded as tensor trains (TTs), a class of tensor networks. Our approach operates entirely in the compressed domain, enabling efficient computation on exponentially large datasets while maintaining a controlled computational cost. We demonstrate its power in two key areas: (I) evaluating highly nonlinear elementary and filtering functions on a 3D reactive flow field, enabling high-fidelity reaction rate computation and region filtering, and (II) finding extrema in complex optimization problems, such as solving Max-SAT instances on spaces up to $2^{70}$ configurations. These results establish ITNT as a foundational tool that provides tensor network methods with the capability for general-purpose data science and large-scale optimization.

I. INTRODUCTION

Tensor trains compress large datasets, but their limited native operations make accurate element-wise nonlinear processing difficult. The introduction presents ITNTs as a compressed-domain framework and demonstrates them on reactive-flow computation and Max-SAT optimization.

I. INTRODUCTION

  • Tensor trains represent an array as products of smaller tensors, often reducing computational and memory requirements exponentially to O(log N).Their compression has supported large-scale simulations that are beyond methods requiring full-vector decompression.Source: §I · p. 1
  • Generic element-wise nonlinear functions lack direct TT implementations, while interpolation can fail on sharp, singular, or rugged transformations and bias nonlinear observables.Composing native operations into repeated, truncated schemes is a potential alternative whose accuracy for relevant applications had not been investigated.Source: §I · p. 1
  • ITNT applies arbitrary functions to TT-encoded data by iteratively composing linear operations, partial integrations, and element-wise multiplications in the compressed domain.The framework evaluates functions, including filtering operations, over N points in parallel with controlled computational cost.Source: §I · pp. 1–2
  • ITNT computes 3D reactive-flow reaction rates at order-of-magnitude higher fidelity than interpolation and finds Max-SAT solutions matching state-of-the-art heuristics across 2^70 configurations.Controlled truncation also enables explicit verification of solution validity.Source: §I · p. 2, Figure 1 · p. 2
  • For rugged Max-SAT landscapes, ITNT uses nonlinear filtering to discard irrelevant bulk structure and isolate near-optimal configurations while retaining a compressed representation.The introduction reports solutions matching heuristic algorithms and explicit validity verification through controlled truncation.Source: §I · p. 2, Figure 1 · p. 2

II. RESULTS

ITNT enables nonlinear transformations and filtering directly on tensor-train data, with accurate results on a reactive-flow field and a 70-variable Max-3-SAT instance. The results also distinguish finding strong solutions from certifying that they are globally optimal.

II. RESULTS

  • TT primitives support polynomial and exponential evaluation, while Newton-Raphson implements additional elementary functions; the Kidder-equation density slope matched analytical solutions to six decimal places.The reported elementary functions include sine, cosine, hyperbolic sine, and hyperbolic cosine.Source: §II · p. 3

a. Computing the sign function

  • For non-invertible functions, ITNT evaluates sign by iterative homomorphic comparison using addition, scalar multiplication, and element-wise products; inputs may require rescaling for convergence.The iteration converges when |Ψ[j]| < 3 for all j; preconditioning can speed convergence.Source: §II · p. 3

b. Extremum-finding ITNT

  • Binary fixation uses partial sums to select the maximum’s index bit by bit; power self-multiplication and SVD truncation manage the landscape, while randomized fixation and deflation provide an approximate fallback.The approximate fallback applies when the self-multiplications needed for exact search are intractably numerous under the available bond dimension.Source: §II · pp. 3–4

c. Application I: Data processing of a 3D reactive flow

  • At χ = 200, ITNT approximated the Arrhenius reaction-rate features using 0.4% of the original size, while TCI missed features and produced artifacts.Across bond dimensions, ITNT error decreased steadily without TCI’s instability around χ = 200.Source: §II · p. 4, Figure 2 · p. 5
  • At χ = 200, the reciprocal-field ITNT converged in five iterations to below 2% relative error, with error decaying as 1/χ.The reciprocal is the first step in the two-stage Arrhenius computation; the Newton-Raphson method enables rapid quadratic convergence.Source: §II · pp. 4–5
  • A maximum-temperature candidate was within 1% of the true maximum, and the filtered volume above 90% of that candidate had less than 1% relative error at χ = 200 after 10 rounds.The maximum search used five self-multiplications; the volume was computed using sign-transformation ITNT.Source: §II · p. 5, Figure 2 · p. 5

d. Application II: Solving NP-hard optimization problems

  • For instance s3v70c700-1, ITNT deflation found three configurations at E = 679, matching the best-known solution, after 1,655, 6,442, and 30,186 extremum-finding steps.Their pairwise Hamming distances are 1, 12, and 13.Source: Figure 3 · p. 6, §II · p. 6
  • The bond dimension required for global-maximum certification grows exponentially, while successful maximum search needs far less, explaining how the 70-variable instance was solved without certification.The truncation-error budget governs certification; the reported resource advantage applies to finding solutions, not verifying optimality.Source: Figure 3 · p. 6, §II · p. 7

III. DISCUSSION

ITNT extends tensor-train methods to arbitrary element-wise nonlinear computations in the compressed domain and introduces an optimization approach that compares partial sums over exponentially large configuration subspaces. The discussion identifies algorithmic refinements and broader applications as directions for future work.

DISCUSSION

  • ITNT combines compressed-domain nonlinear computation with global extremum search, offering high-quality approximate solutions to NP-hard problems in polynomial time under a controlled maximum bond dimension.The search compares partial sums over exponentially large configuration subspaces, keeping it informed by the broader solution landscape.Source: §III · p. 7
  • Alternative scaling methods, tailored preprocessing, high-precision arithmetic, and GPU acceleration may improve ITNT performance and enable larger-scale applications (20, 43, 44) (45) (15, 46).The article identifies the zip-up method as robust, while noting alternatives may scale better in some system-size and bond-dimension regimes; normalization or a Fourier transform may accelerate convergence.Source: §III · p. 7
  • Potential extensions include Ising-mappable optimization tasks, quantum-hardware implementations, and symmetry encoding to enforce physical or combinatorial constraints (47) (48) (49) (50–52) (53).Examples of Ising-mappable tasks include prime factorization, genetic haplotype reconstruction, and large-scale financial simulations.Source: §III · p. 7

V. METHODS · A. The SVD truncation · B. Partial Integration

These methods explain how SVD truncation maintains low-rank tensor-train representations and define partial integration through sums conditioned on a selected index bit.

V. METHODS

  • The methods section also outlines Newton-Raphson elementary-function evaluation, sign-function preconditioning, extremum finding, and compressed Ising-model encoding.The extremum-finding scheme uses self-multiplication, binary fixation, and deflation.Source: §V · p. 8

A. The SVD truncation

  • SVD truncation gives the optimal low-rank tensor approximation by minimizing the L2 truncation error, retaining the most significant singular-value subspace.For a fixed bond dimension χ, this yields the highest-fidelity approximation.Source: A. The SVD truncation · p. 8
  • For smooth functions, two-site SVD sweeps should start at the least significant bit; reversing the order significantly increases truncation error.The passage identifies sweep direction as critical to efficient compression.Source: A. The SVD truncation · p. 8
  • Choosing bond dimension χ carefully supports numerical stability and efficient convergence.Source: A. The SVD truncation · p. 8

B. Partial Integration

C. ITNT for realizing elementary functions

The section develops ITNT operations for evaluating elementary functions element-wise on tensor trains, using iterative products and root-finding methods. It covers integer and real powers, exponentials, trigonometric and hyperbolic functions, reciprocals, square roots, and logarithms.

C. ITNT for realizing elementary functions

  • TT element-wise products construct integer powers with maximum bond dimension χ, time complexity O(nχ^4), and memory complexity O(χ^3).The zip-up method realizes the product by transforming one TT into a diagonal operator using a copy tensor (29, 30).Source: C. ITNT for realizing elementary… · pp. 8–9
  • Iterated self-multiplication from I + f/2^l approaches exp(f), but l must be limited to avoid accumulating truncation errors.The limit approximation error becomes negligible when 2^l ≫ f_max, where f_max = max_x f(x).Source: C. ITNT for realizing elementary… · p. 9
  • For oscillatory functions, self-multiplication may converge slowly; CORDIC enables trigonometric and hyperbolic evaluations using shifts, additions, and comparisons (54).Unitary phase transformations provide a foundation for sine, cosine, and arcsine transforms, while CORDIC avoids the overhead of high-order polynomial expansions.Source: C. ITNT for realizing elementary… · p. 9
  • Newton-Raphson realizes nonlinear transformations T(f(x)) as a TT fixed-point iteration, provided the initial function ensures convergence; convergence is quadratic when g is differentiable at its root.The method reformulates the target using T^-1 and iterates toward R(x) = T(f(x)).Source: C. ITNT for realizing elementary… · p. 9
  • Newton-Raphson reciprocal and square-root operations support fractional, negative, and arbitrary real powers; the reciprocal iteration starts from f/c, with c chosen to ensure convergence.The square-root iteration is also known as Heron’s method.Source: C. ITNT for realizing elementary… · pp. 9–10
  • The logarithm iteration starts from R(0) = 0 and converges to ln(f(x)) when f(x) > 0 for all x.It uses the ITNT exponentiation algorithm to evaluate exp(R) within the transformation.Source: C. ITNT for realizing elementary… · p. 10

D. Accelerating element-wise sign function evaluation · E. Extremum-finding ITNT with a limited number of self-multiplications · F. Encoding the energy landscape of Ising Hamiltonians

These sections show how ITNT accelerates sign evaluation and locates extrema by repeated self-multiplication, then applies the framework directly to sparse TT encodings of Ising energy landscapes.

D. Accelerating element-wise sign function evaluation

  • Applying G twice before iterating F rapidly sharpens f(x)=x toward Sign{f}, while inputs beyond the convergence radius oscillate and diverge unless global rescaling keeps values in range.Source: D. Accelerating element-wise sign… · p. 10

E. Extremum-finding ITNT with a limited number of self-multiplications

F. Encoding the energy landscape of Ising Hamiltonians

  • The Ising landscape is encoded as E[σ]=E(σ) and assembled sparsely from χ=1 interaction TTs, with the construction extending to arbitrary m-body interactions.The resulting TT bond dimension corresponds to the number of energy terms, including the constant offset.Source: F. Encoding the energy landscape of… · p. 12
  • Applying ITNT directly to the encoded landscape extracts lowest- and highest-energy configurations and configurations closest to a specified energy, unlike methods encoding an annealer’s quantum state.Source: F. Encoding the energy landscape of… · p. 12

G. Truncation error budget for certified optimality of Max-3-SAT solutions · I. APPLICATION IN NONLINEAR PDE

The section derives a truncation-error criterion for certifying Max-3-SAT optimality and describes applying Newton-Raphson ITNT to nonlinear PDEs in tensor-train form.

G. Truncation error budget for certified optimality of Max-3-SAT solutions

  • For an M-clause instance, the energy field is normalized by A = max{E}; the unique optimum J has Ψ[J] = 1, while nonoptimal entries are at most 1 − 1/A.The optimum is assumed unique for simplicity; degeneracy only increases the margin.Source: G. Truncation error budget for… · p. 12
  • Under the worst case that every nonoptimal entry equals 1 − 1/A, the bound on powered nonoptimal entries uses A ≤ M to obtain the sufficient P criterion.Source: G. Truncation error budget for… · p. 12
  • The sufficient squaring count obeys P > log2(nM ln 2); Fig. 3(c) uses P = ⌈log2(nM)⌉ + 1.Source: G. Truncation error budget for… · p. 12
  • At step p, t_p = ε((R(p−1))⊙2, R(p)) = ||τ_p||_2 measures injected truncation error, while Δ_p = R(p) − Ψ⊙2^p is accumulated deviation.R(p) denotes the computed field after p self-multiplication steps.Source: G. Truncation error budget for… · p. 12
  • At each fixed site, branch-and-bound identifies the correct bit when the correct-versus-incorrect partial-integral gap remains positive after accounting for accumulated error.The proof gives the sufficient condition Λ(R(P), q) ≥ 1 − 2n exp(−2P/M) − |Λ(Δ_P, q)| > 0.Source: G. Truncation error budget for… · pp. 12–13
  • With zero initial truncation, error propagation is telescoping across steps; the final squaring has t_P = 0 because fusing it into the branch-and-bound contraction requires no compression.Source: G. Truncation error budget for… · p. 13
  • Optimality is certified when the truncation errors across all P steps satisfy the derived bound.The final bound omits the last truncation because the final squaring can be fused into the branch-and-bound contraction without compression.Source: G. Truncation error budget for… · p. 13

I. APPLICATION IN NONLINEAR PDE

  • The Newton-Raphson-based ITNT method is applied to nonlinear PDEs in tensor-train representation, focusing on the Kidder equation for flow pressure in porous tubes.Source: §I · p. 16

Using the Newton-Raphson Method to realize the nonlinearity in Kidder equation · Conducting the self-consistent Picard iteration

The sections describe a TT Newton–Raphson construction for the reciprocal nonlinearity and a Picard iteration for the discretized Kidder equation. The Picard iteration converges to the unique TT solution satisfying the discretized equation and boundary conditions.

Using the Newton-Raphson Method to realize the nonlinearity in Kidder equation

  • In TT representation, Newton–Raphson iteration starting from the unit-element TT R(0)=I on the equally discretized x-grid converges rapidly by quadratic convergence to accurately represent (1 − κw(x))^-1 when |κ| < 1 and |w(x)| < 1.Source: Using the Newton-Raphson Method to… · p. 16
  • For |κ| < 1 and |w(x)| < 1, starting from the unit-element TT R(0) = I yields rapid quadratic convergence to the reciprocal.Source: Using the Newton-Raphson Method to… · p. 16

Conducting the self-consistent Picard iteration

Anderson Acceleration

Anderson Acceleration improves Picard iteration by combining information from past iterates and residuals, but can become slow at high grid finesse. The section reports a refined-grid initial slope and identifies Newton-Raphson in the TT representation as a more effective acceleration option at that scale.

Anderson Acceleration

  • Anderson Acceleration combines multiple past iterate–residual pairs through a small least-squares problem to improve Picard updates, with a common variant constraining coefficients to sum to one.The coefficients minimize the new residual; the resulting combination of old solutions can reduce iterations, especially in stiff or nonlinear regimes.Source: Anderson Acceleration · p. 17
  • In a TT-based Kidder solver, limited history keeps the least-squares problem small, while residual inner products and TT-rank truncation manage computation and memory.These choices make Anderson Acceleration a flexible way to speed Picard iteration when large-scale Newton methods are difficult to implement or too expensive.Source: Anderson Acceleration · p. 17
  • At Nres = 17, Picard iteration with Anderson acceleration yielded an initial slope of -1.1917912520439131, about 6 × 10^-7 from the standard result in Ref. (33).The run used SVD tolerance 10^-12, χ = 400, and Anderson memory m = 10, with grid prolongation from Nres = 4 to 17.Source: Anderson Acceleration · p. 18
  • At Nres ≈ 18, Anderson acceleration becomes slow to converge; reaching a 10-digit initial slope also requires SVD tolerance near 10^-14, making iterations slower as bond dimension grows.The section identifies Newton’s method as a more efficient accelerator and says ITNT enables the Newton-Raphson step for (1−κw(x))−0.5 in the TT representation.Source: Anderson Acceleration · p. 18

II. TRUNCATION ERROR BOUNDING

For a positive field Ψ, the section derives a truncation-error bound that guarantees preservation of the maximum and second-maximum order in Ψ⊙2p. The guarantee holds up to a largest factor of 2.

II. TRUNCATION ERROR BOUNDING

  • 2 is the largest factor for which order preservation is guaranteed when the positive field is raised to Ψ⊙2p and SVD-truncated.The section derives the right-hand side of the order-preservation inequality in Eq. (2).Source: §II · p. 18
  • The bound compares the truncation error ε = ∥Φ − Φ′∥2 with the untruncated gap Δ between the maximum and second maximum, where Φ = Ψ⊙2p.Φ′ is the SVD-truncated array.Source: §II · p. 18
  • Truncation depresses the maximum by δ1 and elevates the second maximum by δ2, so preserving their order requires δ1 + δ2 ≤ Δ.The first inequality is saturated when δ1 = δ2; the truncation-error constraint is saturated at δ1 = δ2 = ε/2.Source: §II · p. 18

III. APPLICATION OF ITNT AS SIGN TRANSFORMATION - ACCURACY AND SCALING

The section evaluates ITNT sign transformation accuracy and scaling, explaining how bond-dimension choices and iteration dynamics govern convergence. It also describes using the transform to locate roots of smooth one-dimensional functions.

Accuracy and scaling

  • χfinal saturates quickly with tensor count and grows linearly with Nroot at ~10^-8 accuracy; χmax ≳5Nroot yields convergence in ≈2N iterations, after which TT bond dimension returns roughly to Nroot.Smaller cutoffs can slow convergence or cause divergence from numerical errors.Source: §III · pp. 18–19, Figure S2 · p. 20
  • ITNT runtimes remain manageable as N increases and are compared with full-grid Python/NumPy sign evaluation on the same Intel Core Ultra 9 275HX laptop.Source: §III · p. 19, Table I · p. 19
  • Raising SVD tolerance from 10^-8 to 10^-6 speeds convergence while increasing L2 error only from ~10^-8 to ~10^-6.Source: §III · p. 19

Iteration dynamics

  • Near the stable fixed points ±1, deviation follows ε(k+1) ≈ 1.5(ε(k))^2, producing double-exponential convergence when 1.5ε(0) < 1.Source: §III · p. 19
  • Near the unstable fixed point 0, values grow by about 1.5 per iteration, so after S steps the resolution threshold is (1.5)^-S; smaller initial values remain far from 1.Values above the threshold are pushed toward 1, yielding a sign-like output up to that resolution.Source: §III · pp. 19–20

Root finding

  • For smooth one-dimensional functions, sign changes indicate roots; applying sign ITNT and the differential operator R̂ − L̂ yields delta peaks that deflation locates on the discretized grid.Source: §III · pp. 20–21

IV. BENCHMARK: PERFORMANCE OF EXTREMUM FINDING ON DISCRETE PROBLEM · Importance of self-multiplication steps

On a 12×12 random Ising model, extremum-finding ITNT converged to the maximum-energy configuration across all 100 runs after 800 deflation steps. Self-multiplication preprocessing was crucial: without it, the algorithm failed on the rugged energy landscape.

IV. BENCHMARK: PERFORMANCE OF EXTREMUM FINDING ON DISCRETE PROBLEM

  • On a 12×12 square-lattice Ising model with random parameters in (−0.5, 0.5), the energy landscape was exactly encoded as a TT with χ = 409.The benchmark fixed the Hamiltonian, performed p = 8 self-multiplications, then ran 800 independent deflations using 100 stochastic seeds.Source: §IV · p. 21
  • After 800 stochastic deflation steps, all 100 runs converged to the same maximum-energy configuration.Across iterations, more trajectories found higher-energy configurations, and each deflation step identified a pronounced peak near the optimum.Source: §IV · p. 21
  • A single self-multiplication of the χ = 409 TT took ∼2000 seconds, while subsequent deflation steps took 3–30 seconds as bond dimension grew from 409 to 1209.The benchmark used an Intel Core Ultra 9 275HX CPU.Source: §IV · p. 21
  • The 144-site benchmark spans a configuration space of 2^144 ∼10^43.Source: §IV · p. 21
  • The extremum-location ITNT can also target arbitrary energy values; the paper describes finding an Ising configuration with |E[σ]| < 10^-4 for target E = 0.Source: §IV · p. 21

Importance of self-multiplication steps

  • Without self-multiplication preprocessing, extremum-finding ITNT failed to identify the correct extremum on the rugged energy landscape.Self-multiplication steps are crucial for resolving tightly packed spectral features near the maximum in continuous data or degenerate configurations; the unpreprocessed result was significantly lower than the preprocessed result.Source: Importance of self-multiplication steps · p. 22, Figure S5 · p. 22

Application in energy matching

The energy-matching protocol transforms the 12 × 12 random-field Ising energy landscape so an extremum-finding ITNT can identify configurations with energy closest to zero. Iterative deflation improves the match in a rugged, degenerate landscape.

Application in energy matching

  • The protocol defines E′(σ) = E(σ)^2 − |E|_max^2, whose most negative value identifies the configuration with E(σ) closest to zero.|E|_max is estimated using extrema-locating ITNT.Source: Application in energy matching · p. 22
  • E(σbest) ∼1.38 × 10−4 after 104 sub-leading peaks improved E(σfirst-try) ∼10−1; E(σnext-best) ∼1.81 × 10−4 is 45 Hamming steps away.The best match was found at the 784th step, and the second-best at the 5813rd deflation.Source: Application in energy matching · pp. 22–23, Figure S6 · p. 23
  • Deflation mitigates bond-dimension truncation error in the rugged, degenerate extremal landscape, helping locate closer matches than random binary fixation.The protocol uses χ = 818 for 14 self-multiplication iterations; subsequent deflation locates 104 sub-leading peaks.Source: Application in energy matching · pp. 22–23
Loading 2608.17135v1…