Quantum computation of Fourier transforms over symmetric groups

Robert Beals University of Arizona Department of Mathematics P.O. Box 210089 617 N. Santa Rita Ave. Tucson, AZ 85721-0089

          e-mail: beals@math.arizona.edu

December 1, 1997

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 machine 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 |G|), 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 S_{n}, adapting results obtained by Clausen and Diaconis–Rockmore to the quantum setting.

1 Introduction

One of the most ubiquitous tools in designing algorithms for quantum computation has been the Fourier transform for finite abelian groups [3, 4, 6, 11, 10]. The Fourier transform is used to solve the following hidden subgroup problem. Let (G, +) be a finite abelian group, and let H be an unknown subgroup of G. Let f be a function which is constant on cosets of H, i.e., for all g ∈ G and h ∈ H, we have f(g + h) = f(g). We wish to find generators for the subgroup H. If we suppose in addition that f(g_{1}) = f(g_{2}) only when g_{1} − g_{2} ∈ H, then it is enough to be able to randomly sample the nonzero Fourier coefficients of the indicator functions of the level sets of f; with high probability, after log |G| trials, H is determined and can be found essentially by Gaussian elimination.

To use the Fourier transform in quantum computation, the machine is put into a superposition of states, one for each element of G, with equal amplitudes: the amplitude of having g written on the tape (for any g ∈ G) is 1/\sqrt{|G|}. Then, next to each g, the value of f(g) is written down, and a Fourier transform is performed (so in each state, a representation ρ of G and a value of y in the range of f are written on the tape). Then, the name of the representation is observed; the value ρ will be seen with amplitude proportional to the square of the ρ Fourier coefficient of the indicator function of f^{−1}(y). This amounts to randomly sampling the nonzero coefficients; each one gives a linear constraint on H, which is recovered after O(log |G|) iterations.

Motivated by the success of the Fourier transform in solving the hidden subgroup problem for abelian groups, we consider quantum Fourier transforms for general finite groups. We consider especially the symmetric groups, for which the hidden subgroup problem is as hard as graph isomorphism: Let Γ be a graph on n vertices, and define f(π) to be π(Γ) for π ∈ S_{n}. Then f is constant on cosets of the automorphism group of Γ. Computing automorphism groups is well-known to be as hard as graph isomorphism. While we are able to give a quantum polynomial time Fourier transform for the symmetric groups, the connection to the hidden subgroup problem is unclear. It remains open whether or not graph isomorphism has a quantum polynomial time solution.

The quantum Fourier transform algorithms for finite abelian groups are similar to the fast Fourier transform (FFT) algorithms for classical computers. In the classical case, G is a group of order n, and the input to the algorithm is an n-tuple of numbers representing a function f : G → ℂ. The Fourier transform f̂ is also an n-tuple of complex numbers (the Fourier coefficients of f), which requires n^{2} arithmetic steps to compute by a naive algorithm. For all abelian groups, and for various nonabelian groups, “fast” transforms are known, which require only n log^{c} n arithmetic steps for some constant c (depending on G).

Intuitively, it seems that whenever a classical fast transform exists, a quantum polynomial time transform should exist as well. Polynomial time means polynomial in log |G|, so if we can have |G| operations take place simultaneously by quantum parallelism, the quantum analog of a fast transform algorithm will take polynomial time.

We shall see that this intuition is valid in the case of symmetric groups, although there are some difficulties to be overcome. For one thing, it is not always apparent from the description of the fast transform how to compute its inverse (although it is now known that the two problems have the same complexity). In particular, individual steps of the transform algorithm are sometimes non-invertible, even though the function computed by the algorithm as a whole is invertible. However, in any quantum computation, each step is invertible: the matrix for the transformation from one superposition to the next is unitary, i.e., its conjugate transpose is its inverse. Therefore, before venturing into the quantum setting, we describe, in a way that makes the inverse transformation clear, the classical algorithm of Clausen and Diaconis–Rockmore [5, 8] for the FFT for the symmetric groups.

