Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1712.01350

Generalization of Quantum Fourier Transformation

Changpeng Shao

Published Dec 1, 2017• 0 citations
arXivHTMLPDF

Abstract

Quantum Fourier transformation is important in many quantum algorithms. In this paper, we generalize quantum Fourier transformation over the Abelian group $\mathbb{Z}_N$ from two different points to get more efficient unitary transformations. The obtained unitary transformations are given in concise and explicit formula which can be used directly. A relationship between the generalized quantum Fourier transformation and the dihedral hidden subgroup problem are discussed in this paper. This may lead a way to solve the dihedral hidden subgroup problem. The second goal of this paper is to give an explicit formula of quantum Haar transformation.

DOI
10.48550/arxiv.1712.01350

Related papers

Quantum algorithms and the fourier transform

Lawrence Ip, Umesh V. Vazirani

The search for practical problems that can be solved exponentially faster on a quantum computer is one of the primary goals in research into algorithms for quantum computers. It has long been known that such speedups are only possible for highly structured problems. We consider two problems with algebraic structure: (1) the hidden subgroup problem, where we have an unknown subgroup, a function that is constant on cosets of the subgroup, and the task is to find the unknown subgroup; (2) the hidden shift problem, where we have an unknown element of a group, a function that has been shifted by that group element, and the task is to find the unknown group element. We show that the Fourier transform is intimately connected to both these problems. This is because the Fourier transform respects group symmetries. For the hidden subgroup problem, we introduce the idea of using information theoretic techniques to design quantum algorithms. This consists of first finding an optimal set of measurements for distinguishing between different subgroups, followed by attempts to implement this set of measurements. We show that the standard algorithm for the abelian hidden subgroup problem is optimal. For the nonabelian hidden subgroup problem, the optimal measurements respect the Fourier transform in that they can be implemented by first performing a Fourier transform on each coset state, measuring the name of the irreducible representation for each state, followed by a joint measurement over the resulting lower dimensional space. This shows that the “strong standard method” cannot be used to implement the optimal set of measurements. For some instances of the hidden shift problem, we give a quantum algorithms that are exponentially faster than the best known classical algorithm. The algorithms make use of the Fourier transform in a way that may be interpreted as solving a deconvolution problem. As evidence of hardness, we give a reduction from algebraically homomorphic cryptosystems to the shifted Legendre symbol problem. This is an example of a problem which admits an exponential quantum speedup yet is not an instance of the abelian hidden subgroup problem.

•Jan 1, 2004•0 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.

Physical review. D/Physical review. D.•Oct 1, 2024•14 citations

The Hidden Subgroup Problem for Generalized Quaternions

Julia Tumasova Upton

The hidden subgroup problem is a pivotal problem in quantum computation since it reflects the structure of tasks for which quantum algorithms significantly outperform classical algorithms. In this paper, a quantum algorithm that solves the hidden subgroup problem over the generalized quaternion group is developed. The algorithm employs the abelian quantum Fourier transform and Kuperberg sieve to reveal the hidden subgroup.

International Conference on Quantum, Nano and Micro Technologies (ICQNM)•Feb 1, 2010•1 citation

The hidden subgroup problem for generalized quaternions

Julia Tumasova Upton

The hidden subgroup problem is a pivotal problem in quantum computation since it reflects the structure of tasks for which quantum algorithms significantly outperform classical algorithms. In this dissertation, a quantum algorithm that solves the hidden subgroup problem over the generalized quaternion group is developed. The algorithm employs the abelian quantum Fourier transform and Kuperberg sieve to reveal the hidden subgroup. (Published By University of Alabama Libraries)

•Jan 1, 2009•0 citations

Highly-efficient quantum Fourier transformations for some nonabelian groups

Murairi, Edison M., 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 QFT is well-studied, important variants corresponding to \emph{nonabelian} groups of interest have seen less development. In particular, fast nonabelian Fourier transformations are important components for both quantum simulations of field theories as well as approaches to the nonabelian hidden subgroup problem. In this work, we present fast quantum Fourier transformations for a number of nonabelian groups of interest for high energy physics, $\mathbb{BT}$, $\mathbb{BO}$, $Δ(27)$, $Δ(54)$, and $Σ(36\times3)$. 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 up to three orders of magnitude for the finite groups that we have investigated.

