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

Quantum wave atom transforms

Marianna Podzorova, Yi-Kai Liu

Published Jul 20, 2026• 0 citations
arXivHTMLPDF

Abstract

Abstract This paper constructs the first efficient implementation of a quantum wavelet packet transform with a ‘parabolic scaling’ tree structure, sometimes called a quantum wave atom transform. Classically, wave atom transforms are used to construct sparse representations of differential operators, which enable fast classical algorithms for solving wave equations. Compared to previous work on quantum wavelet transforms, our quantum algorithm can implement a larger class of wavelet and wave atom transforms, by using an efficient representation for a larger class of possible tree structures. Our quantum implementation has O ( poly ( n ) ) gate complexity for applying a transform of dimension 2 n , while classical implementations use O ( n 2 n ) floating point operations. This is potentially useful for designing quantum algorithms for solving wave equations that achieve an exponential speedup over classical algorithms.

DOI
10.1088/2058-9565/ae8d50

Related papers

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

arXiv:2309.09350•Quantum Science and Technology•Apr 11, 2024•14 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•2 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

Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices

Daan Camps, Lin Lin, Roel Van Beeumen +1 more

Abstract. Many standard linear algebra problems can be solved on a quantum computer by using recently developed quantum linear algebra algorithms that make use of block encodings and quantum eigenvalue/singular value transformations. A block encoding embeds a properly scaled matrix of interest [Formula: see text] in a larger unitary transformation [Formula: see text] that can be decomposed into a product of simpler unitaries and implemented efficiently on a quantum computer. Although quantum algorithms can potentially achieve exponential speedup in solving linear algebra problems compared to the best classical algorithm, such a gain in efficiency ultimately hinges on our ability to construct an efficient quantum circuit for the block encoding of [Formula: see text], which is difficult in general, and not trivial even for well structured sparse matrices. In this paper, we give a few examples on how efficient quantum circuits can be explicitly constructed for some well structured sparse matrices and discuss a few strategies used in these constructions. We also provide implementations of these quantum circuits in MATLAB.

arXiv:2203.10236•SIAM Journal on Matrix Analysis and Applications•Mar 11, 2024•78 citations

Quantum algorithm for solving differential equations using SLAC derivatives

Rakshit M. Gharat, Gopikrishnan Muraleedharan, Dominic W. Berry +1 more

In numerical approaches to solving differential equations on a lattice, a representation of the derivative operator that correctly matches the continuum behaviour of functions of momentum up to the band limit must be non-local. We present the construction of efficient linear-combination-of-unitaries ($\mathrm{LCU}$)-based block-encodings for the first-order derivative and Laplacian operators in the non-local \(N=2^n\)-dimensional SLAC representation. We use state-preparation techniques designed for smoothly decaying functions to prepare the dense $\mathrm{LCU}$ amplitudes with high success probability and low gate cost. Furthermore, we demonstrate how Shannon wavelet transforms can be applied to these block-encodings to obtain multiscale representations of the SLAC derivative operators. We then show how to apply a diagonal preconditioner that reduces the condition number of these matrices in the multiscale wavelet basis to a small constant. This enables the solution of partial differential equations (PDEs) with SLAC-discretised derivative operators on a finite lattice using the quantum linear solving algorithm ($\mathrm{QLSA}$). For a $d$-dimensional PDE, after projection away from the nullspace, the resulting quantum linear-system algorithm has overall gate complexity ${O}(dn^3α^{(k)}\log(1/\varepsilon))$, where $α^{(k)}$ is the subnormalisation factor of the order-$k$ SLAC block-encoding and $\varepsilon$ denotes the algorithmic approximation error.

quant-pharXiv:2605.04861•May 7, 2026•0 citations
Abstract This paper constructs the first efficient implementation of a quantum wavelet packet transform with a ‘parabolic scaling’ tree structure, sometimes called a quantum wave atom transform. Classically, wave atom transforms are used to construct sparse representations of differential operators, which enable fast classical algorithms for solving wave equations. Compared to previous work on quantum wavelet transforms, our quantum algorithm can implement a larger class of wavelet and wave atom transforms, by using an efficient representation for a larger class of possible tree structures. Our quantum implementation has O ( poly ( n ) ) gate complexity for applying a transform of dimension 2 n , while classical implementations use O ( n 2 n ) floating point operations. This is potentially useful for designing quantum algorithms for solving wave equations that achieve an exponential speedup over classical algorithms.
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.
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.
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.
Abstract. Many standard linear algebra problems can be solved on a quantum computer by using recently developed quantum linear algebra algorithms that make use of block encodings and quantum eigenvalue/singular value transformations. A block encoding embeds a properly scaled matrix of interest [Formula: see text] in a larger unitary transformation [Formula: see text] that can be decomposed into a product of simpler unitaries and implemented efficiently on a quantum computer. Although quantum algorithms can potentially achieve exponential speedup in solving linear algebra problems compared to the best classical algorithm, such a gain in efficiency ultimately hinges on our ability to construct an efficient quantum circuit for the block encoding of [Formula: see text], which is difficult in general, and not trivial even for well structured sparse matrices. In this paper, we give a few examples on how efficient quantum circuits can be explicitly constructed for some well structured sparse matrices and discuss a few strategies used in these constructions. We also provide implementations of these quantum circuits in MATLAB.
In numerical approaches to solving differential equations on a lattice, a representation of the derivative operator that correctly matches the continuum behaviour of functions of momentum up to the band limit must be non-local. We present the construction of efficient linear-combination-of-unitaries (LCU\mathrm{LCU}LCU)-based block-encodings for the first-order derivative and Laplacian operators in the non-local N=2nN=2^nN=2n-dimensional SLAC representation. We use state-preparation techniques designed for smoothly decaying functions to prepare the dense LCU\mathrm{LCU}LCU amplitudes with high success probability and low gate cost. Furthermore, we demonstrate how Shannon wavelet transforms can be applied to these block-encodings to obtain multiscale representations of the SLAC derivative operators. We then show how to apply a diagonal preconditioner that reduces the condition number of these matrices in the multiscale wavelet basis to a small constant. This enables the solution of partial differential equations (PDEs) with SLAC-discretised derivative operators on a finite lattice using the quantum linear solving algorithm (QLSA\mathrm{QLSA}QLSA). For a ddd-dimensional PDE, after projection away from the nullspace, the resulting quantum linear-system algorithm has overall gate complexity O(dn3α(k)log⁡(1/ε)){O}(dn^3α^{(k)}\log(1/\varepsilon))O(dn3α(k)log(1/ε)), where α(k)α^{(k)}α(k) is the subnormalisation factor of the order-kkk SLAC block-encoding and ε\varepsilonε denotes the algorithmic approximation error.