Special Computer Science/Discrete Mathematics Seminar

The curvelet transform is a directional wavelet transform over R^n, originally due to Candes and Donoho (2002). It is used to analyze functions that have singularities along smooth surfaces. 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 quantum-samples 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 only require a constant number of quantum-samples or oracle queries, independent of the dimension n -- this can be interpreted as a quantum speed-up. Finally, I prove some rigorous bounds on the distribution of probability mass for the continuous curvelet transform. This almost proves my conjecture, except for issues of discretization.