Recursive Sketched Interpolation: Efficient Hadamard Products of Tensor Trains

arXiv:2602.17974 · quant-ph, cs.NA, math.NA · Submitted 2026-02-20 · Read on arXiv

Listen

Radio episode about this paper

Transcript

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

Kai: Today's paper: "Recursive Sketched Interpolation".

Mira: Recursive Sketched Interpolation (RSI) is a novel algorithm designed to compute the Hadamard product of tensors in tensor-train format with cubic complexity in terms of bond dimension,

Kai: First, who's behind it and why it matters.

Paper summary: Kai: So we're looking at this paper about "Recursive Sketched Interpolation: Efficient Hadamard Products of Tensor Trains," and the main idea seems to be that they've found a way to compute the Hadamard product of tensors in tensor-train format much faster than what we typically use. Mira, can you give us the high-level overview of what this paper is actually proposing?

Mira: Well, Kai, essentially the thesis here is that conventional methods for computing this product usually scale at least as O(chi four) with respect to the TT bond dimension, which becomes a real problem when chi gets large. The authors introduce a novel "scale product" algorithm called Recursive Sketched Interpolation, which claims to compute the Hadamard product at a computational cost of O(chi three) instead. This is motivated by the scalability limits we see in current TT multiplication methods, and they use two main techniques: tensortrain sketching for dimensionality reduction and interpolative decomposition to get low-rank factorizations while still keeping access to the original tensor entries.

Lev: From a quantum error correction standpoint, an O(chi three) complexity is definitely appealing because it keeps the bond dimension compressed throughout the computation, which means we don't immediately hit that exponential wall in terms of memory or required operations when scaling up. But I have to ask, how does this O(chi three) claim hold up when you consider the actual physical constraints of running this on real hardware?

Kai: That's a fair point, Lev; what I'm seeing from the description is that RSI maintains a compressed bond dimension throughout the entire computation, which is what drives that complexity reduction. Mira, can you elaborate on how they achieve this compression without losing too much accuracy during these iterations?

Mira: They achieve this by employing tensortrain sketching for dimensionality reduction and then using interpolative decomposition to obtain low-rank factorizations while preserving access to tensor entries in the defining basis. The process is recursive, building one TT-core per iteration from index one to n and repeating it for subsequent cores, which keeps the bond dimension managed <ref:2602.17974#pg0>. This technique allows them to maintain a compressed bond dimension chi throughout the entire computation, which is what leads to that O(chi three) runtime complexity in their analysis.

Lev: If you're maintaining a compressed bond dimension across these recursive steps, what kind of fidelity issues are they encountering when approximating the output? I'm thinking about real hardware noise and how much error we can tolerate before the approximation becomes useless for actual quantum simulations.

Kai: The paper suggests that while they achieve this O(chi three) runtime, their experimental results across various TT scenarios demonstrate that RSI achieves superior runtime scalability with respect to bond dimension compared to conventional methods, while maintaining comparable approximation accuracy. That suggests the fidelity isn't drastically compromised by the compression technique itself.

Paper summary: Mira: Exactly; the key is that they are getting a reduced computational complexity of O(chi three) while still maintaining comparable approximation accuracy, which is what makes this method relevant for practical applications where we need efficiency without sacrificing too much precision. The authors also show the extensibility of RSI to more complex element-wise operations, like the Hadamard product of more than two TTs and other nonlinear maps.

Lev: Extending it to more than two TTs sounds promising, but I wonder if that increased complexity in the operation itself introduces new error sources that aren't captured by this sketching approach. If we're talking about running this on real hardware, the overhead of managing those more complex operations needs to be considered seriously.

Kai: That brings us to the next part of what they are doing: how they manage those intermediate steps in the process. We need to understand the mechanics behind how RSI actually executes these three main steps—sketched sketching, interpolative decomposition, and re-interpolation of input TTs—before we can judge its practical viability.

Mira: The workflow involves three main steps in each iteration: first, Tensortrain Sketching starts with a dimensionality reduction step by randomized TT sketching to get a sketched TT-core one an approximation of the original tensor at sites s one and s two <ref:2602.17974#pg0>. Then, Step two is Interpolative Decomposition of the Sketched Hadamard Product, which computes s 1s 2k = s 1s 2k one s 1s 2k two and this is decomposed using a row-based interpolative decomposition, yielding a first TT-core X s one alpha one with bond dimension chi G one = chi <ref:2602.17974#pg0>.

Lev: So, the complexity analysis you mentioned earlier relies on the costs associated with these specific steps; specifically, Step two in the j-th iteration involves applying a prrLU-based interpolative decomposition to a matricization of one two which they state incurs a third-order cost of O(d chi three) <ref:2602.17974#pg0>. That sounds computationally intensive even with the sketching.

