  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.
