Quantum Algorithms Using the Curvelet Transform

Details Quantum Algorithms Using the Curvelet Transform Quantum Algorithms Using the Curvelet Transform

2008-10-28

arxiv.org/abs/0810.4968v2

Proc. ACM Symposium on Theory of Computing (STOC), pp.391-400, 2009.

Physics

Quantum Physics

64 pages, 4 figures; improved algorithm and lower bound for finding the center of a radial function; revised presentation; to

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Quantum Algorithms Using the Curvelet Transform does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Algorithms Using the Curvelet Transform, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Algorithms Using the Curvelet Transform will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-485147