Discrete cosine transforms on quantum computers

Author

Klappenecker, Andreas ; Rötteler, Martin

Author_Institution

Dept. of Comput. Sci., Texas A&M Univ., College Station, TX, USA

fYear

2001

fDate

2001

Firstpage

464

Lastpage

468

Abstract

A classical computer does not allow the calculation of a discrete cosine transform on N points in less than linear time. This trivial lower bound is no longer valid for a computer that takes advantage of quantum mechanical superposition, entanglement, and interference principles. In fact, we show that it is possible to realize the discrete cosine transforms and the discrete sine transforms of size N×N and types I, II, III and IV with as little as O(log²N) operations on a quantum computer; whereas the known fast algorithms on a classical computer need O(N logN) operations

Keywords

discrete cosine transforms; discrete transforms; quantum computing; signal processing; discrete cosine transforms; discrete sine transforms; quantum computers; quantum mechanical entanglement; quantum mechanical interference; quantum mechanical superposition; signal processing; Computer science; Discrete Fourier transforms; Discrete cosine transforms; Discrete transforms; Fast Fourier transforms; Physics computing; Quantum computing; Quantum dots; Signal processing algorithms; State-space methods;

fLanguage

English

Publisher

ieee

Conference_Titel

Image and Signal Processing and Analysis, 2001. ISPA 2001. Proceedings of the 2nd International Symposium on

Conference_Location

Pula

Print_ISBN

953-96769-4-0

Type

conf

DOI

10.1109/ISPA.2001.938674

Filename

938674