Efficient quantum transform handles non uniform Chebyshev nodes without conditioning
Conditioning-Free Non-Uniform Quantum Fourier and Chebyshev Transforms
Data Structures and Algorithms
Summary
Some mathematical operations used in quantum computing work well with evenly spaced points but struggle when points are unevenly spaced. The paper introduces a new quantum algorithm that projects functions onto Chebyshev polynomials sampled at points that are uniform in one variable but not in another, a case that previous methods couldn't manage efficiently. The authors improve a quantum Fourier transform for uneven points by removing a conditioning step that made errors depend on tricky geometric factors. Their method uses fewer resources and provides explicit instructions for implementing the transform on a quantum computer.
What this means in practice
- •For quantum software engineers: Implement precise quantum transforms on unevenly spaced data points with predictable error and resource costs.
- •For signal processing developers: Apply improved quantum algorithms for transforms where data samples come from non-uniform grids, enabling new types of efficient analysis.
Authors
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.