The quantum Fourier transform (QFT) is a fundamental primitive in quantum computation and quantum information. In this work, we extend the framework for the QFT from finite groups to finite-dimensional semisimple algebras, and give efficient QFTs 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.The quantum Fourier transform (QFT) is a fundamental primitive in quantum computation and quantum information. In this work, we extend the framework for the QFT from finite groups to finite-dimensional semisimple algebras, and give efficient QFTs 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.

quant-pharXiv:2605.05337May 8, 20260 citations

On the structural properties of Lie algebras via associated labeled directed graphs

Tim Heib, David Edward Bruschi

We present a method for associating labeled directed graphs to finite-dimensional Lie algebras that are $graph$ - $admissible$ . The proposed framework enables visual identification of key structural algebraic features. We first formalize this approach and establish several classes of Lie algebras that admit the categorization as graph-admissible Lie algebras, and then investigate suitable valid graphs for this approach by translating the antisymmetry of the Lie bracket and the Jacobi identity into rules that such graphs must satisfy. Furthermore, based on these foundations, we provide graph-theoretic criteria for solvability, nilpotency, presence of ideals, simplicity, semisimplicity, and reductiveness of an algebra. We also present practical algorithms for constructing such graphs and those associated with the lower central series and derived series via iterative pruning procedures. We further cover specific examples, such as the Schrödinger and Lorentz algebras, which illustrate the applicability of the developed tools to physically relevant cases. Moreover, we explore applications in physics, where the method facilitates computation of similarity transformations essential for determining quantum mechanical time evolution via the Lie-algebraic factorization method. We also discuss a possible generalization of the framework based on magma-gradings of Lie algebras and formulate related open questions. Our approach bridges algebraic and combinatorial perspectives, offering theoretical tools for this area of mathematical physics.We present a method for associating labeled directed graphs to finite-dimensional Lie algebras that are $graph$-$admissible$. The proposed framework enables visual identification of key structural algebraic features. We first formalize this approach and establish several classes of Lie algebras that admit the categorization as graph-admissible Lie algebras, and then investigate suitable valid graphs for this approach by translating the antisymmetry of the Lie bracket and the Jacobi identity into rules that such graphs must satisfy. Furthermore, based on these foundations, we provide graph-theoretic criteria for solvability, nilpotency, presence of ideals, simplicity, semisimplicity, and reductiveness of an algebra. We also present practical algorithms for constructing such graphs and those associated with the lower central series and derived series via iterative pruning procedures. We further cover specific examples, such as the Schrödinger and Lorentz algebras, which illustrate the applicability of the developed tools to physically relevant cases. Moreover, we explore applications in physics, where the method facilitates computation of similarity transformations essential for determining quantum mechanical time evolution via the Lie-algebraic factorization method. We also discuss a possible generalization of the framework based on magma-gradings of Lie algebras and formulate related open questions. Our approach bridges algebraic and combinatorial perspectives, offering theoretical tools for this area of mathematical physics.

math-phCross-listedarXiv:2601.16161Jan 23, 2026

Quantum Algorithms and Applications

Melinda Andrews, Joseph Stephen Dulny, Andrew N. Glaudell +6 more

Sep 1, 20200 citations

Quantum Algorithms: Application and Feasibility

Duong Bui, Kimmo Halunen, Nhan Nguyen +1 more

Lecture notes in computer scienceNov 26, 20240 citations

Quantum Algorithms and Methods

Ivan B. Djordjević

Elsevier eBooksJan 1, 20212 citations

Thermodynamic linear algebra

Maxwell Aifer, Kaelan Donatella, Max Hunter Gordon +5 more

Abstract Linear algebra is central to many algorithms in engineering, science, and machine learning; hence, accelerating it would have tremendous economic impact. Quantum computing has been proposed for this purpose, although the resource requirements are far beyond current technological capabilities. We consider an alternative physics-based computing paradigm based on classical thermodynamics, to provide a near-term approach to accelerating linear algebra. At first sight, thermodynamics and linear algebra seem to be unrelated fields. Here, we connect solving linear algebra problems to sampling from the thermodynamic equilibrium distribution of a system of coupled harmonic oscillators. We present simple thermodynamic algorithms for solving linear systems of equations, computing matrix inverses, and computing matrix determinants. Under reasonable assumptions, we rigorously establish asymptotic speedups for our algorithms, relative to digital methods, that scale linearly in matrix dimension. Our algorithms exploit thermodynamic principles like ergodicity, entropy, and equilibration, highlighting the deep connection between these two seemingly distinct fields, and opening up algebraic applications for thermodynamic computers.Abstract Linear algebra is central to many algorithms in engineering, science, and machine learning; hence, accelerating it would have tremendous economic impact. Quantum computing has been proposed for this purpose, although the resource requirements are far beyond current technological capabilities. We consider an alternative physics-based computing paradigm based on classical thermodynamics, to provide a near-term approach to accelerating linear algebra. At first sight, thermodynamics and linear algebra seem to be unrelated fields. Here, we connect solving linear algebra problems to sampling from the thermodynamic equilibrium distribution of a system of coupled harmonic oscillators. We present simple thermodynamic algorithms for solving linear systems of equations, computing matrix inverses, and computing matrix determinants. Under reasonable assumptions, we rigorously establish asymptotic speedups for our algorithms, relative to digital methods, that scale linearly in matrix dimension. Our algorithms exploit thermodynamic principles like ergodicity, entropy, and equilibration, highlighting the deep connection between these two seemingly distinct fields, and opening up algebraic applications for thermodynamic computers.

arXiv:2308.05660npj Unconventional ComputingNov 5, 202432 citations

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.

We present a method for associating labeled directed graphs to finite-dimensional Lie algebras that are

graph

admissible

. The proposed framework enables visual identification of key structural algebraic features. We first formalize this approach and establish several classes of Lie algebras that admit the categorization as graph-admissible Lie algebras, and then investigate suitable valid graphs for this approach by translating the antisymmetry of the Lie bracket and the Jacobi identity into rules that such graphs must satisfy. Furthermore, based on these foundations, we provide graph-theoretic criteria for solvability, nilpotency, presence of ideals, simplicity, semisimplicity, and reductiveness of an algebra. We also present practical algorithms for constructing such graphs and those associated with the lower central series and derived series via iterative pruning procedures. We further cover specific examples, such as the Schrödinger and Lorentz algebras, which illustrate the applicability of the developed tools to physically relevant cases. Moreover, we explore applications in physics, where the method facilitates computation of similarity transformations essential for determining quantum mechanical time evolution via the Lie-algebraic factorization method. We also discuss a possible generalization of the framework based on magma-gradings of Lie algebras and formulate related open questions. Our approach bridges algebraic and combinatorial perspectives, offering theoretical tools for this area of mathematical physics.