Attested & literatureAlgorithmsQuantum query algorithm2026-08-12

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.

Oracle query

curvelet transformradial functioncenter findingquery complexityoracle

Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.

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.

Circuit & simulation

problem

encodetransform

algorithm

transformmeasure

readout

measure

What this takes and returns

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 →

How it works

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

Implementation

FrameworkUnsupported

radial-function-center.txt

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.

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.

Declared gaps

Nobody has reviewed this record for gaps yet.

Literature & references

Quantum Algorithms Using the Curvelet Transform2008 · Yi-Kai Liu

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.

arxiv.org/abs/0810.4968 ↗

Verification

Attested & literature

Peer-reviewed paper

Method: Curation only. The problem statement and speedup class were checked against the Quantum Algorithm Zoo's entry "Center of Radial Function" (Oracular Algorithms); the primary reference's title, authors and submission year were read from its arXiv abs page; the complexity claim was taken from a clause of that paper's abstract (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.). No circuit was constructed, simulated or run.
Result: Pass · the record's problem, speedup class and primary reference agree with the two sources named above.
Caveat: This is a literature record: no circuit was constructed, compiled, simulated or run, no curvelet transform was implemented here, and no center was located. The headline cost is a conjecture rather than a theorem — the paper conjectures that its algorithms succeed with constant probability using O(1) oracle queries independent of the dimension, and what it proves is a set of bounds on the distribution of probability mass for the continuous curvelet transform — so this record establishes only that the paper states the constant-query claim, not the claim itself. The Zoo carries the same result without that hedge, saying outright that the algorithm solves the problem in a constant number of queries; the hedge is the paper's own, and this record keeps it. That proof covers an idealized continuous model; the Zoo says nonrigorous arguments suggest that discretization effects should be small, which is an expectation and not a result, and nothing here bounds the cost of a discretized version. The figure is a query count, so gate counts, qubit counts, circuit depth, the cost of realizing the oracle for a given f, and the cost of the quantum curvelet transform itself, which the abstract calls efficient without quoting a figure, all fall outside this record. The claim is conditional on the function: the Zoo states that the algorithm works when f fluctuates on sufficiently small scales, for instance when its level sets are sufficiently thin spherical shells, so a smooth or slowly varying radial function is not covered. Precision is treated as fixed for simplicity, so nothing here says how the cost grows as the center is demanded more precisely, and neither source gives a success probability beyond calling it constant. The classical Ω(d) lower bound is the Zoo's figure, quoted and not re-derived. The single-shot ball-center procedure in the same paper is a separate application that consumes a quantum-sample rather than oracle queries, and it is not the algorithm this entry covers.

Facts

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.
Secondary source for the speedup class: Quantum Algorithm Zoo — "Center of Radial Function"
Section it is filed under: Oracular Algorithms
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

Source

Quantum Algorithms Using the Curvelet Transform ↗

Kind: curated reference
Reviewed by: Leona Quantum curation pass
License: Citation metadata only; source publication terms apply