Analysing the Quantum Fourier Transform for finite groups through the Hidden Subgroup

Problem

Jean-Noël Murphy

School of Computer Science McGill University, Montreal

November 2001

A Thesis submitted to the Faculty of Graduate Studies and Research in partial fulfillment of the requirements of the degree

of Master of Science

\begin{matrix}c \\ ◯ \end{matrix}Jean-Noël Murphy 2001

Abstract

We present an in-depth study of the Quantum Fourier Transform for finite groups and the underlying mathematics. The study includes a look at the most salient results linking the Quantum Fourier Transform to the Hidden Subgroup Problem. This provides a useful context for determining the extent to which the Fourier transform can serve to recognize periodicity of a function on a finite group.

Résumé

Cette thèse vise à analyser en profondeur la transformée de Fourier quantique pour groupes finis et la théorie mathématique sur laquelle elle est construite. Elle comporte également une étude des résultats les plus importants parmi ceux qui font un lien entre la transformée de Fourier et le problème du sous-groupe caché. Ce dernier fournit un contexte utile pour déterminer l’aptitude de la transformée de Fourier à reconnaître une fonction périodique définie sur un groupe fini.

Acknowledgments

My deepest gratitude to my supervisors Gilles Brassard and Claude Crépeau. From them I received unique guidance and support. Their efforts on my behalf were truly extraordinary. Thank you for all your help and patience. It was a great honour to work with you both.

My thanks also to all the members of the Cryptography and Quantum Information Laboratory of McGill University.

Contents

1 Introduction 5

2 Theoretical Background 8

2.1 Representation Theory . . . . . . . . . . . . . . . . . . . . . . 8 2.1.1 Decomposing Representations . . . . . . . . . . . . . . 10 2.1.2 Unitary Representations . . . . . . . . . . . . . . . . . 12 2.1.3 Characters . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1.4 Two Important Representations . . . . . . . . . . . . . 16 2.1.5 Fourier Coefficients . . . . . . . . . . . . . . . . . . . . 18

2.2 Representations of Abelian Groups . . . . . . . . . . . . . . . 19 2.3 The Group Algebra . . . . . . . . . . . . . . . . . . . . . . . . 24

3 The Quantum Fourier Transform 26

4 The Hidden Subgroup Problem 30 4.1 Abelian Groups . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2 Groups in General . . . . . . . . . . . . . . . . . . . . . . . . 35

4.2.1 Measuring the Representation Name . . . . . . . . . . 36 4.2.2 Measuring the Fourier Coefficients . . . . . . . . . . . . 41 5 Dihedral Groups and Their Hidden Subgroups 44

5.1 The Representations of the Dihedral Group . . . . . . . . . . 46 5.2 The QFT for the Dihedral Group . . . . . . . . . . . . . . . . 48 5.3 Examples for Dihedral Hidden Subgroup Problem . . . . . . . 49

5.3.1 Finding Normal Subgroups . . . . . . . . . . . . . . . . 50 5.3.2 Distinguishing Between |H| = 1 and |H| = 2 . . . . . . 51

6 Conclusion 56

A Group Theory 62 A.1 Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 A.2 Isomorphisms and Homomorphisms . . . . . . . . . . . . . . . 65 A.3 Group Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

B Concepts from Linear Algebra 69 B.1 Direct Sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 B.2 Unitary Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 70

Chapter 1

Introduction

In the manipulation of quantum information, the obstacle to be overcome is always the creation of suitable interference between logical paths of the computation. Perhaps the most important mechanism of all for accomplishing this to date is the Quantum Fourier Transform for finite groups (QFT). Of course, the QFT is not a single transformation but a family of these with the form depending on the group upon which it is acting. For example, the initiated reader will surely recognize the omnipresent Walsh-Haddamard transform which is in fact the QFT for the group ℤ_{2}. Considering its prevalance, the current literature in quantum computing deals somewhat inadequately with the derivation from representation theory of the Quantum Fourier Transform particularly in it’s general form. A lack of details is aggravated further by the absence of an established convention. Mathematical textbooks on the subject of representation theory date from nearly fourty years ago and use notation which differs from current conventions. Furthermore, they make no reference to the QFT which is a more contemporary subject. Other available sources are those which discuss the classical Fourier Transform. The result is that complete information about the QFT can only be obtained by laboriously piecing together obscure mathematical theories and casual remarks.

In this thesis we seek to remedy this by rigorously defining the Quantum Fourier Transform for finite groups in general and reconciling the different definitions which appear in current research. With this done, we will move on to analysing the QFT. We will do this in a unique way by considering the Hidden Subgroup Problem (HSP). The Hidden Subgroup Problem is one which has been studied extensively and in every instance where an efficient quantum algorithm has been found, the mechanism solving it is the Quantum Fourier Transform. We submit that the relationship between the two is even stronger, that all the power of the QFT for finite groups is embodied in the ability to deal with instances of the Hidden Subgroup Problem. Therefore, it is by studying the HSP that we arrive at a deep understanding of the limits of this power. For there do exist many instances of the HSP for which the Quantum Fourier Transform appears to be inadequate.

This thesis is organized in the following way. As promised, a great deal of time will be spent discussing the mathematical theory upon which this tool is built. This is very important if new applications are to be found, and is the content of chapter 2 in this thesis. Chapter 3 will give the general definition of the Quantum Fourier Transform based on this theory, as well as some initial observations. It is in chapter 4 that we will introduce and define the Hidden Subgroup Problem. A thorough look at how the QFT can sometimes solve the problem and also at where it fails will convince the reader of the interplay between the two. The final chapter concentrates on the special case the dihedral Hidden Subgroup Problem. By introducing a new concrete discussion of how the Quantum Fourier Transform fails to resolve the problem, the reader will see the limitations of the QFT in an illuminating context.

Theoretical Background

The Fourier transform for finite groups is based upon a branch of mathematics called representation theory. It was originally conceived as a means of making the tools of linear algebra available to the study of groups. Particularly, the aim is to study the structure of a group indirectly through its various homomorphic images in matrix groups. Much study was done on this topic in the mid twentieth century, but it is no longer fashionable amongst mathematicians. Nonetheless, a relation to quantum mechanics has kept the subject alive primarily in the work of theoretical physicists. The topics covered are not overly complicated mathematically, although the reader may like to look to the appendices for some additional material.

2.1 Representation Theory

We begin by establishing the notion of a representation.

Definition Let G be a group and V a vector space over a field 𝕂. A homomorphism ρ : G → GL_{𝕂}(V) is called a representation of G. The representation ρ is said to have representation space V and dimension d_{ρ} equal to the dimension of V.

By the above definition we see that a representation is a group homomorphism that sends every element of a group G to a matrix of a linear transformation from V to V. For our purposes we will always take the field 𝕂 to be the complex numbers. This deceptively simple idea is the basis of the entire theory. The remainder of this section will be entirely devoted to exploring the consequences of this one definition.

As ρ is a homomorphism, it is immediate that im ρ is a subgroup of GL_{ℂ}(V) and that ker ρ is a subgroup of G (readers not familiar with this notation can find an explanation in the appendices). Any information about the structure of G is contained in these two groups. There are an infinite number of representations of a given finite group, fortunately we need not consider them all. To begin with, given that the image of every representation is a matrix group, we wish to reduce to a single representative all those representations whose images are isomorphic. There is nothing to be learned by examining multiple copies of the same group. So we collect representations into classes according to this property.

Two representations ρ : G → GL_{ℂ}(V) and τ : G → GL_{ℂ}(W) are said to be equivalent if there exists a linear transformation T : V → W such that,

T ∘ ρ(g) = τ(g) ∘ T ∀g ∈ G.

As T is a linear transformation, it represents a change from some basis B_{V} of V to a basis B_{W} of W. As a consequence we can say that two representations are equivalent if they differ only by a change of basis, with the understanding that this is not limited to within a single vector space.

It will be possible to further limit the field of distinct representations of a group to a number of “elementary” representations. Showing how this is done and that it is sufficient is the work of the next subsection.

2.1.1 Decomposing Representations

Let ρ : G → GL_{ℂ}(V) be a group representation. We may treat ρ as defining an action of G on the elements of V and write g · v to represent the matrix product ρ(g)v, for all g ∈ G and v ∈ V. This point of view leads to the concept of a G-invariant subspace, which is a subspace W ⊆ V such that,

∀g ∈ G g · W = ρ(g)W ⊆ W

Clearly, for any representation with representation space V, both V and the trivial subspace of V are G-invariant. However, when the representation space V of ρ possesses a proper G-invariant subspace W, then by restricting the action of ρ to one on W only, we define a new representation, denoted ρ ↓_{W}^{V}. This representation will now send elements of G to the group GL_{ℂ}(W). As, W is G-invariant, each ρ(g) is indeed a linear transformation from W to W, as it was one before from V to V.

In addition, given such a proper G-invariant subspace W ⊂ V, there exists another proper G-invariant subspace W′, called the orthogonal complement of W, which is independent of W. This allows us to define a second representation, the restriction of ρ to W′, ρ ↓_{W′}^{V}. As W and W′ are independent and furthermore span V, then we can conclude that V is the direct sum of the subspaces W and W′. That is, V = W ⊕ W′. Now with ρ_{1} = ρ ↓_{W}^{V} and ρ_{2} = ρ ↓_{W′}^{V} it is possible to choose a basis for which ρ will have the block diagonal form,

ρ(g) = [ \begin{matrix}ρ_{1}(g) & 0 \\ 0 & ρ_{2}(g) \end{matrix} ] ∀g ∈ G

Therefore, when the representation space of ρ : G → GL_{ℂ}(V) is the direct sum of G-invariant subspaces W and W′, then we say that ρ is the direct sum of the representations ρ ↓_{W}^{V} and ρ ↓_{W′}^{V} and write,

ρ = ρ ↓_{W}^{V} ⊕ρ ↓_{W′}^{V}

So, if we are able to find a proper G-invariant subspace of the representation space, we may decompose a representation into ones of smaller dimension. Obviously this process cannot continue indefinitely. At some point we must arrive at representations over vector spaces which contain no proper G-invariant subspaces. This brings us to the notion of an irreducible representation. A representation ρ : G → GL_{ℂ}(V) is said to be irreducible if, for any subspace W ⊆ V,

W is G-invariant ⇔ W is either equal to V or is the trivial subspace of V .

In particular, any one-dimensional representation must be irreducible.

The full consequence of what we have just seen cannot be yet apparent. However, the following theorem will help to convince the reader of the importance of irreducible representations.

Theorem 1 (Mascke) Every representation can be decomposed into a direct sum of irreducible representations.

We will later add to the above by showing that there are only a finite number of irreducible representations and that these have many remarkable properties.

2.1.2 Unitary Representations

A unitary representation is a homomorphism ρ : G → GL_{ℂ}(V) such that for each g ∈ G, ρ(g) is a unitary matrix. Now, for any group representation τ there exists a basis for V for which every matrix τ(g) will be unitary. Thus every representation is equivalent to a unitary representation. This is a consequence of the fact that every subgroup of the general linear group is isomorphic to a subgroup of the unitary group. This will allow us to prove a number of interesting general properties of representations by using the characteristics of unitary matrices. Particularly so when we discuss characters. For the moment we limit ourselves to noticing that as every unitary matrix is diagonalizable, by the stated equivalence, so must every matrix τ(g) of any group representation τ.

2.1.3 Characters

Definition Let ρ : G → GL_{ℂ}(V) be a representation of the group G. Define a function χ_{ρ} : G → ℂ such that,

χ_{ρ}(g) = trace(ρ(g)) ∀g ∈ G

χ_{ρ} is known as the character of the representation ρ.

As the trace of a matrix is independent of the choice of basis, equivalent representations will have the same character. This will allow us to pick the most convenient basis for every representation, and indeed that which is most appropriate for each individual matrix ρ(g), whenever we are dealing with characters. This allows for many nice properties of characters of which we will make extensive use.

As every representation ρ : G → GL_{ℂ}(V) is by definition a homomorphism, then ρ(e) must be the identity matrix in the vector space V. It follows then that for every representation ρ, χ_{ρ}(e) = d_{ρ}.

Recall that for every g ∈ G and representation ρ : G → GL_{ℂ}(V) it is possible to choose a basis B_{g} of V so that ρ(g) is diagonal. That is,

