Conditioning-Free Non-Uniform Quantum Fourier and Chebyshev Transforms

Problem Statement

The paper addresses the challenge of efficiently computing the Non-Uniform Chebyshev Transform (NUCT) on a quantum computer. The NUCT maps a function $f$ defined on equispaced nodes $x_k \in [-1, 1]$ to its projection onto Chebyshev polynomials $T_j(x)$.

• The Difficulty: While the classical Discrete Chebyshev Transform on Chebyshev nodes (which are non-uniform in $x$ but uniform in the angle $\theta = \arccos x$) reduces to a standard Discrete Fourier Transform (DFT), the NUCT on equispaced $x$ nodes corresponds to a DFT at non-uniform angles $\theta_k = \arccos(x_k)$.
• Prior Limitations: Previous quantum approaches, such as the Non-Uniform Quantum Fourier Transform (NUQFT) by [AKY26], rely on a low-rank factorization of the transform matrix. However, the error bounds of these existing methods depend on a geometry-dependent parameter $\kappa$, defined as the maximum of $1/\sqrt{1-(y^*)^2}$ where $y^*$ is an intermediate point in the mean-value theorem applied to the $\arccos$ function. For nodes near the grid boundaries (where $y^* \to \pm 1$), $\kappa$ can become arbitrarily large, potentially destroying the efficiency guarantees of the algorithm. Additionally, prior works often assumed the existence of "row-access oracles" for the underlying sparse matrices without explicit construction.

Methodology

The authors propose a Conditioning-Free NUQFT and apply it to the NUCT through the following methodological steps:

1. Exact Fixed-Point Treatment: Instead of treating stored node values as noisy approximations of real numbers, the algorithm treats the $m$-bit fixed-point representations $\tau_k$ as the exact input nodes for the transform. The transform matrix $F_\tau$ is constructed from these exact stored values.
2. Error Decomposition: The total error is split into two independent components:
   • Implementation Error: The difference between the implemented circuit and the transform on the stored nodes ($F_\tau$).
   • Node Error: The difference between the transform on the stored nodes ($F_\tau$) and the target real nodes ($F_t$).
3. Removing $\kappa$:
   • In the implementation error analysis, the algorithm computes $\arccos$ on the exact stored offset $z_j$. Since the input to $\arccos$ is exact, the error arises only from the output angle rounding. This avoids the unbounded derivative of $\arccos$ at $\pm 1$ acting on an input error, thereby eliminating the dependence on $\kappa$.
   • The node error is bounded separately by analyzing the sensitivity of the Fourier phases to node perturbations, yielding a bound proportional to $\|t - \tau\|_\infty$ without geometric singularities.
4. Low-Rank Factorization & LCU: The NUCT matrix is reduced to the average of two Type-II Non-Uniform DFTs (NUDFTs). Each NUDFT is approximated via a low-rank Chebyshev-Bessel expansion (rank $K$). The authors implement this using a Linear Combination of Unitaries (LCU) with a weighted outer state, which improves the normalization factor compared to uniform LCU approaches.
5. Explicit Oracle Construction: The paper provides explicit quantum circuits for:
   • Node Oracle ($O_\tau$): Computes $m$-bit approximations of $\arccos(x_k)$ reversibly.
   • Row-Access Oracle ($O_r$): Exploits the specific structure of NUCT nodes (where at most 5 nodes map to the same grid point and indices are consecutive) to provide sparse row access without lookup tables.
   • Coefficient Preparation: Constructs the Bessel-function coefficients classically and loads them into quantum states, proving these are instance-independent.

Key Contributions

1. Conditioning-Free NUQFT: The primary theoretical contribution is a modified NUQFT algorithm (Theorem 4.7) where the error bounds and resource requirements are independent of the geometry parameter $\kappa$. The error depends only on the number of bits per node ($m$), the target accuracy ($\epsilon$), and the row sparsity ($d_r$).
2. Improved Normalization: By utilizing a weighted outer LCU and tighter bounds on the total Bessel weight ($\Lambda < 24$), the authors achieve a block encoding normalization of $O(\sqrt{d_r})$. For the NUCT, where $d_r \le 5$, this results in an $O(1)$ normalization, a significant improvement over the $O(K^2\sqrt{d_r})$ or $O(K\sqrt{d_r})$ scaling of prior methods.
3. Explicit Oracle Constructions: The paper removes the assumption of pre-existing oracles by providing explicit, efficient quantum circuits for node generation and row access specifically tailored to the equispaced Chebyshev setting.
4. End-to-End NUCT Algorithm: The authors present a complete quantum circuit (Algorithm 2) for the NUCT, including a rigorous complexity analysis covering qubit count, gate depth, and success probability.

Results

The paper establishes the following complexity results for the NUCT with $N=2^q$ nodes and target accuracy $\epsilon$:

• Qubit Complexity: $O(L)$ qubits, where $L = q + \log(1/\epsilon)$.
• Gate Complexity: $\tilde{O}(L^2)$ logical gates (reversible arithmetic, Clifford, Toffoli, controlled rotations). When synthesized into Clifford+T gates, the complexity is $\tilde{O}(L^3)$.
• Normalization: $O(1)$ (specifically bounded by $24\sqrt{5}$).
• Accuracy: The algorithm produces an $\epsilon$-accurate block encoding of the NUCT matrix.
• Output State: Given an input state $|f\rangle$, the algorithm prepares a state approximating the normalized output $C_N|f\rangle / \|C_N|f\rangle\|$ with error $O(\epsilon / (r-\epsilon))$, where $r = \|C_N|f\rangle\|$. The number of amplitude amplification rounds required is $O(1/(r-\epsilon))$.

Significance and Claims

The authors claim that this work provides the first efficient, conditioning-free quantum algorithm for the non-uniform Chebyshev transform on equispaced nodes.

• Exponential Speedup: The classical algorithm for this transform (by Driscoll, Healy, and Rockmore [DHR97]) requires $O(N \log^2 N)$ operations. The proposed quantum algorithm is polylogarithmic in $N$ ($\tilde{O}(\log^2 N)$), offering an exponential speedup for the transform itself.
• Foundation for General Transforms: The authors position the NUCT as a critical building block for implementing the full pipeline of [DHR97], which computes discrete polynomial transforms for general orthogonal polynomial families using a divide-and-conquer approach based on three-term recurrences.
• Robustness: By removing the dependence on $\kappa$, the algorithm is robust for any node distribution, including those where nodes are arbitrarily close to grid boundaries, a scenario where previous methods would fail or require unproven assumptions about node placement.

The paper concludes by noting that while the transform itself is exponentially faster, the end-to-end speedup for practical applications depends on the cost of input state preparation, the norm of the output, and the number of output coefficients required. Future work aims to extend these techniques to general orthogonal polynomial families.