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. ITNT evaluates such functions in compressed form and demonstrates higher-fidelity reaction-rate computation and large-scale extremum finding.

  • Problem

    Tensor trains lack direct implementations for generic element-wise nonlinear functions, limiting their use for nonlinear data transformations.

  • Method

    ITNT iteratively combines efficient tensor-train operations to evaluate arbitrary elementary and nonlinear filtering functions entirely within the compressed domain.

  • Results

    ITNT approximates reactive-flow reaction-rate features at bond dimension χ = 200, while interpolation fails to reproduce most features and creates artifacts, and finds near-optimal configurations in 2^70 spaces.

  • Takeaways & Limitations

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

  • Takeaways & Limitations

    The iterative map can become unstable and diverge for inputs outside its convergence domain, requiring global rescaling to maintain convergence.

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

The introduction frames nonlinear processing of large-scale TT-encoded data as a central unresolved challenge. It presents ITNTs as a general, compressed-domain framework for applying arbitrary functions through efficient iterative transformations.

  • Motivation: Tensor trains address the curse of dimensionality by representing large data arrays as products of smaller tensors.This format supports compressed representations of large-scale datasets relevant to complex-system simulations and machine learning.
  • Motivation: Nonlinear physical quantities require transformations within compressed TT representations, but TT formats provide only a limited set of explicit rank-controlled operations.The stated supported operations include linear operations and partial integrations, while general nonlinear transformations remain structurally difficult.
  • ITNT framework: ITNTs introduce a general framework for applying arbitrary functions to TT-encoded data through iterative tensor network transformations.The framework is designed to overcome the structural limitation that makes nonlinear operations difficult in TT format.
  • ITNT framework: ITNTs combine linear operations, partial integrations, and element-wise multiplications to evaluate elementary and highly nonlinear filtering functions over N points entirely in the compressed domain.The approach performs these evaluations in parallel while maintaining a highly controlled computational procedure.

II. RESULTS

ITNT extends tensor-train operations to nonlinear, non-invertible functions and achieves stable, accurate approximations for reactive-flow evaluation and large Max-3-SAT optimization. It can identify optimal or near-optimal configurations while probing only a tiny fraction of exponentially large search spaces, although certification depends on truncation-error control.

  • ITNT framework: ITNT combines scalar multiplication, variational addition, element-wise products, and partial integration, with TT addition scaling as O(nχ^3).These primitives enable direct evaluation of integer polynomials, exponentiation, and functions including sine, cosine, hyperbolic sine, and hyperbolic cosine.
  • Nonlinear functions: ITNT addresses highly nonlinear, non-invertible tasks such as sign evaluation and extremum finding, which elementary iterative methods cannot handle.The sign-function algorithm uses homomorphic comparison implemented through addition, scalar multiplication, and element-wise multiplication.
  • Reactive-flow evaluation: χ = 200 yields a good approximation of reactive-flow reaction-rate features using 0.4% of the original size, whereas TCI misses most features and creates artifacts.The reaction-rate field quantifies methane-combustion chemical kinetics using Ec = 17865.2 [K] and A0 = 1.
  • Reactive-flow evaluation: Below 2% relative error is reached for the reciprocal 1/T field at χ = 200 after 5 iterations, with error decaying as 1/χ.ITNT shows steady error reduction without TCI’s instability around χ = 200, supported by rapid quadratic Newton-Raphson convergence.
  • Extremum finding: E = 679 identifies three configurations matching the best-known n = 70 Max-3-SAT solution, with pairwise Hamming distances of 1, 12, and 13.The encoded energy landscape converges toward a few dominant configurations compared with the full 2^70-space.
  • Extremum finding: O(10^4) peaks are visited instead of exhaustively evaluating 2^70 ≈ 10^21 configurations, while the next-best E = 678 solution appears after 11 steps.Random binary fixation provides an approximate early-stopping mode when exact maximum finding requires intractably many self-multiplications.
  • Certification and scalability: Global-maximum certification requires per-step truncation errors to remain within a budget set by the margin separating the optimum from the rest of the landscape.Successful brute-force fixation can require minimum bond dimensions far below the certification threshold, enabling the n = 70 problem despite certification being out of reach.

