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.