Fast quantum nD Fourier and Radon transforms / Labunets V.G., Rundblad-Labunets E.V., Astola J. // Proceedings of SPIE - The International Society for Optical Engineering. - 2001. - V. 4386, l. . - P. 133-144.

ISSN:
0277786X
Type:
Conference Paper
Abstract:
Fast classical and quantum algorithms are introduced for a wide class of non-separable nD discrete unitary K-transforms (DKT)KN(n). They require a number of 1D DKT KN smaller than in the Cooley-Tukey radix-p FFT-type approach. The method utilizes a decomposition of the nD K-transform into a product of original nD Discrete Radon Transform and of a family parallel/independ 1D K-transforms. If the nD K-transform (for example, Discrete Fourier Transform) has a separable kernel, that again in this case our approach leads to decrease of multiplicative complexity by factor of n (where n is the dimension) compared to the row/column separable Cooley-Tukey p-radix approach.
Author keywords:
Fast quantum algorithms; Fourier transforms; Quantum computer; Radon transform
Index keywords:
Computational complexity; Discrete Fourier transforms; Parallel algorithms; Polynomial approximation; Tensors; Radon transforms; Quantum theory
DOI:
10.1117/12.434211
Смотреть в Scopus:
https://www.scopus.com/inward/record.uri?eid=2-s2.0-0034779192&doi=10.1117%2f12.434211&partnerID=40&md5=be6a7776a2235c1967618c3e6fab072b
Соавторы в МНС:
Другие поля
Поле Значение
Link https://www.scopus.com/inward/record.uri?eid=2-s2.0-0034779192&doi=10.1117%2f12.434211&partnerID=40&md5=be6a7776a2235c1967618c3e6fab072b
Affiliations Dept. of Automat. and Info. Technol., Urals State Technical University, Ekaterinburg, Russian Federation
Author Keywords Fast quantum algorithms; Fourier transforms; Quantum computer; Radon transform
References Chapman, C.H., Generalized Radon transforms and slant stacks (1981) Geophys. J. Roy. Astron. Soc., 66, pp. 445-453; Beylkin, G., (1982) Generalized Radon Transform Its Application, , Ph. D. dissertation, N.Y; Deans, S.R., (1983) The Radon Transform and Some of its Applications, , Wiley, New York; Beylkin, G., Discrete Radon transform (1987) ASSP, pp. 162-172. , Feb; Bolker, E.D., The finite Radon transform (1987) Contemp. Math., 63, pp. 27-50; Diaconis, P., Graham, L., The Radon transform on Z2k (1985) Pacific J. Math., 118, pp. 323-345; Labunets, V.G., Application of superfast Radon transform for calcucation of multidimensional Fourier transforms and cyclic convolutions. P.1 (1985) Methods and Microelectronical Devices of Digital Transform and Processing, pp. 102-110. , (in Russian), All-Union Scientific Conference, Moscow; Labunets, V.G., The Radon transforms: Application for multidimensional Fourier transforms and cyclic convolutions calculation. P.2 (1985) Automatization of Production Technical Preparation, pp. 56-70. , (in Russian), Institute of Technical Cybernetics of Belarussian Academy of Sciences Press, Minsk; Labunets, V.G., Fast Radon transform application for multidimensional Fourier transforms and cyclic convolutions calculation. P.3 (1985) Statistical Methods of Signal Processing: Practical Application, pp. 37-42. , (in Russian), Republic Conference, Char'kov; Labunets, V.G., Superfast multidimensional Fourier-Radon transforms and multidimensional convolutions. P.4 (1985) Statictical Methods of Signal Processing, pp. 140-142. , (in Russia), IX All-Union Seminar "Information Theory", Char'kov; Labunets, V.G., Fast Mersereau-Radon Transform. P.1 (1986) Numerical Methods in Control, Radar and Communication, pp. 152-163. , (in Russian), Ural Polytechnical Institute Press, Sverdlovsk; Labunets, V.G., Fast Mersereau-Radon transform. P.2 (1986) Radioelectronics, pp. 16-28. , (in Russian), High-Shool Press, Char'kov; Labunets, V.G., (1984) Algebraic Theory of Signals and Systems, P.1 (in Russian), , Krasnoyarsk State University Press, Krasnoyarsk; Labunets, V.G., (1989) Algebraic Theory of Signals and Systems. Part 2. (in Russia), , Ural State University Press, Sverdlovsk; Kung, J.P.S., Reconstructing finite Radon transforms (1988) Nuclear Phys. B (Proc. Supl.), 5 A, pp. 44-49; Matuc, F., (1988) Independece and Radon Projections on Compact Groups, , Ph.D. thesis (in Slovak), UTIA CSAV, Prague; Kelley, B.T., Madisetti, V.K., The fast discrete Radon transform. P.1: Theory (1993) Trans. IP, 2 (3); Kelley, B.T., Madisetti, V.K., The fast discrete Radon Transform (1992) Proc. Int. Conf. IEEE-ICASSP'92, 3, pp. 409-412; Labunets, E.V., Labunets, V.G., New fast algorithms of multidimensional Fourier and Radon discrete transforms (1998) First International Workshop on Transform and Filter Banks, pp. 147-178. , Tampere, Finland, TICSP Series, No 1; Rundblad, E., Labunets, V., Egiazarian, K., Astola, J., A superfast convolution technique for Volterra filtering (1999) Proc. of IEEE-EURASIP Workshop on Nonlinear Signal and Image Processing, pp. 399-403. , Antalya, Turkey, June 20-23; Rundblad-Labunets, E., Labunets, V., Astola, L., Astola, J., Egiazarian, K., Fast algorithms of multidimensional discrete nonseparable K-wave transformations and Volterra filtering (1999) Second International Workshop on Transform and Filter Banks, pp. 337-376. , Tampere, Finland, TICSP Series, No 3; Labunets, E.V., Labunets, V.G., Egiazarian, K., Astola, K.J., New fast algorithms of multidimensional Fourier and Radon discrete transforms (1999) IEEE Int. Conf. on ASSP, pp. 3193-3196. , Arizona, USA, March 15-19; Liu, K.J.K., Chiu, C.T., Unified parallel structures for time-recursive discrete cisine/sine/Hartley transform (1993) IEE Trans. on Signal Processing, 41 (3), pp. 1557-1377. , March; Chau, L.P., Siu, W.C., Recursive algorithm for discrete cosine transform with general lenght (1994) Electronics Letters, 30 (3), pp. 197-198. , Errata: vol. 30, no 7, pp. 608, Feb; Canaris, J., A VLSI architecture for the real time computation of discrete trigonometric transforms (1993) Journal of VLSI Signal Processing, 5, pp. 95-104; Sun, M.T., Chen, T.C., Gottlieb, A.M., VLSI implementation of 16 × 16 discrete cosine transform (1989) IEEE Transactions on Circuits and Systems, 36 (4), pp. 610-617. , Apr; Sun, M.T., Wu, L., Liou, M.L., A concurent architecture for VLSI implementation of discrete cosine transform (1987) IEEE Transactions on Circuits and Systems, 34 (8), pp. 992-994. , Aug; Kitaev, A.Yu., (1997) Quantum measurement and the Abelian Stabilizer problem, , LANL preprint quant-ph/9702028, Feb; Vedral, V.V., Barenco, A., Ekert, A., Quantum networks for elememtary arithmetic operations Physical Review A, 54, pp. 147-153; Hoyer, P., (1997) Efficient quantum transforms, , LANL preprint quant-ph/9702028, Feb; Fijany, A., Williams, C.P., (1998) Quantum wavelet transforms: Fast algorithms and complete circuits, , LANL preprint quant-ph/9800904, Sep; Nussbaumer, H.J., (1982) Fast Fourier Transform and Convolution Algorithms, , Springer- Verlag, Berlin and New York; Labunets, V.G., Labunets-Rundblad, E.V., Astola, J., Introduction to quantum and hyperquantum information tecnologies. Part 1. Real probability and unreal probabilities (2000) Proc. of First International Workshop on Spectral Tecniques and Logic Design for Future Digital Systems, pp. 283-321. , Tampere, Finland, June 2-3
Correspondence Address Labunets, V.G.; Dept. of Automat. and Info. Technol., Urals State Technical University, Ekaterinburg, Russian Federation; email: lab@cs.tut.fi
Editors Donkor E.Pirich A.R.Taylor E.W.
Sponsors SPIE
Conference name Photonic and Quantum Technologies for Aerospace Applications III
Conference date 17 April 2001 through 18 April 2001
Conference location Orlando,FL
Conference code 58665
CODEN PSISD
Language of Original Document English
Abbreviated Source Title Proc SPIE Int Soc Opt Eng
Source Scopus