Not Your Usual FFT: QFT$\rightarrow$FFT via Classical Quantum-Circuit Simulation
This work provides a novel approach to classical FFT computation by leveraging quantum circuit simulation, offering competitive performance for high-performance computing users.
The authors introduce QFT→FFT, a family of HPC FFT libraries that compute the discrete Fourier transform by simulating a quantum Fourier transform circuit on classical simulators. On an NVIDIA A100, their CUDA backend achieves over 4× lower runtime than FFTW on an AMD EPYC Zen2 at larger sizes.
We introduce QFT$\rightarrow$FFT, a family of HPC FFT libraries that compute the discrete Fourier transform by executing a quantum Fourier transform (QFT) circuit on classical quantum computer simulators. Input arrays are mapped directly to state amplitudes with explicit normalization/indexing, making QFT a drop-in replacement for FFT primitives. A backend-agnostic planner builds a fused-gate schedule and memory layout adapters to increase arithmetic intensity and reduce memory data movement. We implement this design on top of Google's C++ \texttt{qsim} and evaluate OpenMP, AVX, and CUDA backends. On an AMD EPYC Zen2 processor, our AVX performance is on par with that of multithreaded FFTW, utilizing 64 threads. On an NVIDIA A100, the CUDA backend achieves more than $4\times$ lower time than both AVX and FFTW on AMD EPYC Zen2 at larger sizes. We also employ an approximate QFT (AQFT) that truncates small-angle controlled rotations beyond a cutoff $k$, reducing circuit depth and runtime while preserving accuracy.