arXiv:2610.03581
Quantum algorithms for orthogonal polynomial transforms
Anupam Prakash, Shree Hari Sureshbabu, Dylan Herman, Shouvanik Chakrabarti
Abstract
A quantum orthogonal polynomial transform (QOPT) is an algorithmic primitive that maps a superposition of standard basis states $\sum_k α_{k} \ket{k}$ coherently to a basis of normalized univariate polynomials orthogonal with respect to a probability measure $μ(x)$. We provide new discrete and continuous QOPTs for polynomial families in the Askey scheme extending the results for the quantum Hermite transform (Jain et al., STOC'26). Our efficient QOPT algorithms require time $O(\text{polylog}(N, 1/ε))$, where $N$ is the grid size and $ε$ is the error, for the discrete Charlier, Meixner and Krawtchouk transforms and for the integer-order Laguerre transform in the continuous setting. The efficient QOPTs are obtained by uncovering the links between Askey scheme polynomials and Gaussian quantum optical gates and developing a compilation framework for $SU(2)$ and $SU(1,1)$ optical gates on Cartesian grids extending the framework developed by Iyer et al. (arXiv:2602.15180). Further, we reduce the continuous Jacobi transform to the discrete Hahn transform and provide an $O\!\left(N\operatorname{polylog}((N+α+β+1)/ε)\right)$-time Hahn transform, a quadratic speedup over the naive implementation. This is based on a more efficient compilation of the Clebsch--Gordan transform for coupling $\mathrm{SU}(2)$ representations with spins $(j_{1}, j_{2})$. Finally, we develop a new framework for Laguerre transforms for all orders $ν>0$ by fast-forwarding the corresponding radial oscillator using a 3-term chirp decomposition and an efficient algorithm for the Quantum Hankel Transform on a logarithmic grid.
AI Summary
The paper asks which orthogonal-polynomial basis changes admit quantum circuits with complexity polylogarithmic in dimension and inverse error. It defines a quantum orthogonal polynomial transform as a coherent map from degree labels to states with amplitudes proportional to orthonormal polynomials times the square root of their orthogonality measure. The constructions connect Askey-scheme families to oscillator representations of the Heisenberg–Weyl group, $SU(2)$ and $SU(1,1)$. Displacements, beam splitters and squeezing implement Charlier, Krawtchouk and integer-parameter Meixner transforms, respectively. For fixed distribution parameters, their gate complexities are $\operatorname{polylog}(N,1/\epsilon)$. An integer-order Laguerre transform has the same scaling, producing states embedded on a two-dimensional Cartesian grid through circular-mode conversion and quantum Hermite transforms. The digital compilation analysis extends earlier Gaussian-optics methods to squeezing and controls leakage and discretization error in operator norm. For nonnegative integer $\alpha,\beta$, the Hahn transform uses $O(N\operatorname{polylog}((N+\alpha+\beta+1)/\epsilon))$ gates and $O(N+\operatorname{polylog}((N+\alpha+\beta+1)/\epsilon))$ qubits. It identifies Hahn coefficients with a fixed-magnetic-number Clebsch–Gordan block and implements coupling and Racah recoupling cascades. This improves on naive quadratic synthesis, but is not polylogarithmic. Restricted Jacobi transforms reduce to Hahn transforms, with efficient angular-label extraction remaining another bottleneck. A further framework targets noninteger Laguerre orders using radial-oscillator fast-forwarding, a three-chirp decomposition and a Hankel transform on a logarithmic grid. Continuous transforms require specified grids and energy cutoffs. Applications to PDEs and quadrature, polylogarithmic Hahn/Jacobi transforms, and several higher Askey families remain open.
Error found: The Meixner construction establishes only positive integer beta=|q|+1, a restriction absent from the abstract's unqualified description. The introductory Charlier gate bound omits dimension dependence that is present through log N in the detailed theorem and its implementation. The Charlier algorithm uses exp(−i sqrt(mu) p) where its oscillator conventions require exp(−i sqrt(2mu) p), implementing the wrong Poisson parameter. Conjugating the explicitly defined two-mode squeeze by the Cartesian-to-circular basis change in the Meixner algorithm leaves the arithmetic embedding's fixed-number-difference sector and prevents the claimed auxiliary-register cleanup.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.