Conditioning-Free Non-Uniform Quantum Fourier and Chebyshev Transforms

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 $\theta =\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 $\kappa$ 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 $\epsilon$-accurate block encoding has $O(1)$ normalization and uses $O(L)$ qubits and $\tilde{O}(L^2)$ gates, where $L=\log N+\log (1\mathrm{/}\epsilon )$. We give an end-to-end implementation with complexity analysis, including the success probability and output-state error.