Yi-Kai Liu

California Institute of Technology

Quantum Algorithms Using the Curvelet Transform

November 20, 2008 - 3:55-4:20pm

RLE Conference Center 36-428

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 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.

Bio

Yi-Kai 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.