[ρ(g)]_{B_{g}} = [ \begin{matrix}λ_{1} \\ & λ_{2} \\ & & . & . & . \\ & & & & & λ_{n} \end{matrix} ]

where λ_{1}, λ_{2}, …, λ_{n} are the eigenvalues of the matrix ρ(g) (the eigenvalues do not depend on the basis). Since the trace is independent of the basis, we have χ_{ρ}(g) = tr ([ρ(g)]_{B_{g}}) and so,

χ_{ρ}(g) = λ_{1} + λ_{2} + … + λ_{n}

A further property of ρ as a homomorphism is that ρ(hgh^{−1}) = ρ(h)ρ(g)ρ(h)^{−1}. As we have assumed that representations are unitary, ρ(h)ρ(g)ρ(h)^{−1} can be thought of as a change of basis for the representation space of the matrix ρ(g). Therefore, χ_{ρ}(hgh^{−1}) = χ_{ρ}(g), ∀h, g ∈ G. This means that characters are what are known as class functions or in other words they are constant on the conjugacy classes of the group. Although not a particularly captivating property at first, it will be returned to later.

As G is a finite group, each element g ∈ G has finite order. This means that for some integer r, g^{r} = 1. As ρ is a homomorphism, ρ(g)^{r} is the identity matrix. Thus in an appropriate basis,

ρ(g)^{r} = [ \begin{matrix}λ_{1} \\ & . & . & . \\ & & & & λ_{n} \end{matrix} ]^{r} = [ \begin{matrix}λ_{1}^{r} \\ & . & . & . \\ & & & & λ_{n}^{r} \end{matrix} ] = [ \begin{matrix}1 \\ & . & . & . \\ & & & & 1 \end{matrix} ]

Which tells us that for i = 1, …, n, λ_{i}^{r} = 1. Put another way, the eigenvalues of the matrices ρ(g) are all r^{th}-roots of unity. Now, as χ_{ρ}(g^{−1}) = tr (ρ(g^{−1})) = tr (ρ(g)^{−1}), then again the diagonalisability of ρ(g) allows us to say that χ_{ρ}(g^{−1}) = λ_{1}^{−1} + … + λ_{n}^{−1}. Finally as each λ_{i} is a root of unity, λ_{i}^{−1} = \overline{λ}_{i}. We conclude that

χ_{ρ}(g^{−1}) = \overline{λ}_{1} + … + \overline{λ}_{n} = \overline{χ_{ρ}(g)}

This is useful as there is a standard inner product for complex functions over a group. If f : G → ℂ and g : G → ℂ then

⟨f|g⟩ = \frac{1}{|G|} ∑_{x∈G} f(x)\overline{g(x)}

For characters, which are also complex functions over the group, we then have,

⟨χ_{ρ}|χ_{τ}⟩ = \frac{1}{|G|} ∑_{x∈G} χ_{ρ}(x)χ_{τ}(x^{−1})

This inner product is crucial in manipulating both characters and their representations. Its usefulness stems mostly from the following theorem:

Theorem 2 Characters of irreducible representations are orthonormal with respect to the given inner product. That is, let χ_{ρ} and χ_{τ} be the characters of the inequivalent irreducible representations ρ and τ respectively. Then,

(i) ⟨χ_{ρ}|χ_{ρ}⟩ = ⟨χ_{τ}|χ_{τ}⟩ = 1

(ii) ⟨χ_{ρ}|χ_{τ}⟩ = ⟨χ_{τ}|χ_{ρ}⟩ = 0

This is a beautiful result with very important consequences. The first is that the above leads to the conclusion that characters form a basis for the space of all class functions. Another basis for this space would be the set of indicator functions for the conjugacy classes of the group. So, the number of distinct irreducible characters is exactly the number of conjugacy classes. Therefore we have fixed the number of inequivalent irreducible representations to a precise finite quantity. Secondly, it provides us with a precise way to decompose representations into direct sums of irreducibles.

Let {ρ_{1}, ρ_{2}, …, ρ_{k}} be a complete set of inequivalent irreducible representations of a group G and let χ_{i} be the character of ρ_{i}. Then, any representation τ of G can be decomposed in a unique way as,

τ = ⟨χ_{τ}|χ_{1}⟩ρ_{1} ⊕ ⟨χ_{τ}|χ_{2}⟩ρ_{2} ⊕ … ⊕ ⟨χ_{τ}|χ_{k}⟩ρ_{k}

Thus, the inner product n_{i} = ⟨χ_{τ}|χ_{i}⟩ gives the number of times that the irreducible representation ρ_{i} appears in the decomposition of τ. Furthermore, the same relationship applies to the characters. By taking the trace on both sides of the previous equation, we obtain,

χ_{τ} = n_{1}χ_{1} + n_{2}χ_{2} + … + n_{k}χ_{k}

We can use this to show ⟨χ|χ⟩ = 1 is not only necessary for irreducible characters, but sufficient.

\begin{aligned}& χ & = & n_{1}χ_{1} + n_{2}χ_{2} + … + n_{k}χ_{k} \\ ⇔ & ⟨χ|χ⟩ & = & n_{1}^{2} + n_{2}^{2} + … + n_{k}^{2} \end{aligned}

This last equation being a consequence of the orthogonality of the irreducible characters. As each n_{i} is a non-negative integer, the inner product can only equal 1 if there exist a single n_{i} = 1 and all the rest are zero. We are now equipped with a much easier way of testing irreduciblity than the previous method of searching for G-invariant subspaces.

Now, take two representations ρ and ρ′ with identical characters and let them be decomposed into irreducibles such that,

\begin{aligned}ρ & = & n_{1}ρ_{1} ⊕ … ⊕ n_{k}ρ_{k} \\ ρ′ & = & n′_{1}ρ_{1} ⊕ … ⊕ n′_{k}ρ_{k} \end{aligned}

The assumption that the two representations have identical characters implies,

n_{1}χ_{1} + … + n_{k}χ_{k} = n′_{1}χ_{1} + … + n′_{k}χ_{k}

The orthogonality of irreducible characters then requires that n′_{i} = n_{i} for all i = 1, …, k. Note that this is only true because the decomposition is over the set of inequivalent irreducible representations. The representations decompose identically into a direct sum of irreducibles and hence they must be equivalent. With the property that characters are independent of changes of basis we conclude,

Theorem 3 Two representations are equivalent if and only if their characters are identical.

This theorem tells us that characters completely determine representations up to equivalence. Together with the stunning properties they possess we have a greatly simplified way of dealing with group representations.

2.1.4 Two Important Representations

One of the most useful representations of a group is also the simplest. This is the function 1_{G} : G → GL_{ℂ}, called the trivial representation, which sends every element of the group to the one-dimensional matrix (1). Of course, χ_{1_{G}} is identically 1 over all group elements, which makes it clear that the trivial representation is always irreducible. As the title of this section suggests there is another representation that we will define here, but this will require a somewhat longer explanation.

Previously we hinted at the possibility of considering a representation as the action of a group on a vector space. We now return to the notion of group action in order to define the so-called permutation representations.

Suppose that the group G acts on some set S = {s_{1}, s_{2}, …, s_{n}} by permutation. We define a vector space on S considering all complex linear combinations of the elements of S,

v = ∑_{i=1}^{n} α_{i}s_{i}

Now let us define a representation of G, perm_{S} : G → V (S) such that perm_{S}(g) sends this basis (s_{1}, s_{2}, …, s_{n}) to the basis (gs_{1}, gs_{2}, …, gs_{n}). That is,

perm_{S}(g)v = ∑_{i=1}^{n} α_{i}(gs_{i}) ∀v ∈ V (S), g ∈ G

In other words, each perm_{S}(g) is a n × n permutation matrix. Further study of this representation reveals that its character χ_{S} has the property that χ_{S}(g) is the number of elements of S fixed by the action of g. Particular choices of the set S lead to different representations. Among these, if we set S = G and let G act on itself by left multiplication, we obtain what is known as the regular representation, ρ_{reg}. Note that for the action of left multiplication, the identity element fixes all elements of the group and all other group elements fix none. We deduce that,

