YiKai Liu
California Institute of Technology 
Quantum Algorithms Using the Curvelet Transform
November 20, 2008  3:554:20pm
RLE Conference Center 36428
Abstract
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 singleshot measurement procedure for approximately finding the center of a ball in R^n, given quantumsamples 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 quantumsamples or oracle queries, independent of the dimension n  this can be interpreted as a quantum speedup. 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.
Bio
YiKai Liu is interested in quantum algorithms, and the complexity of simulating quantum systems. He is currently a postdoc at Caltech on an NSF fellowship; he received a PhD in computer science from UC San Diego, and a BA in mathematics from Princeton. He is attracted to difficult problems, but this feeling does not seem to be mutual.
