Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.20739

Efficient Non-Uniform Quantum Hermite Transform through Adaptive Sampling

Nitay Mayo, Aryeh Lev Zabokritskiy

quant-phcs.DCcs.ETSubmitted Sep 17, 2026• Announced Sep 18, 2026• 0 citations• Revised Oct 5, 2026 (v2)
v1 · Sep 17, 2026v2 · Oct 5, 2026
arXivHTMLPDF

Abstract

On the span of the first $N$ oscillator modes, Gauss--Hermite quadrature gives an exact change of basis between mode coefficients and $N$ weighted position space samples. We implement this transform with $O(N\operatorname{polylog}(N,1/\varepsilon))$ logical gates and polylogarithmic quantum width. The operator-error bound $\varepsilon$ holds on arbitrary superpositions and includes all auxiliary registers. The construction uses signed averages on adaptive windows to convert uniform-grid samples into weighted Hermite-root samples. Their varying widths control the amplification cost, giving the near-linear bound.

AI Summary

The paper asks how efficiently a quantum circuit can implement the finite Hermite transform: the exact change of basis between the first $N$ harmonic-oscillator modes and $N$ weighted samples at Gauss–Hermite roots. Quadrature makes this sampling map unitary on the retained mode space; the encoded amplitudes are weighted samples, not raw position values. For $N=2^n$ and $0<\varepsilon\leq1/2$, it constructs a Clifford+$T$ circuit using $O(N\operatorname{polylog}(N,1/\varepsilon))$ logical gates and $\operatorname{polylog}(N,1/\varepsilon)$ qubits. The operator-norm error bound includes all auxiliary registers, fixes phases, and holds for arbitrary superpositions and external reference systems. Reversing the circuit implements the inverse transform with the same resources. The construction converts an existing coherent uniform-grid Hermite sampler into weighted root samples using signed Legendre-kernel averages over disjoint windows. Window radii follow local root spacing, including near the spectral edges. Christoffel-weight estimates and complex Mehler bounds control normalization and approximation error. Kernel degree $d=O(\log(N/\varepsilon))$ and polynomial grid size suffice; block encoding and coherent amplification produce the clean transform. Harmonic-oscillator evolution and fractional Fourier rotation follow by conjugating diagonal mode phases. The resource bounds exclude input loading, full classical readout, and polynomial-time classical certification and compilation. Numerical constants, optimized gate counts, and hardware performance are not supplied. Inputs outside the retained space incur separate truncation and sampled-tail aliasing errors; small $L^2$ truncation error alone does not control aliasing. The oscillator examples and proposed noise diagnostic use ideal dense transforms, not compiled circuits or hardware experiments.

Little sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
30 pages, including supplementary material. Minor corrections to notation and exposition; improved figure legibility and ancillary documentation. Results unchanged

Related papers

Efficient Non-Uniform Quantum Hermite Transform through Adaptive Sampling — E8 Intelligence Research

Andrew Stewart Caldin

On the span of the first $N$ oscillator modes, Gauss--Hermite quadrature gives an exact change of basis between mode coefficients and $N$ weighted position space samples. We implement this transform with $O(N\operatorname{polylog}(N,1/\varepsilon))$ logical gates and polylogarithmic quantum width. The operator-error bound $\varepsilon$ holds on arbitrary superpositions and includes all auxiliary registers. The construction uses signed averages on adaptive windows to convert uniform-grid samples into weighted Hermite-root samples. Their varying widths control the amplification cost, giving the near-linear bound. Source: http://arxiv.org/abs/2609.20739v1 (arXiv:2609.20739v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Nov 7, 2026•0 citations

Conditioning-Free Non-Uniform Quantum Fourier and Chebyshev Transforms

Chaowen Guan, Akshit Katiyar

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.

quant-pharXiv:2609.40277•Oct 1, 2026•0 citations

Non-Uniform Quantum Fourier Transform

Junaid Aftab, Yuehaw Khoo, Haizhao Yang

The Discrete Fourier Transform (DFT) is central to the analysis of uniformly sampled signals, yet many practical applications involve non-uniform sampling, requiring the Non-Uniform Discrete Fourier Transform (NUDFT). While quantum algorithms for the standard DFT are well established, a corresponding framework for the non-uniform case remains underdeveloped. This work introduces a quantum algorithm for the Non-Uniform Quantum Fourier Transform (NUQFT) based on a low-rank factorization of the NUDFT matrix. The factorization is translated into an explicit quantum construction using block encodings, Quantum Signal Processing, and the Linear Combination of Unitaries framework, yielding an $ε$-accurate block encoding of the NUDFT matrix with controlled approximation error from both classical truncation and quantum implementation. Under standard oracle access assumptions for non-uniform sampling points, we derive explicit, non-asymptotic gate-level resource estimates. The resulting complexity scales polylogarithmically with target precision, quadratically with the number of qubits through the quantum Fourier transform, and logarithmically with a geometry-dependent conditioning parameter induced by the non-uniform grid. This establishes a concrete and resource-efficient quantum analogue of the NUDFT and provides a foundation for quantum algorithms on irregularly sampled data.

