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/0201120 · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE

Quantum computing and a unified approach to fast unitary transforms

Sos С. Agaian, Andreas Klappenecker

Published May 23, 2002• 6 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1117/12.467967

Related papers

Efficient Quantum Transforms

Peter Høyer

Quantum mechanics requires the operation of quantum computers to be unitary, and thus makes it important to have general techniques for developing fast quantum algorithms for computing unitary transforms. A quantum routine for computing a generalized Kronecker product is given. Applications include re-development of the networks for computing the Walsh-Hadamard and the quantum Fourier transform. New networks for two wavelet transforms are given. Quantum computation of Fourier transforms for non-Abelian groups is defined. A slightly relaxed definition is shown to simplify the analysis and the networks that computes the transforms. Efficient networks for computing such transforms for a class of metacyclic groups are introduced. A novel network for computing a Fourier transform for a group used in quantum error-correction is also given.

arXiv:quant-ph/9702028•Feb 12, 1997•77 citations

On the Irresistible Efficiency of Signal Processing Methods in Quantum Computing

Andreas Klappenecker, Martin Roetteler

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.

arXiv:quant-ph/0111039•Nov 7, 2001•3 citations

A presentation of the quantum Fourier transform from a recursive viewpoint

Gloria Paradisi, Hugues Randriambololona

In this note we construct a quantum Fourier transform circuit in a recursive way, by directly copying the 'divide and conquer' construction of the fast Fourier transform algorithm, rather than using the explicit formula that is given in most introductory texts to quantum computation. We do not pretend this presentation to be original, nor claim for any anteriority. The aim of this paper is purely pedagogical.

arXiv:quant-ph/0411069•Nov 10, 2004•1 citation

Quantum Wavelet Transforms: Fast Algorithms and Complete Circuits

Amir Fijany, Colin P. Williams

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 is another class of unitary transforms, the wavelet transforms, which are every bit as useful as the Fourier transform. Wavelet transforms are used to expose the multi-scale structure of a signal and are likely to be useful for quantum image processing and quantum data compression. In this paper, we derive efficient, complete, quantum circuits for two representative quantum wavelet transforms, the quantum Haar and quantum Daubechies $D^{(4)}$ transforms. Our approach is to factor the operators for these transforms into direct sums, direct products and dot products of unitary matrices. In so doing, we find that permutation matrices, a particular class of unitary matrices, play a pivotal role. Surprisingly, we find that operations that are easy and inexpensive to implement classically are not always easy and inexpensive to implement quantum mechanically, and vice versa. In particular, the computational cost of performing certain permutation matrices is ignored classically because they can be avoided explicitly. However, quantum mechanically, these permutation operations must be performed explicitly and hence their cost enters into the full complexity measure of the quantum transform. We consider the particular set of permutation matrices arising in quantum wavelet transforms and develop efficient quantum circuits that implement them. This allows us to design efficient, complete quantum circuits for the quantum wavelet transform.

arXiv:quant-ph/9809004•Presented at•Sep 2, 1998•15 citations

Quantum Detection of Sequency-Band Structure

Alok Shukla, Prakash Vedula

We present a quantum algorithm for estimating the amplitude content of user-specified sequency bands in quantum-encoded signals. The method employs a sequency-ordered Quantum Walsh-Hadamard Transform (QWHT), a comparator-based oracle that coherently marks basis states within an arbitrary sequency range, and Quantum Amplitude Estimation (QAE) to estimate the total probability mass in the selected band. This enables the detection of structured signal components, including both high- and low-sequency features, as well as the identification of rapid sign-change behavior associated with noise or anomalies. The proposed method can be embedded as a module within a larger quantum algorithm; in this setting, both the input and output remain fully quantum, enabling seamless integration with upstream and downstream quantum operations. We show that the sequency-ordered QWHT can be implemented with circuit depth $O(\log_2 N)$ (equivalently $O(n)$ for $N=2^n$) when acting on an amplitude-encoded quantum state, whereas computing the full Walsh-Hadamard spectrum of an explicit length-$N$ classical signal requires $O(N\log_2 N)$ operations via the fast Walsh-Hadamard transform. This results in an exponential quantum advantage when the QWHT is used as a modular block within a larger quantum algorithm, relative to classical fast Walsh-Hadamard transform-based approaches operating on explicit data. From an application perspective, the proposed sequency band-energy estimation may be interpreted as a structure-based anomaly indicator, enabling the detection of unexpected high-sequency components relative to a nominal low-sequency signal class. The algorithm is applicable to quantum-enhanced signal processing tasks such as zero-crossing analysis, band-limited noise estimation, and feature extraction in the Walsh basis.

quant-pharXiv:2602.08393•Feb 10, 2026•0 citations

On the Fast Fourier Transform on SU(2)

Julio Delgado, Alejandro Umaña

