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.

arXiv comment30 pages, 9 figures

References in corpus (33)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum algorithm for solving linear systems of equations
• The density-matrix renormalization group
• Real time evolution using the density matrix renormalization group
• Time-dependent density-matrix renormalization-group using adaptive effective Hilbert spaces
• The ITensor Software Library for Tensor Network Calculations
• Classical simulation of infinite-size quantum lattice systems in one spatial dimension
• Quantum measurements and the Abelian Stabilizer Problem
• Entropy scaling and simulability by Matrix Product States
• On the Entangling Power of Quantum Evolutions
• Simulating chemistry using quantum computers
• Minimally Entangled Typical Thermal State Algorithms
• Quantum arithmetic with the Quantum Fourier Transform
• Quantum dynamics as a physical resource
• Entanglement capabilities of non-local Hamiltonians
• On the capacities of bipartite Hamiltonians and unitary gates
• A Quantum Inspired Approach to Exploit Turbulence Structures
• Entanglement rates and area laws
• Entangling power and operator entanglement in qudit systems
• Entanglement area laws for long-range interacting systems
• Linear Depth Stabilizer and Quantum Fourier Transformation Circuits with no Auxiliary Qubits in Finite Neighbor Quantum Architectures
• Quasioptimality of maximum-volume cross interpolation of tensors
• Parallel cross interpolation for high-precision calculation of high-dimensional integrals
• Efficient classical simulation of the semi-classical Quantum Fourier Transform
• Quantum-inspired algorithms for multivariate analysis: from interpolation to partial differential equations
• Entangling power of time-evolution operators in integrable and nonintegrable many-body systems
• Efficient classical simulation of the approximate quantum Fourier transform
• Quantum error mitigation via matrix product operators
• Multigrid Renormalization
• An introduction to entanglement measures
• The Eigenvalue Distribution of Discrete Periodic Time-Frequency Limiting Operators
• Non-Asymptotic behaviour of the spectrum of the Sinc Kernel Operator and Related Applications
• Operator-Schmidt decomposition of the quantum Fourier transform on C^N1 tensor C^N2

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