Conditioning-Free Non-Uniform Quantum Fourier and Chebyshev Transforms

AI summary

Overview

Research area: Quantum algorithms for numerical linear algebra and numerical analysis — specifically quantum implementations of non-uniform Fourier transforms (NUQFT) and Chebyshev transforms, built from block encodings, quantum Fourier transforms, linear combinations of unitaries, and reversible fixed-point arithmetic.

Technical level: Advanced. The paper assumes familiarity with block encoding, the quantum Fourier transform, linear combination of unitaries, Bessel functions, and fixed-point reversible circuits.

Scope: The paper re-derives the error analysis of a low-rank non-uniform quantum Fourier transform so that its cost no longer depends on a node-geometry conditioning parameter κ, and applies the result to give an explicit, conditioning-free block encoding of a non-uniform Chebyshev transform on N = 2^n equispaced nodes.

What This Paper Is About

Chebyshev expansions are a standard way to approximate functions on an interval, and the "Chebyshev transform" is the step that turns sampled function values into expansion coefficients. When the sample points are equally spaced in x ∈ [−1, 1], the corresponding angles θ = arccos x are not equally spaced, so the usual QFT-based quantum Chebyshev transform does not apply. The paper's goal is a quantum algorithm that performs this non-uniform Chebyshev transform (NUCT) as a block encoding, with error bounds that do not degrade as the nodes approach awkward positions.

Key Contributions

1. A κ-free NUQFT analysis. The authors rework the error analysis of the non-uniform quantum Fourier transform of prior work so that the conditioning parameter κ — which measures the conditioning of an auxiliary arccos evaluation and blows up as a scaled node approaches the midpoint between two grid points — disappears entirely from the cost (Theorem 4.7). The resulting NUDFT block encoding has normalization O(√d_r), where d_r is the largest number of nodes rounding to the same grid point, and uses Õ(log²(N/ε)) gates.

2. A reduction of the NUCT to two Type-II NUDFTs. The Chebyshev transform matrix is written as the average of two non-uniform Fourier sums, c_j = ½ Σ_k f_k (e^{ijθ_k} + e^{−ijθ_k}), and implemented with a single controlled NUQFT circuit (Theorem 5.1). Because the resulting operator is generally non-unitary, it is delivered as a block encoding rather than as an orthonormal basis change.

3. Explicit oracle constructions, including the previously assumed row-access oracle. For the NUCT nodes the authors prove that at most five angles round to the same grid point (d_r ≤ 5) and build the row-access oracle explicitly (Proposition 5.5), so no assumption on collisions or row access remains.

4. An end-to-end complexity analysis. The NUCT on N equispaced nodes has an explicit ε-accurate block encoding with O(1) normalization, using O(log(N/ε)) qubits and Õ(log²(N/ε)) gates, with L = log N + log(1/ε) (Theorems 5.9 and 5.10). Success probability and output-state error are analyzed, and preparing C_N|f⟩/‖C_N|f⟩‖ costs O(1/‖C_N|f⟩‖) uses of the circuit.

Main Findings

• Transform cost is polylogarithmic. The block encoding of the NUCT needs Õ(log²(N/ε)) gates and O(log(N/ε)) qubits, with O(1) normalization. The transform itself therefore costs polylogarithmically many gates in N and 1/ε; preparing the output state multiplies this, together with the cost of preparing |f⟩, by O(1/‖C_N|f⟩‖).

• κ is removed by changing what the circuit is asked to compute. Instead of treating the stored m-bit fixed-point nodes τ_j as noisy copies of real nodes t_j, the circuit is analyzed as implementing the matrix F_τ exactly, with the total error split as ‖U_II − F_t‖ ≤ ‖U_II − F_τ‖ + ‖F_τ − F_t‖. The first term involves only rounding the output angle, bounded by K·c_acos·2^{−p}; the second is bounded through Fourier phases as (2π/√3)·N^{3/2}·‖t − τ‖_∞. Consequently m = (3/2)q + O(log(1/ε)) bits per node suffice (with N = 2^q), with no condition on where the nodes sit.

• Prior work's parameter dependence. In the earlier NUQFT, finite-precision node access produced an error term proportional to 1/√(1 − (y_j*)²), defining κ := max_j 1/√(1 − (y_j*)²), and the gate and qubit counts carried terms log(1 + Kκ) — specifically O(n² + L² + log(1 + κL)) gates and O(L + log(1 + κL)) qubits with L := n + log(1/ε). The authors note they could not find a useful bound on κ for NUCT nodes (Appendix B), which motivates the reworking.

• A sharper truncation bound. The paper replaces the Lambert-W rank of prior work with an explicit K = O(log(N/ε)) and bounds the full discarded coefficient sum (over max{ℓ, r} ≥ K), not only the pairs where both indices are at least K. Because the prior bound is entrywise while block encoding needs the operator norm, the prior truncation result must be applied with ε/√N in place of ε.

• Collisions now cost only a square root. Several nodes may round to the same grid point. Classically this is free; quantumly it enters through the normalization O(√d_r) (Lemma 4.2), so the general NUQFT is efficient when d_r = polylog(N). In the worst case d_r = N and the normalization grows to √N. For the NUCT nodes, d_r ≤ 5 is proven, restoring O(1) normalization.

• Improvements summarized in Table 1. Relative to applying the prior NUQFT to the NUCT, the paper reports: no dependence on node geometry (versus log(1 + κL)); improved block-encoding normalization from O(K²√d_r) = O(L²) to √d_r (with Λ < 24√5 listed in the table, where Λ is the total Bessel weight); a collision bound d_r ≤ 5 proven rather than assumed; and explicit circuits for the row-access and coefficient oracles rather than assumptions.