III. DISCUSSION

The discussion establishes ITNTs as a general framework for arbitrary nonlinear computations on tensor-train data in the compressed domain, while outlining performance improvements and broader optimization applications as future directions.

  • Contributions: ITNTs provide a general framework for element-wise computation on tensor-train data, including arbitrary nonlinear functions evaluated entirely in the compressed domain.The authors characterize this capability as broadening the scope of tensor network applications beyond field processing.
  • Future directions: Alternative methods may improve ITNT scaling across different system sizes and bond dimensions, despite the robustness of the zip-up method.The discussion identifies alternative approaches as a future investigation area.
  • Future directions: Tailored preprocessing, including initial normalization or a Fourier transform to the tensor train, could significantly accelerate iterative-routine convergence.These preprocessing steps are proposed as ways to improve convergence rather than reported results.
  • Broader applications: ITNTs could address computationally intensive optimization problems mappable to Ising Hamiltonians, including prime factorization, genetic haplotype reconstruction, and large-scale financial simulations.The discussion presents these applications as a pathway opened by the work.
  • Broader applications: Mapping ITNT algorithms onto quantum hardware is identified as a long-term direction, building on promise from tensor-train methods in quantum settings.The passage frames quantum-hardware integration as future work.

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

The methods maintain compressed tensor-train representations through SVD-based truncation and sweeping, then use partial integration to aggregate tensor entries according to selected index bits.

  • V. METHODS: The methods section details ITNT foundations and applications, beginning with SVD truncation and sweeping for low-rank tensor representations.It also introduces partial integration before later sections on elementary functions and preconditioning.
  • A. The SVD truncation: SVD identifies the optimal low-rank tensor approximation by minimizing the ℓ2 norm of the truncation error.This establishes the compression basis for tensor-train representations.
  • A. The SVD truncation: Retaining singular-vector subspaces associated with the most significant singular values maximizes fidelity for a fixed bond dimension χ.The procedure selects the dominant subspace while keeping the representation low rank.
  • A. The SVD truncation: The bond dimension χ must be chosen carefully to support numerical stability and efficient convergence.The passage identifies χ selection as a practical control in the truncation procedure.
  • B. Partial Integration: Partial integration I(Ψ, q) returns a two-element array that partitions sums according to the qth bit of index j.Its two entries correspond to the two possible values of that bit.
  • B. Partial Integration: I(Ψ, q)[0] sums Ψ[j] over indices whose qth bit equals 0, whereas I(Ψ, q)[1] sums entries whose bit equals 1.The two components therefore separate tensor entries by the selected bit value.
  • B. Partial Integration: The formalism represents the index j with its qth bit removed using the notation j\{jq}.This notation specifies the reduced bit string used in the partial-integration expression.

C. ITNT for realizing elementary functions

ITNT evaluates elementary functions directly in tensor-train form through iterative element-wise products, exponentiation, and Newton-Raphson transformations. This framework supports arbitrary real powers and nonlinear transformations while controlling tensor-network complexity and convergence.

  • Integer powers: ITNT represents integer powers by iteratively applying element-wise products to tensor trains, with truncation limiting the maximum bond dimension to χ.The product uses the zip-up method and has time complexity O(nχ^4) and memory complexity O(χ^3).
  • Exponentiation: Exponentiation is constructed by repeatedly transforming R(0) = I + f/2^l, with lim_l→∞ R(l) = exp(f).The iteration approaches e^f(x), while l must balance approximation accuracy against truncation-error accumulation.
  • Exponentiation: The exponentiation transformation extends to thermal path-integral sums over configurations and to the unitary phase transformation f(x) → e^if(x).These operations are performed directly in the TT representation using iterative self-multiplication techniques.
  • Newton-Raphson transformations: Newton-Raphson transforms tensor trains element-wise by solving g(R(x)) = 0, converging quadratically when g is differentiable at its root.The target transformation satisfies T(f(x)) = lim_k→∞ R(k)(x) when R(0)(x) is chosen to ensure convergence.
  • Newton-Raphson transformations: Combining reciprocal and square-root iterations enables element-wise evaluation of fractional, negative, and arbitrary real powers.The reciprocal uses a suppression constant for the initial guess, while the square-root iteration is also known as Heron’s method.

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

