Efficient Quantum Algorithm for All Quantum Wavelet Transforms

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 \textit{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 quantum wavelet transforms could be used in quantum computing algorithms in a similar manner to their well-established counterpart, the quantum Fourier transform.

This version is identical in content to the published version. Presentation improved, typos fixed, and figures 1 and 2 added

References in corpus (13)

• Elementary gates for quantum computation
• Quantum Circuits for General Multiqubit Gates
• A new quantum ripple-carry addition circuit
• Entanglement renormalization and wavelets
• Efficient Quantum Transforms
• Multi-scale quantum simulation of quantum field theory using wavelets
• Wavelets in Field Theory
• Representation and design of wavelets using unitary circuits
• Accurate and Efficient Quantum Computations of Molecular Properties Using Daubechies Wavelet Molecular Orbitals: A Benchmark Study against Experimental Data
• Nearly optimal quantum algorithm for generating the ground state of a free quantum field theory
• Wavelet representation of light-front quantum field theory
• Fast quantum algorithm for differential equations
• Improved Wavelets for Image Compression from Unitary Circuits

Cited by in corpus (2)

• Chemically Motivated Simulation Problems are Efficiently Solvable by a Quantum Computer
• Hamiltonian formulation of the $1+1$-dimensional ${\varphi }^4$ theory in a momentum-space Daubechies wavelet basis