This paper is organized as follows. In Section 2, background material on Fourier transforms is given. In Section 3, we revisit the [5, 8] FFT algorithms. In Section 4, we summarize some essentials of quantum computation, and in Section 5, we present the quantum Fourier transform for the symmetric groups.

2 The Fourier transform and its inverse

We briefly review the relevant material from representation theory. We refer the reader to [7, 9] for a more complete treatment of this material.

Let G be a finite group of order N, and let f : G → ℂ be a function encoded in the natural way as an N-tuple of complex numbers. For an irreducible representation ρ of G, of dimension d_{ρ}, we define f̂(ρ) as

(\sqrt{\frac{d_{ρ}}{|G|}}) ∑_{g∈G} f(g) · ρ(g).  (1)

Two irreducible representations of G are equivalent if one may be obtained from the other by a change of basis. This is an equivalence relation, and it is known that each equivalence class contains a unitary representation. Let Ĝ denote a complete set of equivalence class representatives of the irreducible representations of G. It is known that |Ĝ| is equal to the number of conjugacy classes of G, and that

∑_{ρ∈_{G}} d_{ρ}^{2} = |G|.

If we know f̂(ρ) for all ρ ∈ Ĝ, then we may recover f as follows:

f(g) = (\frac{1}{\sqrt{|G|}}) ∑_{ρ∈_{G}}(\sqrt{d_{ρ}})Tr(f̂(ρ) · ρ(g^{−1})).  (2)

Note that both f and f̂ can be thought of as |G|-length vectors of complex numbers. If Ĝ consists of unitary representations, then the transformations (1) and (2) are unitary. The coefficients of \sqrt{|G|} and \sqrt{d_{ρ}} in equations (1) and (2) are sometimes rearranged so that no radical sign appears in either equation, but this makes the transformation non-unitary.

3 Classical computation of Fourier transforms

In this section we describe the “classical” FFT algorithms for nonabelian groups of Clausen [5] and Diaconis and Rockmore [8]. We assume throughout that all representations are unitary, so the Fourier transform is a unitary transformation.

Let H be a subgroup of G, of index n (in cases of interest, this is O(log |G|)). Then we may write G as a union of cosets of H:

G = ⋃_{k=1}^{n} Hτ_{k}.

The τ_{k} are a system of coset representatives for H in G. We wish to pick Ĝ, Ĥ, and representatives τ_{k} with the following properties:

1. For all ρ ∈ Ĝ, ρ|_{H} (ρ restricted to H) is block diagonal with the diagonal blocks coming from Ĥ.

2. Each ρ(τ_{k}) can be represented as a short (length n^{c} for some constant c) product of sparse matrices (each row and column has a bounded number of nonzero entries).

Note that property (2) applies to an infinite family of groups G.

For 1 ≤ k ≤ n, let f_{k} denote the following function from H to ℂ: h ↦ f(hτ_{k}). Recursively compute the FFT for H of each f_{k} (that is, compute f̂_{k}(σ) for all σ ∈ Ĥ).

Extend f_{k} to G by setting f_{k}(g) = 0 for g ∉ H. Then, for any ρ ∈ Ĝ, f̂_{k}(ρ) is block diagonal by property (1). The diagonal blocks correspond to elements of Ĥ; the value of a block corresponding to σ ∈ Ĥ is

(\sqrt{\frac{d_{ρ}|H|}{d_{σ}|G|}}) f̂_{k}(σ).

Now we are nearly done: for any ρ ∈ Ĝ, we have

f̂(ρ) = ∑_{k=1}^{n} f̂_{k}(ρ) · ρ(τ_{k}).

By property (2), multiplication by ρ(τ_{k}) can be performed by multiplying a sequence of n^{c} sparse matrices, each in time O(d_{ρ}^{2}). For each ρ, the number of arithmetic operations is O(n^{c+1}d_{ρ}^{2}), so the total time for computing the transform is the time for the recursive calls plus

