Simplified quantum Fourier transforms

Paper Title:

Fast Fourier transforms and fast Wigner and Weyl functions in large quantum systems

Published on:

8 May 2024

Primary Category:

Quantum Physics

Paper Authors:

C. Lei,

A. Vourdas

Bullets

Key Details

•

Proposes techniques to decompose a large quantum Fourier transform into smaller component transforms

•

First method applies for dimensions that are powers of odd numbers; inspired by Cooley-Tukey FFT

•

Second method uses number theory for dimensions that are products of coprimes; builds on Good/Chinese Remainder FFT

•

Second method also speeds up computation of Wigner/Weyl functions in phase space formalism

•

Both methods reduce complexity from O(D^2) to O(D log D); supported by numerical examples

Explore the topics in this paper

algorithms

computational complexity

fourier transforms

performance

quantum computing

AI generated summary

Simplified quantum Fourier transforms

This paper proposes two methods to break down the Fourier transform, a key operation in quantum computing, into sequences of smaller 'component' Fourier transforms. This reduces the computational complexity from quadratic to linearithmic time. One method handles systems with Hilbert space dimension equal to a power of an odd number, and the other handles dimensions that are a product of coprime odd numbers. The latter method is also applied to quickly compute the Wigner and Weyl functions. Overall, this allows large Fourier transforms and other calculations to be performed more efficiently on quantum computers.