Efficient Quantum Fourier Transforms For Semisimple Algebras

• URL: http://arxiv.org/abs/2605.05337v1
• Date: Wed, 06 May 2026 18:08:12 GMT
• Title: Efficient Quantum Fourier Transforms For Semisimple Algebras
• Abstract summary: We generalize the quantum Fourier transform (QFT) for finite groups to a QFT for finite-dimensional semisimple algebras.<n>These algebras play important roles in generalized Schur-Weyl duality, statistical physics and many-body systems.
• Score: 1.4744573105338015
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The quantum Fourier transform (QFT) is a fundamental primitive in quantum computation and quantum information. In this work, we generalize the QFT for finite groups to a QFT for finite-dimensional semisimple algebras, and give efficient quantum Fourier transforms for the partition algebra $P_n(d)$, Brauer algebra $B_n(d)$, and walled Brauer algebra $B_{r,s}(d)$. These algebras play important roles in generalized Schur-Weyl duality, statistical physics and many-body systems, and have recently found several applications in quantum algorithms. Unlike the group case, the Fourier transform over a semisimple algebra can be non-unitary. Nevertheless, we show that when the parameter $d$ is sufficiently large, the Fourier transform is well approximated by a unitary operator. Furthermore, we show that for each of the algebras $A$ from above, such an approximate Fourier transform can be implemented efficiently: we give a quantum algorithm with gate complexity $\mathrm{poly}(n,\log d,\log(1/\varepsilon))$ for approximating the Fourier transform to error $(d^{-1/2} + \varepsilon) \cdot \mathrm{poly}(|A|)$. Along the way, we establish several properties of the Fourier basis of semisimple algebras that may be of independent interest.

Related papers

• 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)
• Quantum two-dimensional superintegrable systems in flat space: exact-solvability, hidden algebra, polynomial algebra of integrals [41.99844472131922]
  It includes the Smorodinsky-Winternitz potentials I-II (the Holt potential), the Fokas-Lagerstrom model, the 3-body Calogero and Wolfes (equivalently, $G$ rational, or $I_6$) models.<n>It is shown that all of them are exactly-solvable, thus, confirming the Montreal conjecture.<n>Each model is characterized by infinitely-many finite-dimensional invariant subspaces, which form the infinite flag.
  arXiv  Detail & Related papers  (2025-12-30T07:39:35Z)
• 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)
• 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)
• Fast Fourier transforms and fast Wigner and Weyl functions in large quantum systems [0.0]
  Two methods for fast Fourier transforms are used in a quantum context. The first method is for systems with dimension of the Hilbert space $D=dn$ with $d$ an odd integer. The second method is also used for the fast calculation of Wigner and Weyl functions, in quantum systems with large finite dimension of the Hilbert space.
  arXiv  Detail & Related papers  (2024-05-08T15:54:35Z)
• 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)
• Fourier expansion in variational quantum algorithms [1.4732811715354455]
  We focus on the class of variational circuits, where constant gates are Clifford gates and parameterized gates are generated by Pauli operators. We give a classical algorithm that computes coefficients of all trigonometric monomials up to a degree $m$ in time bounded by $mathcalO(N2m)$.
  arXiv  Detail & Related papers  (2023-04-07T18:00:01Z)
• Deep Fourier Up-Sampling [100.59885545206744]
  Up-sampling in the Fourier domain is more challenging as it does not follow such a local property. We propose a theoretically sound Deep Fourier Up-Sampling (FourierUp) to solve these issues.
  arXiv  Detail & Related papers  (2022-10-11T06:17:31Z)
• Unified Fourier-based Kernel and Nonlinearity Design for Equivariant Networks on Homogeneous Spaces [52.424621227687894]
  We introduce a unified framework for group equivariant networks on homogeneous spaces. We take advantage of the sparsity of Fourier coefficients of the lifted feature fields. We show that other methods treating features as the Fourier coefficients in the stabilizer subgroup are special cases of our activation.
  arXiv  Detail & Related papers  (2022-06-16T17:59:01Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)
• Learning Set Functions that are Sparse in Non-Orthogonal Fourier Bases [73.53227696624306]
  We present a new family of algorithms for learning Fourier-sparse set functions. In contrast to other work that focused on the Walsh-Hadamard transform, our novel algorithms operate with recently introduced non-orthogonal Fourier transforms. We demonstrate effectiveness on several real-world applications.
  arXiv  Detail & Related papers  (2020-10-01T14:31:59Z)
• Quantum information theory and Fourier multipliers on quantum groups [0.0]
  We compute the exact values of the minimum output entropy and the completely bounded minimal entropy of quantum channels acting on matrix algebras. Our results use a new and precise description of bounded Fourier multipliers from $mathrmL1(mathbbG)$ into $mathrmLp(mathbbG)$ for $1 p leq infty$ where $mathbbG$ is a co-amenable locally compact quantum group.
  arXiv  Detail & Related papers  (2020-08-27T09:47:10Z)
• Quantum Fourier Analysis [1.776439648597615]
  Quantum Fourier analysis is a new subject that combines an algebra with analytic estimates. This provides interesting tools to investigate phenomena such as quantum symmetry. We cite several applications of the quantum Fourier analysis in subfactor theory, in category theory, and in quantum information.
  arXiv  Detail & Related papers  (2020-02-10T00:25:53Z)

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.