A Quantum Bluestein's Algorithm for Arbitrary-Size Quantum Fourier Transform

• URL: http://arxiv.org/abs/2512.15349v2
• Date: Tue, 23 Dec 2025 04:41:22 GMT
• Title: A Quantum Bluestein's Algorithm for Arbitrary-Size Quantum Fourier Transform
• Authors: Nan-Hong Kuo, Renata Wong,
• Abstract summary: QBA produces the exact $N$-point discrete Fourier transform on arbitrary-length inputs.<n>We validate the correctness of QBA through a concrete implementation in Qiskit and classical simulation.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a quantum analogue of Bluestein's algorithm (QBA) that implements an exact $N$-point Quantum Fourier Transform (QFT) for arbitrary $N$. Our construction factors the $N$-dimensional QFT unitary into three diagonal quadratic-phase gates and two standard radix-2 QFT subcircuits of size $M = 2^m$ (with $M \ge 2N - 1$). This achieves asymptotic gate complexity $O((\log N)^2)$ and uses $O(\log N)$ qubits, matching the performance of a power-of-two QFT on $m$ qubits while avoiding the need to embed into a larger Hilbert space. We validate the correctness of the algorithm through a concrete implementation in Qiskit and classical simulation, confirming that QBA produces the exact $N$-point discrete Fourier transform on arbitrary-length inputs.

Related papers

• FFT-Accelerated Auxiliary Variable MCMC for Fermionic Lattice Models: A Determinant-Free Approach with $O(N\log N)$ Complexity [52.3171766248012]
  We introduce a Markov Chain Monte Carlo (MCMC) algorithm that dramatically accelerates the simulation of quantum many-body systems.<n>We validate our algorithm on benchmark quantum physics problems, accurately reproducing known theoretical results.<n>Our work provides a powerful tool for large-scale probabilistic inference and opens avenues for physics-inspired generative models.
  arXiv  Detail & Related papers  (2025-10-13T07:57:21Z)
• Quantum Algorithms for Finite-horizon Markov Decision Processes [40.812944518646006]
  We design quantum algorithms that are more efficient than classical algorithms to solve time-dependent and finite-horizon Markov Decision Processes (MDPs)<n>In the exact dynamics setting, we prove that our $textbfQVI-1$ algorithm achieves a quadratic speedup in the size of the action space $(A)$.<n>In the generative model setting, we prove that our algorithms $textbfQVI-3$ and $textbfQVI-4$ achieve improvements in sample complexity over the state-of-the-art (SOTA) classical algorithm.
  arXiv  Detail & Related papers  (2025-08-07T09:00:23Z)
• Generalized tensor transforms and their applications in classical and quantum computing [0.0]
  We introduce a novel framework for Generalized Transforms (GTTs), constructed through an $n$-fold tensor product of an arbitrary $b times b$ unitary matrix $W$.<n>For quantum applications, our GTT-based algorithm achieves both gate complexity and circuit depth of $O(log_b N)$, where $N = bn$ denotes the length of the vector input.<n>We explore diverse applications of GTTs in quantum computing, including quantum state compression and transmission, function encoding and quantum digital signal processing.
  arXiv  Detail & Related papers  (2025-07-03T08:28:00Z)
• A log-depth in-place quantum Fourier transform that rarely needs ancillas [0.08113005007481719]
  "optimistic quantum circuits" are often sufficient in the context of larger quantum algorithms.<n>We build an optimistic circuit for the in-place quantum Fourier transform (QFT)<n>We apply our reduction technique to yield an approximate QFT with well-controlled error on all inputs.
  arXiv  Detail & Related papers  (2025-05-01T17:58:36Z)
• A Faster Quantum Fourier Transform [0.0]
  We present anally improved algorithm for implementing the Quantum Fourier Transform (QFT) in both the exact and approximate settings.<n>We show that these costs can be reduced by leveraging a novel formulation of the QFT that recurses on two partitions of the qubits.
  arXiv  Detail & Related papers  (2025-01-19T06:18:52Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.<n>Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.<n>We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates [40.56175933029223]
  We propose two types of constant-depth constructions for implementing Uniformly Controlled Gates. We obtain constant-depth circuits for the quantum counterparts of read-only and read-write memory devices.
  arXiv  Detail & Related papers  (2023-08-16T17:54:56Z)
• Multidimensional Quantum Fourier Transformation [0.0]
  In this work, the known QFT circuit is used to derive an efficient circuit for the multidimensional QFT. An example on current hardware is depicted by a 6 qubit 2D-QFT with an IBM quantum computer.
  arXiv  Detail & Related papers  (2023-01-31T18:25:40Z)
• Quantum Legendre-Fenchel Transform [6.643082745560234]
  We present a quantum algorithm to compute the discrete Legendre-Fenchel transform. We show that our quantum algorithm is optimal up to polylogarithmic factors.
  arXiv  Detail & Related papers  (2020-06-08T18:00:05Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)

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.