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.40277

Conditioning-Free Non-Uniform Quantum Fourier and Chebyshev Transforms

Chaowen Guan, Akshit Katiyar

quant-phcs.DSSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations• Revised Oct 6, 2026 (v2)
v1 · Sep 30, 2026v2 · Oct 6, 2026
arXivHTMLPDF

Abstract

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.

AI Summary

The paper considers quantum implementation of the sampled Chebyshev transform $c_j=\sum_k f_kT_j(x_k)$ on equispaced nodes $x_k=-1+2k/N$, where $N=2^n$. Unlike Chebyshev-root sampling, these nodes become nonuniform under $\theta=\arccos x$, so the transform is nonunitary and is implemented through a block encoding. The construction revises an existing low-rank nonuniform quantum Fourier transform (NUQFT). It removes an auxiliary parameter $\kappa$ arising from propagating node-rounding errors through $\arccos$: stored fixed-point nodes are instead treated as exact inputs, and their discrepancy from the target nodes is bounded directly through Fourier phases. The resulting node perturbation bound is $\|F_t-F_\tau\|\le(2\pi/\sqrt3)N^{3/2}\|t-\tau\|_\infty$. Chebyshev–Bessel coefficient bounds and a weighted LCU give normalization $O(\sqrt{d_r})$, where $d_r$ counts nodes rounding to one Fourier-grid point. Writing the Chebyshev matrix as the average of two NUDFTs yields an explicit $\varepsilon$-accurate block encoding of $(C_N)_{jk}=T_j(x_k)/\sqrt N$. The paper proves $d_r\le5$ and constructs node, sparse-row-access, and coefficient-preparation circuits. With $L=\log N+\log(1/\varepsilon)$, resources are $O(L)$ qubits and $\widetilde O(L^2)$ arithmetic/controlled-rotation gates, or $\widetilde O(L^3)$ Clifford+$T$ gates; normalization is below $24\sqrt5$. The output contains sampled-polynomial projections, not interpolation coefficients. State preparation additionally depends on input loading and inverse output norm; extensive readout can also dominate. Arbitrary-node extensions require suitable oracles and retain collision dependence. Conversion to general polynomial families is left open.

Little sign of AI-generated textAI use disclosedIncremental
We used Claude Opus 5.5 for coming up with efficient Oracle constructions, based on standard techniques and help with writing the paper.

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

Related papers

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

Quantum Eigenvalue Processing

Guang Hao Low, Yuan Su

Many problems in linear algebra-such as those arising from non-Hermitian physics, transcorrelated quantum chemistry and differential equations-can be solved on a quan-tum computer by processing eigenvalues of the non-normal input matrices. However, the existing Quantum Singular Value Transformation (QSVT) framework is ill-suited to this task, as eigenvalues and singular values are different in general. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary polynomial transformations on eigenvalues of block-encoded non-normal operators, and a related Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra. QEVT has query complexity to the block encoding nearly recovering that of the QSVT for a Hermitian input, and QEVE achieves the Heisenberg-limited scaling for diagonalizable input matrices. As applications, we develop a linear differential equation solver with strictly linear time query complexity for average-case diagonalizable operators, as well as a ground state preparation algorithm that upgrades previous nearly optimal results for Hermitian Hamiltonians to diagonalizable matrices with real spectra. Underpinning our algorithms is an efficient method to prepare a quantum super-position of Faber polynomials, which generalize the nearly-best uniform approximation properties of Chebyshev polynomials to the complex plane. Of independent interest, we also develop techniques to generate$n$Fourier coefficients with 0 (poly log ($n$)) gates compared to prior approaches with linear cost.

Annual Symposium on Foundations of Computer Science•Oct 27, 2024•22 citations

Quantum Eigenvalue Processing

Guang Hao Low, Yuan Su

