Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0111039

On the Irresistible Efficiency of Signal Processing Methods in Quantum Computing

Andreas Klappenecker, Martin Roetteler

Published Nov 7, 2001• 3 citations
arXivHTMLPDF

Abstract

We show that many well-known signal transforms allow highly efficient realizations on a quantum computer. We explain some elementary quantum circuits and review the construction of the Quantum Fourier Transform. We derive quantum circuits for the Discrete Cosine and Sine Transforms, and for the Discrete Hartley transform. We show that at most O(log^2 N) elementary quantum gates are necessary to implement any of those transforms for input sequences of length N.

DOI
10.48550/arxiv.quant-ph/0111039

Related papers

Quantum computing and a unified approach to fast unitary transforms

Sos С. Agaian, Andreas Klappenecker

A quantum computer directly manipulates information stored in the state of quantum mechanical systems. The available operations have many attractive features but also underly severe restrictions, which complicate the design of quantum algorithms. We present a divide-and-conquer approach to the design of various quantum algorithms. The class of algorithm includes many transforms which are well-known in classical signal processing applications. We show how fast quantum algorithms can be derived for the discrete Fourier transform, the Walsh-Hadamard transform, the Slant transform, and the Hartley transform. All these algorithms use at most O(log^2 N) operations to transform a state vector of a quantum computer of length N.

arXiv:quant-ph/0201120•Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•May 23, 2002•6 citations

Discrete Cosine Transforms on Quantum Computers

Andreas Klappenecker, Martin Roetteler

A classical computer does not allow to calculate 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 NxN and types I,II,III, and IV with as little as O(log^2 N) operations on a quantum computer, whereas the known fast algorithms on a classical computer need O(N log N) operations.

arXiv:quant-ph/0111038•Nov 7, 2001•54 citations

Efficient Quantum Circuits for the Hilbert Transform

Henry Zhang, Joseph Li

The quantum Fourier transform and quantum wavelet transform have been cornerstones of quantum information processing. However, for non-stationary signals and anomaly detection, the Hilbert transform can be a more powerful tool, yet no prior work has provided efficient quantum implementations for the discrete Hilbert transform. This letter presents a novel construction for a quantum Hilbert transform in polylogarithmic size and logarithmic depth for a signal of length $N$, exponentially fewer operations than classical algorithms for the same mapping. We generalize this algorithm to create any $d$-dimensional Hilbert transform in depth $O(d\log N)$. Simulations demonstrate effectiveness for tasks such as power systems control and image processing, with exact agreement with classical results.

quant-pharXiv:2601.10876•IEEE Signal Processing Letters•Jan 19, 2026•2 citations

Discrete cosine transforms on quantum computers

Andreas Klappenecker, Martin Rötteler

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/spl times/N and types I, II, III and IV with as little as O(log/sup 2/N) operations on a quantum computer; whereas the known fast algorithms on a classical computer need O(N logN) operations.

International symposium on image and signal processing and analysis/ISPA ...•Nov 13, 2002•67 citations

Engineering functional quantum algorithms

Andreas Klappenecker, Martin Rötteler

Suppose that a quantum circuit with K elementary gates is known for a unitary matrix U, and assume that ${U}^{m}$ is a scalar matrix for some positive integer m. We show that a function of U can be realized on a quantum computer with at most ${O(mK+m}^{2}\mathrm{ln}m)$ elementary gates. The functions of U are realized by a generic quantum circuit, which has a particularly simple structure. Among other results, we obtain efficient circuits for the fractional Fourier transform.

arXiv:quant-ph/0208130•Physical Review A•Jan 17, 2003•15 citations

The quantum Schur and Clebsch-Gordan transforms: I. efficient qudit circuits

Dave Bacon, Isaac L. Chuang, Aram W. Harrow

We present an efficient family of quantum circuits for a fundamental primitive in quantum information theory, the Schur transform. The Schur transform on n d-dimensional quantum systems is a transform between a standard computational basis to a labelling related to the representation theory of the symmetric and unitary groups. If we desire to implement the Schur transform to an accuracy of e-1, then our circuit construction uses a number of gates which is polynomial in n, d and log(e-1). The key tool in our construction is a poly(d, log n, log(e-1)) algorithm for the ud Clebsch-Gordan transform. Our efficient circuit construction renders numerous protocols in quantum information theory computationally tractable and yields a new possible approach to quantum algorithms which is distinct from the standard paradigm of the quantum Fourier transform.

Symposium on Discrete Algorithms•Jan 7, 2007•19 citations
We show that many well-known signal transforms allow highly efficient realizations on a quantum computer. We explain some elementary quantum circuits and review the construction of the Quantum Fourier Transform. We derive quantum circuits for the Discrete Cosine and Sine Transforms, and for the Discrete Hartley transform. We show that at most O(log^2 N) elementary quantum gates are necessary to implement any of those transforms for input sequences of length N.
A quantum computer directly manipulates information stored in the state of quantum mechanical systems. The available operations have many attractive features but also underly severe restrictions, which complicate the design of quantum algorithms. We present a divide-and-conquer approach to the design of various quantum algorithms. The class of algorithm includes many transforms which are well-known in classical signal processing applications. We show how fast quantum algorithms can be derived for the discrete Fourier transform, the Walsh-Hadamard transform, the Slant transform, and the Hartley transform. All these algorithms use at most O(log^2 N) operations to transform a state vector of a quantum computer of length N.
A classical computer does not allow to calculate 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 NxN and types I,II,III, and IV with as little as O(log^2 N) operations on a quantum computer, whereas the known fast algorithms on a classical computer need O(N log N) operations.
The quantum Fourier transform and quantum wavelet transform have been cornerstones of quantum information processing. However, for non-stationary signals and anomaly detection, the Hilbert transform can be a more powerful tool, yet no prior work has provided efficient quantum implementations for the discrete Hilbert transform. This letter presents a novel construction for a quantum Hilbert transform in polylogarithmic size and logarithmic depth for a signal of length NNN, exponentially fewer operations than classical algorithms for the same mapping. We generalize this algorithm to create any ddd-dimensional Hilbert transform in depth O(dlog⁡N)O(d\log N)O(dlogN). Simulations demonstrate effectiveness for tasks such as power systems control and image processing, with exact agreement with classical results.
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/spl times/N and types I, II, III and IV with as little as O(log/sup 2/N) operations on a quantum computer; whereas the known fast algorithms on a classical computer need O(N logN) operations.
Suppose that a quantum circuit with K elementary gates is known for a unitary matrix U, and assume that Um{U}^{m}Um is a scalar matrix for some positive integer m. We show that a function of U can be realized on a quantum computer with at most O(mK+m2lnm){O(mK+m}^{2}\mathrm{ln}m)O(mK+m2lnm) elementary gates. The functions of U are realized by a generic quantum circuit, which has a particularly simple structure. Among other results, we obtain efficient circuits for the fractional Fourier transform.
We present an efficient family of quantum circuits for a fundamental primitive in quantum information theory, the Schur transform. The Schur transform on n d-dimensional quantum systems is a transform between a standard computational basis to a labelling related to the representation theory of the symmetric and unitary groups. If we desire to implement the Schur transform to an accuracy of e-1, then our circuit construction uses a number of gates which is polynomial in n, d and log(e-1). The key tool in our construction is a poly(d, log n, log(e-1)) algorithm for the ud Clebsch-Gordan transform. Our efficient circuit construction renders numerous protocols in quantum information theory computationally tractable and yields a new possible approach to quantum algorithms which is distinct from the standard paradigm of the quantum Fourier transform.