Superfast Fourier transform using QTT approximation (Q1759431)

Algorithms for the discrete Fourier transform of one- and high-dimensional data represented or approximated in the quantum tensor train (QTT) format are proposed. The approach is based on a radix-2 recursion formula which reduces the Fourier transform to the one of half size and lies behind the well-known Cooley-Tukey fast-Fourier transform (FFT) algorithm. Each step of the proposed QTT-FFT algorithm includes an approximation to reduce the storage size of the intermediate vectors adaptively to the prescribed level of accuracy. The complexity of \(m\)-dimensional \(n\times n\times\dots\times n\) transform with \(n=2^d\) is bounded by \(O(md^2R^3)\), where \(R\) is the maximum QTT-rank of the input, all intermediate vectors and output of the QTT-FFT algorithm. For the vectors with moderate \(R\) and large \(n\) and \(m\) the proposed algorithm outperforms the \(O(n^m\log n)\) fast Fourier transform algorithm and has asymptotically the same log-squared complexity as the superfast quantum Fourier transform algorithm. The authors compare the proposed method with the sparse Fourier transform algorithm.