A quantum Bluestein algorithm for arbitrary size quantum Fourier transform
Published in arXiv, 2025
We propose a quantum analogue of Bluestein’s algorithm (QBA) that implements an exact N-point Quantum Fourier Transform (QFT) for arbitrary N. Our construction factors the N-dimensional QFT unitary into three diagonal quadratic-phase gates and two standard radix-2 QFT subcircuits of size M=2^m (with M≥2N−1). This achieves asymptotic gate complexity O((logN)^2) and uses O(logN) qubits, matching the performance of a power-of-two QFT on m qubits while avoiding the need to embed into a larger Hilbert space. We validate the correctness of the algorithm through a concrete implementation in Qiskit and classical simulation, confirming that QBA produces the exact N-point discrete Fourier transform on arbitrary-length inputs.
Recommended citation: Nan-Hong Kuo and Renata Wong (2025). "A quantum Bluestein algorithm for arbitrary size quantum Fourier transform" arXiv. 2512.15349. https://arxiv.org/abs/2512.15349