The special unitary group SU(2) plays a fundamental role in the description of symmetries in quantum mechanics, theoretical physics, and spherical signal processing. In this paper, we address the computational challenges of performing spectral analysis on this non-abelian compact Lie group. We present the Fourier Transform (FT) on SU(2) and develop a Fast Fourier Transform (FFT) algorithm inspired by the classical Cooley-Tukey divide-and-conquer scheme. Our approach efficiently discretizes the group using Euler angles, applying a two-dimensional FFT on the angular variables and exploiting the recursive properties of Jacobi polynomials. We provide an analysis of the computational complexity, demonstrating that our FFT-based method significantly outperforms the direct computation of the FT. This algorithm serves as a foundational tool for understanding the implementation of the FFT on SU(2), a key component in numerical simulations and advanced data analysis for high-performance computing applications on curved manifolds and quantum systems.

physics.comp-phCross-listedarXiv:2605.23923•Apr 21, 2026
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.
Quantum mechanics requires the operation of quantum computers to be unitary, and thus makes it important to have general techniques for developing fast quantum algorithms for computing unitary transforms. A quantum routine for computing a generalized Kronecker product is given. Applications include re-development of the networks for computing the Walsh-Hadamard and the quantum Fourier transform. New networks for two wavelet transforms are given. Quantum computation of Fourier transforms for non-Abelian groups is defined. A slightly relaxed definition is shown to simplify the analysis and the networks that computes the transforms. Efficient networks for computing such transforms for a class of metacyclic groups are introduced. A novel network for computing a Fourier transform for a group used in quantum error-correction is also given.
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 is another class of unitary transforms, the wavelet transforms, which are every bit as useful as the Fourier transform. Wavelet transforms are used to expose the multi-scale structure of a signal and are likely to be useful for quantum image processing and quantum data compression. In this paper, we derive efficient, complete, quantum circuits for two representative quantum wavelet transforms, the quantum Haar and quantum Daubechies D(4)D^{(4)}D(4) transforms. Our approach is to factor the operators for these transforms into direct sums, direct products and dot products of unitary matrices. In so doing, we find that permutation matrices, a particular class of unitary matrices, play a pivotal role. Surprisingly, we find that operations that are easy and inexpensive to implement classically are not always easy and inexpensive to implement quantum mechanically, and vice versa. In particular, the computational cost of performing certain permutation matrices is ignored classically because they can be avoided explicitly. However, quantum mechanically, these permutation operations must be performed explicitly and hence their cost enters into the full complexity measure of the quantum transform. We consider the particular set of permutation matrices arising in quantum wavelet transforms and develop efficient quantum circuits that implement them. This allows us to design efficient, complete quantum circuits for the quantum wavelet transform.
We present a quantum algorithm for estimating the amplitude content of user-specified sequency bands in quantum-encoded signals. The method employs a sequency-ordered Quantum Walsh-Hadamard Transform (QWHT), a comparator-based oracle that coherently marks basis states within an arbitrary sequency range, and Quantum Amplitude Estimation (QAE) to estimate the total probability mass in the selected band. This enables the detection of structured signal components, including both high- and low-sequency features, as well as the identification of rapid sign-change behavior associated with noise or anomalies. The proposed method can be embedded as a module within a larger quantum algorithm; in this setting, both the input and output remain fully quantum, enabling seamless integration with upstream and downstream quantum operations. We show that the sequency-ordered QWHT can be implemented with circuit depth O(log⁡2N)O(\log_2 N)O(log2​N) (equivalently O(n)O(n)O(n) for N=2nN=2^nN=2n) when acting on an amplitude-encoded quantum state, whereas computing the full Walsh-Hadamard spectrum of an explicit length-NNN classical signal requires O(Nlog⁡2N)O(N\log_2 N)O(Nlog2​N) operations via the fast Walsh-Hadamard transform. This results in an exponential quantum advantage when the QWHT is used as a modular block within a larger quantum algorithm, relative to classical fast Walsh-Hadamard transform-based approaches operating on explicit data. From an application perspective, the proposed sequency band-energy estimation may be interpreted as a structure-based anomaly indicator, enabling the detection of unexpected high-sequency components relative to a nominal low-sequency signal class. The algorithm is applicable to quantum-enhanced signal processing tasks such as zero-crossing analysis, band-limited noise estimation, and feature extraction in the Walsh basis.
The special unitary group SU(2) plays a fundamental role in the description of symmetries in quantum mechanics, theoretical physics, and spherical signal processing. In this paper, we address the computational challenges of performing spectral analysis on this non-abelian compact Lie group. We present the Fourier Transform (FT) on SU(2) and develop a Fast Fourier Transform (FFT) algorithm inspired by the classical Cooley-Tukey divide-and-conquer scheme. Our approach efficiently discretizes the group using Euler angles, applying a two-dimensional FFT on the angular variables and exploiting the recursive properties of Jacobi polynomials. We provide an analysis of the computational complexity, demonstrating that our FFT-based method significantly outperforms the direct computation of the FT. This algorithm serves as a foundational tool for understanding the implementation of the FFT on SU(2), a key component in numerical simulations and advanced data analysis for high-performance computing applications on curved manifolds and quantum systems.