A Caltech Library Service

Quantum Algorithms Using the Curvelet Transform

Liu, Yi-Kai (2009) Quantum Algorithms Using the Curvelet Transform. In: Proceedings ACM Symposium on Theory of Computing (STOC). ACM , pp. 391-400. ISBN 978-1-60558-506-2.

[img] PDF - Published Version
Restricted to Repository administrators only
See Usage Policy.


Use this Persistent URL to link to this item:


The curvelet transform is a directional wavelet transform over R^n, which is used to analyze functions that have singularities along smooth surfaces (Candes and Donoho, 2002). 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 a quantum-sample 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 succeed with constant probability, using one quantum-sample and O(1) oracle queries, respectively, independent of the dimension n -- this can be interpreted as a quantum speed-up. To support this conjecture, I prove rigorous bounds on the distribution of probability mass for the continuous curvelet transform. This shows that the above algorithms work in an idealized "continuous" model.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2009 ACM. The author is grateful to R. Koenig, J. Preskill, L. Schulman, A. Childs, D. Meyer, N. Wallach, S. Jordan, E. Cand`es, U. Vazirani (who suggested the iterative algorithm in section 7.4), Z. Landau, D. Aharonov (who pointed out reference [4]), E. Eban, T. Vidick, and the anonymous referees, for helpful discussions and comments. Supported by an NSF Mathematical Sciences Postdoctoral Fellowship.
Funding AgencyGrant Number
NSF Mathematical Sciences PostdoctoralUNSPECIFIED
Subject Keywords:Curvelet transform; Fourier transform; oracle problems; quantum computation; radial functions; wavelets
Record Number:CaltechAUTHORS:20100510-110636690
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:18212
Deposited By: Tony Diaz
Deposited On:17 May 2010 03:17
Last Modified:03 Oct 2019 01:39

Repository Staff Only: item control page