Quantum Fourier Transform Has Small Entanglement

Understand

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.