Quantum Algorithms Using the Curvelet Transform

SPECIAL COMPUTER SCIENCE/DISCRETE MATH SEMINAR
Topic:Quantum Algorithms Using the Curvelet Transform
Speaker:Yi-Kai Liu
Affiliation:Caltech
Date:Monday, November 24
Time/Room:4:00pm - 5:00pm/S-101

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.