O(n^{c+1} ∑ ρ ∈ Ĝd_{ρ}^{d}) = O(n^{c+1}|G|).

For many groups, n = O(log |G|), and the total time, including the recursive calls, is |G| times some log |G| factors.

For the computation of the inverse transform, instead of using equation (2) directly, the Fourier transform algorithm is essentially run backwards. The difficulty lies in decomposing f̂(ρ) as the sum of the f̂_{k}(ρ) · ρ(τ_{k}). We describe briefly how to recover f̂_{k}(ρ): Assume that τ_{k} = 1 (otherwise for each ρ ∈ Ĝ, multiply f̂(ρ) by ρ(τ_{k}^{−1})). Let f^{1} denote f_{k}, and let f^{0} denote f − f_{k}. Then f^{1} is zero outside of H, and f^{0} is zero on H; both functions are arbitrary with respect to those properties. We show how to compute f̂^{1} from f̂:

Recall that that f̂^{1}(ρ) is block diagonal, with the diagonal blocks corresponding to representations σ ∈ Ĥ. There is no reason that f̂(ρ) should be block diagonal; however we may ignore the entries of f̂(ρ) which do not lie in blocks on the diagonal. This amounts to replacing f with a different function without affecting f^{1}. So assume that for all ρ ∈ Ĝ, f̂(ρ) is in block diagonal form.

Let σ ∈ Ĥ. We wish to find f̂^{1}(σ). Consider all the σ-blocks that occur in the f̂(ρ) for ρ ∈ Ĝ: let A_{1}, …, A_{m} be the diagonal blocks of f̂ corresponding to σ, and let ρ_{1}, …, ρ_{m} ∈ Ĝ be the representations in which they occur. Note that the ρ_{i} are not necessarily distinct. If f^{0} were identically zero, then we would have, for any i, that

f̂^{1}(σ) = (\sqrt{\frac{d_{σ}|G|}{d_{ρ_{i}}|H|}}) A_{i}.

It turns out that in general f̂^{1} is a weighted average of these matrices. Since f^{0} is orthogonal to the space of functions which are zero outside of H, and the Fourier transform is unitary, we have:

f̂^{1}(σ) = ∑_{i=1}^{m} (\sqrt{\frac{d_{ρ_{i}}|H|}{d_{σ}|G|}}) A_{i}.

Thus, we can from f̂ calculate the f̂_{k}.

In the case of the symmetric group G = S_{n}, the particular choice of Ĝ for the [5, 8] algorithm is the Young Orthogonal Form (they also give algorithms for the Young Seminormal Form, which is not unitary). H is chosen to be S_{n−1}, and is treated recursively. The total time is |G| times a polynomial in n.

4 Preliminaries from quantum computing

We summarize some important results on quantum computation [3, 12].

At any time, a quantum computer is in a superposition of states. If the states are described by boolean strings of length n, then the instantaneous description of the machine is the vector in ℂ^{2^{n}} of the probability amplitudes of the various states. For x ∈ {0, 1}^{n}, let e_{x} denote the standard basis vector corresponding to the state x. Sometimes it is convenient to split the string into two pieces; if x is the concatenation x_{1}x_{2}, then e_{x} is the tensor product e_{x_{1}} ⊗ e_{x_{2}}. If x is an all-zero string, then we call e_{x} the zero state of length |x|.

For vectors v, w, let ⟨v, w⟩ denote the Hermitian inner product

∑_{x∈\{0,1\}^{n}} v_{x}\overline{w_{x}},

where v_{x} and w_{x} are the e_{x} coefficients of v and w, and the bar denotes complex conjugation. The unitary transformations are exactly those which preserve the inner product ⟨·⟩. Two vectors are orthogonal if their inner product is zero.

