Quantum Fourier transform toolbox

• URL: http://arxiv.org/abs/2608.28573v1
• Date: Fri, 28 Aug 2026 17:49:30 GMT
• Title: Quantum Fourier transform toolbox
• Abstract summary: We use Mackey theory and Clifford theory to show exponential improvement in circuit cost for specific group families.<n>We obtain explicit quantum circuits for the QFT over $mathrmGL_F_q.<n>These methods provide new systematic tools to construct QFTs for broad classes of finite groups.
• Score: 0.21748200848556343
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum Fourier transforms (QFTs) are essential primitives in quantum algorithms. While abelian groups admit efficient QFT circuits, with circuit size polynomial in the logarithm of the group order, efficient constructions are known for relatively few non-abelian families. We develop two new approaches to QFT circuit construction, based on Mackey theory and Clifford theory, respectively, and use them to show exponential improvement in circuit cost for specific group families. Using the Mackey-theoretic approach, we obtain explicit quantum circuits for the QFT over $\mathrm{GL}_2(F_q)$ that scale polynomially in $\log q$, rather than polynomially in $q$. Using the Clifford-theoretic approach, we obtain QFT circuits for wreath products $F\wr S_n$, whose cost depends on the cost of a QFT over $F$ and the size of its representation registers. This removes the restriction $|F|=\operatorname{poly}(n)$ required by previous generic constructions and can yield exponential improvements when $F$ itself has an efficient QFT. Together, these methods provide new systematic tools to construct QFTs for broad classes of finite groups.

Related papers

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  We give a problem that is solvable by shallow quantum circuits, hard for computation in time under lattice-based assumptions.<n>We prove that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
  arXiv  Detail & Related papers  (2026-09-01T15:54:34Z)
• Quantum Multi-Level Estimation of Functionals of Discrete Distributions [23.53427184324404]
  We propose a quantum multi-level estimation framework for a functional $sum_i=1n f(p_i)$ of a discrete distribution.<n>We present efficient quantum estimators for the $q$-Tsallis entropy of discrete distributions.
  arXiv  Detail & Related papers  (2026-05-05T12:25:17Z)
• On the Fast Fourier Transform on SU(2) [45.899400495223375]
  Special unitary group SU(2) plays a fundamental role in the description of symmetries in quantum mechanics.<n>We develop a Fast Fourier Transform algorithm inspired by the classical Cooley-Tukey divide-and-dimensional scheme.
  arXiv  Detail & Related papers  (2026-04-19T17:38:38Z)
• IQP circuits for 2-Forrelation [2.5782420501870296]
  2-Forrelation problem provides optimal separation between classical and quantum query complexity.<n>We show that 2-Forrelation can be solved using Instantaneous Quantum Polynomial-time ($mathsfIQP$) circuits.
  arXiv  Detail & Related papers  (2026-04-16T17:24:25Z)
• 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)
• A Quantum Bluestein's Algorithm for Arbitrary-Size Quantum Fourier Transform [0.0]
  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.
  arXiv  Detail & Related papers  (2025-12-17T11:45:43Z)
• Quantum Advantage via Solving Multivariate Polynomials [21.099298465042583]
  We show that degree three functions are enough to instantiate the random oracle to obtain non-relativized quantum advantage.<n>We show that there is a expected-time quantum algorithm that provably solves $p_i(x_ldots,x_n)=y_i_iin [m]$ for $mn$ over $mathbbF$.
  arXiv  Detail & Related papers  (2025-09-08T23:19:20Z)
• Quantum Algorithms for Gowers Norm Estimation, Polynomial Testing, and Arithmetic Progression Counting over Finite Abelian Groups [0.0]
  We propose a family of quantum algorithms for estimating Gowers norms $ Uk $ over finite abelian groups.<n>These algorithms leverage recent inverse theorems for Gowers norms, together with amplitude estimation, to reveal higher-order correlations.
  arXiv  Detail & Related papers  (2025-08-02T06:58:12Z)
• Highly-efficient quantum Fourier transformations for some nonabelian groups [0.0]
  We present fast quantum Fourier transformations for a number of nonabelian groups of interest for high energy physics. For each group, we derive explicit quantum circuits and estimate resource scaling for fault-tolerant implementations.
  arXiv  Detail & Related papers  (2024-07-31T18:00:04Z)
• 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)
• Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
  We show that products exponentiated sums of $S(N)$ permutations with random phases match the first $2Omega(n)$ moments of the Haar measure. The heart of our proof is a conceptual connection between the large dimension (large-$N$) expansion in random matrix theory and the method.
  arXiv  Detail & Related papers  (2024-04-25T17:08:34Z)
• 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 Fourier Addition, Simplified to Toffoli Addition [92.18777020401484]
  We present the first systematic translation of the QFT-addition circuit into a Toffoli-based adder. Instead of using approximate decompositions of the gates from the QFT circuit, it is more efficient to merge gates.
  arXiv  Detail & Related papers  (2022-09-30T02:36:42Z)

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.