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:2309.09350 · Quantum Science and Technology

Efficient quantum algorithm for all quantum wavelet transforms

Mohsen Bagherimehrab, Alán Aspuru‐Guzik

Published Apr 11, 2024• 21 citations
arXivHTMLPDF

Abstract

Abstract Wavelet transforms are widely used in various fields of science and engineering as a mathematical tool with features that reveal information ignored by the Fourier transform. Unlike the Fourier transform, which is unique, a wavelet transform is specified by a sequence of numbers associated with the type of wavelet used and an order parameter specifying the length of the sequence. While the quantum Fourier transform, a quantum analog of the classical Fourier transform, has been pivotal in quantum computing, prior works on quantum wavelet transforms (QWTs) were limited to the second and fourth order of a particular wavelet, the Daubechies wavelet. Here we develop a simple yet efficient quantum algorithm for executing any wavelet transform on a quantum computer. Our approach is to decompose the kernel matrix of a wavelet transform as a linear combination of unitaries (LCU) that are compilable by easy-to-implement modular quantum arithmetic operations and use the LCU technique to construct a probabilistic procedure to implement a QWT with a known success probability. We then use properties of wavelets to make this approach deterministic by a few executions of the amplitude amplification strategy. We extend our approach to a multilevel wavelet transform and a generalized version, the packet wavelet transform, establishing computational complexities in terms of three parameters: the wavelet order M , the dimension N of the transformation matrix, and the transformation level d . We show the cost is logarithmic in N , linear in d and superlinear in M . Moreover, we show the cost is independent of M for practical applications. Our proposed QWTs could be used in quantum computing algorithms in a similar manner to their well-established counterpart, the quantum Fourier transform.

DOI
10.1088/2058-9565/ad3d7f

Related papers

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•31 citations

Quantum wavelet transforms of any order

Francisco Argüello

Many classical algorithms are known to efficiently compute the wavelet transforms. However, those classical algorithms cannot be directly translated to quantum algorithms. Recently, efficient and complete quantum algorithms for two representative wavelet transforms (quantum Haar and quantum Daubechies of fourth order) have been proposed. In this paper, we generalize these algorithms in order to they can be applied to Daubechies wavelet kernels of any order. Specifically, we develop a method that efficiently factorize those kernels. The factorization is compatible with the existing pyramidal and packet quantum wavelet algorithms. All steps of the algorithm are unitary and easily implementable on a quantum computer.

Quantum Information and Computation•May 1, 2009•3 citations

Quantum Wavelet Transforms

The classical wavelet transform has been widely applied in the information processing field. It implies that quantum wavelet transform (QWT) may play an important role in quantum information processing. This chapter firstly describes the iteration equations of the general QWT using generalized tensor product. Then, Haar QWT (HQWT), Daubechies D4 QWT (DQWT), and their inverse transforms are proposed respectively. Meanwhile, the circuits of the two kinds of multi-level HQWT are designed. What's more, the multi-level DQWT based on the periodization extension is implemented. The complexity analysis shows that the proposed multi-level QWTs on 2n elements can be implemented by O(n3) basic operations. Simulation experiments demonstrate that the proposed QWTs are correct and effective.

Advances in computer and electrical engineering book series•Aug 26, 2020•0 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•3 citations

Multilevel 2-D Quantum Wavelet Transforms

Hai-Sheng Li, Ping Fan, Huiling Peng +2 more

Wavelet transform is being widely used in classical image processing. One-dimension quantum wavelet transforms (QWTs) have been proposed. Generalizations of the 1-D QWT into multilevel and multidimension have been investigated but restricted to the quantum wavelet packet transform (QWPTs), which is the direct product of 1-D QWPTs, and there is no transform between the packets in different dimensions. A 2-D QWT is vital for image processing. We construct the multilevel 2-D QWT's general theory. Explicitly, we built multilevel 2-D Haar QWT and the multilevel Daubechies D4 QWT, respectively. We have given the complete quantum circuits for these wavelet transforms, using both noniterative and iterative methods. Compared to the 1-D QWT and wavelet packet transform, the multilevel 2-D QWT involves the entanglement between components in different degrees. Complexity analysis reveals that the proposed transforms offer exponential speedup over their classical counterparts. Also, the proposed wavelet transforms are used to realize quantum image compression. Simulation results demonstrate that the proposed wavelet transforms are significant and obtain the same results as their classical counterparts with an exponential speedup.

