Conditioning-Free Non-Uniform Quantum Fourier and Chebyshev Transforms

1 Introduction

• QFT-based Chebyshev transforms do not directly handle samples uniform in x, because their angles θ_k = arccos x_k are non-uniform.The QFT-based transform in [WPW+23] uses Chebyshev roots, whose angles are uniformly spaced.Source: §1 · p. 3
• The NUCT computes ℓ2 projections of sampled data onto Chebyshev polynomials, not interpolation coefficients, because the polynomials are not orthogonal on arbitrary grids.The paper focuses on nodes evenly spaced in x, which become non-uniformly spaced in θ = arccos x.Source: §1 · p. 3
• The authors remove κ from NUQFT error bounds by reworking its analysis, since κ depends on an auxiliary arccos evaluation rather than transform conditioning.For the NUCT nodes, they report no useful bound on κ.Source: §1 · p. 4

1.1 Main contributions

• For arbitrary nodes, the NUQFT block encoding has normalization O(√d_r), where d_r bounds how many nodes round to one grid point.The NUCT reduction uses two Type-II NUDFTs, and for equispaced x-nodes the authors show d_r ≤ 5 and construct row access explicitly.Source: §1.1 · pp. 4–5
• The NUCT on N equispaced nodes has an explicit ε-accurate block encoding with normalization O(1), using O(log(N/ε)) qubits and eO(log2(N/ε)) gates.Preparing the normalized output state uses O(1/∥C_N|f⟩∥) circuit calls.Source: §1.1 · p. 5
• The technique extends to arbitrary nodes given a node oracle with the stated precision and row access; equispacing is needed to construct those oracles and bound d_r.The authors leave extensions to other polynomial families for future work.Source: §1 · p. 3, §1.1 · p. 5

• A signed fixed-point number with p fractional bits is represented as a/2^p in two’s-complement form, and shifts, additions, subtractions, and comparisons are exact.The paper calls a register-held fixed-point quantity exact when it has not been rounded.Source: §2 · p. 6
• Real or irrational nodes may first be approximated by fixed-point nodes, with the resulting matrix perturbation accounted for separately from the transform applied to the stored nodes.For stored nodes, the nearest-grid-point and offset split is computed exactly.Source: §2 · p. 6
• Each node is split into its nearest DFT grid point and a scaled offset; the DFT factor depends on the grid point, while the remaining factor depends on the offset.The wrapped index names a DFT column, and the grid-point map determines how many nodes share each point.Source: §2 · p. 6
• The Jacobi–Anger expansion expresses e^(iz cos u) as a Fourier series weighted by Bessel functions J_n(z), whose magnitudes decay super-geometrically in n.That decay supports truncating the expansion.Source: §2 · p. 6
• Reversible CORDIC circuits approximate arccos, sine, and cosine on fixed-point inputs with p fractional bits using O(b+p) qubits and eO(b+p) gates.At z = −1, an endpoint flag can implement T_n(−1) exactly.Source: §2 · p. 7

3 Background on Low-Rank NUFFT and NUQFT

• The paper uses frequencies as rows and nodes as columns, calling the resulting matrix Type-II despite its transpose-relative orientation to [AKY26].Complexity bounds from [AKY26] carry over unchanged because transposition preserves the operator norm.Source: §3 · p. 8

3.1 Low-rank factorization of the NUDFT

• Each node is split into a nearest grid point and an offset, making the NUDFT entry a uniform DFT entry times a correction factor.Rescaling the frequency makes the correction kernel analytic on a bounded domain, so its Chebyshev expansion separates into node- and frequency-dependent terms.Source: §3.1 · pp. 8–9
• The revised truncation analysis bounds the full discarded rectangular tail and gives an explicit K = O(log(N/ε)), rather than a smaller rank.The earlier tail bound omitted terms for which exactly one index is at least K; the improvement is a complete bound with explicit constants, not a smaller rank.Source: §3.1 · p. 9

3.2 The NUQFT circuit and the parameter κ