quant-pharXiv:2602.13472•Feb 17, 2026•1 citation

Efficient Quantum Hermite Transform

Siddhartha Jain, Vishnu Iyer, Rolando D. Somma +2 more

We present a new primitive for quantum algorithms that implements a discrete Hermite transform efficiently, in time that is polylogarithmic in the dimension and the inverse of the allowable error. This transform, which maps basis states to states whose amplitudes are proportional to the Hermite functions, can be interpreted as the Gaussian analogue of the Fourier transform. Our algorithm is based on a method to exponentially fast-forward the evolution of the quantum harmonic oscillator, giving a simulation algorithm with nearly optimal circuit complexity for a fundamental Hamiltonian more than four decades after Feynman posed the simulation of quantum physics as an application of quantum computers.

arXiv:2510.04929•ACM Symposium on Theory of Computing (STOC)•Jun 9, 2026•16 citations

Quantum algorithms for orthogonal polynomial transforms

Anupam Prakash, Shree Hari Sureshbabu, Dylan Herman +1 more

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.

quant-pharXiv:2610.03581•Oct 5, 2026•1 citation

Efficient Qubit Simulation of Hybrid Oscillator-Qubit Quantum Computation

Xi Lu, Bojko N. Bakalov, Yuan Liu

We introduce a framework for simulating hybrid oscillator-qubit quantum processors on qubit-only systems through position encoding. By encoding continuous-variable position and momentum wave functions into qubit amplitudes, our method efficiently simulates all Gaussian and conditional Gaussian operations -- encompassing the phase-space instruction set (beam splitter, single-qubit rotation, conditional displacement) and extending to squeezing, conditional squeezing, conditional rotation, and conditional beam splitter -- using $O\!\left(\log^2\!\left(Γ+ \log(1/ε)\right)\right)$ qubit gates per hybrid gate, where $Γ$ is the Fock-level bound and $ε$ is the target precision. This polylogarithmic per-gate complexity represents an exponential improvement over Fock basis encoding approaches, which require exponential quantum or classical resources in the number of qubits per mode. We provide rigorous numerical characterization of quantum Fourier transform errors for Fock-bounded states, enabling precise resource estimation for practical implementations. This work establishes that hybrid oscillator-qubit algorithms can be implemented on qubit processors with polynomial overhead, providing new insights into the computational power trade-offs between discrete-variable and hybrid continuous-discrete-variable quantum computing.