The paper accelerates sign-function evaluation with auxiliary preconditioning, develops an iterative extremum-finding procedure with binary fixation and deflation, and encodes Ising energy landscapes sparsely in tensor trains for global feature extraction.

  • D. Accelerating element-wise sign function evaluation: Applying the auxiliary transformation G twice before iterating F accelerates convergence toward the sign function and produces a sharp step-like profile near the origin.The composition F(3) ◦ G(2) is illustrated starting from f(x) = x.
  • D. Accelerating element-wise sign function evaluation: Sign-function iteration remains accurate within its stable domain but oscillates and diverges when |x| exceeds the convergence radius.The instability arises because the polynomial composition F ◦ G has fixed points at {−1, 0, 1}, with inputs outside their basins driven toward infinity.
  • E. Extremum-finding ITNT with a limited number of self-multiplications: Iterative self-multiplication with normalization transforms a TT field into R(k), proportional to f ⊙2^k, whose dominant peaks identify indices with large |f[j]|.Self-multiplication amplifies large elements while normalization follows each step.
  • E. Extremum-finding ITNT with a limited number of self-multiplications: Binary fixation extracts a candidate maximum by comparing partial-integral magnitudes for each binary branch and selecting the larger branch until all sites are fixed.The procedure uses a randomly chosen site ordering.
  • E. Extremum-finding ITNT with a limited number of self-multiplications: Deflation subtracts each selected peak, and repeated binary fixation–deflation yields ranked candidate maxima from which the largest is accepted as the true maximum.The removed peak is represented by a χ = 1 TT localized at the candidate index.
  • E. Extremum-finding ITNT with a limited number of self-multiplications: Self-multiplication can exponentially increase bond dimension, while intermediate truncation, truncation errors, and double-precision round-off can prevent reliable recovery of the true maximum.Randomized fixation-site traversal and deflation mitigate local-extrema trapping and help the global maximum emerge.
  • F. Encoding the energy landscape of Ising Hamiltonians: The Ising energy landscape is encoded as a TT by assigning E[σ] = E(σ) to each bit-string configuration, with bond dimension bounded by the number of nonzero coupling terms.Two-body interactions are described, and the construction generalizes to arbitrary m-body interactions.
  • F. Encoding the energy landscape of Ising Hamiltonians: Because the encoded landscape is sparse, ITNTs can operate directly on it to extract lowest- and highest-energy configurations and configurations near a specified energy.Summing coupling-term TTs produces a bond dimension corresponding to the number of energy terms, including the constant offset.

G. Truncation error budget for certified optimality of Max-3-SAT solutions · Supplemental Material for Iterative Tensor Network transformations for · I. APPLICATION IN NONLINEAR PDE