arXiv:2408.00075•Jul 31, 2024•0 citations

Dihedral Hidden Subgroup Problem: A Survey

Hirotada Kobayashi, François Le Gall

After Shor's discovery of an efficient quantum algorithm for integer factoring, hidden subgroup problems play a central role in developing efficient quantum algorithms. In spite of many intensive studies, no efficient quantum algorithms are known for hidden subgroup problems for many non-Abelian groups. Of particular interest are the hidden subgroup problems for the symmetric group and for the dihedral group, because an efficient algorithm for the former implies an efficient solution to the graph isomorphism problem, and that for the latter essentially solves a certain lattice-related problem whose hardness is assumed in cryptography. This paper focuses on the latter case and gives a comprehensive survey of known facts related to the dihedral hidden subgroup problem.

IPSJ Digital Courier•Jan 1, 2005•7 citations
Quantum Fourier transformation is important in many quantum algorithms. In this paper, we generalize quantum Fourier transformation over the Abelian group ZN\mathbb{Z}_NZN​ from two different points to get more efficient unitary transformations. The obtained unitary transformations are given in concise and explicit formula which can be used directly. A relationship between the generalized quantum Fourier transformation and the dihedral hidden subgroup problem are discussed in this paper. This may lead a way to solve the dihedral hidden subgroup problem. The second goal of this paper is to give an explicit formula of quantum Haar transformation.
The search for practical problems that can be solved exponentially faster on a quantum computer is one of the primary goals in research into algorithms for quantum computers. It has long been known that such speedups are only possible for highly structured problems. We consider two problems with algebraic structure: (1) the hidden subgroup problem, where we have an unknown subgroup, a function that is constant on cosets of the subgroup, and the task is to find the unknown subgroup; (2) the hidden shift problem, where we have an unknown element of a group, a function that has been shifted by that group element, and the task is to find the unknown group element. We show that the Fourier transform is intimately connected to both these problems. This is because the Fourier transform respects group symmetries. For the hidden subgroup problem, we introduce the idea of using information theoretic techniques to design quantum algorithms. This consists of first finding an optimal set of measurements for distinguishing between different subgroups, followed by attempts to implement this set of measurements. We show that the standard algorithm for the abelian hidden subgroup problem is optimal. For the nonabelian hidden subgroup problem, the optimal measurements respect the Fourier transform in that they can be implemented by first performing a Fourier transform on each coset state, measuring the name of the irreducible representation for each state, followed by a joint measurement over the resulting lower dimensional space. This shows that the “strong standard method” cannot be used to implement the optimal set of measurements. For some instances of the hidden shift problem, we give a quantum algorithms that are exponentially faster than the best known classical algorithm. The algorithms make use of the Fourier transform in a way that may be interpreted as solving a deconvolution problem. As evidence of hardness, we give a reduction from algebraically homomorphic cryptosystems to the shifted Legendre symbol problem. This is an example of a problem which admits an exponential quantum speedup yet is not an instance of the abelian hidden subgroup problem.
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, BT\mathbb{B}\mathbb{T}BT, BO\mathbb{B}\mathbb{O}BO, $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 QFT is well-studied, important variants corresponding to \emph{nonabelian} groups of interest have seen less development. In particular, fast nonabelian Fourier transformations are important components for both quantum simulations of field theories as well as approaches to the nonabelian hidden subgroup problem. In this work, we present fast quantum Fourier transformations for a number of nonabelian groups of interest for high energy physics, BT\mathbb{BT}BT, BO\mathbb{BO}BO, Δ(27)Δ(27)Δ(27), Δ(54)Δ(54)Δ(54), and Σ(36×3)Σ(36\times3)Σ(36×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 up to three orders of magnitude for the finite groups that we have investigated.
After Shor's discovery of an efficient quantum algorithm for integer factoring, hidden subgroup problems play a central role in developing efficient quantum algorithms. In spite of many intensive studies, no efficient quantum algorithms are known for hidden subgroup problems for many non-Abelian groups. Of particular interest are the hidden subgroup problems for the symmetric group and for the dihedral group, because an efficient algorithm for the former implies an efficient solution to the graph isomorphism problem, and that for the latter essentially solves a certain lattice-related problem whose hardness is assumed in cryptography. This paper focuses on the latter case and gives a comprehensive survey of known facts related to the dihedral hidden subgroup problem.