quant-pharXiv:2603.09233•Mar 11, 2026•0 citations
On the span of the first NNN oscillator modes, Gauss--Hermite quadrature gives an exact change of basis between mode coefficients and NNN weighted position space samples. We implement this transform with O(Npolylog⁡(N,1/ε))O(N\operatorname{polylog}(N,1/\varepsilon))O(Npolylog(N,1/ε)) logical gates and polylogarithmic quantum width. The operator-error bound ε\varepsilonε holds on arbitrary superpositions and includes all auxiliary registers. The construction uses signed averages on adaptive windows to convert uniform-grid samples into weighted Hermite-root samples. Their varying widths control the amplification cost, giving the near-linear bound.
The paper asks how efficiently a quantum circuit can implement the finite Hermite transform: the exact change of basis between the first NNN harmonic-oscillator modes and NNN weighted samples at Gauss–Hermite roots. Quadrature makes this sampling map unitary on the retained mode space; the encoded amplitudes are weighted samples, not raw position values.
For N=2nN=2^nN=2n and 0<ε≤1/20<\varepsilon\leq1/20<ε≤1/2, it constructs a Clifford+TTT circuit using O(Npolylog⁡(N,1/ε))O(N\operatorname{polylog}(N,1/\varepsilon))O(Npolylog(N,1/ε)) logical gates and polylog⁡(N,1/ε)\operatorname{polylog}(N,1/\varepsilon)polylog(N,1/ε) qubits. The operator-norm error bound includes all auxiliary registers, fixes phases, and holds for arbitrary superpositions and external reference systems. Reversing the circuit implements the inverse transform with the same resources.
The construction converts an existing coherent uniform-grid Hermite sampler into weighted root samples using signed Legendre-kernel averages over disjoint windows. Window radii follow local root spacing, including near the spectral edges. Christoffel-weight estimates and complex Mehler bounds control normalization and approximation error. Kernel degree d=O(log⁡(N/ε))d=O(\log(N/\varepsilon))d=O(log(N/ε)) and polynomial grid size suffice; block encoding and coherent amplification produce the clean transform. Harmonic-oscillator evolution and fractional Fourier rotation follow by conjugating diagonal mode phases.
The resource bounds exclude input loading, full classical readout, and polynomial-time classical certification and compilation. Numerical constants, optimized gate counts, and hardware performance are not supplied. Inputs outside the retained space incur separate truncation and sampled-tail aliasing errors; small L2L^2L2 truncation error alone does not control aliasing. The oscillator examples and proposed noise diagnostic use ideal dense transforms, not compiled circuits or hardware experiments.
On the span of the first NNN oscillator modes, Gauss--Hermite quadrature gives an exact change of basis between mode coefficients and NNN weighted position space samples. We implement this transform with O(Npolylog⁡(N,1/ε))O(N\operatorname{polylog}(N,1/\varepsilon))O(Npolylog(N,1/ε)) logical gates and polylogarithmic quantum width. The operator-error bound ε\varepsilonε holds on arbitrary superpositions and includes all auxiliary registers. The construction uses signed averages on adaptive windows to convert uniform-grid samples into weighted Hermite-root samples. Their varying widths control the amplification cost, giving the near-linear bound. Source: http://arxiv.org/abs/2609.20739v1 (arXiv:2609.20739v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
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∈[−1,1]x\in[-1,1]x∈[−1,1], and hence non-uniform in the angle θ=arccos⁡xθ=\arccos xθ=arccosx, 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)O(1)O(1) normalization and uses O(L)O(L)O(L) qubits and O~(L2)\widetilde O(L^2)O(L2) gates, where L=log⁡N+log⁡(1/ε)L=\log N+\log(1/\varepsilon)L=logN+log(1/ε). We give an end-to-end implementation with complexity analysis, including the success probability and output-state error.
The Discrete Fourier Transform (DFT) is central to the analysis of uniformly sampled signals, yet many practical applications involve non-uniform sampling, requiring the Non-Uniform Discrete Fourier Transform (NUDFT). While quantum algorithms for the standard DFT are well established, a corresponding framework for the non-uniform case remains underdeveloped. This work introduces a quantum algorithm for the Non-Uniform Quantum Fourier Transform (NUQFT) based on a low-rank factorization of the NUDFT matrix. The factorization is translated into an explicit quantum construction using block encodings, Quantum Signal Processing, and the Linear Combination of Unitaries framework, yielding an εεε-accurate block encoding of the NUDFT matrix with controlled approximation error from both classical truncation and quantum implementation. Under standard oracle access assumptions for non-uniform sampling points, we derive explicit, non-asymptotic gate-level resource estimates. The resulting complexity scales polylogarithmically with target precision, quadratically with the number of qubits through the quantum Fourier transform, and logarithmically with a geometry-dependent conditioning parameter induced by the non-uniform grid. This establishes a concrete and resource-efficient quantum analogue of the NUDFT and provides a foundation for quantum algorithms on irregularly sampled data.
We present a new primitive for quantum algorithms that implements a discrete Hermite transform efficiently, in time that is polylogarithmic in the dimension and the inverse of the allowable error. This transform, which maps basis states to states whose amplitudes are proportional to the Hermite functions, can be interpreted as the Gaussian analogue of the Fourier transform. Our algorithm is based on a method to exponentially fast-forward the evolution of the quantum harmonic oscillator, giving a simulation algorithm with nearly optimal circuit complexity for a fundamental Hamiltonian more than four decades after Feynman posed the simulation of quantum physics as an application of quantum computers.
A quantum orthogonal polynomial transform (QOPT) is an algorithmic primitive that maps a superposition of standard basis states ∑kαk∣k⟩\sum_k α_{k} \ket{k}∑k​αk​∣k⟩ coherently to a basis of normalized univariate polynomials orthogonal with respect to a probability measure μ(x)μ(x)μ(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/ε))O(\text{polylog}(N, 1/ε))O(polylog(N,1/ε)), where NNN 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)SU(2)SU(2) and SU(1,1)SU(1,1)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)/ε))O\!\left(N\operatorname{polylog}((N+α+β+1)/ε)\right)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)\mathrm{SU}(2)SU(2) representations with spins (j1,j2)(j_{1}, j_{2})(j1​,j2​). Finally, we develop a new framework for Laguerre transforms for all orders ν>0ν>0ν>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.
We introduce a framework for simulating hybrid oscillator-qubit quantum processors on qubit-only systems through position encoding. By encoding continuous-variable position and momentum wave functions into qubit amplitudes, our method efficiently simulates all Gaussian and conditional Gaussian operations -- encompassing the phase-space instruction set (beam splitter, single-qubit rotation, conditional displacement) and extending to squeezing, conditional squeezing, conditional rotation, and conditional beam splitter -- using O ⁣(log⁡2 ⁣(Γ+log⁡(1/ε)))O\!\left(\log^2\!\left(Γ+ \log(1/ε)\right)\right)O(log2(Γ+log(1/ε))) qubit gates per hybrid gate, where ΓΓΓ is the Fock-level bound and εεε is the target precision. This polylogarithmic per-gate complexity represents an exponential improvement over Fock basis encoding approaches, which require exponential quantum or classical resources in the number of qubits per mode. We provide rigorous numerical characterization of quantum Fourier transform errors for Fock-bounded states, enabling precise resource estimation for practical implementations. This work establishes that hybrid oscillator-qubit algorithms can be implemented on qubit processors with polynomial overhead, providing new insights into the computational power trade-offs between discrete-variable and hybrid continuous-discrete-variable quantum computing.