Quantum Wave Atom Transforms

Author(s)

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.

Download Paper

Keywords

Quantum information science and Numerical methods and software

Citation

Issues

If you have any questions about this publication or are having problems accessing it, please contact [email protected].