Kai: It is indeed quite intensive, but the paper breaks down the leading iteration cost as O(nd two chi three), derived from applying random matrices and computing Khatri–Rao products, which they show simplifies to O(n chi three) for each input TT <ref:2602.17974#pg0>. Then we have the specific costs for Step one in the j-th iteration being O(d two chi three when contracting the sketch matrix with s j and s j+one cores <ref:2602.17974#pg0>.

Mira: And they don't forget Step three which is crucial for keeping things aligned: re-interpolation of the input TTs before computing the next core, requiring slicing and re-interpolating both input cores for T one and T two which incurs a complexity of O(d two chi three neglecting indexing costs <ref:2602.17974#pg0>. This entire sequence is what allows them to maintain a compressed bond dimension chi throughout the computation, as shown in their analysis.

Paper summary: Lev: That level of detailed accounting for the cost of re-interpolation and contracting matrices tells me that if we were trying to implement this on actual hardware, we'd need very efficient matrix contraction routines, especially given the O(d two chi three) cost recurring in every step <ref:2602.17974#pg0>. The real challenge isn't just the theoretical complexity; it's realizing that level of efficiency in practice.

Kai: So, to summarize what we have covered so far about "Recursive Sketched Interpolation: Efficient Hadamard Products of Tensor Trains," the paper proposes a method that achieves an O(chi three) computational cost for computing the Hadamard product, overcoming the traditional O(chi four) bottleneck by using randomized sketching and interpolative decomposition.

Mira: And we've established that this is achieved through a recursive process where they manage to keep the bond dimension compressed throughout, which is vital for scalability while keeping approximation accuracy comparable to prior methods.

Lev: If we look at the overall picture, the implications for error correction systems are significant because lower complexity means you can simulate larger Hilbert spaces or handle more complex interactions without immediately running into intractable computational limits.

Kai: And looking at the broader impact, if this method works as described, it suggests that operations we currently treat as prohibitively expensive in quantum simulations might become feasible with this kind of scaling improvement. This is something I'm really excited about from a hardware experimentalist point of view because it opens up new possibilities for what we can actually simulate.

Mira: The potential impact lies in the ability to perform more sophisticated calculations on tensor networks, which are fundamental to modeling many physical systems, without being strictly limited by the bond dimension constraints that have historically defined our simulation capabilities.

Lev: I just want to emphasize that this is a theoretical complexity reduction; the real test for any quantum error correction researcher will be how robust this algorithm is when you introduce realistic noise and decoherence into the hardware setup. That's where we need concrete results on error propagation, not just ideal complexity bounds.

Kai: So, to wrap up our discussion on "Recursive Sketched Interpolation: Efficient Hadamard Products of Tensor Trains," the paper presents a scalable algorithm that reduces the cost of this fundamental operation from at least O(chi four) down to O(chi three).

Mira: And we see that this reduction comes from cleverly combining tensortrain sketching for dimensionality reduction with interpolative decomposition to manage the complexity iteratively.

Lev: Ultimately, if these scaling properties hold up under physical noise conditions, it means we can tackle problems in quantum simulations that were previously out of reach due to computational overhead.

Kai: That’s what I’ve been thinking about; this paper points toward a new way to approach the core multiplication operations in tensor networks that could change how we build and analyze those systems.

Conclusion: Kai: So, we've been looking at this paper on "Recursive Sketched Interpolation," and now we need to wrap up by talking about what that title really means and what this work actually points toward for the future.

Mira: I think the core of it is understanding how they managed to squeeze a cubic complexity, O(chi three), out of an operation that was previously hitting a fourth-order wall, O(chi four). That compression across the entire process is what makes this title so significant for condensed matter theory.

Lev: From my side, I’m focused on whether that theoretical reduction translates into actual hardware performance; if we can't run it reliably on physical systems, it stays a paper result.

Kai: Exactly. When we talk about the authors and the title, what's the most important thing for our listeners to grasp about this new approach to tensor multiplication?

Mira: The key is that they found a way to keep the bond dimension compressed during every step of a recursive calculation, which allows them to perform these massive multiplications without immediately blowing up their required resources.

Lev: And what I want people to hear is the comparison against those older methods; showing that this method scales better than the direct Kronecker product approach is what really tells us something about future simulation limits.

Kai: So, in simple terms, we're talking about a more efficient recipe for multiplying these giant tensor networks that respects the constraints of current hardware while still being powerful enough for complex physics.

