In this paper, new techniques to implement the Daubechies wavelets and multiwavelets are presented using quantum computing synthesis structures. Also, a new quantum implementation of inverse Daubechies multiwavelet transform is proposed. The permutation matrices, particular unitary matrices, play a pivotal role. The particular set of permutation matrices arising in quantum wavelet and multiwavelet transforms is considered, and efficient quantum circuits that implement them are developed. This allows the design of efficient and complete quantum circuits for the quantum wavelet and multiwavelet transforms.In this paper, new techniques to implement the Daubechies wavelets and multiwavelets are presented using quantum computing synthesis structures. Also, a new quantum implementation of inverse Daubechies multiwavelet transform is proposed. The permutation matrices, particular unitary matrices, play a pivotal role. The particular set of permutation matrices arising in quantum wavelet and multiwavelet transforms is considered, and efficient quantum circuits that implement them are developed. This allows the design of efficient and complete quantum circuits for the quantum wavelet and multiwavelet transforms.

Facta universitatis - series Electronics and EnergeticsJan 1, 20138 citations

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.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/9809004Presented atSep 2, 199815 citations

Quantum Harr wavelet transform and its complete circuits

XU Wen-bo

Because of the prominent advantages of quantum computation compared to classic computation,implementation of quantum wavelet transforms has profound significance to its completion and application.After the circuit for perfect shuffle permutation matrices is finished,the unitary matrices for Harr functions are decomposed into a sequence of W-H and perfect shuffle permutation matrices,based on the generalized Kronecker product.Then the quantum circuit for Harr matrices is provided,its realizable complexity and pos-sibility of physical implementation is analyzed.Because of the prominent advantages of quantum computation compared to classic computation,implementation of quantum wavelet transforms has profound significance to its completion and application.After the circuit for perfect shuffle permutation matrices is finished,the unitary matrices for Harr functions are decomposed into a sequence of W-H and perfect shuffle permutation matrices,based on the generalized Kronecker product.Then the quantum circuit for Harr matrices is provided,its realizable complexity and pos-sibility of physical implementation is analyzed.

Jisuanji gongcheng yu shejiJan 1, 20070 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.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 ComputationMay 1, 20092 citations

Efficient quantum algorithm for all quantum wavelet transforms

Mohsen Bagherimehrab, Alán Aspuru‐Guzik

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.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.

arXiv:2309.09350Quantum Science and TechnologyApr 11, 202414 citations

Representation and design of wavelets using unitary circuits

Glen Evenbly, Steven R. White

The representation of discrete, compact wavelet transformations (WTs) as circuits of local unitary gates is discussed. We employ a similar formalism as used in the multiscale representation of quantum many-body wave functions using unitary circuits, further cementing the relation established in the literature between classical and quantum multiscale methods. An algorithm for constructing the circuit representation of known orthogonal, dyadic, discrete WTs is presented, and the explicit representation for Daubechies wavelets, coiflets, and symlets is provided. Furthermore, we demonstrate the usefulness of the circuit formalism in designing WTs, including various classes of symmetric wavelets and multiwavelets, boundary wavelets, and biorthogonal wavelets.The representation of discrete, compact wavelet transformations (WTs) as circuits of local unitary gates is discussed. We employ a similar formalism as used in the multiscale representation of quantum many-body wave functions using unitary circuits, further cementing the relation established in the literature between classical and quantum multiscale methods. An algorithm for constructing the circuit representation of known orthogonal, dyadic, discrete WTs is presented, and the explicit representation for Daubechies wavelets, coiflets, and symlets is provided. Furthermore, we demonstrate the usefulness of the circuit formalism in designing WTs, including various classes of symmetric wavelets and multiwavelets, boundary wavelets, and biorthogonal wavelets.

arXiv:1605.07312Physical Review AMay 11, 201828 citations

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.