Direct interpolative construction of the discrete Fourier transform as a matrix product operator
arXiv:2404.03182 · doi:10.1016/j.acha.2025.101817
Abstract
The quantum Fourier transform (QFT), which can be viewed as a reindexing of the discrete Fourier transform (DFT), has been shown to be compressible as a low-rank matrix product operator (MPO) or quantized tensor train (QTT) operator. However, the original proof of this fact does not furnish a construction of the MPO with a guaranteed error bound. Meanwhile, the existing practical construction of this MPO, based on the compression of a quantum circuit, is not as efficient as possible. We present a simple closed-form construction of the QFT MPO using the interpolative decomposition, with guaranteed near-optimal compression error for a given rank. This construction can speed up the application of the QFT and the DFT, respectively, in quantum circuit simulations and QTT applications. We also connect our interpolative construction to the approximate quantum Fourier transform (AQFT) by demonstrating that the AQFT can be viewed as an MPO constructed using a different interpolation scheme.
arXiv comment18 pages, 6 figures
References in corpus (15)
- Efficient classical simulation of slightly entangled quantum computations
- Real time evolution using the density matrix renormalization group
- Time-dependent density-matrix renormalization-group using adaptive effective Hilbert spaces
- Thermodynamic limit of the density matrix renormalization for the spin-1 Heisenberg chain
- Classical simulation of infinite-size quantum lattice systems in one spatial dimension
- Matrix product operator representations
- A Quantum Inspired Approach to Exploit Turbulence Structures
- Quasioptimality of maximum-volume cross interpolation of tensors
- Parallel cross interpolation for high-precision calculation of high-dimensional integrals
- Efficient classical simulation of the semi-classical Quantum Fourier Transform
- Quantum Fourier Transform Has Small Entanglement
- Butterfly Factorization
- Efficient classical simulation of the approximate quantum Fourier transform
- A quantum-inspired method for solving the Vlasov-Poisson equations
- Tensor network reduced order models for wall-bounded flows