• Extension to arbitrary nodes. The reduction uses only x_k = cos θ_k, so it holds for any nodes x_k ∈ [−1, 1]. Equispacing is used only to build the node oracle, to prove d_r ≤ 5, and to construct the row oracle; for other nodes Theorem 4.7 gives the same construction with normalization O(√d_r) given a node oracle with ‖t − τ‖_∞ ≤ 2^{−m} and row access.

• Outputs are projections, not interpolation coefficients. The NUCT computes c_j = Σ_k f_k T_j(x_k) for j = 0, …, N−1, i.e. ℓ² projections onto sampled Chebyshev polynomials; these are not interpolation coefficients because the polynomials are not orthogonal on an arbitrary grid.

Methodology in Plain English

The starting point is a known classical trick: every non-uniform node sits within half a grid spacing of some uniform grid point, so a non-uniform Fourier transform can be written as a short sum of ordinary Fourier transforms sandwiched between diagonal scalings. Each node's exponential splits into a uniform DFT entry times a correction factor depending only on the small offset from the nearest grid point. That correction factor is smooth, so it is expanded in Chebyshev polynomials via the Jacobi–Anger/Bessel expansion and truncated at rank K, whose coefficients decay faster than any geometric sequence. Quantumly, each term of the resulting sum is a product of block encodings (frequency diagonal, QFT, node-to-grid-point map, node diagonal), and the terms are combined with a linear combination of unitaries.

The new ingredient is bookkeeping. Rather than pretending the circuit knows the exact real nodes, the authors let the circuit implement the transform built from the stored fixed-point nodes, and then separately bound the difference between the stored-node and real-node matrices. This matters because the earlier analysis pushed node-rounding error through arccos, whose derivative 1/√(1 − y²) is singular at ±1 — the origin of κ. In the new analysis the arccos circuit receives exactly the same fixed-point offset that the target matrix is defined on, so the only error is the rounding of the output angle, which is uniform in the node. The node approximation error is instead accounted for in the Fourier phases. The authors also fix a boundary issue in prior work where the offset was formed from the wrapped index, placing nodes within 1/(2N) of t = 1 outside the arccos domain.

Why This Matters

Impact on research. The result makes the cost of a quantum non-uniform Fourier/Chebyshev transform depend on the problem size and target accuracy, not on incidental node geometry. It removes a parameter whose control was instance-dependent — certifying a bound on κ amounts to lower-bounding the distance of every scaled node Nt_j from a half-integer. It also supplies explicit oracle circuits where earlier work assumed row access, which matters for end-to-end complexity claims.

Potential applications (as motivated in the paper):

• Spectral methods for differential equations and numerical software for computing with functions, where Chebyshev coefficients decay rapidly for smooth functions.
• Quantum routines that embed, learn, or sample from distributions, where the Chebyshev transform converts sampled values into expansion coefficients.
• The first stage of the O(N log² N) polynomial-transform framework of Driscoll, Healy, and Rockmore, which uses three-term recurrences to reach other orthogonal families such as Hahn polynomials; the authors note Chebyshev polynomials are much better conditioned than monomials on a uniform grid.
• Fourier/cosine-type signal analysis on grids that are uniform in the variable of interest but non-uniform in angle.

Industry relevance. The work targets quantum numerical computing and simulation toolchains: any application that needs to load a classical function into a quantum state, or to move between sample space and coefficient space, benefits from a transform whose gate count is polylogarithmic and whose error does not depend on grid details.

Future Directions

• Extending beyond the first stage. The authors explicitly leave the extension from the NUCT to general polynomial families satisfying a three-term recurrence (the rest of the O(N log² N) framework) for future work.
• Arbitrary node sets. The reduction already holds for any x_k ∈ [−1, 1], but the explicit node/row oracles and the d_r ≤ 5 bound use equispacing; other grids require a node oracle with ‖t − τ‖_∞ ≤ 2^{−m} and row access, and inherit normalization O(√d_r).
• Collision-heavy node sets. The general NUQFT is efficient only when d_r = polylog(N); the worst case d_r = N pushes normalization to √N, so better handling of many-to-one node-to-grid mappings is an open cost question.
• State-preparation overhead. The factor O(1/‖C_N|f⟩‖) in preparing the output state is set by the input rather than the node geometry; how this behaves across input classes is left to the end-to-end analysis rather than resolved.

Target Audience

Quantum algorithms researchers working on block encodings, quantum numerical linear algebra, and QFT-based transforms; numerical analysts interested in quantum implementations of fast polynomial and non-uniform Fourier transforms; and graduate students with background in quantum computing and approximation theory who want a worked example of turning a classical low-rank NUFFT into a rigorous, oracle-explicit quantum circuit with end-to-end error accounting.

Authors’ abstract

We present an efficient quantum algorithm for the non-uniform Chebyshev transform. It is defined as the projection of a function onto Chebyshev polynomials sampled at given nodes that are uniform in $x\in[-1,1]$, and hence non-uniform in the angle $θ=\arccos x$, a setting that QFT-based quantum Chebyshev transforms cannot handle. Our construction is based on an improvement of an existing Non-uniform Quantum Fourier Transform (NUQFT) whereby we remove the conditioning from non-uniform node sampling. Hence, error bounds are independent of the geometry-dependent parameter $κ$ of prior work. We use the fact that Chebyshev transform matrix is the average of two Type-II non-uniform DFTs, which we implement with a single controlled NUQFT circuit. We provide explicit oracle constructions, including the row-access oracle previously left as an assumption. The resulting $\varepsilon$-accurate block encoding has $O(1)$ normalization and uses $O(L)$ qubits and $\widetilde O(L^2)$ gates, where $L=\log N+\log(1/\varepsilon)$. We give an end-to-end implementation with complexity analysis, including the success probability and output-state error.