The section derives a truncation-error budget that certifies optimality for Max-3-SAT solutions found by maximum-finding ITNT. It also identifies supplemental material and introduces a Newton-Raphson ITNT application to nonlinear PDEs, focusing on the Kidder equation.

  • G. Truncation error budget for certified optimality of Max-3-SAT solutions: The energy landscape is normalized as Ψ = E/A, with A equal to the maximum number of satisfied clauses.The derivation first establishes a sufficient number P of self-multiplication steps for the encoded Max-3-SAT field.
  • G. Truncation error budget for certified optimality of Max-3-SAT solutions: P > log2(nM ln 2) suffices for retaining an optimal branch, and Fig. 3(c) uses P = ⌈log2(nM)⌉+ 1.The bound uses A ≤ M, because at most M clauses can be satisfied.
  • G. Truncation error budget for certified optimality of Max-3-SAT solutions: At each self-multiplication step, truncation injects error τp, whose ℓ2 norm is tp, while ∆p measures deviation from the exact self-multiplied field.The computed field is denoted R(p), with R(0) = Ψ.
  • G. Truncation error budget for certified optimality of Max-3-SAT solutions: BF identifies the optimal branch when the correct-versus-incorrect partial-integral difference remains positive after accounting for truncation deviation.The sufficient condition is Λ(R(P), q) ≥ 1 − 2n exp(−2P/M) − |Λ(∆P, q)| > 0.
  • G. Truncation error budget for certified optimality of Max-3-SAT solutions: The optimality certificate follows from telescoping error propagation across the P steps, with the final truncation omitted because the fused final squaring requires no compression.The truncation errors tm must obey the resulting bound over the full P steps.
  • Supplemental Material for Iterative Tensor Network transformations for: The supplemental material is titled “Element-Wise Evaluation of Elementary and Filtering Functions” and lists the paper’s authors and affiliations.These passages provide the supplemental document heading and institutional information.
  • I. APPLICATION IN NONLINEAR PDE: The Newton-Raphson-based ITNT method is applied to nonlinear PDEs in TT representation, focusing on the Kidder equation for flow pressure in porous tubes.The application is described as belonging to section V C.

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

The Kidder equation is solved in tensor-train form by combining Newton–Raphson evaluation of its nonlinear transformation with a self-consistent Picard iteration. The discretized fixed-point procedure enforces the boundary conditions and converges to the unique TT solution.

  • Using the Newton-Raphson Method to realize the nonlinearity in Kidder equation: The nonlinear transformation required by the Kidder equation is realized through an element-wise TT mapping.The method formulates the transformation as solving g(R(x)) = R(x)−2−1 −κ −w(x) = 0.
  • Using the Newton-Raphson Method to realize the nonlinearity in Kidder equation: For |κ| < 1 and |w(x)| < 1, Newton–Raphson converges from the unit-element initialization R(0) = I.The initialization represents R(0)(x) = 1.
  • Using the Newton-Raphson Method to realize the nonlinearity in Kidder equation: Quadratic convergence makes the Newton–Raphson iteration rapidly produce a TT accurately representing the target nonlinear function.The limiting TT is limk→∞|R(k)⟩.
  • Conducting the self-consistent Picard iteration: The discretized field uses finite differences for w′(x) and w′′(x), while w0 = 1 and w2^n = 0 remain fixed.These fixed endpoint values enforce the boundary conditions w(0) = 1 and lim x→∞w(x) = 0.
  • Conducting the self-consistent Picard iteration: The numerical Kidder-equation solver discretizes [0, xmax] into 2^n grid points with spacing ∆x = xmax/2^n.For κ = 0.5, xmax = 16 gives ∆x = 2^-12.
  • Conducting the self-consistent Picard iteration: A Picard fixed-point iteration isolates each interior wi and updates it using values from the previous iteration.The update is represented in TT form using coordinate and shift operators.
  • Conducting the self-consistent Picard iteration: The TT implementation encodes grid coordinates with X and index shifts with the operators ˆL and ˆR.ˆL shifts Ψ[j] to Ψ[j+1], while ˆR shifts Ψ[j] to Ψ[j−1].
  • Conducting the self-consistent Picard iteration: The fixed-point iteration continues until successive solutions are sufficiently close and converges to the unique TT satisfying the discretized equation and all boundary conditions.The procedure starts from an initial guess w(0).

Anderson Acceleration

