The Quantum Fourier Transform Has Small Entanglement | Quantum Colloquium

The Quantum Fourier Transform (QFT) is a key component of many important quantum algorithms, most famously as being the essential ingredient in Shor's algorithm for factoring products of primes. Given its remarkable capability, one would think it can introduce large entanglement to qubit systems and would be difficult to simulate classically. While early results showed QFT indeed has maximal operator entanglement, we show that this is entirely due to the bit reversal in the QFT. The core part of the QFT has Schmidt coefficients decaying exponentially quickly, and thus it can only generate a constant amount of entanglement regardless of the number of qubits. In addition, we show the entangling power of the QFT is the same as the time evolution of a Hamiltonian with exponentially decaying interactions, and thus a variant of the area law for dynamics can be used to understand the low entanglement intuitively. Using the low entanglement property of the QFT, we show that classical simulations of the QFT on a matrix product state with low bond dimension only take time linear in the number of qubits, providing a potential speedup over the classical fast Fourier transform (FFT) on many classes of functions. We demonstrate this speedup in test calculations on some simple functions. For data vectors of length 10^6 to 10^8, the speedup can be a few orders of magnitude.

Bio: Chris (Jielun) Chen is a first-year graduate student at Caltech, (tentatively) supervised by Garnet Chan and John Preskill. Previously he was an undergrad at UC Irvine, with research experiences under Steve White. He's interested in the interface of quantum information and tensor network theory.

Panel discussion: Stefanos Kourtis (University of Sherbrooke), Miles Stoudenmire (Flatiron Institute), and Frank Verstraete (University of Cambridge). Moderated by Umesh Vazirani (UC Berkeley)