A quantum computation consists of a unitary transformation T followed by an observation of the machine state. The transformation T is the product of the transformations which are performed at each step of the computation. At any step, the transformation which is performed is the tensor product of a unitary transformation dealing with a constant number of bits of the machine state with the identity transformation on the remaining bits of the machine state. The final observation of the machine state sees state x with probability v_{x}\overline{v_{x}}, where v is the final instantaneous description of the machine. Note that every step of a quantum computation is reversible, except for the observation.

The above description of quantum computation is non-uniform, and corresponds to quantum circuits [12]. The algorithm presented here is uniform, and can be carried out on a quantum Turing machine [3], which is equivalent to uniform quantum circuits [12]. Instead of giving a detailed circuit or machine description of the algorithm, we give a high-level description, appealing to the following general facts from the theory of quantum computation:

Lemma 4.1 Let F : {0, 1}^{∗} → {0, 1}^{∗} be a bijection such that both F and F^{−1} are computable in polynomial time. Then there is a quantum polynomial time machine which, when initialized with tape contents x, x ∈ {0, 1}^{∗}, terminates with tape contents F (x).

Lemma 4.2 Let F : {0, 1}^{∗} → {0, 1} be computable in polynomial time. Then there is a quantum polynomial time machine which, when initialized with tape contents x, x ∈ {0, 1}^{∗}, terminates with (x, F (x)) on its tape.

These two Lemmas are actually true even if the word “quantum” is replaced by the word “reversible” [1]. Since any reversible Turing machine is also a quantum Turing machine, the Lemmas are also true as stated.

The following Lemma is not used directly, but the technique used is at the heart of the “hard part” of the quantum Fourier algorithm.

Lemma 4.3 Let v ∈ ℂ^{2^{n}} have unit length. Suppose that a quantum computer can in t steps, starting in the zero state e_{0^{n}}, be put in the superposition of states v. Then the following can be effected in 2t + n + 1 steps: starting from a superposition of states w ∈ ℂ^{2^{n}}, the machine can be put in the superposition

w_{0} ⊗ e_{0} + ⟨v, w⟩e_{0^{n}} ⊗ e_{1} ∈ C^{2^{n+1}},

where w_{0} is orthogonal to v and w = w_{0} + ⟨v, w⟩v.

Proof: We describe the actions required of the machine. Let T denote the t-step transformation taking e_{0^{n}} to v, The machine first performs T^{−1}. Then, using Lemma 4.2, if the n-bit string on the tape is 0^{n}, a 1 is written down in position n + 1, otherwise a 0 is written down (this is done for all states in the superposition—no observation is performed). Finally, if there is a 0 in position n + 1, then the machine performs T, otherwise, nothing is done for t steps.

We now show that the machine is in the desired superposition: Let w_{0} = w − ⟨v, w⟩v. Then after performing T^{−1}, the machine is in

T^{−1}w = T^{−1}w_{0} + ⟨v, w⟩T^{−1}v = T^{−1}w_{0} + ⟨v, w⟩e_{0^{n}}.

By construction, w_{0} is orthogonal to v. Since T^{−1} is unitary, T^{−1}w_{0} is orthogonal to e_{0^{n}}. In other words, the probability amplitude of having tape contents 0^{n} in w_{0} is zero. Therefore, the superposition after applying Lemma 4.2 is

(T^{−1}w_{0}) ⊗ e_{0} + ⟨v, w⟩e_{0^{n}} ⊗ e_{1}.

Finally, T is applied to the ℂ^{2^{n}} ⊗ e_{0} subspace, yielding

w_{0} ⊗ e_{0} + ⟨v, w⟩e_{0^{n}} ⊗ e_{1}

as desired.□

5 Quantum Fourier transforms

