Non-Uniform Quantum Fourier Transform

• URL: http://arxiv.org/abs/2602.13472v1
• Date: Fri, 13 Feb 2026 21:26:02 GMT
• Title: Non-Uniform Quantum Fourier Transform
• Authors: Junaid Aftab, Yuehaw Khoo, Haizhao Yang,
• Abstract summary: This work introduces a quantum algorithm for the Non-Uniform Quantum Fourier Transform (NUQFT) based on a low-rank factorization of the NUDFT matrix.<n>The factorization is translated into an explicit quantum construction using block encodings, Quantum Signal Processing, and the Linear Combination of Unitaries framework.<n>Under standard oracle access assumptions for non-uniform sampling points, we derive explicit, non-asymptotic gate-level resource estimates.
• Score: 6.46147328920679
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Quantum Detection of Sequency-Band Structure [0.5729426778193398]
  We present a quantum algorithm for estimating the amplitude content of user-specified sequency bands in quantum-encoded signals.<n>The method employs a sequency-ordered Quantum Walsh-Hadamard Transform (QWHT), a comparator-based oracle that coherently marks basis states within an arbitrary sequency range.<n>This enables the detection of structured signal components, including both high- and low-sequency features, as well as the identification of rapid sign-change behavior associated with noise or anomalies.
  arXiv  Detail & Related papers  (2026-02-09T08:47:51Z)
• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  Multiple-input multiple-output (MIMO) is critical for 6G communication, offering improved spectral efficiency and reliability.<n>This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA) and alternating optimization to address the problem of b-bit quantized phase shifters both at the transmitter and the receiver.<n>We demonstrate that the structure of this quantized beamforming problem aligns naturally with hybrid-classical methods like QAOA, as the phase shifts used in beamforming can be directly mapped to rotation gates in a quantum circuit.
  arXiv  Detail & Related papers  (2025-10-07T17:53:02Z)
• Inverse nonlinear fast Fourier transform on SU(2) with applications to quantum signal processing [10.193028145901248]
  We investigate the inverse NLFT on $mathrmSU(2)$ and establish the numerical stability of the layer stripping algorithm for the first time.<n>We develop a fast and numerically stable algorithm, called inverse nonlinear fast Fourier transform, for performing inverse NLFT with near-linear complexity.
  arXiv  Detail & Related papers  (2025-05-19T01:57:04Z)
• Generalized Quantum Signal Processing and Non-Linear Fourier Transform are equivalent [0.0]
  Quantum signal processing (QSP) and quantum singular value transformation (QSVT) are powerful techniques for the development of quantum procedures.<n>Recent research showed that Non-Linear Fourier Analysis (NLFA) can be employed to numerically compute a QSP protocol, with provable stability.
  arXiv  Detail & Related papers  (2025-03-04T22:02:38Z)
• Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach [36.05085942729295]
  This paper introduces a Quantum Natural Policy Gradient (QNPG) algorithm, which replaces the random sampling used in classicalNPG estimators with a deterministic gradient estimation approach.<n>The proposed QNPG algorithm achieves a sample complexity of $tildemathcalO(epsilon-1.5)$ for queries to the quantum oracle, significantly improving the classical lower bound of $tildemathcalO(epsilon-2)$ for queries to the Markov Decision Process (MDP)
  arXiv  Detail & Related papers  (2025-01-27T17:38:30Z)
• Sample-Efficient Estimation of Nonlinear Quantum State Functions [5.641998714611475]
  We introduce the quantum state function (QSF) framework by extending the SWAP test via linear combination of unitaries and parameterized quantum circuits.<n>Our framework enables the implementation of arbitrarily normalized degree-$n$ functions of quantum states with precision.<n>We apply QSF for developing quantum algorithms for fundamental tasks, including entropy, fidelity, and eigenvalue estimations.
  arXiv  Detail & Related papers  (2024-12-02T16:40:17Z)
• Evaluation of phase shifts for non-relativistic elastic scattering using quantum computers [39.58317527488534]
  This work reports the development of an algorithm that makes it possible to obtain phase shifts for generic non-relativistic elastic scattering processes on a quantum computer.
  arXiv  Detail & Related papers  (2024-07-04T21:11:05Z)
• Direct interpolative construction of the discrete Fourier transform as a matrix product operator [0.0]
  We present a simple closed-form construction of the QFT MPO using the interpolative decomposition. This construction can speed up the application of the QFT and the DFT, respectively, in quantum circuit simulations and QTT applications.
  arXiv  Detail & Related papers  (2024-04-04T03:42:17Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Circuit Symmetry Verification Mitigates Quantum-Domain Impairments [69.33243249411113]
  We propose circuit-oriented symmetry verification that are capable of verifying the commutativity of quantum circuits without the knowledge of the quantum state. In particular, we propose the Fourier-temporal stabilizer (STS) technique, which generalizes the conventional quantum-domain formalism to circuit-oriented stabilizers.
  arXiv  Detail & Related papers  (2021-12-27T21:15:35Z)
• Simulating the Mott transition on a noisy digital quantum computer via Cartan-based fast-forwarding circuits [62.73367618671969]
  Dynamical mean-field theory (DMFT) maps the local Green's function of the Hubbard model to that of the Anderson impurity model. Quantum and hybrid quantum-classical algorithms have been proposed to efficiently solve impurity models. This work presents the first computation of the Mott phase transition using noisy digital quantum hardware.
  arXiv  Detail & Related papers  (2021-12-10T17:32:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.