χ_{reg}(g) = \{ \begin{matrix}|G| & if g = e \\ 0 & otherwise \end{matrix}

As a consequence, for any group representation ρ with character χ_{ρ},

⟨χ_{reg}|χ_{ρ}⟩ = \frac{1}{|G|} ∑_{g∈G} χ_{reg}(g)χ_{ρ}(g^{−1}) = \frac{1}{|G|} (|G|χ_{ρ}(e)) = d_{ρ}

Therefore, if ρ_{1}, ρ_{2}, …, ρ_{k} is a complete set of inequivalent irreducibles of the group G with characters χ_{i} and dimensions d_{i}, when we decompose the regular representation in the standard way, we arrive at,

ρ_{reg} = ⟨χ_{reg}|χ_{1}⟩ρ_{1} ⊕ … ⊕ ⟨χ_{reg}|χ_{k}⟩ρ_{k}

which, by what we have just seen, gives

ρ_{reg} = d_{1}ρ_{1} ⊕ d_{2}ρ_{2} ⊕ … ⊕ d_{k}ρ_{k}

Naturally, this also implies a similar relationship between the character of the regular representation and the irrreducible characters. This is particularly interesting in the values assumed at the identity.

\begin{aligned}χ_{reg}(e) & = & d_{1}χ_{1}(e) + d_{2}χ_{2}(e) + … + d_{k}χ_{k}(e) \\ |G| & = & ∑_{i=1}^{k} d_{i}^{2} \end{aligned}

Thus we make the general statement that for any complete set R of inequivalent irreducible representations of a group G, ∑_{ρ∈R} d_{ρ}^{2} = |G|.

2.1.5 Fourier Coefficients

Let R = {ρ_{1}, ρ_{2}, …, ρ_{k}} be a complete set of inequivalent irreducible representations of the group G. For each representation ρ ∈ R and g ∈ G, ρ(g) is a d_{ρ} × d_{ρ} matrix with complex entries. Therefore, it is possible to define a family of functions ρ_{ij} : G → ℂ, called the Fourier coefficients which will send every element g to the (i, j)^{th} entry of the matrix ρ(g). That is,

ρ_{ij}(g) = (ρ(g))_{i,j} for all g ∈ G and 1 ≤ i, j ≤ d_{ρ}

A fundamental result in the theory of representations is Schur’s Lemma. We will not state it here as it is goes beyond the intended scope of this survey. We will however use one of its corollaries.

Theorem 4 Let ρ and τ be two unitary irreducible representations of the group G. Then, for all i, j, r, s,

⟨ρ_{ij}|τ_{rs}⟩ = 0

and

⟨ρ_{ij}|ρ_{rs}⟩ = \{ \begin{matrix}\frac{1}{d_{ρ}} & if i = r and j = s \\ 0 & otherwise \end{matrix}

Note that the inner product ⟨ | ⟩ is the standard one for complex functions we used previously for characters. Thus we see that the Fourier coefficients defined from a set inequivalent irreducible representations are pairwise orthogonal. It is also from this theorem that the orthonormality of irreducible characters is proved.

2.2 Representations of Abelian Groups

We saw that the number of inequivalent irreducibles of a group is equal to the number of conjugacy classes. In an Abelian group, g^{−1}hg = hg^{−1}g = h and so, every element forms a conjugacy class onto itself. Therefore, for a complete set of irreducibles {ρ_{i}|1 ≤ i ≤ k} of an Abelian group we have, k = |G| and, ∑_{i=1}^{|G|} d_{ρ_{i}}^{2} = |G|. The last equation is only satisfied if d_{ρ_{i}} = 1, ∀i. Hence we conclude that for any Abelian group, all irreducibles are one-dimensional. As every finite Abelian group is the direct product of cyclic groups we will first find the irreducibles of these to arrive at a general expression for the irreducibles of all Abelian groups.

Claim 1 For the cyclic group ℤ_{n} of order n, the following functions ρ_{k} : G → GL_{ℂ} form a complete set of irreducible representations of the group,

ρ_{k}(a^{r}) = (ω_{n}^{kr}) for k = 0, …, n − 1

Proof This proof and several others which will follow, use the following lemma,

Lemma 1 Let d ∈ ℕ, m ∈ ℤ and ω_{d} = e^{\frac{2πi}{d}} be the standard d^{th} root of unity. Then,

∑_{r=0}^{d−1} ω_{d}^{mr} = \{ \begin{matrix}d & if d|m \\ 0 & otherwise \end{matrix}

(Proof omitted)

Let a^{r} and a^{s} be two elements of ℤ_{n} = ⟨a⟩. Then, for all k = 0, …, n−1,

ρ_{k}(a^{r})ρ_{k}(a^{s}) = ω_{n}^{kr}ω_{n}^{ks} = ω_{n}^{k(r+s)} = ρ_{k}(a^{r+s}) = ρ_{k}(a^{r}a^{s})

Furthermore as, ρ_{k}(e = a0) = ω_{n}^{0k} = 1, it is clear that ρ_{k} is a homomorphism. All that remains is to use the inner product for characters to show that all representations ρ_{k} are irreducible and inequivalent. Irreducibility is already given as each ρ_{k} is one-dimensional.

Now, without loss of generality we compute the inner product of the characters of the representations ρ_{k} and ρ_{l} where l < k.

\begin{matrix}⟨χ_{k}|χ_{l}⟩ = \frac{1}{n} ∑_{r=0}^{n−1}χ_{k}(a^{r})χ_{l}(a^{−r}) \\ = \frac{1}{n} ∑_{r=0}^{n−1}ω_{n}^{r(k−l)} \end{matrix}

By Lemma 1, as 0 ≤ l, k ≤ n − 1, we have that n does not divide k − l and so the summation must be zero. Therefore, as p_{k} and p_{l} are irreducible they must be inequivalent.□

With the next result we will be able to extend what we know of the representations of cyclic groups to all Abelian groups.

Proposition 1 Let A be an Abelian group with identity e and let {ρ_{i}|0 ≤ i ≤ k} be a complete set of irreducible representations of A with respective characters χ_{i}. Now consider the group G = A×ℤ_{n}. Then, the functions, τ_{ij} : G → GL_{ℂ} given by,

τ_{ij}((a, r)) = (χ_{ρ_{i}}(a)ω_{n}^{rj}) ∀a ∈ A, 0 ≤ r ≤ n − 1

for all 1 ≤ i ≤ k, 0 ≤ j ≤ n − 1, form a complete set of irreducible representations of the group G.

Proof A is an Abelian group, hence every irreducible representation of A is one-dimensional. Consequently, we know the following are true:

(i) Each χ_{i} is a homomorphism from A to GL_{ℂ}. Hence, for all elements a, b ∈ A,

χ_{i}(a)χ_{i}(b) = χ_{i}(a + b) and χ_{i}(e) = 1

(ii) By irreducibility and inequivalence,

⟨χ_{i}|χ_{i}⟩ = 1 and ⟨χ_{i}|χ_{j}⟩ = 0

(iii) The number k of inequivalent irreducible representations of A is equal to the order of A.

In order to show that each τ_{ij} is a homomorphism, let (a, r) and (b, s) be two elements of the group G. Then,

τ_{ij} ((a, r)) · τ_{ij} ((b, s)) = (χ_{i}(a)ω_{n}^{rj}) (χ_{i}(b)ω_{n}^{sj})
= (χ_{i}(a)χ_{i}(b)ω_{n}^{rj}ω_{n}^{sj})
= (χ_{i}(a + b)ω_{n}^{j(r+s)})
= τ_{ij} ((a + b, r + s))
= τ_{ij} ((a, r) + (b, s))

Furthermore it is clear that each function τ_{ij} sends the identity element of G, (e, 0) to the identity in GL_{ℂ}, (1). Therefore, for every 1 ≤ i ≤ k and 0 ≤ j ≤ n − 1, the function τ_{ij} is a one-dimensional representation of the group G and hence irreducible as well. Showing that they are inequivalent requires a bit more work for there are two cases to consider. Take the representations, τ_{is} and τ_{jt} where 1 ≤ i, j ≤ k and 0 ≤ s, t ≤ n − 1.

Case 1 (i ≠ j) We reorganize the expression for the inner product of χ_{τ_{is}} and χ_{τ_{jt}} as follows,

\begin{matrix}⟨χ_{τ_{is}}|χ_{τ_{jt}}⟩ = \frac{1}{nk} ∑_{a∈A} ∑_{r=0}^{n−1} (χ_{i}(a)ω_{n}^{rs}) (χ_{j}(a^{−1})ω_{n}^{−rt}) \\ = \frac{1}{n} ∑_{r=0}^{n−1}⟨χ_{i}|χ_{j}⟩ω_{n}^{r(s−t)} \end{matrix}

However, i ≠ j by assumption means χ_{i} and χ_{j} are inequivalent characters and so ⟨χ_{i}|χ_{j}⟩ = 0. Therefore in this case, ⟨χ_{τ_{is}}|χ_{τ_{jt}}⟩ = 0 and we conclude that the representations τ_{is} and τ_{jt} are inequivalent.

Case 2 (s ≠ t) Without loss of generality suppose that s > t. This time we change the order of the sum so that,

⟨χ_{τ_{is}}|χ_{τ_{jt}}⟩ = \frac{1}{nk} ∑_{a∈A} (∑_{r=0}^{n−1} ω_{n}^{r(s−t)}) χ_{i}(a)χ_{j}(a^{−1})

Invoking Lemma 1 and remarking that s > t ⇒ n |̸(s − t) we see that the sum, ∑_{r=0}^{n−1} ω_{n}^{r(s−t)} = 0. Thus we again conclude that τ_{is} and τ_{jt} are inequivalent irreducible representations of the group G.

That the set of all representations τ_{ij} is complete can be verified by simply stating that there are nk = |G| of them.□

As a corollary to this consider the general form of an Abelian group as a direct product of cyclic groups, G = ℤ_{n_{1}} × ℤ_{n_{2}} × … × ℤ_{n_{k}}. The elements of such a group can be treated as k-tuples (a_{1}^{r_{1}}, …, a_{k}^{r_{k}}) where a_{i} generates ℤ_{n_{i}}. It follows that then, the function

ρ_{(i_{1},...,i_{k})} ((a_{1}^{r_{1}}, …, a_{k}^{r_{k}})) = (∏_{j=1}^{k} ω_{n_{j}}^{i_{j}r_{j}})

from G to GL_{ℂ} is an irreducible representation of G for every 0 ≤ i_{1} ≤ n_{1} − 1, …, 0 ≤ i_{k} ≤ n_{k} − 1.

2.3 The Group Algebra

Given any finite group G, it is natural to consider the set of complex - valued functions over G. This set, denoted ℂ[G] has the structure of an algebra over the complex numbers. A complex algebra is a ring (A, +, ·, 0, 1) with the additional property that the set A and the addition operation “+” form a complex vector space. In the case of the complex algebra ℂ[G] the addition and scalar multiplication are the obvious operations for functions. Multiplication between functions is the composition operation.

For every g ∈ G, we can define the point-mass or delta function δ_{g},

δ_{g}(x) = \{ \begin{matrix}1 & if x = g \\ 0 & otherwise \end{matrix}

The set Γ = {δ_{g}|g ∈ G} of all such point-mass functions forms a basis for ℂ[G]. For if f is any complex-valued function over the group,

f = ∑_{g∈G} c_{g}δ_{g} where f(g) = c_{g}, ∀g ∈ G

The above tells us that in the basis Γ we can write any function f as a complex vector (c_{g_{1}}, c_{g_{2}}, …, c_{g_{n}}) and that the vector space ℂ[G] has dimension |G|.

There is another important basis for the group algebra which we have already encountered. This is the set of all Fourier coefficient functions drawn from a complete set of inequivalent irreducibles of the group G. For each representation ρ ∈ R we have d_{ρ}^{2} such functions. As ∑_{ρ∈R} d_{ρ}^{2} = |G|, then there are clearly |G| such functions in total. That they form a linearly independent set follows from Theorem 4 which we saw when Fourier coefficients were first discussed. Thus, the set {ρ_{ij}|ρ ∈ R and 1 ≤ i, j ≤ d_{ρ}} forms a basis for the group algebra. Although it has taken quite a bit of work we now have all the raw materials needed to define the Quantum Fourier Transform over any finite group.

The Quantum Fourier

Transform

In simplest terms a Fourier transform over a group G is a change of basis in the group algebra from the basis Γ of point-mass functions to the basis of Fourier coefficient functions. It may of course not be completely obvious at first what this implies in a quantum setting. If the Fourier transform is a change of basis, then it is natural to relate the basis vectors to basis states. Hence, we adopt a naming convention for the elements of both bases. First, we write the state |g⟩ to represent the function δ_{g}. Second, we represent the function ρ_{ij} by a state in three registers |ρ, i, j⟩. With this we will redefine the Quantum Fourier Transform in terms of the effect on an arbitrary vector in ℂ[G].

Let G be a finite group and R a complete set of inequivalent irreducible representations of G.

Definition Let f be a complex-valued function on the group G and ρ ∈ R. The Fourier transform of the function f at the representation ρ is denoted by f̂(ρ) and is given by

f̂(ρ) = \sqrt{\frac{d_{ρ}}{|G|}} ∑_{g∈G} f(g)ρ(g)

f̂(ρ) is a d_{ρ} × d_{ρ} matrix with complex entries. The Fourier transform of f at R is composed of the |G| entries of the matrices f̂(ρ) for each ρ ∈ R.

Consider the case when f is function of unit norm in the group algebra with respect to the basis Γ. (Of course, if the function does not have unit norm, we take the normalized form.) Then by extending the logic we used previously, we associate to the function a state |f⟩ such that,

|f⟩ = \frac{1}{\sqrt{|G|}} ∑_{g∈G} f(g)|g⟩

By the above definition, the Quantum Fourier Transform (QFT) sends the state |f⟩ to,

∑_{ρ∈R} ∑_{1≤i,j≤d_{ρ}} f̂(ρ)_{i,j}|ρ, i, j⟩

This allows us to translate the definition of the QFT into more useful forms. In particular, let f be identical to the point-mass function δ_{g} for some element g ∈ G and so |f⟩ = |g⟩ according to our naming convention. It is clear that,

f̂(ρ) = \sqrt{\frac{d_{ρ}}{|G|}}ρ(g) ∀ρ ∈ R

Then, the QFT is a function F such that for every g ∈ G,

F (|g⟩) = ∑_{ρ∈R} ∑_{1≤i,j≤d_{ρ}} \sqrt{\frac{d_{ρ}}{|G|}}ρ_{i,j}(g)|ρ, i, j⟩

Let us briefly consider the matrix form of the QFT. Let us choose an ordering of the group elements, (g_{1}, g_{2}, …, g_{n}), with n = |G| and have the state |g_{i}⟩ correspond to the i^{th} n-dimensional elementary vector e_{i}. We also define some bijection μ which sends each integer t between 1 and n to a triple (ρ, i, j). This allows us to write f_{t} to denote the function \sqrt{\frac{d_{ρ}}{|G|}}ρ_{ij} where μ(t) = (ρ, i, j). With this definition, as the QFT was established to be a change of basis, we can describe it by a matrix F with,

F = [ \begin{matrix}f_{1}(g_{1}) & f_{1}(g_{2}) & … & f_{1}(g_{n}) \\ f_{2}(g_{1}) & f_{2}(g_{2}) & … & f_{2}(g_{n}) \\ ⋮ & ⋮ & ... & ⋮ \\ f_{n}(g_{1}) & f_{n}(g_{2}) & … & f_{n}(g_{n}) \end{matrix} ]

Naturally, we may also consider the conjugate transpose of this matrix,

F^{†} = [ \begin{matrix}\overline{f_{1}(g_{1})} & \overline{f_{2}(g_{1})} & … & \overline{f_{n}(g_{1})} \\ \overline{f_{1}(g_{2})} & \overline{f_{2}(g_{2})} & … & \overline{f_{n}(g_{2})} \\ ⋮ & ⋮ & ... & ⋮ \\ \overline{f_{1}(g_{n})} & \overline{f_{2}(g_{n})} & … & \overline{f_{n}(g_{3})} \end{matrix} ]

Looking at the product of the two matrices F F^{†}, we notice that the (i, j)^{th} entry of this product is of the form ∑_{k=1}^{n} f_{i}(g_{k})\overline{f_{j}(g_{k})} which by Theorem 4 we know to be 0 for i ≠ j and 1 when i = j. Thus, the product F F^{†} is the identity matrix and hence, F is unitary. Therefore, the Quantum Fourier Transform is a unitary transformation.

We may now also define the inverse of the Quantum Fourier Transform, QF T^{−1}. Computing QF T^{−1}|ρ, i, j⟩ is equivalent to performing the multiplication F^{†}e_{t} where μ(t) = (ρ, i, j).

F^{†}e_{t} = \overline{f_{t}(g_{1})}e_{1} + \overline{f_{t}(g_{2})}e_{2} + … + \overline{f_{t}(g_{n})}e_{n}

By the definition \overline{f_{t}(g_{k})} = \sqrt{\frac{d_{ρ}}{|G|}} \overline{ρ_{ij}(g_{k})} and e_{k} corresponds to the state |g_{k}⟩. In summary we have

QF T^{−1}(|ρ, i, j⟩) = \sqrt{\frac{d_{ρ}}{|G|}} ∑_{g∈G} \overline{ρ_{ij}(g)}|g⟩

In particular, notice that QF T^{−1}(|1_{G}, 1, 1⟩) = \frac{1}{|G|} ∑_{g∈G} |g⟩ providing a simple way of producing an equal superposition over all group elements.

We will attempt now to study the properties of the Quantum Fourier Transform, somewhat indirectly, in its application to a problem which seems to capture its essential nature.

The Hidden Subgroup Problem

The field of quantum computing is still in its infancy. Yet a few spectacular results have been achieved. Deutsch’s seminal algorithm which launched the entire field. Shor’s algorithm ([17]), which factors integers and solves discrete logarithm problems in polynomial-time, drastically outperforms all known classical algorithms and presents serious problems for cryptography. Simon’s algorithm ([18]), the first to solve a problem in polynomial time which provably requires exponential time to solve classically with any bounded-error probabilistic algorithm. The remarkable thing is that Deutsch’s problem, the discrete logarithm problem, Simon’s problem and a few others in this select group of successes are all special cases of the Hidden Subgroup Problem ([12]). This would suggest that other special cases of the HSP which are difficult problems classically might also have efficient quantum algorithms. Consider that even Graph Isomorphism is a special case of the Hidden Subgroup Problem.

Historically discoveries are rarely made so neatly as they appear in retrospect. Indeed, in this case, the Hidden Subgroup Problem arose as a generalization, first formulated by Brassard and Høyer ([2]), of Simon’s Problem. The realization that it contained so many others came later. It is stated as follows:

Given a group G and a function f : G → R such that f is contained in a black box and R is some range. Also it is promised that the function f is constant and distinct on the cosets of some unknown subgroup H ≤ G.

Find a generating set for the subgroup H.

The mathematical elegance of the above problem has generated a good deal of interest and a lot of work has been done in the attempt to find the general solution. At this point, efficient algorithms have only been found for restricted classes of groups. What is interesting to note is that in all cases of efficient algorithms, the main tool at work is the Quantum Fourier Transform. Not only that, but the quantum parts of these algorithms are in essence identical. This is not accidental. The Hidden Subgroup Problem is nothing more than a generalization to groups of the notion known as “periodicity of a function”, to which classical Fourier transforms have long been associated. A discrete function is periodic if there exists a an integer α such that

∀x ∈ ℤ, f(x + α) = f(x)

In a group setting we are forced to replace integer addition in the above relation by the group operation. Thus, a function on a group G is periodic if for some fixed α ∈ G, f(xα) = f(x) for all group elements x. Of course, this definition has the consequence that if the element α has order n,

f(x) = f(xα) = f(xα^{2}) = … = f(xα^{n−1})

Therefore, f is automatically constant on the cosets of the subgroup generated by α in G. By extending the concept to arbitrary subgroups and adding the restriction that f be distinct on different cosets, we recover the premise of the Hidden Subgroup Problem.

Suppose we are given a black box which contains a circuit, which we will call U_{f} such that, U_{f}(|g⟩|b⟩) = |g⟩|b ⊕ f(g)⟩, for all g ∈ G. The first step is to create an equal superposition over a random coset cH of the hidden subgroup H ≤ G as follows:

1. Create an equal superposition over all group elements. That is,

\frac{1}{\sqrt{|G|}} ∑_{g∈G} |g⟩

In general this is done by calculating QF T^{−1}|1_{G}, 1, 1⟩. However, if the order of the group is 2^{n}, for some n ∈ ℕ this is accomplished by applying a stack of Walsh-Haddamard transforms to a sufficient number of qubits all initialized to |0⟩.

2. Apply the unitary transformation U_{f} to the previous state in the first registers and a second register containing |0^{m}⟩. This calculates the value of the function f on every group element. Thus the resulting state is,

\frac{1}{\sqrt{|G|}} ∑_{g∈G} |g⟩|f(g)⟩

3. Measure the second register. The result of the measurement is a random value of the function f, f(c) for some c ∈ G. As a consequence the state of the first register becomes,

|cH⟩ = \frac{1}{\sqrt{|H|}} ∑_{h∈G} |ch⟩

All that remains is to compute the QFT on the state |cH⟩ and measure the outcome. The first step presents a problem in that efficient implementations of QF T^{−1} are not known for all groups. However as an issue outside the scope of this thesis, we will assume that by some means the desired outcome can be achieved in deterministic polynomial time. Step 2 is straightforward within the quantum computing model. It is in the last step which interests us primarily and distinctions need to be made amongst groups starting from the application of the QFT. We will follow the historical progression and consider the case of Abelian groups first.

4.1 Abelian Groups

Let G be a finite Abelian group and |cH⟩ = \frac{1}{\sqrt{|H|}} ∑_{h∈H} |ch⟩ be the equal superposition over a random coset of H ≤ G. Recall that the representations of an Abelian group are all one-dimensional. Therefore, the general form of the QFT on an element g becomes,

\begin{matrix}F (|g⟩) = \sqrt{\frac{1}{|G|}} ∑_{ρ∈R}ρ_{1,1}(g)|ρ, 1, 1⟩ \\ = \sqrt{\frac{1}{|G|}} ∑_{ρ∈R}χ_{ρ}(g)|ρ⟩ \end{matrix}

It is now immediate that here, by linearity,

F (|cH⟩) = \frac{1}{\sqrt{|H|}} ∑_{h∈H}F (|ch⟩)

= \frac{1}{\sqrt{|H|}} ∑_{h∈H} (\frac{1}{\sqrt{|G|}} ∑_{ρ∈R}χ_{ρ}(ch)|ρ⟩)

= \frac{1}{\sqrt{|H||G|}} ∑_{ρ∈R} (∑_{h∈H}χ_{ρ}(ch)) |ρ⟩

Now, as each ρ ∈ R is one-dimensional, the character χ_{ρ} : G → ℂ^{×} is also a homomorphism. This means that χ_{ρ}(ch) = χ_{ρ}(c)χ_{ρ}(h). Therefore, the amplitude of the state |ρ⟩ is \frac{χ_{ρ}(c)}{\sqrt{|H||G|}} ∑_{h∈H} χ_{ρ}(h). We saw that the sum in this expression had an interesting property. It is |H| if ρ is the trivial representation over H and is zero for any other irreducible representation. Now, ρ is one-dimensional, therefore not only is it irreducible over G but also over H. The difference is that even if ρ is not the trivial representation over G, it may yet be over H.

We can rewrite ∑_{h∈H} in a more compact form by letting 1_{H} be the trivial representation of H and noticing that,

\begin{aligned}& ⟨χ_{ρ}|χ_{1_{H}}⟩ & = & \frac{1}{|H|} ∑_{h∈H}χ_{ρ}(h)χ_{τ_{1}}(h^{−1}) \\ ⇔ & ∑_{h∈H}χ_{ρ}(h) & = & ⟨χ_{ρ}|χ_{1_{H}}⟩|H| \end{aligned}

and remark that ⟨χ_{ρ}|χ_{1_{H}}⟩ is here only ever 0 or 1. The result is that the probability of observing ρ is,

\begin{matrix}|\frac{χ_{ρ}(c)}{\sqrt{|G||H|}} ∑_{h∈H}χ_{ρ}(h)|^{2} = \frac{|χ_{ρ}(c)|^{2}}{|H||G|} |H|^{2}⟨χ_{ρ}|χ_{1_{H}}⟩ \\ = \sqrt{|H|}|G|⟨χ_{ρ}|χ_{1_{H}}⟩ \end{matrix}

Let us focus on the case where G = ⟨a⟩, G ≡ ℤ_{n}. The hidden subgroup H ≤ G must also be cyclic generated by ⟨a^{t}⟩ for some 0 ≤ t ≤ n − 1. That is, H = {1, a^{t}, a^{2t}, …, a^{(d−1)t}} where d is the order of H. Therefore, for each representation ρ_{k} of the cyclic group G,

∑_{h∈H} χ_{ρ_{k}}(h) = ∑_{r=0}^{d−1} χ_{ρ_{k}}(a^{tr}) = ∑_{r=0}^{d−1} ω_{n}^{ktr}

This sum, by Lemma 1, is non-zero if and only if n|kt. If this is the case it is observed with probability \frac{|H|}{|G|}. In other words, if a representation is obtained as the result of a measurement on the state F (|cH⟩) then we know that \frac{n}{gcd(n,k)}|t. Repeating the procedure m times, we obtain values k_{1}, k_{2}, …, k_{m} with this property. We would then conclude that t = lcm (\frac{n}{gcd(n,k_{1})}, \frac{n}{gcd(n,k_{2})}, …, \frac{n}{gcd(n,k_{m})}) with probability dependent on m. In fact for m ∈ 0(log |G|) this probability can be made arbitrarily close to 1.

Returning to the general Abelian case, notice that the procedure would correspond to solving for the hidden subgroup with the function restricted to each of the cyclic groups in the direct product.

There is a significant problem in the implementation of this algorithm. Unfortunately, according to existing techniques, efficient implementations of the QFT only exist for Abelian groups which are of smooth order. The order n of a group is said to be smooth when all the prime factors of n are of size O(log n). It has been suggested by Jozsa ([10]) that this problem might be overcome by taking the smallest m such that 2^{m} is greater than n and using an implementation of the QFT for ℤ_{2^{m}} as an approximation. Nothing to this effect exists yet.

4.2 Groups in General

We now move on to more general results. As was mentioned the algorithm is essentially the same. However, as in general a group will have irreducible representations which are not all one-dimensional, we have a choice in what we measure. Intuitively, the natural choices are to measure either simply the representation name or the entire Fourier coefficient names. The first case is drawn from the work of Hallgren, Russell and Ta-Shma ([7]) and the second from the work of Grigni, Schulman, Vazirani and Vazirani ([6]).

4.2.1 Measuring the Representation Name

If we choose to measure only the representation name, the state F |g⟩ is best expressed in the form:

∑_{ρ∈R} \sqrt{\frac{d_{ρ}}{|G|}}|ρ⟩ ( ∑_{1≤i,j≤d_{ρ}} ρ_{ij}(g)|i, j⟩)

By linearity, for a random coset cH we have,

F (|cH⟩) = ∑_{ρ∈R} \sqrt{\frac{d_{ρ}}{|G|}}|ρ⟩ ( ∑_{1≤i,j≤d_{ρ}} (∑_{h∈H} ρ_{ij}(ch)) |i, j⟩)

If A is a matrix with complex entries we may define the euclidean norm of A, ∥A∥ such that,

∥A∥^{2} ≡ ∑_{i,j} |a_{ij}|^{2} = tr(A^{†}A)

For a unitary matrix U we have the property that ∥UA∥^{2} = ∥A∥^{2}. Note that this implies that if U is a unitary matrix, then ∥UAU^{†}∥^{2} = ∥A∥^{2} and so the euclidean norm is invariant under any change of basis for unitary matrices.

Armed with this we see that the probability of observing a representation name when we measure the state (F |cH⟩) is exactly \frac{d_{ρ}}{|H||G|}∥ ∑_{h∈H} ρ(ch)∥^{2}. As each representation ρ is unitary and a homomorphism we have ∥ ∑_{h∈H} ρ(ch)∥^{2} = ∥ρ(c) ∑_{h∈H} ρ(h)∥^{2} = ∥ ∑_{h∈H} ρ(h)∥^{2}. Therefore, the distribution on the representation names is independent of the coset.

Now we seek to simplify ∥ ∑_{h∈H} ρ(h)∥^{2}. We know that for any irreducible representation which is not the trivial one, ∑_{g∈G} χ_{ρ}(g) = 0. This property is again useful when combined with the following lemma, Lemma 2 Let K be a finite subgroup of GL_{ℂ}(V) for some complex vector

space V of dimension n. Then,

∑_{k∈K} tr(k) = 0 ⟹ ∑_{k∈K} k = 0_{n×n}

That is, if the sum of the traces of all the matrices in a subgroup is zero, then the sum of the matrices must be the zero matrix. The image of a representation is a subgroup of a general linear group and so, by Lemma 2, whenever ρ is an irreducible representation which is not the trivial one,

∑_{g∈G} χ_{ρ}(g) = 0 ⟹ ∑_{g∈G} ρ(g) = 0_{d_{ρ}×d_{ρ}}

On the other hand, for the trivial representation 1_{G}, ∑_{g∈G} 1_{G}(g) = |G|.

We now apply a reasoning similar to that which we used for Abelian groups. The problem here is that an irreducible representation ρ of G is not in general irreducible for H. Hence first we decompose each irreducible representation ρ of G into a direct sum of irreducibles of H.

ρ = n_{1}τ_{1} ⊕ n_{2}τ_{2} ⊕ … ⊕ n_{l}τ_{l}

Therefore, there exists a certain basis for the representation space so that each matrix ρ(g) will have block diagonal form,

ρ(g) = [ τ_{1}(g) ; ... ; τ_{l}(g) ]

with each representation τ_{i} appearing n_{i} = ⟨χ_{ρ}|χ_{τ_{i}}⟩ times. Thus by Lemma 2, when we take the sum of the ρ(h) over all h ∈ H, all blocks which do not correspond to the trivial representation will disappear. Let us assume without loss of generality that τ_{1} is the trivial representation of H. Therefore, the only entries which will not be zero are the n_{1} diagonal entries which correspond to each of the occurrences of τ_{1}. Necessarily, these will each have the value |H|. The conclusion is that, as the euclidean norm is independent of the basis, the probability of observing ρ is,

\frac{d_{ρ}}{|H||G|}∥∑_{h∈H}ρ(h)∥^{2} = \frac{d_{ρ}}{|H||G|} ∑_{1≤i,j≤d_{ρ}}| (∑_{h∈H}ρ(h))_{ij} |^{2}
= \frac{d_{ρ}}{|H||G|}⟨χ_{ρ}|χ_{τ_{1}}⟩|H|^{2}
= \frac{d_{ρ}}{|H||G|}|H|∑_{h∈H}χ_{ρ}(h)

which is exactly the same form we obtained when we restricted ourselves to Abelian groups. Despite the appeal of this symmetry, it now implies a serious drawback. When characters were introduced we saw that they were class functions. As a consequence, we see that if we only measure the representation name we will not be able to distinguish between conjugate subgroups. That is, the distribution on representation names given by F (|H⟩) is identical to that of F (|g^{−1}|Hg⟩). This is very disturbing, for in noncommutative groups there may be many subgroups which are conjugate.

Happily though, it will now be shown that if the hidden subgroup is promised to be self-conjugate (i.e. normal), sampling the QFT on random cosets will be sufficient to determine subgroup uniquely. That is consistent with what is known of the Abelian case where every subgroup is normal.

The essential observation is contained in the following lemma:

Lemma 3 If H is a normal subgroup, the probability of observing a representation ρ as a result of measuring F (|cH⟩) is non-zero if and only if H ⊆ ker ρ.

Proof We know that under the given circumstances, the probability of observing a representation name ρ is,

\frac{d_{ρ}}{|G||H|}∥ ∑_{h∈H} ρ(h)∥^{2} = \frac{d_{ρ}}{|G||H|}|H|^{2}⟨χ_{ρ}|χ_{1_{H}}⟩ = d_{ρ} \frac{|H|}{|G|}⟨χ_{ρ}|χ_{1_{H}}⟩

Let us introduce a new representation of the group, τ : G → GL_{ℂ}(V). We will define τ as the permutation representation on the set G/H on which the group acts by left multiplication. Thus, τ(g′) is a \frac{|G|}{|H|} × \frac{|G|}{|H|} matrix which sends basis vector corresponding to gH to the one for g′gH. As H is normal in G, hgH = gH for all h ∈ H. This means that the action of any h ∈ H leaves every coset fixed. Since each τ(g) is a permutation, it must then be that τ(h) is the identity matrix for all h ∈ H. On the other hand, every element of the group not in the subgroup H will fix no elements by this action. This allows us to describe the character of the representation completely:

χ_{τ}(g) = \{ \begin{matrix}\frac{|G|}{|H|} & if g ∈ H \\ 0 & otherwise \end{matrix}

Now let ρ be any irreducible representation of the group G.

⟨χ_{ρ}|χ_{τ}⟩ = \frac{1}{|G|} ∑_{g∈G}χ_{ρ}(g)χ_{τ}(g^{−1})

= \frac{1}{|G|} \frac{|G|}{|H|} ∑_{h∈H}χ_{ρ}(h)

= ⟨χ_{ρ}|χ_{1_{H}}⟩

Recall that ⟨χ_{ρ}|χ_{τ}⟩ corresponds to the number of times the irreducible representation ρ appears in the decomposition of τ. That is, if R = {ρ_{1}, …, ρ_{k}} is a complete set of inequivalent irreducibles of G,

τ = ⟨χ_{1}|χ_{τ}⟩ρ_{1} ⊕ … ⊕ ⟨χ_{k}|χ_{τ}⟩ρ_{k}

However we also know that in the appropriate basis τ will have block diagonal form,

τ(g) = [ ρ_{1}(g) ; ... ; ρ_{k}(g) ]

It is clear from this form, that for τ(h) to be the identity matrix for every h ∈ H, we require the same of every representation ρ which appears in the decomposition of τ over G, for which the condition is that ⟨χ_{ρ}|χ_{τ}⟩ ≠ 0. In summary then,

⟨χ_{ρ}|χ_{τ}⟩ ≠ 0 ⇔ ρ(h) = 1_{d_{ρ}×d_{ρ}} ∀h ∈ H

which we can restate as,

⟨χ_{ρ}|χ_{1_{H}}⟩ ≠ 0 ⇔ H ⊆ ker ρ

This completes the proof.□

Another way of seeing this lemma is that if a representation ρ of G, contains the trivial representation of a normal subgroup H ≤ G when decomposed over H, it can contain no other irreducible representation of H in this decomposition. As a last remark, notice that when H ⊆ ker ρ, then the probability of observing the representation is d_{ρ}^{2} \frac{|H|}{|G|}.

Given Lemma 3 we see that the procedure to determine a hidden subgroup is to sample a series of representations and take the intersection of the kernels of these. After a sufficient number of samples, with high probability the intersection of the kernels of the sampled representations will be the hidden subgroup H. The number of such samples required will be linear in the size of the input. However, intersecting the kernels of the representations is a problem with complexity related to the underlying group and thus little can be said of this in general. This last operation will typically be performed classically.

4.2.2 Measuring the Fourier Coefficients

One might hope that by not restricting ourselves only to the representation names, the obstacle on non-normal subgroups might be overcome. There is so far no indication that this might be the case. One of the main problems is that whereas previously the distribution of F |cH⟩ was independent of the coset, when we measure the Fourier coefficients individually this is no longer true. This follows from the fact that the Fourier coefficients ρ_{ij} are not homomorphisms in general. Surprisingly, the consequence of this will be that measuring the rows provides no additional information whatever. But there are further problems. The probability of observing (ρ, i, j) is a function of

∑_{h∈H} ρ(gh)_{ij} = ∑_{k=1}^{d_{ρ}} ρ(g)_{ik} (∑_{h∈H} ρ(h)_{kj})

We may now reason as for representation names. The representation ρ can be decomposed into irreducibles over H, and a basis can be chosen so that ρ(h) will have block diagonal form for all h ∈ H. Once in this form, we know that ∑_{h∈H} ρ(h)_{kj} = 0 unless (k, j) is the coordinate of a diagonal entry which corresponds to a manifestation of the trivial representation of H. In the latter case ∑_{h∈H} ρ(h)_{kj} = 1. It would seem then that despite the difficulty of dependence on the coset there are nonetheless interesting properties to be exploited similar to those which served us so well in the last section. However, here again we are foiled for the actual expression for the probability of observing (ρ, i, j) for a fixed coset gH is,

\frac{d_{ρ}}{|G||H|}| ∑_{h∈H} ρ_{ij}(gh)|^{2}

which very sadly depends on the basis of the representation space. The loss of freedom in choosing bases is a severe obstacle and in particular means that the tidy conclusions made about the sum ∑_{h∈H} ρ_{ij}(gh) cannot be used.

The dependence of the above probability on the coset implies that we are actually sampling from the statistical mixture,

\{(F (|gH⟩), \frac{1}{|G|})\}_{g∈G}

Therefore, the resulting probability of obtaining (ρ, i, j) is

\frac{d_{ρ}}{|H||G|^{2}} ∑_{g∈G} | ∑_{h∈H} ρ_{ij}(gh)|^{2}

For the sake of brevity let us write ρ(H) to signify ∑_{h∈H} ρ(h). Let us further define an ordering of the group elements, (g_{1}, g_{2}, …, g_{n}), where n = |G|. This allows us to restate the sum ∑_{g∈G} | ∑_{h∈H} ρ_{ij}(gh)|^{2} as the norm squared of the complex vector,

v = (ρ(g_{1}H)_{ij}, ρ(g_{2}H)_{ij}, …, ρ(g_{n}H)_{ij})

As ρ is a homomorphism, we know that ρ(gH)_{ij} = ∑_{k=1}^{d_{ρ}} ρ(g)_{ik}ρ(H)_{kj} and so,

v = ∑_{k=1}^{d_{ρ}} (ρ(g_{1})_{ik}, ρ(g_{2})_{ik}, …, ρ(g_{n})_{ik}) ρ(H)_{kj} ≡ ∑_{k=1}^{d_{ρ}} v_{ik} (ρ(H)_{kj})

It turns out that the vectors v_{ik} are orthogonal with respect to the standard inner product (X, Y) = XY^{†}. This follows from the orthogonality relations of the Fourier coefficients. For notice that,

(v_{ik}, v_{il}) ≡ v_{ik}v_{il}^{†} = ∑_{j=1}^{n} ρ_{ik}(g_{j})\overline{ρ_{il}(g_{j})} = n⟨ρ_{ik}|ρ_{il}⟩

Therefore,

(v_{ik}, v_{il}) = \{ \begin{matrix}0 & if k ≠ l \\ \frac{n}{d_{ρ}} & if k = l \end{matrix}

The conclusion is that the probability of observing the triple (p, i, j) by measuring the given statistical mixture is,

\frac{d_{ρ}}{|H||G|^{2}} ∑_{g∈G} | ∑_{h∈H} ρ_{ij}(gh)|^{2} = \frac{1}{|G||H|} ∑_{k=1}^{d_{ρ}} |ρ(H)_{kj}|^{2}

This shows that the probability of observing (ρ, i, j) is a linear function of ρ(H) and completely independent of the row. Thus if we are to extend the type of measurement from the representation name, we need at most to measure the name and columns. Please note that ∥ρ(H)_{j}∥^{2} is also a quantity which is dependent on the basis. The second general result is that if the basis is chosen randomly, only a negligible amount of additional information can be obtained. This does not exclude the possibility that a more deliberate choice of bases might prove more fruitful.

Dihedral Groups and Their

Hidden Subgroups

As a summary of the results we have just seen, we will look at a specific family of groups, the dihedral group. This provides a interesting context because it is a group which is noncommutative yet with a structure otherwise near to that of an Abelian group. On the other hand it is complex enough that the obstacles anticipated in the previous section cannot be avoided.

Definition The dihedral group of order 2N, denoted by D_{N} is the group of symmetries of the regular N-sided polygon in the plane. It is generated by two elements a and b subject to the following relations,

(i) a^{N} = e (ii) b^{2} = e (iii) ab = ba^{−1}

Thus, the generator a corresponds to a rotation about the center of the polygon of \frac{2π}{N} and b to any one of it’s reflection symmetries. Note that every element of the group D_{N} can be written as b^{s}a^{r} for some choice of s and r.

We will limit our attention only to the case where N = 2^{n} or in other words, dihedral groups of order 2^{n+1}. Not only is this a natural first step in quantum computing, but again it is only for groups of such orders that efficient implementations of the QFT currently exist. The reason for this might be found in the fact that the dihedral groups of order 2^{n} are exactly those which are nilpotent, although this requires more investigation.

We may also view the group D_{N} as the semi-direct product between the two cyclic groups ℤ_{N} and ℤ_{2}. This means that every element of D_{N} may be viewed as a pair (x, y) such x ∈ ℤ_{N} and y ∈ ℤ_{2} and with multiplication defined by,

(x_{1}, y_{1}) · (x_{2}, y_{2}) = (x_{1} + (−1)^{y_{1}}x_{2}, y_{1} ⊕ y_{2})

We can relate the two definitions by setting a = (1, 0) and b = (0, 1).

Let us now look at the subgroups of D_{N}. It is clear that K = ⟨a⟩ = {(x, 0)|x ∈ ℤ_{N}} is a subgroup of D_{N} of order N, isomorphic to ℤ_{N}. It is also normal in D_{N}. All other normal subgroups of the dihedral group are also subgroups of K. In fact they can all be assembled in a chain of inclusion,

K_{1} ◁ K_{2} ◁ … ◁ K_{n} = K ◁ D_{N}

where for each 0 ≤ i ≤ n is the cyclic subgroup of D_{N} of order 2^{i} generated by a^{2^{n−i}}. There are no other normal subgroups of D_{N} apart from those listed.

Besides these normal subgroups there is one more family which will complete the list of all cyclic subgroups of D_{N}. Each has order two and is of the form H_{t} = {e, ba^{t}} with 0 ≤ t ≤ N − 1. Not only are these not normal but the conjugacy class of H_{t} contains \frac{N}{2} subgroups. Every other subgroup of D_{N} can be described as the product of at most two of those we have just seen. In other words they are of the form K_{i}H_{t} for some 0 ≤ i ≤ n, 0 ≤ j ≤ N − 1. In particular notice that K_{i}H_{0} is a subgroup of D_{N} isomorphic to D_{2^{i−1}} for every admissible i. We conclude that every subgroup of the dihedral group can be written as K_{i}L with L = e or L = H_{t} for some t.

5.1 The Representations of the Dihedral Group

Again Lemma 1 will be extremely useful in proving that the following representations are irreducible.

Claim 2 Let ρ_{k} : D_{N} → GL_{ℂ}(ℂ^{2}) be the map given by

ρ_{k}(a^{r}) = ( \begin{matrix}ω_{N}^{kr} & 0 \\ 0 & ω_{N}^{−kr} \end{matrix} ) ρ_{k}(ba^{r}) = ( \begin{matrix}0 & ω_{N}^{−kr} \\ ω_{N}^{kr} & 0 \end{matrix} )

Then, ρ_{k} is an irreducible representation for each k = 1, …, N − 1 and k ≠ \frac{N}{2} . Moreover, each ρ_{k} is equivalent to only one other representation in this list, ρ_{k^{−1}}.

Proof Let ρ_{k} be defined as above and let χ_{k} be the associated character. Clearly, χ_{k}(a^{r}) = ω_{N}^{kr} + ω_{N}^{−kr} and χ_{k}(ba^{r}) = 0. It is also easily verified that ρ_{k} is a homomorphism for each k = 1, …, N − 1.

(i) ρ_{k} is irreducible if and only if ⟨χ_{k}|χ_{k}⟩ = 1. By definition,

⟨χ_{k}|χ_{k}⟩ = \frac{1}{2N} ∑_{r=0}^{N−1} ∑_{s=0}^{1}χ_{k}(b^{s}a^{r})\overline{χ_{k}(b^{s}a^{r})}

= \frac{1}{2N} ∑_{r=0}^{N−1}χ_{k}(a^{r})χ_{k}(a^{−r})

= \frac{1}{2N} ∑_{r=0}^{N−1} (ω_{N}^{2kr} + 2ω_{N}^{k(r−r)} + ω_{N}^{−2kr})

= 1 + \frac{1}{2N} ∑_{r=0}^{N−1}ω_{N}^{2kr} + \frac{1}{2N} ∑_{r=0}^{N−1}ω_{N}^{−2kr}

For each k = 1, …, N − 1, k ≠ \frac{N}{2} , we have N |̸2k and N |̸(−2k). Then by Lemma 1,

∑_{r=0}^{N−1} ω_{N}^{2kr} = 0 = ∑_{r=0}^{N−1} ω_{N}^{−2kr}

Therefore, ⟨χ_{k}|χ_{k}⟩ = 1 and the representation ρ_{k} is irreducible for all such k.

(ii) ρ_{k_{1}} and ρ_{k_{2}} are inequivalent irreducible representations iff ⟨χ_{k_{1}}|χ_{k_{2}}⟩ = 0. Now by definition, for 1 ≤ k_{1} < k_{2} ≤ N − 1 and k_{1}, k_{2} ≠ \frac{N}{2} , we have

⟨χ_{k_{1}}|χ_{k_{2}}⟩ = \frac{1}{2N} ∑_{r=0}^{N−1} ∑_{s=0}^{1}χ_{k_{1}}(b^{s}a^{r})\overline{χ_{k_{2}}(b^{s}a^{r})}

= \frac{1}{2N} ∑_{r=0}^{N−1}χ_{k_{1}}(a^{r})χ_{k_{2}}(a^{−r})

= \frac{1}{2N} ∑_{r=0}^{N−1} (ω_{N}^{r(k_{1}+k_{2})} + ω_{N}^{−r(k_{1}+k_{2})} + ω_{N}^{r(k_{1}−k_{2})} + ω_{N}^{−r(k_{1}−k_{2})})

As k1 < k_{2} it follows immediately that N |̸(k_{1} − k_{2}) and that N |̸(−(k_{1} − k_{2})). Now, for 1 ≤ k_{1}, k_{2} ≤ N − 1, if N|(k_{1} + k_{2}) then k_{2} = k_{1}^{−1}. Therefore, if k_{2} ≠ k_{1}^{−1} then the sum of each of the terms is zero. In this case ρ_{k_{1}} and ρ_{k_{2}} are inequivalent.□

Therefore, by taking k = 1, …, \frac{N}{2} − 1 we have found a set of \frac{N}{2} − 1 inequivalent irreducible representations of the group D_{N}, each of dimension two. The set can be made complete by adding the following one-dimensional representations:

(i) τ_{0} : G → GL_{ℂ} with τ_{0}(a^{r}) = (1) and τ_{0}(ba^{r}) = (1)

(ii) τ_{1} : G → GL_{ℂ} with τ_{1}(a^{r}) = (1) and τ_{1}(ba^{r}) = (−1)

(iii) τ_{2} : G → GL_{ℂ} with τ_{2}(a^{r}) = (−1)^{r} and τ_{2}(ba^{r}) = (−1)^{r}

(iv) τ_{3} : G → GL_{ℂ} with τ_{3}(a^{r}) = (−1)^{r} and τ_{3}(ba^{r}) = (−1)^{r+1}

5.2 The QFT for the Dihedral Group

Now that we have pinpointed a precise complete set of irreducible representations of the dihedral group D_{N}, we may write down explicitly the form of the QFT. Recall that we had the following expression in general,

F (|g⟩) = ∑_{ρ∈R} ∑_{1≤i,j≤d_{ρ}} \sqrt{\frac{d_{ρ}}{|G|}}ρ_{i,j}(g)|ρ, i, j⟩

Consider the expression now with the representations we know,

F (|g⟩) = \frac{1}{\sqrt{2N}} (∑_{q=0}^{3} χ_{τ_{q}}(g)|τ_{q}⟩ + ∑_{k=1}^{\frac{N}{2} −1} ∑_{1≤i,j≤2} \sqrt{2}ρ_{k}(g)_{i,j}|ρ_{k}, i, j⟩)

By setting |g⟩ = |a^{r}⟩ we have,

F (|a^{r}⟩) = \frac{1}{\sqrt{2N}} (∑_{q=0}^{3} χ_{τ_{q}}(g)|τ_{q}⟩ + ∑_{k=1}^{\frac{N}{2} −1} ∑_{1≤i,j≤2} \sqrt{2}ρ_{k}(a^{r})_{i,j}|ρ_{k}, i, j⟩)

Which simplifies to,

F (|a^{r}⟩) = \frac{1}{\sqrt{2N}} (∑_{q=0}^{3} χ_{τ_{q}}(g)|τ_{q}⟩ + \sqrt{2} ∑_{k=1}^{\frac{N}{2} −1} (ω_{N}^{kr}|ρ_{k}, 1, 1⟩ + ω_{N}^{−kr}|ρ_{k}, 2, 2⟩))

On the other hand suppose we set |g⟩ = |ba^{r}⟩, then we obtain,

F (|ba^{r}⟩) = \frac{1}{\sqrt{2N}} (∑_{q=0}^{3} χ_{τ_{q}}(g)|τ_{q}⟩ + \sqrt{2} ∑_{k=1}^{\frac{N}{2} −1} (ω_{N}^{−kr}|ρ_{k}, 2, 1⟩ + ω_{N}^{kr}|ρ_{k}, 1, 2⟩))

Notice that in the expression for the state F |a^{r}⟩ all the basis states |ρ_{k}, i, j⟩ have amplitudes of norm 0 when i ≠ j and amplitudes of norm 1 when i = j. In contrast in the state F |ba^{t}⟩ the situation is the reverse.

5.3 Examples for Dihedral Hidden Subgroup

Problem

Let D_{N} be the dihedral group of order 2N and let f be a function which fulfills the hidden subgroup promise on D_{N} with respect to some subgroup H ≤ D_{N}.

We saw that any subgroup of D_{N} can be written as the product K_{i}L where K_{i} is the cyclic subgroup ⟨a^{2^{n−i}}⟩ and L = {e} or L = H_{t} = {e, ba^{t}}. So in particular, without loss of generality we say that the hidden subgroup H = K_{j}L. By restricting f to K_{n} we create an instance of the Abelian Hidden Subgroup Problem for this restriction of f fulfills the hidden subgroup promise for K_{j} ≤ K_{n}. As K_{n} is both Abelian and smooth, we have a quantum algorithm for finding K_{j} efficiently.

Now, once the generator of K_{j} has been found, and as K_{j} is a normal subgroup, we will be able to construct a homomorphism φ : D_{N} → D_{2^{n−i}} with kernel K_{i}. Then, the composition f ∘ φ will hide L in D_{2^{n−i}} just as before f hid K_{j}L. In this way the problem of finding an arbitrary hidden subgroup in D_{N} is reduced to finding one which is either trivial or H_{t} for some 0 ≤ t ≤ N − 1. Of course, while the situation has become much simpler to describe, it remains nontrivial. For not only are there an exponential number in the size of the input n of such subgroups in D_{N}, but also none of the H_{t} are normal. Hence we immediately run into a serious obstacle, the method of measuring only the representation name cannot distinguish between conjugate subgroups. Even if this method could be used to determine a conjugacy class, the size of the conjugacy class of each H_{t} is still exponential in n. It would be impossible then by inspection alone to determine the hidden subgroup within its conjugacy class in polynomial time.

5.3.1 Finding Normal Subgroups

We have seen how all normal subgroups of D_{N} can be found by restricting the function f to the subgroup of D_{N} which is isomorphic to the cyclic group ℤ_{N}. However, since our interest lies more in examining the properties of the QFT, than in solving the Hidden Subgroup Problem, let us briefly see how we may find hidden normal subgroups using the QFT for D_{N}, rather than with the previous shortcut.

Let |cH⟩ be a random coset state of a subgroup H ◁ D_{N} where H is generated by an element a^{t} for some 0 ≤ t ≤ N − 1. Little can be learned in this case if the result of the measurement is one of the τ_{q}. This would occur with probability \frac{|H|}{2^{N−2}} . When the result of a measurement is one of the ρ_{k} we learn a great deal more. The probability of observing ρ_{k} from a measurement of F (|cH⟩) is,

\frac{1}{|H|2^{N−1}} ∑_{i,j} | ∑_{h∈H} ρ_{i,j}(ch)|^{2}

No matter the coset we are considering, for some 0 ≤ r ≤ N − 1 the above can be written as,

= \frac{2}{|H|2^{N−1}} | ∑_{s=0}^{|H|−1}ω_{N}^{(r+st)k}|^{2}

= \frac{2}{|H|2^{N−1}} |ω_{N}^{rk}|^{2}| ∑_{s=0}^{|H|−1}ω_{N}^{(tk)s}|^{2}

= \frac{2}{|H|2^{N−1}} | ∑_{s=0}^{|H|−1}ω_{N}^{(tk)s}|^{2}

This probability is non-zero if and only if n|(kt) in which case it is \frac{|H|}{2^{N−2}} . The procedure for determining t so that H = ⟨a^{t}⟩ is the same as was used for Abelian groups. Note that if we wish to accomplish the reduction from a hidden subgroup K_{j}L to L only, we cannot use this last method and must first restrict the function f to K_{n}.

5.3.2 Distinguishing Between |H| = 1 and |H| = 2

Let us return now to the reduced problem of determining a hidden subgroup H ≤ D_{N} when H is promised to be either trivial or one of the H_{t} = {e, ba^{t}}. We know that there is no hope of finding the hidden subgroup by measuring only the representation name. However, perhaps we would be more lucky if the entire Fourier coefficient name were measured instead. Unfortunately this is not the case and we show this by considering an equivalent problem.

One of the results of Hallgren, Russell and Ta-Shma ([7]), which we did not cover, is that one cannot use the Quantum Fourier Transform to distinguish between a subgroup of order 1 and one of order 2 in the Symmetric group S_{n}. Specifically, their result applies to the case where only the representation name is measured. Here we will see a similar result for Dihedral groups with the difference that we will be measuring the indices as well. Note that we are not including the normal subgroup of order 2 in D_{N}, \{e, a^{\frac{N}{2}} \} as one of the instances which the algorithm need distinguish. This is important to determine for the two problems are equivalent. If we had an algorithm which finds a hidden subgroup H ≤ D_{N} of the required form, then we necessarily learn its order. On the other hand, an efficient means of determining the order of a hidden subgroup H in a dihedral would enable us to determine H explicitly using the approach we will now describe.

Let ϕ : D_{N} → D_{\frac{N}{2}} be the group homomorphism given by,

ϕ(b^{s}a^{r}) = \{ \begin{matrix}b^{s}a^{r} & if r < \frac{N}{2} \\ b^{s} & if r = \frac{N}{2} \\ b^{s}a^{r− \frac{N}{2}} & if r > \frac{N}{2} \end{matrix}

Suppose that H = \{e, ba^{t}\}. It is easily verified that if t > \frac{N}{2} then, f ∘ ϕ hides the trivial subgroup in D_{\frac{N}{2}} . Whereas if t < \frac{N}{2} , the function f ∘ ϕ would still hide H ≤ D_{\frac{N}{2}} .

Therefore, if one had an oracle O for deciding whether a hidden subgroup K was of order 1 or of order 2 in a dihedral group, one could construct a recursive algorithm A as follows:

A(D_{K}, g)

1. If g(ba^{\frac{K}{2}} ) = g(0) then return (ba^{\frac{K}{2}} )

2. Otherwise, apply the oracle O to D_{K} and g ∘ ϕ.

3. If the oracle answers that the hidden subgroup has order two then return (A(D_{\frac{K}{2}} , g)). Otherwise the subgroup was trivial. So, return (A(D_{\frac{K}{2}} , g ∘ ξ)a^{\frac{K}{2}} ). Where ξ : D_{\frac{K}{2}} → D_{K} is given by,

ξ(b^{s}a^{r}) = \{ \begin{matrix}a^{r} & if s = 0 \\ ba^{r+ \frac{K}{2}} & if s = 1 \end{matrix} for all 0 ≤ r ≤ \frac{K}{2} − 1

We precede algorithm A by a call to the oracle on D_{N} and f to eliminate the possibility that the hidden subgroup H is initially trivial. Then, by running A(D_{N}, f), at each step of the recursion we learn the current most significant bit of t such that H = {e, ba^{t}}. Thus finding the value of t in a linear number of recursive steps.

It is clear that when H is the trivial subgroup, a random coset of H is simply a random element of the group. Therefore, when we are sampling from the Fourier transform of these, we are in fact sampling from the statistical mixture,

\{(F (|g⟩), \frac{1}{2N} )\}_{g∈G}

From earlier findings we know that the probability of observing the triple (ρ_{k}, i, j) from this statistical mixture is,

\frac{1}{|2N|}∥ρ(e)_{j}∥^{2} = \frac{1}{|2N|}(|1|^{2} + |0|^{2}) = \frac{1}{|2N|}

where ρ_{k}(e)_{j} is the j^{th} column of ρ_{k}(e). The remaining representations τ_{0}, τ_{1}, τ_{2}, and τ_{3} each being one-dimensional are also each observed with this same probability. The result is that all of the Fourier coefficients are observed with equal probability \frac{1}{2N}.

Suppose now that H = {e, ba^{t}}. Then the form of a random coset of H is {a^{r}, ba^{t−r}}. As each coset has two possible representatives, we are sampling now from the statistical mixture,

\{(\frac{F |a^{r}⟩ + F |ba^{t−r}⟩}{\sqrt{2}}, \frac{1}{N} )\}_{r=0}^{N−1}

In this case the probabilities of observing a triple (ρ, i, j) is still \frac{1}{2N} exactly as when H was trivial. For, if we take j = 1 (and the other case j = 2 gives the same value), the probability of observing (ρ, i, 1) is,

\frac{1}{2} \frac{1}{N} ∥ρ_{k}(e)_{1} + ρ_{k}(ba^{t})∥^{2} = \frac{1}{2N} (|1|^{2} + |ω_{n}^{kt}|^{2}) = \frac{1}{2N}

The only differences appear in the distribution of the τ_{q}’s. Specifically,

- τ_{0} is observed with probability \frac{1}{N}, hence twice as often as when H is trivial.

- τ_{1} is observed with probability 0.

- Depending on the value of t, one of τ_{2} and τ_{3} is observed with probability \frac{1}{N} and the other not at all.

The differences are so small that we can see how a polynomial number of samples would be insufficient to distinguish between the two cases with any reasonable degree of confidence. Of course, as this was based on a specific choice of basis for each representation, the evidence is not conclusive. In contrast if we only perform a partial measurement of the representation name, then there is absolutely no way of distinguishing directly between some H_{t} and the trivial subgroup efficiently. The underlying problem is that for any hidden subgroup of the form H_{t}, every representation ρ_{k} decomposes identically over H_{t} as the direct sum of both irreducibles of the subgroup. Explicitly recall that when we perform a partial measurement, the probability of observing ρ is,

\frac{d_{ρ}}{|G|} ∑_{h∈H} χ_{ρ}(h)

independent of the basis on which ρ is expressed. Therefore, when H = H_{t}, the probability of observing the name ρ_{k} is,

\frac{2}{2N} (χ_{k}(e) + χ_{k}(ba^{t})) = \frac{1}{N} (2 + 0) = \frac{2}{N}

If, however H = \{e\}, the probability of observing ρ_{k} is still \frac{1}{N} (χ_{k}(e)) = \frac{2}{N}. The relative probabilities of observing the τ_{i}’s are exactly the same as for complete measurements, for they are all one-dimensional. In summary, we conclude that the Fourier Transform does not allow us to distinguish between subgroups of order 1 and order 2 no matter the basis if we only measure the representation name.

Conclusion

This thesis has sought to provide a thorough study of the Quantum Fourier Transform for finite groups of which there is a lack in the existing literature. Previously, the mathematics concerned in the construction of the QFT were only briefly summarised in papers whose focus was the presentation of an algorithm that made use of it. Yet, for the purposes of further research in the area of quantum algorithms, a true understanding is necessary. Thus, whereas before the uninitiated would be required to combine elements from many sources in several different fields, now these can be found integrated in a single source.

The relationship of the Quantum Fourier Transform and the Hidden Subgroup Problem was also firmly established. It shows the mechanism by which the QFT creates interference and the extent to which, according to current knowledge, this can be used. We learned that the partial measurement of representation names has well defined limits. Subsequently, we saw that complete measurements might be able to extend these but that they require careful choice of bases for the representations. A choice which would depend very much on the group and the type of interference desired. These considerations were made explicit by the example of the dihedral Hidden Subgroup Problem.

As a good summary of what we learned of the Quantum Fourier Transform, consider the function given by,

|gH⟩ = ∑_{ρ∈R} (\sqrt{\frac{d_{ρ}}{|G|}} ∑_{h∈H} χ_{ρ}(h)) |ρ⟩

The above gives exactly the same distribution on the representation names as the QFT on any group and for any subgroup H. It allows us to see at a glance the advantages the QFT possess when measurement is restricted to representation names: The right-hand side is independent of the coset and independent of the choice of basis for the representation space of each ρ ∈ R. This last characteristic is the most important. It is the crucial element which is lost when moving from a partial measurement to a complete one.

Earlier we alluded to other problems which have been shown to be special cases of the Hidden Subgroup Problem. Besides Simons problem, these include Shors factorization and discrete logarithm algorithms ([17]) and Kitaevs Abelian stabilizer problem ([11]). Regarding the non-Abelian Hidden Subgroup Problem, there are a few results which were not included in the main body that need mentioning. These were excluded on the basis that although they almost all make use of the Quantum Fourier Transform, the algorithms used contain important variations. This renders the results less interesting for use as illustrative examples of the Quantum Fourier Transform at work. The first step was made by Ettinger and Høyer ([3]). They were able to devise an algorithm for solving the Hidden Subgroup Problem for the dihedral case which used only a linear number of samples from coset states.

However, the algorithm remained inefficient as determining the subgroup required an exponential-time classical algorithm to process the information obtained from the samples. Furthermore, the algorithm uses the Quantum Fourier Transform for the Abelian group ℤ_{N} × ℤ_{2}, rather than the one for dihedral group proper.

Very soon after Rötteler and Beth ([15]) developed the first polynomialtime algorithm for solving the HSP in a noncommutative case. The group they considered was the wreath product group ℤ_{N} ≀ ℤ_{2}. This was followed by another paper by Ettinger, Høyer and Knill ([5]) which shows that information theoretically, it is possible to determine an arbitrary hidden subgroup for any fixed group with only a linear number of samples. Unfortunately they were unable to discover how this could be done and again their result required an exponential-time classical algorithm to analyse the samples. The results of Hallgren, Russell and Ta-Shma ([7]), as well as those of Grigni, Schulman, Vazirani ([6]) we have already covered. Lately, Ivanyos, Magniez and Santha ([9]) were able to find polynomial time solutions to the Hidden Subgroup Problem for a few select classes of noncommutative groups with the added virtue that they allowed for the group to be given in a black box.

Bibliography

[1] M. Artin. Algebra. (Prentice-Hall, New Jersey), 1991.

[2] G. Brassard, P. Høyer. An Exact Quantum Polynomial-Time Algorithm for Simon’s Problem. Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems. pages 12-33. ISTCS IEEE Computer Society Press, 1997. LANL preprint quant-ph/9704027, April 1997.

[3] M. Ettinger, P. Høyer. On Quantum Algorithms for Noncommutative Hidden Subgroups. LANL preprint quant-ph/9807029, July 1998.

[4] M. Ettinger, P. Høyer. Quantum State Detection via Elimination. LANL preprint quant-ph/9905099, May 1999.

[5] M. Ettinger, P. Høyer, E. Knill. Hidden Subgroup States are Almost Orthogonal. LANL preprint quant-ph/9901034, 1999.

[6] M. Grigni, L. Schulman, M. Vazirani and U. Vazirani. Quantum Mechanical Algorithms for the Nonabelian Hidden Subgroup Problem. Proc. 33rd Annual ACM Symposium on the Theory of Computing-STOC 2001. (ACM Press, New York), 68-74.

[7] S. Hallgren, A. Russell, A. Ta-Shma. Normal Subgroup Reconstruction and Quantum Computation Using Group Representations. Proc. 32nd Annual ACM Symposium on the Theory of Computing-STOC 2000. (ACM Press, New York), 627-35.

[8] P. Høyer.Efficient Quantum Transforms. LANL preprint quantph/9702028, February 1997.

[9] G. Ivanyos, F. Magniez, M. Santha. Efficient Quantum Algorithms for some Instances of the Non-Abelian Hidden Subgroup Problem. LANL preprint quant-ph/0102014, February 2001.

[10] R. Jozsa. Quantum Factoring Discrete Logarithms, and the Hidden Subgroup Problem. LANL preprint quant-ph/0012084, 2000.

[11] A. Yu. Kitaev. Quantum Measurement and the Abelian Stabilizer Problem. LANL preprint quant-ph/9511026, November, 1995.

[12] M. Mosca, A. Ekert. The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer. LANL preprint quant-ph/9903071, 1999.

[13] M. Püschel, M. Rötteler, T. Beth. Fast Quantum Fourier Transforms for a Class of Non Abelian Groups. LANL preprint quant-ph/9807064, 1998.

[14] D. Rockmore. Some Applications of Generalized FFTs. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 28, 1997.

[15] M. Rötteler, T. Beth. Polynomial-Time Solution to the Hidden Subgroup Problem for a Class of Non-Abelian Groups. LANL preprint quantph/9812070, December 1998.

[16] J.-P. Serre. Linear Representations of Finite Groups. Graduate Texts in Mathematics, volume 42. (Springer-Verlag, New York), 1977.

[17] P. W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal of Computing, Vol. 26, No. 5, 1484-1509, October 1997

[18] D. R. Simon. On the Power of Quantum Computing. SIAM Journal of Computing, Vol. 26, No. 5, 1474-1483, October 1997.

Appendix A

Group Theory

Formally, a group is a triple (G, ·, e) composed of a set G equipped with an associative operation “·” on the members of the set such that,

(i) There is a unique element e known as the identity with the property that ∀g ∈ G, e · g = g · e = g.

(ii) For every element g of the group there is an inverse element g^{−1} with respect to the operation “·”. That is, ∀g ∈ G, ∃g^{−1} ∈ G such that g · g^{−1} = g^{−1} · g = e.

Note that in the above definition, there is no requirement that the group operation be commutative. When this is the case the group is said to be Abelian. One should note that it follows from the definition that the inverse of an element is unique.

Typically the group (G, ·, e) is referred to simply by G. In agreement with set notation, the number of elements in a group is called the order of the group and is denoted |G|. We will only deal with those groups of finite order. The structure and properties of groups can vary enormously depending on the choice of set and operation. The following are some common examples:

- The symmetric group of order n, S_{n}, is the set of all permutations of n objects, together with the composition operation. It has order n!. Interestingly, it can be shown that every group of order n is equivalent to a subgroup of S_{n}.

- The group ℤ_{N} is defined by taking, for some fixed integer n, the set {0, 1, …, n − 1}. The operation on this set is then addition modulo n. Thus, for a, b ∈ ℤ_{N}, a·b ≡ a+b( mod n). It follows that 0 is the identity element of the group. The group ℤ_{n} has order n and is Abelian. It is often taken as the representative of the cyclic group of order n.

- For any vector space V over a field 𝕂, the set of all linear transformations from V to V forms a group under composition. It is known as the general linear group over V and is denoted GL_{𝕂}(V). If the vector space V has dimension n then, by fixing a basis of V, the group can be associated to all n × n invertible matrices with entries in the field 𝕂 in the chosen basis. In this case the group operation is matrix multiplication.

- For any vector space V over a field 𝕂, the set of all unitary transformations from V to V also forms a group under composition. It is known as the unitary group over V and is denoted U_{𝕂}(V).

A.1 Subgroups

A non empty subset H ⊆ G which fulfills the properties of a group with respect to the operation defined on G is called a subgroup of G which we denote by H ≤ G. Precisely, H ⊆ G is subgroup if we have:

(i) Closure: a, b ∈ H ⇒ a · b ∈ H (iii) a ∈ H ⇒ a^{−1} ∈ H.

Suppose we choose some g ∈ G, and consider the set of all powers of g, {g, g^{2}, …, g^{k}, …}. As each g^{i} must be an element of the group, which is finite, then there must exist repetitions of group elements in the set. That is, for some integers i > j, we must have g^{i} = g^{j}. It follows by the definition of the group that g^{i−j} = e. We conclude that for every element g of a finite group, there exists an integer n such that g^{n} = e. The smallest such positive integer is known as the order of g. Now let n be the order of g ∈ G, (also denoted |g|), and let ⟨g⟩ = {e, g, g^{2}, …, g^{n−1}}. The set ⟨g⟩ forms a subgroup of G of order n. It is said to be the subgroup generated by the element g as it consists only of products of g with itself. Indeed, for any subset S of elements of a group we may consider the subgroup generated by S, ⟨S⟩. In accordance with what we have already seen, this subgroup consists of all distinct products between elements of S.

If H ≤ G is a subgroup then consider the sets gH = {gh|h ∈ H} for all g ∈ G. These are known as the cosets of H in G. They define an equivalence relation ≡_{H} on the group elements by the property x ≡_{H} y ⇔ xH = yH ⇔ y^{−1}x ∈ H. As with any equivalence relation, this creates a partition of G into equivalence classes. The definition of the relation implies that the number of partitions is exactly the number of distinct cosets of the subgroup H ≤ G. Suppose we denote this quantity by [G : H], called the index of H in G, and note that the number of elements in each coset gH is exactly |H|. Then this leads to the following theorem, Theorem 5 (Lagrange) Let G be a group and let H ≤ G be a subgroup of

G. Then,

|G| = [G : H]|H|

As a corollary, remark that the order of a subgroup divides the order of the group. Furthermore we saw that the subgroup generated by an element g contained precisely |g| elements. Therefore, by Lagrange, the order of an element must also divide the order of the group. In general it is important to distinguish between left cosets gH and right cosets Hg when the group operation is not commutative. The properties of these two are the same but they are not interchangeable once a choice has been made. There may exist subgroups for which the left and right cosets are all equal. These are all called normal subgroups. By definition, if N ≤ G is a normal subgroup of a group G then,

gN = Ng ∀g ∈ G ⟺ gNg^{−1} = N ∀g ∈ G

If N is a normal subgroup of G, then the set of all distinct cosets of N also forms a group. This is called the quotient or factor group of N and is written G/N. The operation in this group is defined as follows,

∀aN, bN ∈ G/N (aN) · (bN) = (ab)N

The identity element of the group is the coset 1N = N. The order of the group G/N is clearly the index of N in G. Therefore for a normal subgroup N, |G| = |G/N||N|.

A.2 Isomorphisms and Homomorphisms

Two groups G_{1} and G_{2} are said to be isomorphic if they are equivalent up to a renaming of their elements. When confronted with two groups, to show that this is the case, we require a well defined function φ : G_{1} → G_{2} which will establish this correspondence appropriately. Formally, this implies that the function φ must have the following characteristics:

(i) φ is one-to-one. That is,

∀y ∈ G_{2} ∃x ∈ G_{1} such that y = φ(x)
φ(x_{1}) = φ(x_{2}) ⇒ x_{1} = x_{2} for all x_{1}, x_{2} ∈ G

(ii) φ preserves the group operation for G_{1}. Mathematically,

φ(x)φ(y) = φ(xy) for all x, y ∈ G_{1}

Such a function is known as an isomorphism between the groups G_{1} and G_{2}. Suppose that we remove the first condition. It that case, the function is known as a homomorphism. This of course no longer serves to establish equivalence of groups, but is nonetheless very useful. To any homomorphism ϕ we can define two sets, im ϕ = {y ∈ G_{2}|ϕ(x) = y for some x ∈ G_{1} } called the image of ϕ, and ker ϕ = {x ∈ G_{1}|ϕ(x) is the identity in G_{2}} called the kernel of ϕ. The image of ϕ is a subgroup of G_{2} whereas the kernel of ϕ is a subgroup of G_{1}. It is the kernel of a homomorphism which is particularly interesting. It can be shown that the kernel of any homomorphism is always a normal subgroup. Furthermore, for every normal subgroup N ⊴G there exits a homomorphism on G with kernel N. Finally, the quotient group G/ ker ϕ is isomorphic to the image of ϕ.

Now that we are familiar with group isomorphisms we can introduce a important fact used many times in this thesis. Let (G, ·, e) and (G′, ∘, e′) be two groups. From these we can form a new group G × G′ called the direct product of G and G′. Each element of G × G′ is an ordered pair (g, g′) where g ∈ G and g′ ∈ G′. The identity element is (e, e′) and the operation between the elements takes place as follows,

(x, x′)(y, y′) = (x · y, x′ ∘ y′)

It is easily proved that e very Abelian group is isomorphic to a direct product of cyclic groups.

A.3 Group Actions

A final concept to which we refer in the body of the thesis is that of the action of a group on a set. Let G be a group and let S be some set of objects. Suppose that to each g ∈ G we associate an operation ϕ_{g} from S to itself. Then, if the operation meets certain conditions, the group is said to act on the set S. The common notation for group actions is unfortunately somewhat misleading, for it is customary to denote ϕ_{g}(s) by gs. However, as long as we bear in mind that gs is an element of S and does not represent the product of g and s in general, confusion can be avoided.

We require two properties of the action of G on S: First that the action of the identity of the group be the identity operation. That is, es = s for all s ∈ S. The second is the associativity of the action (hg)s = h(gs) for all h, g ∈ G and s ∈ S.

Every group actions defines two main structures, the orbit of s ∈ S, O_{s}, and the stabilizer of s, G_{s}. The former is the set of all images of s under the action of G. That is,

O_{s} = {gs|g ∈ G}

Reminiscent of cosets, O_{s} is a subset of S and defines an equivalence relation in S by which two elements of S are consider equivalent if the belong to the same orbit. The stabilizer of an element s ∈ S is a subgroup of G consisting of all those group elements which fix s. Hence,

G_{s} = {g ∈ G|gs = s}

A common example of a group action occurs when we set S = G and define the operation to be that of left multiplication. Formally, to each g ∈ G we associated the map g_{L} : G → G such that,

∀x ∈ G g_{L}(x) = g · x

In this case, the orbit of each group element is the entire group itself and the stabilizer is the identity. Much more interesting is to have a group G act on the cosets of some subgroup H ≤ G, again by left multiplication. Thus, for all xH ∈ G/H, g(xH) = (gx)H. It is easily verified that O_{H} = G/H and G_{H} = H, where H = eH ∈ G/H. It turns out that every action of a group on a set is equivalent to the action by left multiplication on the cosets of some subgroup of H, as stated in the following:

Theorem 6 Suppose G acts on some set S. Let G_{s} be the stabilizer for some s ∈ S. As G_{s} is a subgroup of G, there is a bijective map ψ : G/G_{s} → O_{s} such that,

ψ(xG_{s}) = xs

Not only does this provide a simple general form for describing all group actions but it also leads to a result inherited from the theorem of Lagrange,

|G| = |G_{s}||O_{s}| ∀s ∈ S

for every group action on a set S.

Appendix B

Concepts from Linear Algebra

B.1 Direct Sums

Let V be a vector space with subspaces W_{1}, W_{2}, …, W_{n}. The span of these subspaces is the set of all vectors v that can be written as a sum of the following form,

v = w_{1} + w_{2} + … + w_{n} such that w_{i} ∈ W_{i} for all i = 1, …, n

This span is denoted by W_{1} + W_{2} + … + W_{n}. These subspaces are said to be independent if every set of vectors {w_{1}, …, w_{n}|w_{i} ∈ W_{i}} is an independent set in the usual way for vectors. Now, if W_{1}, W_{2}, …, W_{N} are independent subspaces of V and additionally they span the entire vector space V, then we say that V is the direct sum of the subspaces W_{1}, …, W_{n} and write

V = W_{1} ⊕ W_{2} ⊕ … ⊕ W_{n}

B.2 Unitary Matrices

Let A be an n × n matrix with complex entries. The adjoint matrix, A^{†}, of A is its conjugate transpose. That is,

If A = (a_{ij}) then A^{†} = (a′_{ij}) where a′_{ij} = \overline{a_{ji}}

Note that especially in references with a more mathematical focus, it is common to see the adjoint denoted A^{∗}. A matrix is said to be unitary if its adjoint is also its inverse. In other words, an n × n matrix A is unitary if and only if,

AA^{†} = A^{†}A = 1_{n×n}

By a result known as the Spectral Theorem, it can be shown that every unitary matrix is diagonalizable. But there are other more powerful properties. The columns of a unitary matrix are mutually orthonormal, as are the rows. The converse statement is that if the columns of an n × n matrix are orthonormal then the matrix is unitary. Additionally, the product of unitary matrices is also unitary and the determinant of a unitary matrix is always 1. If A is a unitary matrix then so are A^{t}, \overline{A}, A^{−1} and the matrix,

[ \begin{matrix}I & 0 \\ 0 & A \end{matrix} ]

Another fact is that unitary matrices preserve the norm of a vector and more generally the inner product (X, Y) = \overline{X}^{t}Y, which is a necessary and sufficient condition for unitary matrices.