We sketch the quantum Fourier transform for G = S_{n}. Let H denote S_{n−1}, the stabilizer in G of the point 1. The coset representatives τ_{k} can be arbitrary permutations such that τ_{k} takes point 1 to point k. For each τ_{k}, we can easily find an expression of τ_{k} as the product of polynomially many transpositions of the form (j j +1), which are represented by sparse matrices in Young Orthogonal Form.

Initially, the machine is in a superposition of states, where the permutation g is written on the tape with amplitude f(g). First, the machine factors g (for each g independently) as a product hτ_{k} for h ∈ H. Since the map g ↦ (h, τ_{k}) is invertible, by Lemma 4.1 we can actually replace the tape contents g with (h, τ_{k}). In order to write τ_{k} on the tape, we need only write the integer k, since the τ_{k} are fixed beforehand. So at this point, we have that (h, k) is written on the tape with amplitude f(hτ_{k}).

Now the computer will ignore the part of the tape that contains the integer k, and perform, recursively, the Fourier transform for H. Ignoring k has the effect of performing n transforms on H in parallel; the computations for different values of k cannot interfere with each other (even though the value of k is not referred to by the computation). At this point, the tape contains (σ, i, j, k) with amplitude f̂_{k}(σ)_{ij} (i.e., the amplitude is the (i, j) entry of the matrix f̂_{k}(σ)), where f_{k} is as in Section 3.

From this point on, in every state, the tape will contain the name of a representation of either G or H. There is no danger of confusion; the representations of G are labeled with partitions of n, and the representations of H are labeled with the partitions of n − 1. At this point, the states with representations of G have zero amplitude, but this will change. At any point, for ρ ∈ Ĝ, let A_{ρ} denote the matrix whose (i, j) entry is the amplitude of (ρ, i, j). Note that, for 1 ≤ k ≤ n and σ ∈ Ĥ, the matrix whose (i, j) entry is the amplitude of (σ, i, j, k) is simply f̂_{k}(σ).

For k = 1, …, n, we wish to replace A_{ρ} with A_{ρ} + f̂_{k}(ρ)ρ(τ_{k}), simultaneously, for all ρ ∈ Ĝ. We do this by first multiplying A_{ρ} on the right by ρ(τ_{k}^{−1}). Next follows the most difficult step of the algorithm: we add f̂_{k}(ρ) to A_{ρ}. Finally we multiply on the right by ρ(τ_{k}). Adding f̂_{k}(ρ) to A_{ρ} has the side effect of zeroing out the amplitude of (σ, i, j, k).

Before sketching how the addition is performed, we comment on the multiplication by ρ(τ_{k}) and its inverse. Note that τ_{k} is a short product of sparse unitary matrices. Recall that the matrix entries of A_{ρ} are not written down anywhere. They are simply the amplitudes of the state that has (ρ, i, j) written down on the tape. The matrix ρ(τ_{k}) is broken down as a product of sparse matrices, where for any row or column it is easy to compute the (one or two) nonzero entries. If a row or column has two nonzero entries, then it is part of a 2 × 2 unitary submatrix. To multiply A_{ρ} by the sparse unitary matrix B, if (ρ, i, j) is written down on the tape, then the machine must write down (ρ, i, ℓ) with amplitude (A_{ρ})_{ij}B_{jℓ}. This is easily simulated (to any desired degree of accuracy) by a quantum Turing machine [3].

The addition is the most difficult part of the algorithm, since it is not immediately obvious why it is unitary. Indeed, the key reason why it is unitary has not yet been stated. Replacing A_{ρ} by A_{ρ} + f̂_{k}(ρ) while simultaneously zeroing out the amplitude of all the (σ, i, j) is a unitary transformation if A_{ρ} is known to lie in a space which is orthogonal (as a d_{ρ}^{2}-dimensional vector space) to a space containing f̂_{k}(ρ). This is the case at all times when we wish to do this: before multiplying by ρ(τ_{k}^{−1}), A_{ρ} is the transform of a function which is zero on the coset Hτ_{k}. After the multiplication, therefore, A_{ρ} is the transform of a function which is zero on H. On the other hand, f_{k} is zero outside H, so its transform is orthogonal to A_{ρ} as desired.

