arXiv:2609.40277
Conditioning-Free Non-Uniform Quantum Fourier and Chebyshev Transforms
Chaowen Guan, Akshit Katiyar
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.
AI Summary
The paper considers quantum implementation of the sampled Chebyshev transform $c_j=\sum_k f_kT_j(x_k)$ on equispaced nodes $x_k=-1+2k/N$, where $N=2^n$. Unlike Chebyshev-root sampling, these nodes become nonuniform under $\theta=\arccos x$, so the transform is nonunitary and is implemented through a block encoding. The construction revises an existing low-rank nonuniform quantum Fourier transform (NUQFT). It removes an auxiliary parameter $\kappa$ arising from propagating node-rounding errors through $\arccos$: stored fixed-point nodes are instead treated as exact inputs, and their discrepancy from the target nodes is bounded directly through Fourier phases. The resulting node perturbation bound is $\|F_t-F_\tau\|\le(2\pi/\sqrt3)N^{3/2}\|t-\tau\|_\infty$. Chebyshev–Bessel coefficient bounds and a weighted LCU give normalization $O(\sqrt{d_r})$, where $d_r$ counts nodes rounding to one Fourier-grid point. Writing the Chebyshev matrix as the average of two NUDFTs yields an explicit $\varepsilon$-accurate block encoding of $(C_N)_{jk}=T_j(x_k)/\sqrt N$. The paper proves $d_r\le5$ and constructs node, sparse-row-access, and coefficient-preparation circuits. With $L=\log N+\log(1/\varepsilon)$, resources are $O(L)$ qubits and $\widetilde O(L^2)$ arithmetic/controlled-rotation gates, or $\widetilde O(L^3)$ Clifford+$T$ gates; normalization is below $24\sqrt5$. The output contains sampled-polynomial projections, not interpolation coefficients. State preparation additionally depends on input loading and inverse output norm; extensive readout can also dominate. Arbitrary-node extensions require suitable oracles and retain collision dependence. Conversion to general polynomial families is left open.
We used Claude Opus 5.5 for coming up with efficient Oracle constructions, based on standard techniques and help with writing the paper.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.