Anderson Acceleration improves Picard iteration by combining multiple past iterates and residuals through a small least-squares problem, reducing iterations in stiff or nonlinear regimes. In the TT-based Kidder solver, controlled memory and TT-rank truncation support this acceleration, although convergence slows at higher grid finesse and accuracy requirements.

  • Method: Anderson Acceleration combines past iterates and residuals by solving a small least-squares problem for update coefficients.The coefficients are obtained from stored residual inner products and used to form a linear combination of previous solutions.
  • Method: An affine-invariant variant constrains the combination coefficients to sum to one.This preserves affine invariance while combining stored iterates.
  • Implementation: The TT-based implementation limits memory and truncates TT ranks while computing inner products of tensor-form residuals.Storing m previous iterates keeps the least-squares problem small and controls memory usage.
  • Numerical result: 10^-12 SVD tolerance and χ = 400 with m = 10 Anderson memory produced an initial slope of -1.1917912520439131, with error ∼6 × 10^-7 versus the standard result.The procedure used 10^5 Picard iterations and grid finesse Nres from 4 to 17, with TT prolongation to a finer grid before rerunning.
  • Limitations: At Nres ∼18, Anderson Acceleration becomes slow to converge, while 10-digit initial-slope accuracy requires an SVD tolerance of ∼10^-14.Tighter tolerance increases iteration cost as the bond dimension grows, motivating more efficient schemes such as Newton’s method.

II. TRUNCATION ERROR BOUNDING

The section derives a truncation-error condition ensuring that the maximum and second maximum of a positive field’s powered array retain their order after SVD truncation. It formalizes this using the maximum gap and perturbations caused by truncation, identifying 2 as the largest guaranteed factor.

  • Order-preservation condition: For a positive field Ψ, SVD truncation preserves the ordering of the maximum and sub-maximum of Ψ⊙2p under the derived condition.The condition is presented as Eq. (2), whose right-hand side is derived in the appendix.
  • Order-preservation condition: 2 is the largest factor for which order preservation is guaranteed.This factor is the stated sharp guarantee associated with the truncation bound.
  • Error and gap definitions: The proof defines Φ = Ψ⊙2p, its truncated counterpart Φ′, truncation error ε = ∥Φ − Φ′∥2, and gap ∆ between the maximum and second-largest untruncated values.The gap is defined as ∆ = max{Φ} − maxsub{Φ} > 0.
  • Perturbation analysis: Truncation lowers the maximum by δ1 and raises the second maximum by δ2, so order conservation requires δ1 + δ2 ≤ ∆.The perturbations represent depression of the maximum and elevation of the second maximum.
  • Perturbation analysis: The error constraints are tight when δ1 = δ2, with the second inequality saturated at δ1 = δ2 = ε/2.These saturation cases complete the derivation of Eq. (2).

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

ITNT sign transformation achieves controlled accuracy and scalable computation through bond-dimension and SVD-tolerance choices. Its iteration converges rapidly near stable fixed points while imposing a resolution threshold near the unstable zero.

  • Accuracy and scaling: Choosing χmax ≳5Nroot is crucial to minimize the convergent iteration step Niter.A cutoff bond dimension bounds resource requirements, while choosing it slightly above χmin can accelerate convergence.
  • Accuracy and scaling: Increasing the SVD tolerance from 10−8 to 10−6 slightly increases the L2-norm error from ∼10−8 to ∼10−6.The larger tolerance can further boost convergence speed.
  • Iteration dynamics: Near f = ±1, the homomorphic comparison iteration exhibits double-exponential convergence toward its stable fixed points.The deviation follows approximately ϵ(k+1) ≈1.5(ϵ(k))^2, and a similar argument applies near f = −1.
  • Iteration dynamics: Near f = 0, nonzero values grow approximately as f(k) ≈f(0) × (1.5)^k, establishing the resolution threshold f(0) ≈(1.5)^−S after S iterations.Values larger than (1.5)^−S are effectively sign-transformed, whereas smaller values remain far from 1.
  • Root finding: ITNT locates roots by sign transformation, differential operator ˆR −ˆL, and deflation of the resulting multi-delta-peak TT.The procedure outputs root positions on the discretized grid.

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

