Function Interpolation

Interpolation allows to extend the number of points on which a function is defined by estimating the new data points from the original ones. The SeeMPS library provides two interpolation algorithms suitable for an MPS representation.

Finite difference interpolation

Finite differences is a widespread algorithm for approximation of derivatives. This technique is also useful for interpolation when combined with the Taylor expansion. When given a representation of a function \(f\left(x_s^{(n)}\right)\) on an \(n\)-qubit system with a discretization step of \(\Delta x_s^{(n)}\), the second-order finite difference interpolant calculates the new points of the \((n+1)\)-qubit grid as

\[f(x + \Delta x/2) \approx f(x) + \frac{f(x + \Delta x)-f(x)}{2}.\]

In the quantum register representation—equivalently MPS representation— the function displacements are performed by the displacement operators

\[\begin{split}\hat{\Sigma}^+|s\rangle = \left\{ \begin{array}{ll} |s+1\rangle, & s < 2^{n} \\ 0 & \mbox{else.} \end{array} \right. \quad \hat{\Sigma}^- = \left(\hat{\Sigma}^+\right)^\dagger.\end{split}\]

finite_differences_interpolation(tensor, space)

Finite differences interpolation of an MPS representing a multidimensional function.

Ref. García-Molina et al. [GMTGR24] presents a more detailed explanation and an use case.

Fourier interpolation

If the function is bandwidth-limited and for a sufficiently small spacing \(\Delta{x}^{(n)}\leqslant 2\pi/L_p\) according to the Nyquist-Shannon theorem, it is possible to use Fourier interpolation to reconstruct the continuous function with up to doubly-exponentially decaying error in the number of qubits as

\[f(x) \propto \sum_{s=0}^{2^n-1} e^{-ip_s x} \langle{s|\text{QFT} |f^{(n)}}\rangle.\]

Its quantum register implementation has three steps: (i) computation of the QFT of the originally encoded function \(|{\tilde{f}^{(n)}}\rangle\), (ii) addition of \(m\) auxiliary qubits to enlarge the momentum space with qubit reordering \(U_\text{sym}\) to map the original discretization with \(2^n\) to the intervals \(s \in [0,2^{n-1}) \cup [2^{n+m}-2^{n-1},2^{n+m})\), and (iii) Fourier transform back to recover the state with \(n+m\) qubits. The complete algorithm reads

\[|f^{(n+m)}\rangle = \text{QFT}^{-1}U_{\text{sym}} \left(|{0}\rangle^{\otimes m} \otimes \text{QFT}|{f^{(n)}}\rangle\right)=: U_\text{int}^{n,m}|{f^{(n)}}\rangle.\]

fourier_interpolation(tensor, space, ...[, ...])

Fourier interpolation on an MPS.

Ref. García-Molina et al. [GMRMGR22] presents a more detailed explanation and an use case.

An example on how to use these functions is shown in Interpolation.ipynb.