Using orthogonality, we describe the addition step of the algorithm. Let k be fixed, we describe the addition of f̂_{k}(ρ) to A_{ρ}. The machine will replace (σ, i, j, k) by (ρ, i′, j′) for some ρ ∈ Ĝ which, when restricted to H, contains σ as a diagonal constituent. Once a ρ has been selected, the matrix entries i′ and j′ are determined (each ρ|_{H} contains each σ with multiplicity 0 or 1). It is easy to compute the possible ρ values for a given σ, along with the

“scaling factor” \sqrt{\frac{d_{ρ}|H|}{d_{σ}|G|}}. Therefore, we may use the technique of Lemma 4.3 in reverse: Let T be a sequence of steps on the quantum Turing machine which takes tape contents (σ, i, j, −1) and replaces them with (ρ, i′, j′) with

amplitude \sqrt{\frac{d_{ρ}|H|}{d_{σ}|G|}} for each ρ such that ρ|_{H} contains a σ constituent. T does

nothing if the state of the form (σ, i, j, ℓ) for some ℓ ≠ −1. Let S be the transformation which takes (σ, i, j, ℓ) and replaces it with (σ, i, j, ℓ′), where:

l′ = \{ \begin{matrix}−1 & if ℓ = k \\ k & if ℓ = −1 \\ ℓ & otherwise \end{matrix}

Then the desired sequence of steps is T^{−1}, followed by S, followed by T. This completes the description of the algorithm. We have shown:

Theorem 5.1 Let f be a function defined on the symmetric group S_{n}, and suppose that a quantum computer has tape contents g with amplitude f(g), for all g ∈ S_{n}. Then in quantum polynomial time, the machine may be put into a superposition of states corresponding to the Fourier transform of f with respect to the Young Orthogonal Form basis for Ŝ_{n}. That is, the amplitude of tape contents (ρ, i, j) will be the (i, j) entry of f̂(ρ), where ρ ∈ Ŝ_{n} is in Young Orthogonal Form.□

6 Conclusion

The research presented in this paper was motivated by the question of whether or not graph isomorphism has an efficient solution on the quantum Turing machine. This question remains open; we hope that the results presented here represent a step towards its resolution.

References

[1] C. Bennett: Logical reversability of computation, IBM J. Res. Develop. 17 (1973), 525–532.

[2] C. Bennett, E. Bernstein, G. Brassard, U. Vazirani: Strengths and weaknesses of quantum computing, preprint.

[3] E. Bernstein, U. Vazirani: Quantum complexity theory, Proc. 25th ACM STOC (1993).

[4] D. Boneh, R. Lipton: Quantum cryptanalysis of hidden linear functions, Proc. CRYPTO’95.

[5] M. Clausen: Fast generalized Fourier transforms, Theoret. Comput. Sci. 56 (1989), 55–63.

[6] D. Coppersmith: An approximate Fourier transform useful in quantum factoring, IBM Research Report 19642, 1994.

[7] P. Diaconis: Group representations in probability and statistics, IMS Lecture Notes—Monograph Series 11, IMS, Hayward, California, 1988.

[8] P. Diaconis, D. Rockmore: Efficient computation of the Fourier transform on finite groups, J. AMS 3 no. 2 (1990), 297–332.

[9] J. P. Serre: Linear representations of finite groups, Springer-Verlag, 1977.

[10] P. Shor: Algorithms for quantum computation: discrete logarithms and factoring, Proc. 35th IEEE FOCS (1994), 124–134.

[11] D. Simon: On the power of quantum computation, Proc. 35th IEEE FOCS (1994), 116–123.

[12] A. Yao: Quantum circuit complexity, Proc. 34th IEEE FOCS (1993), 352–360.