ACM Symposium on Theory of Computing (STOC)

Quantum computation of Fourier transforms over symmetric groups

Robert Beals

Published Jan 1, 1997• 140 citations

Abstract

Many algorithmic developments in quantum complexity theory, including Shor's celebrated algorithms for factoring and discrete logs, have made use of Fourier transforms over abelian groups.That is, at some point in the computation, the macline is in a superposition of states corresponding to elements of a finite abelian group G, and in quantum polynomial time (i.e., polynomial in log IGI), the machine is transformed according to the Fourier transform to a superposition of states corresponding to the irreducible representations of G.We give a quantum polynomial time algorithm for the Fourier transform for the symmetric groups Sn, adapting results obtained by Clausen and Diaconis-Rockmore to the quantum setting.

DOI: 10.1145/258533.258548

Related papers

Quantum Fourier Transform over Symmetric Groups

Yasuhito Kawano, Hiroshi Sekigawa

This paper improves the main result in our paper "Quantum Fourier Transform over Symmetric Groups, Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 227--234, Northeastern University, Boston, USA (June 26-29, 2013)." In that paper, we presented an O(n4) quantum Fourier transform (QFT) algorithm over symmetric group Sn, which was faster than the existing algorithm. This paper proposes an O(n3 log n) QFT algorithm over Sn by relieving bottlenecks of our previous algorithm.

ACM communications in computer algebraFeb 5, 20152 citations

The Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem

Lisa Hales

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.

arXiv:quant-ph/0212002Nov 30, 200225 citations

Quantum measurements and the Abelian Stabilizer Problem

Alexei Kitaev

We present a polynomial quantum algorithm for the Abelian stabilizer problem which includes both factoring and the discrete logarithm. Thus we extend famous Shor's results. Our method is based on a procedure for measuring an eigenvalue of a unitary operator. Another application of this procedure is a polynomial quantum Fourier transform algorithm for an arbitrary finite Abelian group. The paper also contains a rather detailed introduction to the theory of quantum computation.

Nov 20, 1995442 citations

Quantum measurements and the Abelian Stabilizer Problem

A. Yu. Kitaev

arXiv:quant-ph/9511026Nov 20, 1995472 citations

Fast quantum algorithms for approximating some irreducible representations of groups

Stephen P. Jordan

We consider the quantum complexity of estimating matrix elements of unitary irreducible representations of groups. For several finite groups including the symmetric group, quantum Fourier transforms yield efficient solutions to this problem. Furthermore, quantum Schur transforms yield efficient solutions for certain irreducible representations of the unitary group. Beyond this, we obtain poly(n)-time quantum algorithms for approximating matrix elements from all the irreducible representations of the alternating group A_n, and all the irreducible representations of polynomial highest weight of U(n), SU(n), and SO(n). These quantum algorithms offer exponential speedup in worst case complexity over the fastest known classical algorithms. On the other hand, we show that average case instances are classically easy, and that the techniques analyzed here do not offer a speedup over classical computation for the estimation of group characters.

arXiv:0811.0562Nov 4, 20088 citations

Quantum algorithms and the Fourier transform

Richard Jozsa

The quantum algorithms of Deutsch, Simon and Shor are described in a way which highlights their dependence on the Fourier transform. The general construction of the Fourier transform on an Abelian group is outlined and this provides a unified way of understanding the efficacy of the algorithms. Finally we describe an efficient quantum factoring algorithm based on a general formalism of Kitaev and contrast its structure to the ingredients of Shor’s algorithm.

Jan 1, 1997149 citations