• The NUQFT combines block encodings of the frequency diagonal, QFT, node-to-grid map, and node diagonal using an LCU.A weighted outer LCU and a node-uniform diagonal bound reduce normalization from O(K^2√dr) to O(√dr), where dr bounds grid-point collisions.Source: §3.2 · pp. 10–11
• The prior NUQFT’s arccos-based precision bound depends on κ, which can grow without bound as scaled nodes approach grid-cell boundaries.κ measures conditioning of the auxiliary arccos evaluation, not conditioning of the NUDFT matrix itself.Source: §3.2 · p. 11
• For nodes near t = 1, the construction forms the offset from the unwrapped index and uses the wrapped index only to select a DFT column.The prior wrapped-index offset could approach 2N, outside arccos’s domain.Source: §3.2 · p. 11

4 Conditioning-Free NUQFT

• Treating the stored m-bit nodes as the transform input separates angle-implementation error from node error, eliminating κ from the bounds even near ±1.The circuit remains essentially that of [AKY26], but its error analysis changes: node error is bounded through Fourier phases rather than arccos.Source: §4 · p. 12
• Theorem 4.7 gives an ε-accurate block encoding of Ft with normalization O(√dr) and eO(m^2 + L^2) gates.The section also proves the needed coefficient bounds and describes the circuit oracles, including row access.Source: §4 · p. 12

4.1 Error analysis of block encoding factors

• The Chebyshev-Bessel expansion has tail error below 24 · 2^-K and total weight Λ below 24, yielding assembled normalization below 24√dr.The weighted outer LCU combines the factors, and the angle precision is chosen so its implementation error is at most ε/2.Source: §4.1 · pp. 14, 17
• The nearest-point matrix has an exact sparse block encoding with normalization √dr, while fixed-point nodes yield an exactly computed offset zj.Exact diagonal inputs leave only finite-precision angle error, so the Chebyshev diagonal bounds do not depend on κ.Source: §4.1 · pp. 14–15

4.2 Oracle assumptions

• The required oracles provide stored nodes and row access to Mσ, while coefficient preparations depend only on K and the window convention, not on the nodes.The coefficient preparation can therefore be built once and reused across transform instances.Source: §4.2 · pp. 17–18
• Coefficient preparations are instance-independent, while node data enter through T_l(z_j) and frequency coordinates through T_r(w_k); transposition leaves the coefficient table unchanged.The same preparations serve the transposed construction; the node and row-access oracles supply the instance-specific information.Source: §4.2 · p. 18

4.3 Conditioning-free NUQFT

• The construction treats stored fixed-point nodes as the exact transform nodes and computes σ_j and z_j exactly from them.The transposed construction uses the same bounds, oracles, and resources.Source: §4.3 · pp. 19, 21
• The conditioning-free Type-II NUQFT block-encodes the transform with normalization O(√dr), given fixed-point nodes and ordered sparse row access with declared row-sparsity bound dr.The theorem assumes N = 2^q and applies for every 0 < ε ≤ 1.Source: §4.3 · p. 19
• The circuit uses O(m + L) qubits and eO(m^2 + L^2) logical gates, where L = q + log(1/ε); when m = O(L), these become O(L) qubits and eO(L^2) gates.Instance-specific node and ordered row-access circuit costs remain separate.Source: §4.3 · pp. 19–20

5.2 Constructing the Oracles

• The two NUDFTs require node access, row access to Mσ, and Bessel-coefficient preparations, which the section constructs explicitly.The row-access construction uses at most sixteen calls each to Oσ and O†σ and needs no lookup table or search.Source: §5.1 · p. 21, §5.2 · p. 22, Row access · p. 23

Node oracle.

• The node oracle approximates tk by evaluating arccos on the exact grid input and rounding once at the end.This is the only arccos evaluation contributing error; the NUQFT's frequency and node-factor evaluations use exact inputs, so κ does not appear.Source: Node oracle · p. 22

Row access.

• Each row of Mσ has at most five consecutive entries, and the row-access oracle is constructed without lookup tables or search.The stated row-access condition is N∥t−τ∥∞ < 1/(2π).Source: Row access · pp. 22–23

5.1 Reduction to two NUDFTs