Abstract. Many problems in linear algebra—such as those arising from non-Hermitian physics, transcorrelated quantum chemistry, and differential equations—can be solved on a quantum computer by processing eigenvalues of the non-normal input matrices. However, the existing Quantum Singular Value Transformation (QSVT) framework is ill-suited for this task because eigenvalues and singular values are different in general. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary polynomial transformations on eigenvalues of block-encoded non-normal operators and a related Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra. QEVT has query complexity to the block encoding nearly recovering that of the QSVT for a Hermitian input, and QEVE achieves the Heisenberg-limited scaling for diagonalizable input matrices. As applications, we develop a linear differential equation solver with strictly linear time query complexity for average-case diagonalizable operators, as well as a ground state preparation algorithm that upgrades previous nearly optimal results for Hermitian Hamiltonians to diagonalizable matrices with real spectra. Underpinning our algorithms is an efficient method to prepare a quantum superposition of Faber polynomials, which generalize the nearly-best uniform approximation properties of Chebyshev polynomials to the complex plane. Of independent interest, we also develop techniques to generate [Formula: see text] Fourier coefficients with [Formula: see text] gates compared to prior approaches with linear cost.

arXiv:2401.06240•SIAM Journal on Computing•Feb 12, 2026•39 citations

The Quantum Fourier Transform for Continuous Variables

Gianfranco Cariolaro, Edi Ruffa, Amir Mohammad Yaghoobianzadeh +1 more

The quantum Fourier transform for discrete variable (dvQFT) is an efficient algorithm for several applications. It is usually considered for the processing of quantum bits (qubits) and its efficient implementation is obtained with two elementary components: the Hadamard gate and the controlled--phase gate. In this paper, the quantum Fourier transform operating with continuous variables (cvQFT) is considered. Thus, the environment becomes the Hilbert space, where the natural definition of the cvQFT will be related to rotation operators, which in the $N$--mode are completely specified by unitary matrices of order $N$. Then the cvQFT is defined as the rotation operator whose rotation matrix is given by the discrete Fourier transform (DFT) matrix. For the implementation of rotation operators with primitive components (single--mode rotations and beam splitters), we follow the well known Murnaghan procedure, with appropriate modifications. Moreover, algorithms related to the fast Fourier transform (FFT) are applied to reduce drastically the implementation complexity. The final part is concerned with the application of the cvQFT to general Gaussian states. In particular, we show that cvQFT has the simple effect of transforming the displacement vector by a one-dimensional DFT, the squeeze matrix by a two-dimensional DFT, and the rotation matrix by a Fourier-like similarity transform.

quant-pharXiv:2512.12771•Dec 16, 2025•0 citations

Quantum Chebyshev Transform: Mapping, Embedding, Learning and Sampling Distributions

Chelsea A. Williams, Annie E. Paine, Hsin‐Yu Wu +2 more

We develop a paradigm for building quantum models in the orthonormal space of Chebyshev polynomials. We show how to encode data into quantum states with amplitudes being Chebyshev polynomials with degree growing exponentially in the system size. Similar to the quantum Fourier transform which maps computational basis space into the phase (Fourier) basis, we describe the quantum circuit for the mapping between computational and Chebyshev spaces. We propose an embedding circuit for generating the orthonormal Chebyshev basis of exponential capacity, represented by a continuously-parameterized shallow isometry. This enables automatic quantum model differentiation, and opens a route to solving stochastic differential equations. We apply the developed paradigm to generative modeling from physically- and financially-motivated distributions, and use the quantum Chebyshev transform for efficient sampling of these distributions in extended computational basis.

arXiv:2306.17026•Jun 29, 2023•30 citations

A unifying framework for quantum algorithms for time-dependent non-unitary dynamics

Xiaojing Dong, Chuwen Ma, Yizhe Peng +1 more

We present an improved autonomization method for quantum simulation of time-dependent homogeneous dissipative linear systems, combining a clock-variable reformulation with Schrödingerization to obtain a time-independent Hamiltonian system. To control both discretization error and recovery probability, we construct the clock profile from a compactly supported window function and a normalized Dirichlet kernel: the former imposes endpoint regularity, while the latter concentrates the sampled mass and keeps the discrete normalization bounded. For the subsequent Schrödingerization step, we use an exactly periodic version of an error-function initial profile, whose explicit Fourier coefficients allow direct error estimates and simplify the analysis of smooth initialization. By combining Fourier projection with weighted recovery, we retain a single logarithmic precision factor in the full algorithm. Under finite-order derivative bounds, sampled matrix access, and exact state-preparation access, we prepare the normalized solution at time $T$ to accuracy $\varepsilon$ with success probability $Θ(1)$ using $\mathcal O\!\bigl(gα_AT\log(gα_AT/\varepsilon)\bigr)$ matrix queries and $\mathcal O(g)$ queries to each state-preparation oracle, where $g=\|\boldsymbol{x}_0\|/\|\boldsymbol{x}(T)\|$ and $α_A$ is the matrix-oracle normalization. We illustrate the construction and its recovery probabilities through a numerical experiment on a time-dependent two-cavity system.

