Fast Quantum Fourier Transforms for a Class of Non-Abelian Groups

Markus Püschel, Martin Rötteler, Thomas BethAAECC 1999 · DOI

TL;DR

This paper presents a constructive algorithm for building fast quantum Fourier transforms (QFTs) for a specific class of non-abelian 2-groups. The authors demonstrate that these QFTs can be implemented with a computational complexity of $O(\log^2 |G|)$, matching the efficiency of QFTs for abelian groups, and provide explicit quantum circuit constructions for these groups.

What Problem Does This Paper Address?

The quantum Fourier transform (QFT) is a fundamental building block for many quantum algorithms, including Shor's factoring algorithm. While efficient QFTs for cyclic groups (like $Z_n$) are well-established, generalizing them to arbitrary finite groups, especially non-abelian ones, presents a significant challenge. This paper tackles the problem of constructing efficient QFTs for a class of non-abelian 2-groups, which are groups whose order is a power of 2. The goal is to achieve a computational complexity comparable to that of abelian groups, which is $O(n^2)$ for $Z_{2^n}$, where $n$ is the number of qubits.

Methods

The authors employ an algebraic approach rooted in representation theory. They leverage a recursive algorithm, derived from decomposing a group's regular representation along a composition series, to construct the QFT. This algorithm, presented in Section 4, is general for any solvable group and serves as a foundation for quantum QFTs. The core of the method involves:

  • Decomposition along Composition Series: The algorithm breaks down the problem of constructing a QFT for a group $G$ by first considering a normal subgroup $N$ of prime index $p$, and then extending the representations from $N$ to $G$.
  • Representation Theory: Key concepts like irreducible representations, extensions of representations, and inner conjugates are used to define the structure of the QFT.
  • Quantum Circuit Construction: The paper translates the algebraic decomposition into concrete quantum circuits using elementary gates (local unitaries and controlled-NOT gates). This involves constructing specific matrices (A, P, M, D, C) that represent different stages of the decomposition and then realizing them as quantum circuits.
  • Focus on 2-Groups: The general algorithm is then specialized for 2-groups, where the structure of the quantum computer (qubits) aligns well with the tensor products arising in the decomposition.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unified Approach for Non-Abelian 2-Groups: The paper demonstrates that a single algorithmic framework (based on representation theory and recursive decomposition) can be used to construct efficient QFTs for a diverse class of non-abelian 2-groups.
  • $O(\log^2 |G|)$ Complexity Achieved: For the considered non-abelian 2-groups, the QFTs are shown to have a computational complexity of $O(\log^2 |G|)$, which is asymptotically optimal and matches the efficiency of QFTs for abelian groups. This is a significant result as it suggests that efficient QFTs are not limited to abelian structures.
  • Explicit Quantum Circuit Designs: The paper goes beyond theoretical construction by providing explicit quantum circuits for these QFTs, making the results directly applicable to quantum hardware.
  • Connection to Classical Algorithms: The presented method builds upon classical algorithms for fast Fourier transforms, highlighting the interplay between classical and quantum computational approaches.

Key Results

The paper successfully constructs fast quantum Fourier transforms for four specific isomorphism types of non-abelian 2-groups of order $2^{n+1}$ (for $n \ge 3$): the dihedral group ($D_{2^{n+1}}$), the quaternion group ($Q_{2^{n+1}}$), and two related groups ($QP_{2^{n+1}}$ and $QD_{2^{n+1}}$). For all these groups, the QFT can be performed on a quantum computer with $O(\log^2 |G|)$ elementary operations. The paper provides detailed descriptions of the quantum circuits required for these transformations, including specific circuits for permutation and Twiddle matrices.

Limitations and Future Work

  • Class of Groups: The presented algorithm and constructions are specifically for a class of non-abelian 2-groups. While this is a significant step, it does not cover all possible non-abelian groups.
  • Implementation Complexity: While the theoretical complexity is $O(\log^2 |G|)$, the actual implementation of certain permutation and block diagonal matrices can be complex and requires careful circuit design, which the authors have addressed for the specific groups.
  • Generalization: The authors suggest that the recursive formula from Theorem 4.1 could be used to construct QFTs for other classes of groups and for realizing signal transforms via symmetry-based decomposition. This indicates a clear path for future research into a broader range of groups.
  • Practical Realization: The paper mentions that the Fourier transforms have been implemented in GAP using the AREP package, suggesting future work on practical realization and testing of these QFTs.

Summary updated

BibTeX
@inproceedings{puschel1999fast,
  author = {Markus Püschel and Martin Rötteler and Thomas Beth},
  title = {{Fast Quantum Fourier Transforms for a Class of Non-Abelian Groups}},
  booktitle = {AAECC},
  year = {1999},
  doi = {10.1007/3-540-46796-3\_15},
}
Figure