Quantum Wave Atom Transforms

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.