Overview
The Quantum Fourier Transform (QFT) is identified as a fundamental component in quantum algorithms. While efficient QFT circuits exist for abelian groups, exhibiting a circuit size polynomial in the logarithm of the group order, efficient constructions for non-abelian group families are relatively limited. This research introduces two distinct approaches for QFT circuit construction, grounded in Mackey theory and Clifford theory, respectively.
Research Context
QFTs are integral to quantum algorithmic design. For abelian groups, established methods yield QFT circuits whose size scales polynomially with the logarithm of the group order $(\log N)$. However, for non-abelian groups, the availability of efficient construction methods has been sparse. Generic constructions for certain non-abelian structures, such as wreath products $F\wr S_n$, previously imposed restrictions, specifically that the size of the group $F$ be polynomial in $n$ (i.e., $|F|=\operatorname{poly}(n)$).
Approach
This work develops two novel methodologies for QFT circuit construction:
- Mackey-theoretic approach: This method is applied to construct explicit quantum circuits for the QFT over the general linear group $\mathrm{GL}_2(F_q)$.
- Clifford-theoretic approach: This method is utilized to construct QFT circuits for wreath products $F\wr S_n$.
Findings
The application of these new approaches yielded specific results for distinct non-abelian group families:
- $\mathrm{GL}_2(F_q)$ QFTs: Using the Mackey-theoretic approach, explicit quantum circuits for the QFT over $\mathrm{GL}_2(F_q)$ were obtained. These circuits demonstrate a scaling cost that is polynomial in $\log q$, a significant improvement over prior constructions that scaled polynomially in $q$. This represents an exponential improvement in circuit cost.
- Wreath Product $F\wr S_n$ QFTs: The Clifford-theoretic approach facilitated the construction of QFT circuits for wreath products $F\wr S_n$. The cost of these circuits is dependent on two factors: the cost of a QFT over $F$, and the size of its representation registers. A key outcome of this approach is the removal of the previous restriction that $|F|=\operatorname{poly}(n)$ for generic constructions. This removal can lead to exponential improvements in cases where $F$ itself possesses an efficient QFT.
Collectively, these methods are identified as new systematic tools for constructing QFTs across a broad spectrum of finite groups.
Why This Matters
Quantum Fourier Transforms are foundational elements in quantum algorithms. The development of these new methodologies provides systematic tools to construct efficient QFTs for a broader range of finite groups, including non-abelian ones, where efficient constructions were previously limited. This advancement offers exponential improvements in circuit cost for specific group families, potentially enhancing the practicality and scalability of quantum algorithms that rely on QFTs.