01371nas a2200121 4500008004100000245005200041210005200093260001500145300001200160520102400172100001601196856003701212 2009 eng d00aQuantum Algorithms Using the Curvelet Transform0 aQuantum Algorithms Using the Curvelet Transform c2009/10/28 a391-4003 a 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.
1 aLiu, Yi-Kai uhttp://arxiv.org/abs/0810.4968v2