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.
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, 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.
The quantum Fourier transform (QFT) has emerged as the primary tool in quantum algorithms which achieve exponential advantage over classical computation and lies at the heart of the solution to the abelian hidden subgroup problem, of which Shor's celebrated factoring and discrete log algorithms are a special case. We begin by addressing various computational issues surrounding the QFT and give improved parallel circuits for both the QFT over a power of 2 and the QFT over an arbitrary cyclic group. These circuits are based on new insight into the relationship between the discrete Fourier transform over different cyclic groups. We then exploit this insight to extend the class of hidden subgroup problems with efficient quantum solutions. First we relax the condition that the underlying hidden subgroup function be distinct on distinct cosets of the subgroup in question and show that this relaxation can be solved whenever G is a finitely-generated abelian group. We then extend this reasoning to the hidden cyclic subgroup problem over the reals, showing how to efficiently generate the bits of the period of any sufficiently piecewise-continuous function on R. Finally, we show that this problem of period-finding over R, viewed as an oracle promise problem, is strictly harder than its integral counterpart. In particular, period-finding over R lies outside the complexity class MA, a class which contains period-finding over the integers.
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, BO, Δ(27), Δ(54), and Σ(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.
Quantum Fourier transforms (QFTs) are essential primitives in quantum algorithms. While abelian groups admit efficient QFT circuits, with circuit size polynomial in the logarithm of the group order, efficient constructions are known for relatively few non-abelian families. We develop two new approaches to QFT circuit construction, based on Mackey theory and Clifford theory, respectively, and use them to show exponential improvement in circuit cost for specific group families. Using the Mackey-theoretic approach, we obtain explicit quantum circuits for the QFT over GL2(Fq) that scale polynomially in logq, rather than polynomially in q. Using the Clifford-theoretic approach, we obtain QFT circuits for wreath products F≀Sn, whose cost depends on the cost of a QFT over F and the size of its representation registers. This removes the restriction ∣F∣=poly(n) required by previous generic constructions and can yield exponential improvements when F itself has an efficient QFT. Together, these methods provide new systematic tools to construct QFTs for broad classes of finite groups.
The quantum Fourier transform (QFT) is the principal algorithmic tool underlying most efficient quantum algorithms. We present a generic framework for the construction of efficient quantum circuits for the QFT by ``quantizing'' the separation of variables technique that has been so successful in the study of classical Fourier transform computations. Specifically, this framework applies the existence of computable Bratteli diagrams, adapted factorizations, and Gel'fand-Tsetlin bases to offer efficient quantum circuits for the QFT over a wide variety a finite Abelian and non-Abelian groups, including all group families for which efficient QFTs are currently known and many new group families. Moreover, the method gives rise to the first subexponential-size quantum circuits for the QFT over the linear groups GL_k(q), SL_k(q), and the finite groups of Lie type, for any fixed prime power q.
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.