IEEE Transactions on Cybernetics•Jan 27, 2021•49 citations

Windowed Fourier transform and general wavelet algorithms in quantum computation

Guangsheng Ma, Hongbo Li, Jiman Zhao

In this paper, we define the quantum windowed Fourier transform and study some of its properties, then we develop two useful operations called quantum convolution and `integral'. Quantum `integral' allows us to implement the integral transforms quantum-mechanically with a certain probability, including general wavelet kernel transforms. Furthermore, we propose an improved wavelet kernel transform for quantum computation.

Quantum Information and Computation•Mar 1, 2019•2 citations
Abstract Wavelet transforms are widely used in various fields of science and engineering as a mathematical tool with features that reveal information ignored by the Fourier transform. Unlike the Fourier transform, which is unique, a wavelet transform is specified by a sequence of numbers associated with the type of wavelet used and an order parameter specifying the length of the sequence. While the quantum Fourier transform, a quantum analog of the classical Fourier transform, has been pivotal in quantum computing, prior works on quantum wavelet transforms (QWTs) were limited to the second and fourth order of a particular wavelet, the Daubechies wavelet. Here we develop a simple yet efficient quantum algorithm for executing any wavelet transform on a quantum computer. Our approach is to decompose the kernel matrix of a wavelet transform as a linear combination of unitaries (LCU) that are compilable by easy-to-implement modular quantum arithmetic operations and use the LCU technique to construct a probabilistic procedure to implement a QWT with a known success probability. We then use properties of wavelets to make this approach deterministic by a few executions of the amplitude amplification strategy. We extend our approach to a multilevel wavelet transform and a generalized version, the packet wavelet transform, establishing computational complexities in terms of three parameters: the wavelet order M , the dimension N of the transformation matrix, and the transformation level d . We show the cost is logarithmic in N , linear in d and superlinear in M . Moreover, we show the cost is independent of M for practical applications. Our proposed QWTs could be used in quantum computing algorithms in a similar manner to their well-established counterpart, the quantum Fourier transform.
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.
Many classical algorithms are known to efficiently compute the wavelet transforms. However, those classical algorithms cannot be directly translated to quantum algorithms. Recently, efficient and complete quantum algorithms for two representative wavelet transforms (quantum Haar and quantum Daubechies of fourth order) have been proposed. In this paper, we generalize these algorithms in order to they can be applied to Daubechies wavelet kernels of any order. Specifically, we develop a method that efficiently factorize those kernels. The factorization is compatible with the existing pyramidal and packet quantum wavelet algorithms. All steps of the algorithm are unitary and easily implementable on a quantum computer.
The classical wavelet transform has been widely applied in the information processing field. It implies that quantum wavelet transform (QWT) may play an important role in quantum information processing. This chapter firstly describes the iteration equations of the general QWT using generalized tensor product. Then, Haar QWT (HQWT), Daubechies D4 QWT (DQWT), and their inverse transforms are proposed respectively. Meanwhile, the circuits of the two kinds of multi-level HQWT are designed. What's more, the multi-level DQWT based on the periodization extension is implemented. The complexity analysis shows that the proposed multi-level QWTs on 2n elements can be implemented by O(n3) basic operations. Simulation experiments demonstrate that the proposed QWTs are correct and effective.
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.
Wavelet transform is being widely used in classical image processing. One-dimension quantum wavelet transforms (QWTs) have been proposed. Generalizations of the 1-D QWT into multilevel and multidimension have been investigated but restricted to the quantum wavelet packet transform (QWPTs), which is the direct product of 1-D QWPTs, and there is no transform between the packets in different dimensions. A 2-D QWT is vital for image processing. We construct the multilevel 2-D QWT's general theory. Explicitly, we built multilevel 2-D Haar QWT and the multilevel Daubechies D4 QWT, respectively. We have given the complete quantum circuits for these wavelet transforms, using both noniterative and iterative methods. Compared to the 1-D QWT and wavelet packet transform, the multilevel 2-D QWT involves the entanglement between components in different degrees. Complexity analysis reveals that the proposed transforms offer exponential speedup over their classical counterparts. Also, the proposed wavelet transforms are used to realize quantum image compression. Simulation results demonstrate that the proposed wavelet transforms are significant and obtain the same results as their classical counterparts with an exponential speedup.