Mira: Precisely; it’s about finding the right mathematical structure—the interpolation and sketching—to tame the exponential growth inherent in these operations.

Lev: If this scaling holds up under realistic noise conditions, then we might actually start seeing simulations of much larger systems that were previously computationally prohibitive.

Kai: That leads perfectly into our next topic, because if this works, what does it mean for the real experiments we're doing with qubits?

Department of Computer Science, North Carolina State University · CCAM and Department of Statistics, University of Chicago · Center for Computational Quantum Physics, Flatiron Institute

quant-ph, cs.NA, math.NA

Submitted: 2026-02-20

Updated: 2026-10-06

Comments: 20 pages, 15 figures

Code: https://github.com/zmeng137/Recursive-Sketched-Interpolation

License: http://creativecommons.org/licenses/by-nc-sa/4.0/

Importance score: 69/100

The gist: Recursive Sketched Interpolation (RSI) is a novel algorithm designed to compute the Hadamard product of tensors in tensor-train format with cubic complexity in terms of bond dimension, offering

Key concepts

Hadamard Product
This is a fundamental operation in tensor networks where two tensors are multiplied element-wise. It is crucial for applications like multiplying quantum wavefunctions, but standard methods become computationally expensive as the tensor size grows.
Tensortrain Sketching
This technique uses random matrices contracted with the TT cores to create a lower-dimensional approximation of the original tensor. This dimensionality reduction helps manage complexity during the computation by sampling key information from the large tensors.
Interpolative Decomposition
This method is used to find low-rank factorizations of tensors by decomposing them into simpler components. In RSI, it is used to compute a sketched version of the Hadamard product while keeping the resulting bond dimension small.

Terminology

Summary

Recursive Sketched Interpolation (RSI) is a novel algorithm designed to compute the Hadamard product of tensors in tensor-train format with cubic complexity in terms of bond dimension, offering superior scalability compared to conventional methods.

The gist: RSI computes the Hadamard product of two TTs at a computational cost of O(χ3) by combining randomized tensor-train sketching with slice selection via interpolative decomposition.

Motivation and Problem

The Hadamard product is a fundamental operation in applications like TT-based function multiplication for nonlinear differential equations, but conventional methods scale as at least O(χ4) with respect to the TT bond dimension (TT-rank) χ, creating a severe computational bottleneck. The direct method involves forming the Kronecker product of TT-cores, which requires at least O(χ4) operations and yields a redundant output bond dimension of χ2. This redundancy necessitates a rank-compression step like TT-rounding, which has even higher complexity, dominating the total overhead. Other methods like cross interpolation also scale as at least O(χ4).

The RSI Algorithmic Framework

RSI is a scale product algorithm that maintains a compressed bond dimension throughout the computation to achieve a reduced computational complexity of O(χ3). The algorithm employs two key techniques:

  1. Tensortrain sketching for dimensionality reduction and range extraction.

  2. Interpolative decomposition to obtain low-rank factorizations while preserving access to tensor entries in the defining basis.

The process is recursive, constructing one TT-core per iteration from index 1 to n, and then repeating the procedure recursively for subsequent cores. The workflow involves three main steps in each iteration:

  1. Step 1—Tensor-Train Sketching: This starts with a dimensionality reduction step by randomized TT sketching. For the TT core, this involves contracting random matrices with the core tensor, resulting in a sketched TT-core T˜1, which is an approximation of the original tensor at sites s1 and s2.

  2. Step 2—Interpolative Decomposition of the Sketched Hadamard Product: This step computes G˜s1s2k = T˜s1s2k1 T˜s1s2k2, which is the sketched version of the output G = T1 ⊙ T2. This is decomposed using a row-based interpolative decomposition, yielding a first TT-core X s1,α1, with bond dimension χ G1 = χ.

  3. Step 3—Re-Interpolation of the Input TTs: Before computing the next core, the input TT-cores must be re-interpolated to align their s1 basis with I1, which is a pivot set determined by the ID step. This involves slicing and re-interpolating the input cores for both T1 and T2.

Complexity Analysis

The overall computational complexity of RSI is analyzed based on two order-n tensors, assuming uniform external dimensions (d) and bond dimensions (χ). The leading iteration cost is O(nd2χ3). This is derived from:

- Step 1 before iteration:

  1. Applying each random matrix omega to its corresponding TT-core, costing O(nχ2dk), which reduces to O(nχ3) when k = χ/d.

  2. Successively computing the Khatri–Rao product of the sketch matrix (χ×k) with the preceding sketched TT-core (χ×k×χ) to form the preceding sketch matrix, requiring O(knχ2) = O(nχ3) operations for each input TT.

- Step 1 in the j-th iteration:

Contracting the sketch matrix with the s j and s j+1 cores costs O(d2χ3).

- Step 2 in the j-th iteration:

The Hadamard product of T˜1 and T˜2 requires O(χd2k) = O(dχ2) operations. Applying a prrLU-based interpolative decomposition to the (χd, χ) matricization of T˜1T˜2 incurs a third-order cost of O(dχ3).

- Step 3 in the j-th iteration:

Neglecting indexing costs, the re-interpolation step requires contracting two cores for each TT and incurs a complexity of O(d2χ3).

Comparison with Baselines and Applications

Numerical experiments compare RSI against two conventional baselines:

  1. The direct method: Forms the explicit Kronecker product followed by TT-rounding.

  2. The TCI method: Queries tensor entries from input TTs at O(χ2) cost to build a TT approximation via back-and-forth iterations.

In product of quantum wavefunction MPSs, RSI exhibits superior scalability over both baselines as the bond dimension increases, yielding substantial speedups over the direct method in runtime.

Improvements for AI systems

As a fastidious researcher, I have analyzed Recursive Sketched Interpolation: Efficient Hadamard Products of Tensor Trains. This paper introduces Recursive Sketched Interpolation (RSI), an algorithm that computes the Hadamard product of Tensor Train (TT) representations with a computational complexity of only O(χ3) in terms of the TT bond dimension χ, significantly outperforming conventional methods that scale at least O(χ4).

Here are the specific improvements to AI systems and what those improved systems can achieve:

The core contribution is an efficient, scalable method for performing element-wise nonlinear operations (like Hadamard products or ReLU) on high-dimensional tensor representations without incurring the prohibitive cost of intermediate bond dimension growth. The improvements focus on three main areas:

  1. The ability to perform fast, scalable element-wise nonlinear mapping between tensor representations.

  2. The efficiency of complex, multi-tensor operations (e.g., Hadamard products of many TTs).

  3. The overall complexity scaling for high-dimensional tensor manipulation in machine learning models and simulations.

Here are the specific improvements and capabilities:

  1. The ability to perform element-wise nonlinear mapping between tensor representations with O(χ3) complexity instead of O(χ4) or higher, where χ is the TT bond dimension.

  2. The capacity to compute Hadamard products of multiple TTs and other element-wise nonlinear mappings (like ReLU) on TTs without increasing the complexity beyond O(χ3).

  3. The ability to use these operations within models utilizing Quantics Tensor Trains (QTTs) for representing high-dimensional functions, enabling fast computation of products of functions, convolutions, and differential equation solvers.

Improved AI Systems Can Do:

  1. The system can efficiently compute the product of two or more TT-represented high-dimensional functions (e.g., in quantum chemistry or fluid dynamics simulations) with a computational cost that scales cubically with the required approximation rank, allowing for much larger, more complex systems than currently feasible.

  2. The system can perform element-wise activation functions (like ReLU) on QTTs representing continuous high-dimensional data (e.g., discretized PDE solutions or neural network features) with a runtime complexity of O(χ3), enabling faster training and inference for models operating in this tensor format.

  3. It can accelerate operations within TT-based solvers for nonlinear differential equations (like Navier–Stokes or Gross–Pitaevskii equations) by replacing the standard, expensive Hadamard product with the RSI algorithm, leading to faster time-to-solution while maintaining comparable accuracy.

  4. It can perform fast convolutions between functions represented in QTT format by combining the TT-based Fourier transform with RSI for multiplication, resulting in a high-speed convolution scheme for complex functions.

  5. It can serve as a more computationally efficient alternative to existing tensor network methods (like TCI) for applying general element-wise nonlinear mappings to TTs, especially when the required bond dimension is large, providing substantial speedups in runtime and memory efficiency during model execution or simulation steps.

Abstract

The Hadamard product of two tensors in the tensor-train (TT) format is a fundamental operation across various applications, such as TT-based function multiplication for nonlinear differential equations or convolutions. However, conventional methods for computing this product typically scale as at least O(χ 4) with respect to the TT bond dimension (TT-rank) χ, creating a severe computational bottleneck in practice. By combining randomized tensor-train sketching with slice selection via interpolative decomposition, we introduce Recursive Sketched Interpolation (RSI), a ``scale product'' algorithm that computes the Hadamard product of TTs at a computational cost of O(χ 3). Benchmarks across various TT scenarios demonstrate that RSI offers superior scalability compared to traditional methods while maintaining comparable accuracy. We generalize RSI to compute more complex operations, including Hadamard products of multiple TTs and other element-wise nonlinear mappings, without increasing the complexity beyond O(χ 3).

Sources

Related papers