Efficient Non-Uniform Quantum Hermite Transform through Adaptive Sampling

Nitay Mayo and Aryeh Lev Zabokritskiy (Yohananov) present an efficient non-uniform quantum Hermite transform using adaptive sampling in their September 17, 2026 arXiv paper. The method achieves a near-linear gate complexity of $\tilde{O}(N)$ with polylogarithmic quantum width, improving upon prior quadratic bounds.

The algorithm utilizes Gauss–Hermite quadrature to provide an exact change of basis between mode coefficients and weighted position space samples. By converting uniform-grid samples into weighted Hermite-root samples via signed averages on adaptive windows, the construction controls amplification costs to maintain high precision with minimal resource overhead.

The paper develops a quantum algorithm for a non-uniform Hermite transform on the truncated space spanned by the first \(N\) harmonic-oscillator modes. Its central mathematical observation is that Gauss–Hermite quadrature provides an exact finite-dimensional change of basis between oscillator mode coefficients and \(N\) weighted position-space samples. In other words, within the \(N\)-mode truncation, the position-space data needed to reconstruct or transform a state can be represented by a nonuniform set of quadrature nodes and weights rather than by a dense uniform grid. This ties the quantum transform directly to the natural structure of the Hermite-function basis.

The main algorithmic contribution is an efficient quantum implementation of this transform with near-linear gate complexity: \(O(N\operatorname{polylog}(N,1/\varepsilon))\) logical gates and only polylogarithmic quantum width. The procedure achieves an operator-norm error bounded by \(\varepsilon\) on the truncated \(N\)-mode space, meaning the approximation is uniform over inputs in that subspace. The use of adaptive, nonuniform sampling is what allows the algorithm to avoid the overhead of sampling on a large uniform position grid, replacing it with a quadrature-based representation whose cost scales more favorably with both the mode number \(N\) and the desired precision.

This result matters because many quantum simulation and quantum information tasks involving bosonic modes require efficient movement between Fock/mode representations and position or momentum representations. A near-linear-time, low-width quantum Hermite transform could therefore be a useful subroutine for simulating harmonic systems, vibrational dynamics, field modes, or hybrid bosonic algorithms where both coefficient-space and real-space operations are needed. More broadly, the work illustrates how classical quadrature theory can be converted into efficient quantum signal-processing primitives, yielding algorithms that are both mathematically structured and resource-efficient.