• A single controlled NUQFT circuit combines the positive- and negative-node branches to implement the average of two NUDFTs.The negative-node circuit is obtained from the positive-node circuit without a second arccos evaluation.Source: Negative nodes · p. 23, §5.3 · p. 24

5.3 Main result

• The transform is implemented as a block encoding using O(L) qubits and eO(L^2) gates, with no parameter depending on node geometry.Synthesizing rotations over Clifford+T gives eO(L^3) gates; the stated counts exclude input preparation and amplitude amplification.Source: §5.3 · pp. 24–25

Then Algorithm 1 succeeds with probability

• Applying the block encoding to |f⟩ succeeds with probability at least (r−ε)^2/α^2 when r > ε, and amplification uses O(α/(r−ε)) circuit applications.The normalized output-state error is relative to r=∥CN|f⟩∥; end-to-end cost can also be dominated by input loading or readout.Source: §5.3 · p. 25, Then Algorithm 1 succeeds with… · p. 26

6 Conclusion and Discussion

• Removing κ lets the NUQFT complexity be stated in advance for any node set, with remaining geometric dependence through the collision count dr.The total Bessel weight is bounded by a constant, so normalization does not depend on truncation rank.Source: §6 · p. 26
• The transform acts directly on uniformly sampled data and returns projections onto sampled Chebyshev polynomials, not interpolation coefficients.Recovering interpolation coefficients on equispaced nodes is exponentially ill-conditioned; end-to-end speedup also depends on input preparation, output norm, and readout.Source: §6 · p. 26
• Whether the remaining recurrence-based stages can achieve polylogarithmic cost remains an open question.Other non-uniform node families require bounding dr and constructing the row oracle.Source: §6 · p. 26

A Oracle constructions

• The appendix gives circuits and proofs for the oracles introduced in Section 5.2.Source: A Oracle constructions · p. 28

A.1 Node oracle

• The oracle maps each index k to an m-bit approximation τk of arccos(xk)/(2π), rounding the scaled angle to m fractional bits.It computes the signed grid value, evaluates arccos, scales by 1/(2π), clips to [0, 1/2], and writes the result.Source: §A.1 · p. 28
• The oracle uses O(m) qubits and eO(m^2) gates, with depth eO(m).The construction uses working precision w=m+g for constant guard-bit count g.Source: §A.1 · p. 28
• Choosing m according to the target accuracy bounds the node error and ensures N∥t−τ∥∞ < 1/(2π).The error analysis accounts for approximate arccos evaluation, multiplication by the stored 1/(2π), and rounding before the final m-bit rounding.Source: §A.1 · p. 29

A.2 Row access

• The bound d_r = 5 counts nodes per grid point and is unchanged whether M_σ or its transpose is used.Numerically, the largest multiplicity is 3 for N ≤ 64 and 4 for 128 ≤ N ≤ 218.Source: §A.2 · p. 29
• Each nonempty row’s columns are consecutive, and the search window contains at most five integers.Rows ℓ > N/2 are empty; the bound of five is attained for N = 8 and ℓ = 2.Source: §A.2 · p. 29
• The oracle finds row entries by testing eight candidate columns derived from an approximation to a_ℓ, then records the smallest valid column and the row’s size.It substitutes index 0 for out-of-range oracle queries and sets f_ℓ = d_ℓ = 0 for empty rows.Source: §A.2 · pp. 29–30
• For each slot, the construction returns f_ℓ + r when r < d_ℓ and the padding value N + r otherwise.Two passes use sixteen calls each to O_σ and O_σ†; the stated cost is Õ(m²) per call plus O(q)-bit candidate and shift arithmetic.Source: §A.2 · p. 30

A.3 Negative nodes

• A negative node is assigned to row ℓ exactly when its positive counterpart is assigned to row (−ℓ) mod N.The argument uses τ_k > 0, so (−τ_k) mod 1 = 1 − τ_k.Source: §A.3 · p. 30
• Lemma 4.2 and Theorem 4.7 apply to τ directly except at a nearest-integer tie, where either choice is valid.Their use of the nearest integer relies on Nτ_k = s_k^unw + z_k/2 with integer s_k^unw and z_k ∈ [−1, 1].Source: §A.3 · p. 30

A.4 Coefficient preparation

