Algorithms · Quantum query algorithm
Finding the center of a radial function with the curvelet transform
Given oracle access to a spherically symmetric function f from R^d to an arbitrary set S, locate its center of symmetry to a fixed precision using as few queries as possible.
Attested & literatureUpdated
- Record typeLiterature reference
- Speedup class (secondary source)Polynomial
- Primary source on the speedupNot checked against the primary source yet
- Reported costA constant number of quantum queries independent of the dimension, written O(1) oracle queries, against a classical lower bound of Ω(d) queries, the Zoo naming that dimension d where the paper names it n. The Zoo states the constant-query result flatly, but the paper puts the count forward as a conjecture rather than a theorem: it conjectures that the algorithms succeed with constant probability using one quantum-sample and O(1) oracle queries respectively, independent of the dimension n. What the paper reports as proved are rigorous bounds on the distribution of probability mass for the continuous curvelet transform, which show that the algorithms work in an idealized continuous model. The precision to which the center is located is fixed for simplicity in the Zoo statement, and neither source states a gate count.
- Papers1
Given oracle access to a spherically symmetric function f from R^d to an arbitrary set S, locate its center of symmetry to a fixed precision using as few queries as possible. Liu takes up the curvelet transform, a directional wavelet transform over R^n used to analyze functions that have singularities along smooth surfaces, and gives an efficient implementation of a quantum curvelet transform. Two applications rest on that implementation: a single-shot measurement procedure that approximately finds the center of a ball in R^n from a quantum-sample over the ball, and — the algorithm this record covers — a quantum algorithm for finding the center of a radial function over R^n from oracle access to the function. The Zoo records the condition under which the second one applies, namely that f fluctuates on sufficiently small scales, for example when the level sets of f are sufficiently thin spherical shells. What the paper proves are bounds on the distribution of probability mass for the continuous curvelet transform, offered as support for its own conjecture and showing that the algorithms work in an idealized continuous model.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
Liu takes up the curvelet transform, a directional wavelet transform over R^n used to analyze functions that have singularities along smooth surfaces, and gives an efficient implementation of a quantum curvelet transform. Two applications rest on that implementation: a single-shot measurement procedure that approximately finds the center of a ball in R^n from a quantum-sample over the ball, and — the algorithm this record covers — a quantum algorithm for finding the center of a radial function over R^n from oracle access to the function. The Zoo records the condition under which the second one applies, namely that f fluctuates on sufficiently small scales, for example when the level sets of f are sufficiently thin spherical shells. What the paper proves are bounds on the distribution of probability mass for the continuous curvelet transform, offered as support for its own conjecture and showing that the algorithms work in an idealized continuous model. This record's speedup class, "Polynomial", is a secondary source's classification of the oracular algorithms it files this under — not a claim its primary paper makes. Not checked against the primary source yet. Reported cost: A constant number of quantum queries independent of the dimension, written O(1) oracle queries, against a classical lower bound of Ω(d) queries, the Zoo naming that dimension d where the paper names it n. The Zoo states the constant-query result flatly, but the paper puts the count forward as a conjecture rather than a theorem: it conjectures that the algorithms succeed with constant probability using one quantum-sample and O(1) oracle queries respectively, independent of the dimension n. What the paper reports as proved are rigorous bounds on the distribution of probability mass for the continuous curvelet transform, which show that the algorithms work in an idealized continuous model. The precision to which the center is located is fixed for simplicity in the Zoo statement, and neither source states a gate count..
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
- Record type
- Literature reference
- Speedup class (secondary source)
- Polynomial
- Primary source on the speedup
- Not checked against the primary source yet
- Reported cost
- A constant number of quantum queries independent of the dimension, written O(1) oracle queries, against a classical lower bound of Ω(d) queries, the Zoo naming that dimension d where the paper names it n. The Zoo states the constant-query result flatly, but the paper puts the count forward as a conjecture rather than a theorem: it conjectures that the algorithms succeed with constant probability using one quantum-sample and O(1) oracle queries respectively, independent of the dimension n. What the paper reports as proved are rigorous bounds on the distribution of probability mass for the continuous curvelet transform, which show that the algorithms work in an idealized continuous model. The precision to which the center is located is fixed for simplicity in the Zoo statement, and neither source states a gate count.
- Speedup class
- Polynomial (not yet checked against the record's own primary paper)
- Complexity basis
- abstract of arXiv:0810.4968: "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", and, for what is actually established, "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." The abstract encloses continuous in double quotation marks; they appear here as single marks so as not to close the quotation around them. Quantum Algorithm Zoo entry "Center of Radial Function", LaTeX rendered into Unicode: "We wish to locate the center of symmetry, up to some precision. (For simplicity, let the precision be fixed.)", "Liu gives a quantum algorithm, based on a curvelet transform, that solves this problem using a constant number of quantum queries independent of d. This constitutes a polynomial speedup over the classical lower bound, which is Ω(d) queries", together with "The quantum algorithm is shown to work in an idealized continuous model, and nonrigorous arguments suggest that discretization effects should be small." Neither source states a gate count, a circuit depth or a constant factor, and the two name the dimension differently, n in the paper and d in the Zoo.
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Quantum query algorithm with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
ALGORITHM: Finding the center of a radial function with the curvelet transform
PROBLEM: Given oracle access to a spherically symmetric function f from R^d to an arbitrary set S, locate its center of symmetry to a fixed precision using as few queries as possible.
IDEA: Liu takes up the curvelet transform, a directional wavelet transform over R^n used to analyze functions that have singularities along smooth surfaces, and gives an efficient implementation of a quantum curvelet transform. Two applications rest on that implementation: a single-shot measurement procedure that approximately finds the center of a ball in R^n from a quantum-sample over the ball, and — the algorithm this record covers — a quantum algorithm for finding the center of a radial function over R^n from oracle access to the function. The Zoo records the condition under which the second one applies, namely that f fluctuates on sufficiently small scales, for example when the level sets of f are sufficiently thin spherical shells. What the paper proves are bounds on the distribution of probability mass for the continuous curvelet transform, offered as support for its own conjecture and showing that the algorithms work in an idealized continuous model.
REPORTED COST: A constant number of quantum queries independent of the dimension, written O(1) oracle queries, against a classical lower bound of Ω(d) queries, the Zoo naming that dimension d where the paper names it n. The Zoo states the constant-query result flatly, but the paper puts the count forward as a conjecture rather than a theorem: it conjectures that the algorithms succeed with constant probability using one quantum-sample and O(1) oracle queries respectively, independent of the dimension n. What the paper reports as proved are rigorous bounds on the distribution of probability mass for the continuous curvelet transform, which show that the algorithms work in an idealized continuous model. The precision to which the center is located is fixed for simplicity in the Zoo statement, and neither source states a gate count.
BASIS: abstract of arXiv:0810.4968: "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", and, for what is actually established, "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." The abstract encloses continuous in double quotation marks; they appear here as single marks so as not to close the quotation around them. Quantum Algorithm Zoo entry "Center of Radial Function", LaTeX rendered into Unicode: "We wish to locate the center of symmetry, up to some precision. (For simplicity, let the precision be fixed.)", "Liu gives a quantum algorithm, based on a curvelet transform, that solves this problem using a constant number of quantum queries independent of d. This constitutes a polynomial speedup over the classical lower bound, which is Ω(d) queries", together with "The quantum algorithm is shown to work in an idealized continuous model, and nonrigorous arguments suggest that discretization effects should be small." Neither source states a gate count, a circuit depth or a constant factor, and the two name the dimension differently, n in the paper and d in the Zoo.
PRIMARY SOURCE: Yi-Kai Liu (2008), Quantum Algorithms Using the Curvelet Transform — https://arxiv.org/abs/0810.4968
This is a literature reference record, not an executable circuit.A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Related entries
- Hidden nonlinear structures over finite fields
Algorithms
- Hidden shift problem
Algorithms
- Quantum Fourier Transform
Algorithms
References
- Quantum Algorithms Using the Curvelet Transform
Yi-Kai Liu · 2008
Primary source. It gives an efficient implementation of a quantum curvelet transform — the curvelet transform being a directional wavelet transform over R^n for functions with singularities along smooth surfaces, which the abstract attributes to Candes and Donoho, 2002 — and applies it both to finding the center of a ball from a quantum-sample and to finding the center of a radial function from oracle access. The O(1)-query cost is stated there as a conjecture supported by bounds on the distribution of probability mass for the continuous curvelet transform, so consult the paper for what the continuous model assumes and for how far the rigorous bounds reach.