Quantum Fourier Transform Has Small Entanglement

Abstract

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.

30 pages, 9 figures

References in corpus (9)

• Quantum algorithm for solving linear systems of equations
• Real time evolution using the density matrix renormalization group
• Classical simulation of infinite-size quantum lattice systems in one spatial dimension
• Entropy scaling and simulability by Matrix Product States
• Simulating chemistry using quantum computers
• Minimally Entangled Typical Thermal State Algorithms
• Linear Depth Stabilizer and Quantum Fourier Transformation Circuits with no Auxiliary Qubits in Finite Neighbor Quantum Architectures
• Efficient classical simulation of the semi-classical Quantum Fourier Transform
• Efficient classical simulation of the approximate quantum Fourier transform

Cited by in corpus (26)

• Review of Distributed Quantum Computing. From single QPU to High Performance Quantum Computing
• Is quantum computing green? An estimate for an energy-efficiency quantum advantage
• Quantics Tensor Cross Interpolation for High-Resolution, Parsimonious Representations of Multivariate Functions in Physics and Beyond
• Learning tensor networks with tensor cross interpolation: new algorithms and libraries
• Gauging tensor networks with belief propagation
• The Quantum House Of Cards
• Stabilizer Tensor Networks with Magic State Injection
• Quantum-Inspired Fluid Simulation of 2D Turbulence with GPU Acceleration
• QFactor: A Domain-Specific Optimizer for Quantum Circuit Instantiation
• Compactness of quantics tensor train representations of local imaginary-time propagators
• Efficient Quantum Circuit Compilation for Near-Term Quantum Advantage
• Simulating the quantum Fourier transform, Grover's algorithm, and the quantum counting algorithm with limited entanglement using tensor-networks
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits
• Quantum circuit compilation with quantum computers
• Direct interpolative construction of the discrete Fourier transform as a matrix product operator
• Efficient and systematic calculation of arbitrary observables for the matrix product state excitation ansatz
• Solving the Gross-Pitaevskii equation on multiple different scales using the quantics tensor train representation
• A Quantum-Inspired Algorithm for Wave Simulation Using Tensor Networks
• Simulating Quantum Turbulence with Matrix Product States
• Simulating Quantum Circuits with Tree Tensor Networks using Density-Matrix Renormalization Group Algorithm
• Pseudospectral method for solving PDEs using Matrix Product States
• Inchworm tensor train hybridization expansion quantum impurity solver
• Tradeoff between noise and banding in a quantum adder with qudits
• Who can compete with quantum computers? Lecture notes on quantum inspired tensor networks computational techniques
• An efficient explicit implementation of a near-optimal quantum algorithm for simulating linear dissipative differential equations
• Dynamical cluster-based strategy for improving tensor network algorithms in quantum circuit simulations