• The nonnegative-amplitude preparation uses uniformly controlled R_y rotations, and implementing S rotations with error η gives circuit error at most Sη.No phase-equalizing R_z rotations are needed in this case.Source: §A.4 · p. 31
• The controlled coefficient-preparation family uses O(K²) gates, with angle precision chosen so the encoded-matrix error is O(ε_prep).The controlled cascade has O(K²) rotations and CNOTs; angle errors O(2^-bα) yield encoded error O(αK²2^-bα).Source: §A.4 · p. 31
• The outer states and their controlled rotation are prepared with O(K) gates, with angle precision setting the selected-block error.Angle errors O(2^-b_out) give encoded-matrix error O(Kα_unif2^-b_out).Source: §A.4 · p. 31

B Why κ cannot be bounded for the NUCT nodes

• For the NUCT nodes, κ has no known closed form or polynomial-in-N bound; heuristic fractional-part estimates do not give a bound valid for every N.Near x = 0, the linearized question concerns how multiples of 1/π approximate half-integers; away from zero, the dependence is nonlinear.Source: B Why κ cannot be bounded for the NUCT… · pp. 31–32
• κ depends on the distance δ_N of offsets to cell boundaries, and controlling it also requires precision m ≥ q + 2 + log2(1/δ_N).The auxiliary arccos derivative is singular at ±1, so admissible nodes near a cell boundary can make κ arbitrarily large; the condition on m is needed for the stated bound.Source: B Why κ cannot be bounded for the NUCT… · p. 32
• κ is small exactly when no grid point x_k lies close to a zero of T_(N/2), and the paper’s best bound uses the nonzero polynomial values at those points.The polynomial argument gives |T_(N/2)(x_k)| ≥ 2^−((q−1)N/2).Source: B Why κ cannot be bounded for the NUCT… · p. 32
• The best bound obtained yields O(N log N) qubits and gates under the prior cost estimate, removing the exponential speedup.Source: B Why κ cannot be bounded for the NUCT… · p. 32
• The numerical values are irregular: Nδ_N ranges from 0.055 to 5.2, and κ_0 is non-monotone, with an outlier δ_N ≈ 5.2 × 10^-8 at q = 20.The reported values were computed in double precision and checked with 50-digit arithmetic for q ≤ 12 and for the q = 20 minimizer.Source: B Why κ cannot be bounded for the NUCT… · p. 32
• The revised Theorem 4.7 analysis needs no δ_N because arccos evaluations use exact inputs and node error affects only nonsingular Fourier phases.This is why the NUCT complexity is explicit.Source: B Why κ cannot be bounded for the NUCT… · p. 33

C Uniform and weighted outer LCU constructions

• The weighted selector cancels each branch’s λ_r, giving normalization √(d_rΛ) = O(√d_r), while the uniform LCU pads branches and incurs an additional factor K.Both alternatives combine the K component block encodings Ar = DvrFMσDur, whose normalizations are βr = √(d_rλ_r).Source: C Uniform and weighted outer LCU… · p. 33
• Theorem 4.7 uses only the weighted alternative; the uniform outer LCU is retained for comparison, and the two constructions are never applied simultaneously.Source: C Uniform and weighted outer LCU… · p. 33
• The constant-mass estimate and weighted selector independently remove one factor of K; the constant-mass estimate improves normalization but is not needed to remove κ.With d_r ≤ 5, the respective proved bounds are O(K^2), O(K), and O(1) for the source-level, uniform, and weighted constructions.Source: C Uniform and weighted outer LCU… · p. 33
• For the NUCT with d_r ≤ 5, the proved normalization bounds are O(K^2) for the source-level construction, O(K) for the uniform construction, and O(1) for the weighted construction.These are upper-bound comparisons, not a lower bound on what the original NUQFT architecture can achieve.Source: C Uniform and weighted outer LCU… · p. 33
• The weighted construction improves postselection success probability by K^2 and reduces amplitude-amplification overhead by K = O(q + log(1/ε)).The improvement carries over to coherent output-state preparation and applications that repeatedly invoke the transform block encoding.Source: C Uniform and weighted outer LCU… · p. 34