The quantum Fourier transform (QFT), a quantum analog of the classical Fourier transform, has been shown to be a powerful tool in developing quantum algorithms. However, in classical computing there are another classes of unitary transforms, e.q. the Radon transforms. The Radon Transform (RT) and its ill-conditioned inverse were first formulated by J. Radon in 1917. Currently, the RT is used in a wide variety of applications including tomography, ultrasound, optics, and geophysics, to name a few.

In this paper, we introduce nD Quantum Radon Transform (QRT). Using discrete versions of the Generalized Central Slice Theorem we derive a new superfast algorithm for the nD quantum Fourier and Radon Transforms. Our method utilizes a decomposition of the nD Quantum Fourier transform into a product of nD Quantum Radon Transform (DRT) and a family of independent/parallel 1D Quantum Fourier transforms. Fast QRT is based on the fast Quantum Nussbauner Polynomial Transform (QNPT). Our approach leads to decrease of computational complexity by factor n comparing to the Deuthsch's-Kitaev's approach.

lab@cs.tut.fi