quantum algorithms using the curvelet transform
The curvelet transform is a directional wavelet transform over R n , which is used to analyze functions that have singularities along smooth surfaces (Candes and Donoho, 2002). I demonstrate how this can lead to new quantum algorithms. I give an efficient implementation of a quantum curvelet transform, together with two applications: a single-shot measurement procedure for approximately finding the center of a ball in R n , given a quantum-sample over the ball; and, a quantum algorithm for finding the center of a radial function over R n , given oracle access to the function. I conjecture that these algorithms succeed with constant probability, using one quantum-sample and O(1) oracle queries, respectively, independent of the dimension n -- this can be interpreted as a quantum speed-up. To support this conjecture, I prove rigorous bounds on the distribution of probability mass for the continuous curvelet transform. This shows that the above algorithms work in an idealized "continuous" model.
curvelet transform wavelets radial functions fourier transform oracle problems quantum computation