Quantum algorithms speed orthogonal polynomial transformations exponentially
Quantum algorithms for orthogonal polynomial transforms
Data Structures and Algorithms
Summary
The paper addresses how to efficiently convert quantum data into specialized mathematical forms called orthogonal polynomials. These polynomials are useful in many scientific and engineering problems. The authors expand existing quantum algorithms beyond one type to several families of polynomials, speeding up transformations that would normally take much longer. Their approach uses principles from quantum optics and group theory to build these algorithms efficiently.
What this means in practice
- •For quantum algorithm developers: Implement faster quantum subroutines for polynomial basis changes in simulation and signal processing by using new transforms for several important orthogonal polynomial families.
- •For quantum optics engineers: Design optical quantum circuits that realize complex polynomial transforms by leveraging the connection between polynomial families and quantum optical gate operations.
Authors
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.