Quantum Algorithms Using the Curvelet Transform

TitleQuantum Algorithms Using the Curvelet Transform
Publication TypeJournal Article
Year of Publication2009
AuthorsLiu, Y-K
JournalProc. ACM Symposium on Theory of Computing (STOC)
Date Published2009/10/28

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.

Short TitleProc. ACM Symposium on Theory of Computing (STOC)