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.
https://resolver.caltech.edu/CaltechAUTHORS:20100510-110636690

PDF
- Published Version
Restricted to Repository administrators only See Usage Policy. 587Kb |

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20100510-110636690

## Abstract

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: |
| |||||||||

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. | |||||||||

Funders: |
| |||||||||

Subject Keywords: | Curvelet transform; Fourier transform; oracle problems; quantum computation; radial functions; wavelets | |||||||||

Record Number: | CaltechAUTHORS:20100510-110636690 | |||||||||

Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20100510-110636690 | |||||||||

Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||

ID Code: | 18212 | |||||||||

Collection: | CaltechAUTHORS | |||||||||

Deposited By: | Tony Diaz | |||||||||

Deposited On: | 17 May 2010 03:17 | |||||||||

Last Modified: | 03 Oct 2019 01:39 |

Repository Staff Only: item control page