An algorithm is presented allowing the construction of fast Fourier transforms for any solvable group on a classical computer. The special structure of the recursion formula being the core of this algorithm makes it a good starting point to obtain systematically fast Fourier transforms for solvable groups on a quantum computer. The inherent structure of the Hilbert space imposed by the qubit architecture suggests to consider groups of order 2^n first (where n is the number of qubits). As an example, fast quantum Fourier transforms for all 4 classes of non-abelian 2-groups with cyclic normal subgroup of index 2 are explicitly constructed in terms of quantum circuits. The (quantum) complexity of the Fourier transform for these groups of size 2^n is O(n^2) in all cases.An algorithm is presented allowing the construction of fast Fourier transforms for any solvable group on a classical computer. The special structure of the recursion formula being the core of this algorithm makes it a good starting point to obtain systematically fast Fourier transforms for solvable groups on a quantum computer. The inherent structure of the Hilbert space imposed by the qubit architecture suggests to consider groups of order 2^n first (where n is the number of qubits). As an example, fast quantum Fourier transforms for all 4 classes of non-abelian 2-groups with cyclic normal subgroup of index 2 are explicitly constructed in terms of quantum circuits. The (quantum) complexity of the Fourier transform for these groups of size 2^n is O(n^2) in all cases.

arXiv:quant-ph/9807064Jul 22, 19980 citations

Highly-efficient quantum Fourier transformations for certain non-Abelian groups

Edison M. Murairi, M. Sohaib Alam, Henry Lamm +2 more

Quantum Fourier transformations are an essential component of many quantum algorithms, from prime factoring to quantum simulation. While the standard Abelian QFrT is well studied, important variants corresponding to non-Abelian groups of interest have seen less development. In particular, fast non-Abelian Fourier transformations are important components for both quantum simulations of field theories as well as approaches to the non-Abelian hidden subgroup problem. In this work, we present fast quantum Fourier transformations for a number of non-Abelian groups of interest for high energy physics, $\mathbb{B}\mathbb{T}$ , $\mathbb{B}\mathbb{O}$ , $6\mathrm{\ensuremath{\Delta}}(27)$, $\mathrm{\ensuremath{\Delta}}(54)$, and $\mathrm{\ensuremath{\Sigma}}(36\ifmmode\times\else\texttimes\fi{}3)$. For each group, we derive explicit quantum circuits and estimate resource scaling for fault-tolerant implementations. Our work shows that the development of a fast Fourier transformation can substantively reduce simulation costs by an up to three orders of magnitude for the finite groups that we have investigated.Quantum Fourier transformations are an essential component of many quantum algorithms, from prime factoring to quantum simulation. While the standard Abelian QFrT is well studied, important variants corresponding to non-Abelian groups of interest have seen less development. In particular, fast non-Abelian Fourier transformations are important components for both quantum simulations of field theories as well as approaches to the non-Abelian hidden subgroup problem. In this work, we present fast quantum Fourier transformations for a number of non-Abelian groups of interest for high energy physics, $\mathbb{B}\mathbb{T}$, $\mathbb{B}\mathbb{O}$, $6\mathrm{\ensuremath{\Delta}}(27)$, $\mathrm{\ensuremath{\Delta}}(54)$, and $\mathrm{\ensuremath{\Sigma}}(36\ifmmode\times\else\texttimes\fi{}3)$. For each group, we derive explicit quantum circuits and estimate resource scaling for fault-tolerant implementations. Our work shows that the development of a fast Fourier transformation can substantively reduce simulation costs by an up to three orders of magnitude for the finite groups that we have investigated.

Physical review. D/Physical review. D.Oct 1, 202414 citations

Quantum Fourier transform over symmetric groups — improved result

Yasuhito Kawano, Hiroshi Sekigawa

Journal of Symbolic ComputationNov 5, 201512 citations

Quantum Fourier Transform and Its Applications

Weng-Long Chang, Athanasios V. Vasilakos

Studies in big dataDec 21, 20202 citations

Efficient Quantum Transforms

Peter Høyer

Quantum mechanics requires the operation of quantum computers to be unitary, and thus makes it important to have general techniques for developing fast quantum algorithms for computing unitary transforms. A quantum routine for computing a generalized Kronecker product is given. Applications include re-development of the networks for computing the Walsh-Hadamard and the quantum Fourier transform. New networks for two wavelet transforms are given. Quantum computation of Fourier transforms for non-Abelian groups is defined. A slightly relaxed definition is shown to simplify the analysis and the networks that computes the transforms. Efficient networks for computing such transforms for a class of metacyclic groups are introduced. A novel network for computing a Fourier transform for a group used in quantum error-correction is also given.Quantum mechanics requires the operation of quantum computers to be unitary, and thus makes it important to have general techniques for developing fast quantum algorithms for computing unitary transforms. A quantum routine for computing a generalized Kronecker product is given. Applications include re-development of the networks for computing the Walsh-Hadamard and the quantum Fourier transform. New networks for two wavelet transforms are given. Quantum computation of Fourier transforms for non-Abelian groups is defined. A slightly relaxed definition is shown to simplify the analysis and the networks that computes the transforms. Efficient networks for computing such transforms for a class of metacyclic groups are introduced. A novel network for computing a Fourier transform for a group used in quantum error-correction is also given.

arXiv:quant-ph/9702028Feb 12, 199777 citations

\mathbb{B}\mathbb{T}

\mathbb{B}\mathbb{O}

, $6\mathrm{\ensuremath{\Delta}}(27)$, $\mathrm{\ensuremath{\Delta}}(54)$, and $\mathrm{\ensuremath{\Sigma}}(36\ifmmode\times\else\texttimes\fi{}3)$. For each group, we derive explicit quantum circuits and estimate resource scaling for fault-tolerant implementations. Our work shows that the development of a fast Fourier transformation can substantively reduce simulation costs by an up to three orders of magnitude for the finite groups that we have investigated.