quant-pharXiv:2608.07133•Aug 10, 2026•1 citation
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 paper considers quantum implementation of the sampled Chebyshev transform cj=∑kfkTj(xk)c_j=\sum_k f_kT_j(x_k)cj​=∑k​fk​Tj​(xk​) on equispaced nodes xk=−1+2k/Nx_k=-1+2k/Nxk​=−1+2k/N, where N=2nN=2^nN=2n. Unlike Chebyshev-root sampling, these nodes become nonuniform under θ=arccos⁡x\theta=\arccos xθ=arccosx, so the transform is nonunitary and is implemented through a block encoding.
The construction revises an existing low-rank nonuniform quantum Fourier transform (NUQFT). It removes an auxiliary parameter κ\kappaκ arising from propagating node-rounding errors through arccos⁡\arccosarccos: stored fixed-point nodes are instead treated as exact inputs, and their discrepancy from the target nodes is bounded directly through Fourier phases. The resulting node perturbation bound is ∥Ft−Fτ∥≤(2π/3)N3/2∥t−τ∥∞\|F_t-F_\tau\|\le(2\pi/\sqrt3)N^{3/2}\|t-\tau\|_\infty∥Ft​−Fτ​∥≤(2π/3​)N3/2∥t−τ∥∞​. Chebyshev–Bessel coefficient bounds and a weighted LCU give normalization O(dr)O(\sqrt{d_r})O(dr​​), where drd_rdr​ counts nodes rounding to one Fourier-grid point.
Writing the Chebyshev matrix as the average of two NUDFTs yields an explicit ε\varepsilonε-accurate block encoding of (CN)jk=Tj(xk)/N(C_N)_{jk}=T_j(x_k)/\sqrt N(CN​)jk​=Tj​(xk​)/N​. The paper proves dr≤5d_r\le5dr​≤5 and constructs node, sparse-row-access, and coefficient-preparation circuits. With L=log⁡N+log⁡(1/ε)L=\log N+\log(1/\varepsilon)L=logN+log(1/ε), resources are O(L)O(L)O(L) qubits and O~(L2)\widetilde O(L^2)O(L2) arithmetic/controlled-rotation gates, or O~(L3)\widetilde O(L^3)O(L3) Clifford+TTT gates; normalization is below 24524\sqrt5245​.
The output contains sampled-polynomial projections, not interpolation coefficients. State preparation additionally depends on input loading and inverse output norm; extensive readout can also dominate. Arbitrary-node extensions require suitable oracles and retain collision dependence. Conversion to general polynomial families is left open.
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.
Many problems in linear algebra-such as those arising from non-Hermitian physics, transcorrelated quantum chemistry and differential equations-can be solved on a quan-tum computer by processing eigenvalues of the non-normal input matrices. However, the existing Quantum Singular Value Transformation (QSVT) framework is ill-suited to this task, as eigenvalues and singular values are different in general. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary polynomial transformations on eigenvalues of block-encoded non-normal operators, and a related Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra. QEVT has query complexity to the block encoding nearly recovering that of the QSVT for a Hermitian input, and QEVE achieves the Heisenberg-limited scaling for diagonalizable input matrices. As applications, we develop a linear differential equation solver with strictly linear time query complexity for average-case diagonalizable operators, as well as a ground state preparation algorithm that upgrades previous nearly optimal results for Hermitian Hamiltonians to diagonalizable matrices with real spectra. Underpinning our algorithms is an efficient method to prepare a quantum super-position of Faber polynomials, which generalize the nearly-best uniform approximation properties of Chebyshev polynomials to the complex plane. Of independent interest, we also develop techniques to generatennnFourier coefficients with 0 (poly log (nnn)) gates compared to prior approaches with linear cost.
Abstract. Many problems in linear algebra—such as those arising from non-Hermitian physics, transcorrelated quantum chemistry, and differential equations—can be solved on a quantum computer by processing eigenvalues of the non-normal input matrices. However, the existing Quantum Singular Value Transformation (QSVT) framework is ill-suited for this task because eigenvalues and singular values are different in general. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary polynomial transformations on eigenvalues of block-encoded non-normal operators and a related Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra. QEVT has query complexity to the block encoding nearly recovering that of the QSVT for a Hermitian input, and QEVE achieves the Heisenberg-limited scaling for diagonalizable input matrices. As applications, we develop a linear differential equation solver with strictly linear time query complexity for average-case diagonalizable operators, as well as a ground state preparation algorithm that upgrades previous nearly optimal results for Hermitian Hamiltonians to diagonalizable matrices with real spectra. Underpinning our algorithms is an efficient method to prepare a quantum superposition of Faber polynomials, which generalize the nearly-best uniform approximation properties of Chebyshev polynomials to the complex plane. Of independent interest, we also develop techniques to generate [Formula: see text] Fourier coefficients with [Formula: see text] gates compared to prior approaches with linear cost.
The quantum Fourier transform for discrete variable (dvQFT) is an efficient algorithm for several applications. It is usually considered for the processing of quantum bits (qubits) and its efficient implementation is obtained with two elementary components: the Hadamard gate and the controlled--phase gate. In this paper, the quantum Fourier transform operating with continuous variables (cvQFT) is considered. Thus, the environment becomes the Hilbert space, where the natural definition of the cvQFT will be related to rotation operators, which in the NNN--mode are completely specified by unitary matrices of order NNN. Then the cvQFT is defined as the rotation operator whose rotation matrix is given by the discrete Fourier transform (DFT) matrix. For the implementation of rotation operators with primitive components (single--mode rotations and beam splitters), we follow the well known Murnaghan procedure, with appropriate modifications. Moreover, algorithms related to the fast Fourier transform (FFT) are applied to reduce drastically the implementation complexity. The final part is concerned with the application of the cvQFT to general Gaussian states. In particular, we show that cvQFT has the simple effect of transforming the displacement vector by a one-dimensional DFT, the squeeze matrix by a two-dimensional DFT, and the rotation matrix by a Fourier-like similarity transform.
We develop a paradigm for building quantum models in the orthonormal space of Chebyshev polynomials. We show how to encode data into quantum states with amplitudes being Chebyshev polynomials with degree growing exponentially in the system size. Similar to the quantum Fourier transform which maps computational basis space into the phase (Fourier) basis, we describe the quantum circuit for the mapping between computational and Chebyshev spaces. We propose an embedding circuit for generating the orthonormal Chebyshev basis of exponential capacity, represented by a continuously-parameterized shallow isometry. This enables automatic quantum model differentiation, and opens a route to solving stochastic differential equations. We apply the developed paradigm to generative modeling from physically- and financially-motivated distributions, and use the quantum Chebyshev transform for efficient sampling of these distributions in extended computational basis.
We present an improved autonomization method for quantum simulation of time-dependent homogeneous dissipative linear systems, combining a clock-variable reformulation with Schrödingerization to obtain a time-independent Hamiltonian system. To control both discretization error and recovery probability, we construct the clock profile from a compactly supported window function and a normalized Dirichlet kernel: the former imposes endpoint regularity, while the latter concentrates the sampled mass and keeps the discrete normalization bounded. For the subsequent Schrödingerization step, we use an exactly periodic version of an error-function initial profile, whose explicit Fourier coefficients allow direct error estimates and simplify the analysis of smooth initialization. By combining Fourier projection with weighted recovery, we retain a single logarithmic precision factor in the full algorithm. Under finite-order derivative bounds, sampled matrix access, and exact state-preparation access, we prepare the normalized solution at time TTT to accuracy ε\varepsilonε with success probability Θ(1)Θ(1)Θ(1) using O ⁣(gαATlog⁡(gαAT/ε))\mathcal O\!\bigl(gα_AT\log(gα_AT/\varepsilon)\bigr)O(gαA​Tlog(gαA​T/ε)) matrix queries and O(g)\mathcal O(g)O(g) queries to each state-preparation oracle, where g=∥x0∥/∥x(T)∥g=\|\boldsymbol{x}_0\|/\|\boldsymbol{x}(T)\|g=∥x0​∥/∥x(T)∥ and αAα_AαA​ is the matrix-oracle normalization. We illustrate the construction and its recovery probabilities through a numerical experiment on a time-dependent two-cavity system.