Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Quantum Computation Seminar

Yi-Kai Liu

Institute for Quantum Information, Caltech

Towards Quantum Algorithms using the Curvelet Transform

Abstract:

The curvelet transform is a directional wavelet transform, introduced by Candes and Donoho (2002). I will present some preliminary results on curvelet-based quantum algorithms. First, the quantum curvelet transform can be implemented efficiently, for a simple class of ``Haar curvelets," and possibly for other curvelets as well. Next, consider the following example. Given a state that is a uniform superposition over a ball in $\mathbb{R}^n$, we compute the (continuous) curvelet transform. We then measure the state, and observe a scale $a$, direction $\theta$ and location $b$. With significant probability, $a$ is small (corresponding to a fine-scale element), and $b$ and $\theta$ determine a line that passes close to the center of the ball. This suggests an interesting quantum algorithm for finding the center of a radial function. However, there remain some technical obstacles in carrying this result over to the discrete setting, and in designing a suitable mother curvelet that can be implemented efficiently.

Host: David Meyer

July 24, 2008

12:30 PM

AP&M 7218

****************************