Quantum algorithms using the curvelet transform

DOI10.1145/1536414.1536469MaRDI QIDQ5172733zbMATH OpenOpenAlexWikidataFDO

Authors Yi-Kai Liu

Publication date 4 February 2015

Published in Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0810.4968

zbMATH Keywords

curvelet transformFourier transformoracle problemsquantum computationradial functionswavelets

Mathematics Subject Classification ID

Numerical methods for wavelets (65T60) Quantum algorithms and complexity in the theory of computing (68Q12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum computation (81P68)

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.

Recommendations

• Wavelet matrix operations and quantum transforms
• scientific article; zbMATH DE number 5568621
• scientific article; zbMATH DE number 1985235
• scientific article; zbMATH DE number 1406111
• Quantum fourier transform over symmetric groups

Cited in

(6)

• Wavelet matrix operations and quantum transforms
• scientific article; zbMATH DE number 5669860 (Why is no real title available?)
• scientific article; zbMATH DE number 1406111 (Why is no real title available?)
• Quantum fast corner detection algorithm
• Quantum wave packet transforms with compact frequency support: Implementations for wavelets and Gabor atoms
• The quadratic-phase curvelet transform and associated uncertainty relations

This page was built for publication: Quantum algorithms using the curvelet transform

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5172733)