Quantum algorithms for orthogonal polynomial transforms
Abstract
A quantum orthogonal polynomial transform (QOPT) is an algorithmic primitive that maps a superposition of standard basis states ∑k αk ketk 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(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 (Npolylog((N+α+β+1)/ε))-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 SU(2) representations with spins (j1, j2). 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.
Related
- Quantum Algorithms for Multivariable Polynomial Transformations: From Efficient Synthesis to Quantum Channel Transformations
- Polynomial Initial-State Jumps and Christoffel Transforms in Krylov Complexity
- Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Separability
- Polynomial-time classical algorithms for mean-field models up to the glass transition
- An Annealing-based Quantum Neural Network with Discrete Wavelet Transforms for Enhanced Air Pollution Nowcasting
BibTeX
@misc{prakash2026quantum,
title = {{Quantum algorithms for orthogonal polynomial transforms}},
author = {Anupam Prakash and Shree Hari Sureshbabu and Dylan Herman and Shouvanik Chakrabarti},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03581},
eprint = {2610.03581},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03581},
}
RIS
TY - UNPB
TI - Quantum algorithms for orthogonal polynomial transforms
AU - Anupam Prakash
AU - Shree Hari Sureshbabu
AU - Dylan Herman
AU - Shouvanik Chakrabarti
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03581
UR - https://arxiv.org/abs/2610.03581
AB - A quantum orthogonal polynomial transform (QOPT) is an algorithmic primitive that maps a superposition of standard basis states ∑_k α_k ketk 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(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 (Npolylog((N+α+β+1)/ε))-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 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.
ER -