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) is a fundamental primitive in quantum computation and quantum information. In this work, we extend the framework for the QFT from finite groups to finite-dimensional semisimple algebras, and give efficient QFTs for the partition algebra
Pn(d), Brauer algebra
Bn(d), and walled Brauer algebra
Br,s(d). These algebras play important roles in generalized Schur-Weyl duality, statistical physics and many-body systems, and have recently found several applications in quantum algorithms.
Unlike the group case, the Fourier transform over a semisimple algebra can be non-unitary. Nevertheless, we show that when the parameter
d is sufficiently large, the Fourier transform is well approximated by a unitary operator. Furthermore, we show that for each of the algebras
A from above, such an approximate Fourier transform can be implemented efficiently: we give a quantum algorithm with gate complexity
poly(n,logd,log(1/ε)) for approximating the Fourier transform to error
(d−1/2+ε)⋅poly(∣A∣). Along the way, we establish several properties of the Fourier basis of semisimple algebras that may be of independent interest.
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.
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(dlogN). Simulations demonstrate effectiveness for tasks such as power systems control and image processing, with exact agreement with classical results.