The benchmark evaluates extremum-finding ITNT on a 12×12 classical Ising model and shows that self-multiplication preprocessing is crucial for locating the correct global extremum. The method handles a 144-site configuration space while incurring substantial self-multiplication cost and shorter deflation steps.

  • IV. BENCHMARK: PERFORMANCE OF EXTREMUM FINDING ON DISCRETE PROBLEM: A 12×12 square-lattice classical Ising model with random nearest-neighbor interactions and on-site terms is represented as an energy-landscape tensor train.The open-boundary example uses bond dimension χ = 409.
  • IV. BENCHMARK: PERFORMANCE OF EXTREMUM FINDING ON DISCRETE PROBLEM: Across 100 independent runs, subsequent ITNT steps identify and converge toward the true optimum as more trajectories locate the maximum-energy configuration.Runs use the same Hamiltonian but different random site sequences for binary fixation.
  • IV. BENCHMARK: PERFORMANCE OF EXTREMUM FINDING ON DISCRETE PROBLEM: 2^144 ∼ 10^43 configurations are covered by the 144-site system, demonstrating the scale of the discrete extremum-finding task.The benchmark concerns a 144-site configuration space.
  • IV. BENCHMARK: PERFORMANCE OF EXTREMUM FINDING ON DISCRETE PROBLEM: ∼2000 seconds is required for one self-multiplication of a χ = 409 tensor train on an Intel Core Ultra 9 275HX CPU.The same CPU was used for all computational benchmarks.
  • IV. BENCHMARK: PERFORMANCE OF EXTREMUM FINDING ON DISCRETE PROBLEM: 3 to 30 seconds are required for subsequent deflation steps as the bond dimension grows from 409 to 1209.Deflation follows the self-multiplication step in the extremum-location ITNT procedure.
  • Importance of self-multiplication steps: Without self-multiplication preprocessing, extremum-finding ITNT finds significantly lower-valued configurations and fails to detect the global extremum.The comparison is shown for a single instance without preprocessing.
  • Importance of self-multiplication steps: Self-multiplication before the main extremum-finding routine is crucial for resolving tightly packed spectral features, degenerate configurations, and rugged energy landscapes.The method can otherwise fail to identify the correct extremum.

Application in energy matching

The energy-matching protocol transforms the Ising energy landscape so that minimizing the transformed landscape identifies configurations whose energies are closest to zero. Deflation and enlarged bond dimension improve accuracy for this rugged, degenerate extremum-finding problem, producing highly accurate matches.

  • Application in energy matching: The protocol seeks configurations σ with E(σ) ≈ 0 by transforming the landscape as E′(σ) = E(σ)^2 − |E|^2_max.Here, |E|_max = max_σ|E(σ)| is estimated using the extrema-locating ITNT.
  • Application in energy matching: Because E′(σ) ≤ 0, its most-negative extremum identifies the configuration with E(σ) closest to zero.The configuration is located using the same extremum-finding ITNT steps.
  • Application in energy matching: Deflation mitigates truncation error in the highly degenerate and rugged transformed landscape near its extrema.The protocol uses 14 self-multiplications with fixed bond dimension χ = 818 for improved ITNT accuracy.
  • Application in energy matching: 104 candidates are identified for the 144-qubit energy-matching problem.The figure reports energy matching for E(σ) = 0 in the 144-qubit model.
  • Application in energy matching: |E(σbest)| ∼1.38 × 10^-4 is the best match, found after the i = 784th step.The second-best match is |E(σnext-best)| ∼1.81 × 10^-4 after the i = 5813rd deflation.
  • Application in energy matching: The self-multiplication phase takes ∼10^4 seconds per iteration, while subsequent extremum-finding ITNT runs take ∼60 seconds.During deflation, the bond dimension is truncated to 1900 whenever it reaches 2000.
Loading 2608.17135v1…