Direct interpolative construction of the discrete Fourier transform as a matrix product operator

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.

18 pages, 6 figures

References in corpus (8)

• Real time evolution using the density matrix renormalization group
• Classical simulation of infinite-size quantum lattice systems in one spatial dimension
• A Quantum Inspired Approach to Exploit Turbulence Structures
• Efficient classical simulation of the semi-classical Quantum Fourier Transform
• Quantum Fourier Transform Has Small Entanglement
• 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

Cited by in corpus (2)

• Solving the Gross-Pitaevskii equation on multiple different scales using the quantics tensor train representation
• Who can compete with quantum computers? Lecture notes on quantum inspired tensor networks computational techniques