{'fraction_non_alphanumeric': 0.04944765912677538, 'fraction_numerical': 0.009790168916944298, 'mean_word_length': 3.7825296995108317, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Efficient Quantum Algorithm for the Hidden Subgroup Problem over Weyl-Heisenberg Groups

Many exponential speedups that have been achieved in quantum computing are obtained via hidden subgroup problems (HSPs). We show that the HSP over Weyl-Heisenberg groups can be solved efficiently on a quantum computer. These groups are well-known in physics and play an important role in the theory of quantum error-correcting codes. Our algorithm is based on non-commutative Fourier analysis of coset states which are quantum states that arise from a given black-box function. We use Clebsch-Gordan decompositions to combine and reduce tensor products of irreducible representations. Furthermore, we use a new technique of changing labels of irreducible representations to obtain low-dimensional irreducible representations in the decomposition process. A feature of the presented algorithm is that in each iteration of the algorithm the quantum computer operates on two coset states simultaneously. This is an improvement over the previously best known quantum algorithm for these groups which required four coset states.


Introduction
Exponential speedups in quantum computing have hitherto been shown for only a few classes of problems, most notably for problems that ask to extract hidden features of certain algebraic structures. Examples for this are hidden shift problems [DHI03], hidden non-linear structures [CSV07], and hidden subgroup problems (HSPs). The latter class of hidden subgroup problems has been studied quite extensively over the past decade. There are some successes such as the efficient solution of the HSP for any abelian group [Sho97,Kit97,BH97,ME98], including factoring and discrete log as well as Pell's equation [Hal02], and efficient solutions for some non-abelian groups [FIM + 03,BCD05]. Furthermore, there are some partial successes for some non-abelian groups such as the dihedral groups [Reg04,Kup05] and the affine groups [MRRS04]. Finally, it has been established that for some groups, including the symmetric group which is connected to the graph isomorphism problem, a straightforward approach requires a rather expensive quantum processing in the sense that entangling operations on a large number of quantum systems would be required [HMR + 06]. What makes matters worse, there are currently no techniques, or even promising candidates for techniques, to implement these highly entangling operations.
The present paper deals with the hidden subgroup problem for a class of non-abelian groups that-in a precise mathematical sense that will be explained below-is not too far away from the abelian case, but at the same time has some distinct non-abelian features that make the HSP over these groups challenging and interesting.
The hidden subgroup problem is defined as follows: we are given a function f : G → S from a group G to a set S, with the additional promise that f takes constant and distinct values on the left cosets gH, where g ∈ G, of a subgroup H ≤ G. The task is to find a generating system of H. The function f is given as a black-box, i. e., it can only be accessed through queries and in particular whose structure cannot be further studied. The input size to the problem is log |G| and for a quantum algorithm solving the HSP to be efficient means to have a running time that is poly(log |G|) in the number of quantum operations as well as in the number of classical operations.
We will focus on a particular approach to the HSP which proved to be successful in the past, namely the so-called standard method, see [GSVV04]. Here the function f is used in a special way, namely it is used to generate coset states which are states of the form 1/ |H| h∈H |gh for random g ∈ G. The task then becomes to extract a generating system of H from a polynomial number of coset states (for random values of g). A basic question about coset states is how much information about H they indeed convey and how this information can be extracted from suitable measurements. 1 A fixed POVM M operates on a fixed number k of coset states at once and if k ≥ 2 and M does not decompose into measurements of single copies, we say that the POVM is an entangled measurement. As in [HMR + 06], we call the parameter k the "jointness" of the measurement. It is known that information-theoretically for any group G jointness k = O(log |G|) is sufficient [EHK04]. While the true magnitude of the required k can be significantly smaller (abelian groups serve as examples for which k = 1), there are cases for which indeed a high order of k = Θ(log |G|) is sufficient and necessary. Examples for such groups are the symmetric groups [HMR + 06]. However, on the more positive side, it is known that some groups require only a small, sometimes even only constant, amount of jointness. Examples are the Heisenberg groups of order p 3 for a prime p for which k = 2 is sufficient [BCD05,Bac08a]. In earlier work [ISS07], it has been shown that for the Weyl-Heisenberg groups order p 2n+1 , k = 4 is sufficient [ISS07].
The goal of this paper is to show that in the latter case the jointness can be improved. We give a quantum algorithm which is efficient in the input size (given by log p and n) and which only requires a jointness of k = 2.
Our results and related work: The family of groups we consider in the present paper are well-known in quantum information processing under the name of generalized Pauli groups or Weyl-Heisenberg groups [NC00]. Their importance in quantum computing stems from the fact that they are used to define stabilizer codes, the class of codes most widely used for the construction of quantum error-correcting codes [CRSS97,Got96,CRSS98].
In a more group-theoretical context, the Weyl-Heisenberg groups are known as extraspecial p-groups (actually, they constitute one of the two families of extraspecial p-groups [Hup83]). A polynomial-time algorithm for the HSP for the extraspecial pgroups was already given by Ivanyos, Sanselme, and Santha, [ISS07]. Our approach differs to this approach in two aspects: first, our approach is based on Fourier sampling for the non-abelian group G. Second, and more importantly, we show that the jointness k, i. e., the number of coset states that the algorithm has to operate jointly on, can be reduced from k = 4 to k = 2. Crucial for our approach is the fact that in the Weyl-Heisenberg group the labels of irreducible representations can be changed. This is turn can be used to "drive" Clebsch-Gordan decompositions in such a way that low-dimensional irreducible representations occur in the decomposition.
It is perhaps interesting to note that for the Weyl-Heisenberg groups the states that arise after the measurement in the Fourier sampling approach (also called Fourier coefficients) are typically of a very large rank (i. e., exponential in the input size). Generally, large rank usually is a good indicator of the intractability of the HSP, such as in case of the symmetric group when H is a full support involution. Perhaps surprisingly, in the case of the Weyl-Heisenberg group it still is possible to extract H efficiently even though the Fourier coefficients have large rank. We achieve this at the price of operating on two coset states at the same time. This leaves open the question whether k = 1 is possible, i. e., if the hidden subgroup H can be identified from measurements on single coset states. We cannot resolve this question but believe that this will be hard. Our reasoning is as follows. Having Fourier coefficients of large rank implies that the random basis method [RRS05,Sen06] cannot be applied. The random basis method is a method to derive algorithms with k = 1 whose quantum part can be shown to be polynomial, provided that the rank of the Fourier coefficients is constant. 2 Based on this we therefore conjecture that any efficient quantum algorithm for the extraspecial groups will require jointness of k ≥ 2.
Finally, we mention that a similar method to combine the two registers in each run of the algorithm has been used by Bacon [Bac08a] to solve the HSP in the Heisenberg groups of order p 3 . The method uses a Clebsch-Gordan transform which is a unitary transform that decomposes the tensor product of two irreducible representations [Ser77] into its constituents. The main difference between the Heisenberg group and the Weyl-Heisenberg groups is that the Fourier coefficients are no longer pure states and are of possibly high rank.
Organization of the paper: In Section 2 we review the Weyl-Heisenberg group and its subgroup structure. The Fourier sampling approach and the so-called standard algorithm are reviewed in Section 3. In Section 4 we provide necessary facts about the representation theory that will be required in the subsequent parts. The main result of this paper is the quantum algorithm for the efficient solution of the HSP in the Weyl-Heisenberg groups presented in Section 5. Finally, we offer conclusions in Section 6.

The Weyl-Heisenberg groups
We begin by recalling some basic group-theoretic notions. Recall that the center Z(G) of a group G is defined as the set of elements which commute with every element of the group i.e., Z(G) = {c : [c, g] = cgc −1 g −1 = e for all g ∈ G}, where e is the identity element of G. The derived (or commutator) subgroup G ′ is generated by elements of the type [a, b] = aba −1 b −1 , where a, b ∈ G. The reader is invited to recall the definition of semidirect products G = N ⋊ H, see for instance [Hup83,Ser77]. In the following we give a definition of the Weyl-Heisenberg groups as a semidirect product and give two alternative ways of working with these groups. Definition 1. Let p be a prime and let n be an integer. The Weyl-Heisenberg group of order p 2n+1 is defined as the semidirect product Z n+1 p ⋊ φ Z n p , where the action φ in the semidirect product is defined on x = (x 1 , . . . , x n ) ∈ Z n p as the (n + 1) × (n + 1) matrix given by (1) Any group element of Z n+1 p ⋊ φ Z n p can be written as a triple (x, y, z) where x and y are vectors of length n whose entries are elements of Z p and z is in Z p . To relate this triple to the semidirect product, one can think of (y, z) ∈ Z n+1 p and x ∈ Z n p . Then, the product of two elements in this group can be written as where x · y = i x i y i is the dot product of two vectors (denoted as xy in the rest of the paper).
Fact 1 [Hup83] For any p prime, and n ≥ 1, the Weyl-Heisenberg group is an extraspecial p group. Recall that a group G is extraspecial if Z(G) = G ′ , the center is isomorphic to Z p , and G/G ′ is a vector space.
Up to isomorphism, extraspecial p-groups are of two types: groups of exponent p and groups of exponent p 2 . The Weyl-Heisenberg groups are the extraspecial p-groups of exponent p. It was shown in [ISS07] that an algorithm to find hidden subgroups in the groups of exponent p can be used to find hidden subgroups in groups of exponent p 2 . Therefore, it is enough to solve the HSP in groups of exponent p. In this paper, we present an efficient algorithm for the HSP over groups of exponent p.
Realization via matrices over Z p : First, we recall that the Heisenberg group of order p 3 (which is the group of 3 × 3 upper triangular matrices with ones on the main diagonal and other entries in Z p ) is a Weyl-Heisenberg group and can be regarded as the semidirect product Z 2 p ⋊ Z p . An efficient algorithm for the HSP over this group is given in [BCD05]. Elements of this group are of the type (3) The product of two such elements is Thus, such a matrix can be identified with a triple (x, y, z) in Z 2 p ⋊ Z p . This matrix representation of the Heisenberg group can be generalized for any n. We can associate a triple (x, y, z) where x, y ∈ Z n p and z ∈ Z p with the (n + 2) × (n + 2) matrix Realization via unitary representation: Finally, there is another useful way to represent the Weyl-Heisenberg group. The n qupit Pauli matrices form a faithful (irreducible) representation of the Weyl-Heisenberg p-group. For any k = 0, we can associate with any triple (x, y, z) in Z n+1 p ⋊ Z n p , the following matrix: where the matrix X = u∈Z n p |u + 1 u| is the generalized X operator and the matrix Z k = u∈Z n p ω k p |u u| is the generalized Z operator, see e. g. [NC00].
Subgroup structure: In the following we will write G in short for Weyl-Heisenberg groups. Using the notation introduced above the center Z(G) (or G ′ ) is the group Z(G) = {(0, 0, z)|z ∈ Z p } and is isomorphic to Z p . As mentioned above, the quotient group G/G ′ is a vector space isomorphic to Z 2n p . This space can be regarded as a symplectic space with the following inner product: The quotient map is just the restriction of the triple (x, y, z) ∈ G to the pair (x, y) ∈ Z 2n p . From Eq.
(2), it follows that two elements commute if and only if xy ′ − yx ′ = 0. Denote the set of (x, y) pairs occurring in H as S H i.e., for each triple (x, y, z) ∈ H, we have that (x, y) ∈ S H and so |S H | ≤ |H|. It can be easily verified that S H is a vector space and is in fact, a subspace of Z 2n p . Indeed, for two elements (x, y), then (ax, ay) ∈ S H for any a ∈ Z p , observe that if (x, y, z) ∈ H, then (x, y, z) a = (ax, ay, az + a(a−1) 2 xy) ∈ H. Therefore, (ax, ay) ∈ S H (in fact, it can be shown that S H ≃ HG ′ /G ′ , but we do not need this result.) Therefore, H ≤ G is abelian if and only if ∀(x, y), (x ′ , y ′ ) ∈ S H , we have that xy ′ − x ′ y = 0. Such a space where all the elements are orthogonal to each other is called isotropic. Now, we make a few remarks about the conjugacy class of some subgroup H. Consider conjugating H by some element of G, say g = (x ′ , y ′ , z ′ ). For any h = (x, y, z) ∈ H, we obtain From this we see that S H g = S H . We show next that S H actually characterizes the conjugacy class of H. Before proving this result we need to determine the stabilizer of H. The stabilizer H S of H is defined as the set of elements of G which preserve H under conjugation i.e., H S = {g ∈ G|H g = H}. From Eq. (7), we can see that Proof. We have already seen that if H 1 and H 2 are conjugates, then S H1 = S H2 . To show the other direction, we use a counting argument ie., we show that the number of subgroups H ′ of G such that S H ′ = S H is equal to the number of conjugates of H. First, assume that the dimension of the vector space S H1 is k. Now, the number of conjugates of H 1 is the index of the stabilizer of H 1 . From the above result, the stabilizer has a size |G ′ ||S ⊥ H1 | = p · p 2n−k . Therefore, the index or the number of conjugates of H 1 are p 2n+1 /p 2n−k−1 = p k . Now, the number of different possible subgroups H such that S H = S H1 is p k since each of the k basis vectors of S H1 are generators of the subgroup and they can have any z component independent of each other i.e., there are p possible choices of z for each of the k generators.
The property G ′ = Z(G) will be useful in that it will allow us to consider only a certain class of hidden subgroups. We show next that it is enough to consider hidden subgroups which are abelian and do not contain Proof. Since G ′ is the commutator subgroup, for any g 1 , g 2 ∈ G, there exists g ′ ∈ G ′ such that g 1 g 2 = g 2 g 1 g ′ . Now, let h ∈ H and g ∈ G. We have g −1 hg = hg ′ for some where e is the identity element of G. This means that g ′ ∈ H. Since G ′ is cyclic of prime order, it can be generated by any g ′ = e and hence, we have G ′ ≤ H. Now, Lemma 2 implies that H G.
From these two lemmas, we have only two cases to consider for the hidden subgroup H: (a) H is abelian and does not contain G ′ and (b) H is normal in G. It is possible to tell the cases apart by querying the hiding function f twice and checking whether f (e) and f (g ′ ) are equal for some g ′ = e and g ′ ∈ G ′ . If they are equal then G ′ ≤ H and H G, otherwise H is abelian. If H is normal, then one can use the algorithm of [HRT03], which is efficient if one can intersect kernels of the irreducible representations (irreps) efficiently. For the Weyl-Heisenberg group, the higher dimensional irreps form a faithful representation and hence do not have a kernel. Thus, when the hidden subgroup is normal, only one dimensional irreps occur and their kernels can be intersected efficiently and the hidden subgroup can be found using the algorithm of [HRT03]. Therefore, we can consider only those hidden subgroups which are abelian and moreover do not contain G ′ . Now, we restrict our attention to the case of abelian H. Finally, we need the following two results. Proof. Suppose that for some (x, y) ∈ S H there exist two different elements (x, y, z 1 ) and (x, y, z 2 ) in H, then by multiplying one with the inverse of the other we get (0, 0, z 1 − z 2 ). Since z 1 − z 2 = 0, this generates G ′ , but by our assumption on H, G ′ H. Therefore, |S H | = |H|.
Note that H 0 can be thought of as a representative of the conjugacy class of H since it can be uniquely determined from S H . The above lemma does not apply for the case p = 2. When p = 2, we have that (x, y, z) 2 = (2x, 2y, 2z + xy) = (0, 0, xy). But since we assume that G ′ H, when p = 2 we must have that xy = 0, ∀(x, y, z) ∈ H.

Fourier sampling approach to HSP
We recall some basic facts about the Fourier sampling approach to the HSP, see also [GSVV04,HMR + 06]. First, we recall some basic notions of representation theory of finite groups [Ser77] that are required for this approach. Let G be a finite group, let C[G] to denote its group algebra, and letĜ be the set of irreducible representations (irreps) of G. We will consider two distinguished orthonormal vector space bases for C[G], namely, the basis given by the group elements on the one hand (denoted by |g , where g ∈ G) and the basis given by normalized matrix coefficients of the irreducible representations of G on the other hand (denoted by |ρ, i, j , where ρ ∈Ĝ, and i, j = 1, . . . , d ρ for d ρ , where d ρ denotes the dimension of ρ). Now, the quantum Fourier transform over G, QFT G is the following linear transformation [Bet87,GSVV04]: An easy consequence of Schur's Lemma is that QFT G is a unitary transformation in C |G| , mapping from the basis of |g to the basis of |ρ, i, j . For a subgroup H ≤ G and irrep ρ ∈Ĝ, define ρ(H) := 1 |H| h∈H ρ(h). Again from Schur's Lemma we obtain that ρ(H) is an orthogonal projection to the space of vectors that are point-wise fixed by every ρ(h), h ∈ H.
The standard method [GSVV04] starts from 1/ |G| g∈G |g |0 . It then queries f to get the superposition 1/ |G| g∈G |g |f (g) . The state becomes a mixed state given by the density matrix σ G H = 1 |G| g∈G |gH gH| if the second register is ignored. Applying QFT G to σ G H gives the density matrix where ρ * (H) operates on the space of column indices of ρ. The probability distribution induced by this base change is given by P (observe ρ) =

dρ|H|rρ(H) |G|
. It is easy to see that measuring the rows does not furnish any new information: indeed, the distribution on the row indices is a uniform distribution 1/d ρ . The reduced state on the space of column indices on the other hand can contain information about H: after having observed an irrep ρ and a row index i, the state is now collapsed to ρ * (H)/r ρ (H). From this state we can try to obtain further information about H via subsequent measurements.
Finally, we mention that Fourier sampling on k ≥ 2 registers can be defined in a similar way. Here one starts off with k independent copies of the coset state and applies QFT ⊗k G to it. In the next section, we describe the representation theory of the Weyl-Heisenberg groups. An efficient implementation of QFT G is shown in Appendix A.

The irreducible representations
In this section, we discuss the representation theory of G, where G ∼ = Z n+1 p ⋊ Z n p is a Weyl-Heisenberg group. From the properties of being an extraspecial group, it is easy to see that G has p 2n one dimensional irreps and p − 1 irreps of dimension p n . The one dimensional irreps are given by where ω p = e 2πi/p and a, b ∈ Z n p . Note that Since S H is a linear space, this expression is non-zero if and only if a, b ∈ S ⊥ H . Suppose we perform a QFT on a coset state and measure an irrep label. Furthermore, suppose that we obtain a one dimensional irrep (although the probability of this is exponentially small as we show in the next section). Then this would enable us to sample from S ⊥ H . If this event of sampling one dimensional irreps would occur some O(n) times, we would be able to compute a generating set of S ⊥ H with constant probability. This gives us information about the conjugacy class of H and from knowing this, it is easy to see that generators for H itself can be inferred by means of solving a suitable abelian HSP.
Thus, obtaining one dimensional irreps would be useful. Of course we cannot assume to sample from one dimensional irreps as they have low probability of occurring. Our strategy will be to "manufacture" one dimensional irreps from combining higherdimensional irreps. First, recall that the p n dimensional irreps are given by where k ∈ Z p and k = 0. This representation is a faithful irrep and its character is given by χ k (g) = 0 for g = e and χ k (e) = p n . In particular, χ k (H) = p n /|H|. The probability of a high dimensional irrep occurring in Fourier sampling is very high (we compute this in Section 5). We consider the tensor product of two such high dimensional irreps. This tensor product can be decomposed into a direct sum of irreps of the group. A unitary base change which decomposes such a tensor product into a direct sum of irreps is called a Clebsch-Gordan transform, denoted by U CG . Clebsch-Gordan transforms have been used implicitly to bound higher moments of a random variable that describes the probability distribution of a POVM on measuring a Fourier coefficient. They have also been used in [Bac08a] to obtain a quantum algorithm for the HSP over Heisenberg groups of order p 3 , and in [Bac08b] for the HSP in the groups D n 4 as well as for Simon's problem. Our use of Clebsch-Gordan transforms will be somewhat similar.
For the Weyl-Heisenberg group G, the irreps that occur in the Clebsch-Gordan decomposition of the tensor product of high dimensional irreps ρ k (g) ⊗ ρ l (g) depend on k and l. The Clebsch-Gordan transform for G is given by If k + l = 0, then only one irrep of G occurs with multiplicity p n , namely If k + l = 0, then all the one dimensional irreps occur with multiplicity one i.e., Note, however, that the state obtained after Fourier sampling is not 1 |H| g∈H ρ k (g) ⊗ ρ l (g), but rather ρ k (H) ⊗ ρ l (H). When we apply the Clebsch-Gordan transform to this state, we obtain one dimensional irreps χ a,b (H) on the diagonal. Applying this to Since v ′ does not occur in the quantum state, the sum over v ′ vanishes unless w 2 = w 1 + y ′ − y. Therefore, the state is The diagonal entries are obtained by putting x = x ′ and y = y ′ and since |H| = |S H |, we get z = z ′ . The diagonal entry is then proportional to (17) Up to proportionality, this can be seen to be χ w1,−u ′ (H), a one dimensional irrep. The bottom line is that, although not diagonal in the Clebsch-Gordan basis, the resulting state's diagonal entries correspond to one dimensional irreps we are interested in.

The quantum algorithm
In this section, we present a quantum algorithm that operates on two copies of coset states at a time and show that it efficiently solves the HSP over G = Z n+1 p ⋊ Z n p , where the input is n and log p. The algorithm is as follows: 1. Obtain two copies of coset states for G. 2. Perform a quantum Fourier transform on each of the coset states and measure the irrep label and row index for each state. Assume that the measurement outcomes are high-dimensional irreps with labels k and l. With high probability the irreps are indeed both high dimensional and k + l = 0, when p > 2 (see the analysis below). When p = 2, there is only one high dimensional irrep which occurs with probability 1/2 and k + l = 0 always, since k = l = 1. We deal with this case at the end of this section. For now assume that p > 2 and k + l = 0. 3. If −k/l is not a square in Z p , then we discard the pair (k, l) and obtain a new sample. Otherwise, perform a unitary U α ⊗ I : |u, v → |αu, v , where α is determined by the two irrep labels as α = −k/l. This leads to a "change" in the irrep label 3 of the first state from k to −l. We can then apply the Clebsch-Gordan transform and obtain one dimensional irreps. 4. Apply a Clebsch-Gordan transform defined as to these states. 5. Measure the two registers in the standard basis. With the measurement outcomes, we have to perform some classical post-processing which involves finding the orthogonal space of a vector space. Now, we present the analysis of the algorithm.
1. In step 1, we prepared the state 1 |G| g |g |0 and apply the black box U f to obtain the state 1 |G| g |g |f (g) . After discarding the second register, the resulting state is |H| |G| |gH gH|. We have two such copies. 2. After performing a QFT over G on two such copies, we measure the irrep label and a row index. The probability of measuring an irrep label µ is given by p(µ) = d µ χ µ (H)|H|/|G|, where χ µ is the character of the irrep. If µ is a one-dimensional irrep, then the character is either 0 or 1 and so the probability becomes 0 or |H|/|G| accordingly. The character χ µ (H) = 0 if and only if µ = (a, b) ∈ S ⊥ H . Therefore, the total probability of obtaining a one dimensional irrep is |H||S ⊥ H |/|G|. Now, we have that |H| = |S H | and so |H||S ⊥ H | = p 2n since S ⊥ H is the orthogonal space in Z 2n p . Therefore, the total probability of obtaining a one dimensional irrep in the measurement is p 2n /p 2n+1 = 1/p. This is exponentially small in the input size (log p). Therefore, the higher dimensional irreps occur with total probability of 1 − 1/p. Since all of them have the same χ µ (H) = p n /|H|, each of them occurs with the same probability of 1/p. Take two copies of coset states and perform weak Fourier sampling and obtain two high dimensional irreps k and l. The state is then |H| 2 p 2n ρ k (H) ⊗ ρ l (H). In the rest, we omit the normalization |H| p n of each register.
Therefore, the state is proportional to 3. We can assume that k and l are such that k + l = 0 since this happens with probability (p − 1)/p 2 . Now, choose α = −k l . Since the equation lx 2 + k = 0 has at most two solutions for any k, l ∈ Z p , for any given k, l chosen uniformly there exist solutions of the equation lx 2 + k = 0 with probability 1/2. Perform a unitary U α : |u → |αu on the first copy. The first register becomes proportional to where (x 1 , y 1 , z 1 ) = φ α (x, y, z) = (αx, αy, α 2 z) and u 1 = αu. It can be seen easily that φ α is an isomorphism of G for α = 0 and hence φ α (H) is subgroup of then so is every multiple of it i.e., (αx, αy) ∈ S H ). Thus, we have obtained an irrep state with a new irrep label over a different subgroup. But this new subgroup is related to the old one by a known transformation. In choosing the value of α as above, we ensure that k/α 2 = −l and hence obtain one dimensional irreps in the Clebsch-Gordan decomposition. 4. We now compute the state after performing a Clebsch-Gordan transform U CG on the two copies of the coset states, i.e., perform the unitary given by the action The initial state of the two copies is The resulting state after the transform is Note that the term in the squared brackets is non-zero only when (v + (1 − α)ŷ, u + (1 − α)x) lies in S ⊥ H . This means that if we measure the above state we obtain pairs H . This can be used to determine both S ⊥ H (and hence S H ) and (x,ŷ). Repeat this O(n) times and obtain values for u and v by measurement. 5. From the above, say we obtain n + 1 values (u 1 , v 1 ), . . . , (u n+1 , v n+1 ). Therefore, we have the following vectors in S ⊥ H .
The affine translation can be removed by first dividing by (1 − α i ) and then taking the differences since S ⊥ H is a linear space. Therefore, the following vectors lie in S ⊥ H : ).
With high probability, these vectors form a basis for S ⊥ H and hence we can determine S H efficiently. This implies that the conjugacy class and hence the subgroup H 0 is known. It remains only to determine (x,ŷ). We can set (x,ŷ) = (1 − α 1 ) −1 (u 1 − u ′ 1 , v 1 − v ′ 1 ) since the conjugating element can be determined up to addition by an element of S ⊥ H . H can be obtained with the knowledge of H 0 and (x,ŷ).
Finally, for completeness we consider the case p = 2. Assume that after Fourier sampling we have two high dimensional irreps with states given by (23) The Clebsch-Gordan transform is given by the base change: Applying this to the two states, we obtain (in a similar manner as above) (x,y,z)∈H,u,v∈Z n The inner sum is non-zero if and only if (u, v) ∈ S ⊥ H . Thus, measuring this state gives us S ⊥ H from which we can find S H . We cannot determine H directly from here as in the case p > 2. But since we know S H , we know the conjugacy class of H and we can determine the abelian group HG ′ which contains H. This group is obtained by appending the elements of S H with every element of G ′ = Z 2 i.e., for (x, y) ∈ S H we can say that (x, y, 0) and (x, y, 1) are in HG ′ . Once we know HG ′ , we now restrict the hiding function f to the abelian subgroup HG ′ of G and run the abelian version of the standard algorithm to find H. In summary, we have shown the following result: Sketch of proof. From the above discussion follows that O(n) iterations of Steps 1.-4. in the algorithm will lead to system of equations in Step 5. that with constant probability has a unique solution. The number of queries in each iteration is constant and the computational complexity of each of these steps can be upper bounded as follows: O(n log p log log p) operations for each computation of QFT over G as described in Appendix A. The transform U α and the Clebsch-Gordan transform U CG can easily be implemented using arithmetic modulo p and QFTs over Z p , both of which can be done in O(log p log log p) elementary quantum operations. Hence the running time of the quantum part of the algorithm can be upper bounded by O(n 2 log p log log p) operations and the number of queries by O(n). The overall running time is dominated by the cost for classical post-processing which consists in computing the kernel of an n × n matrix over Z p . This can be upper bounded by O(n 3 ) arithmetic operations over Z p for the Gaussian elimination, leading to a total bit complexity of O(n 3 log p log log p 2 O(log * log p) ) operations when using the currently fastest known algorithm for integer multiplication [Für07].

Conclusions
Using the framework of coset states and non-abelian Fourier sampling we showed that the hidden subgroup problem for the Weyl-Heisenberg groups can be solved efficiently. In each iteration of the algorithm the quantum computer operates on k = 2 coset states simultaneously which is an improvement over the previously best known quantum algorithm which required k = 4 coset states. We believe that the method of changing irrep labels and the technique of using Clebsch-Gordan transforms to devise multiregister experiments has some more potential for the solution of HSP over other groups. Finally, this group has importance in error correction. In fact, the state we obtain after Fourier sampling and measurement of an irrep is a projector onto the code space whose stabilizer generators are given by the generators of H. In view of this fact, it will be interesting to study the implications of the quantum algorithm derived in this paper to the design or decoding of quantum error-correcting codes.  · · · · · · · · · · · · . . . g s s Fig. 1. QFT for the Weyl-Heisenberg group. The QFT gates shown in the circuit are QFTs for the cyclic groups Zp. Each of these QFTs can be implemented approximately [Kit97,HH00] or exactly [MZ04], in both cases with a complexity bounded by O(log p log log p). It should be noted that the wires in this circuit are actually p-dimensional systems. The meaning of the controlled gates where the control wire is an open circle is that the operation is applied to the target wire if and only if the control wire is in the state |0 . The meaning of the controlled P gates where the control wire is a closed circle here means that the gate P k is applied in case the control wire is in state |k with k = 0, and P0 = Ip. Here P k is the permutation matrix for which QFT (k) = P k QFT holds. The complexity of this circuit can be bounded by O(n log p log log p).

B Changing labels of irreducible representations
In this section, we describe the technique of changing labels of irreducible representations (irreps) in a more abstract, representation theoretic, fashion. We consider a situation slightly more general than the Weyl-Heisenberg groups considered in the paper, namely for semidirect products of the form G = A ⋊ φ B, where A is an Abelian group, B is an arbitrary finite group, and φ : B → Aut(A). We make some further assumptions regarding the irreps of G that arise during Fourier sampling. First, note that in general there might be some irreps of G that arise as inductions [Ser77,Hup83] of irreps of A to G. Suppose that, with high probability, we sample only such irreps, so that we can restrict our attention to this case. This happens for the Weyl-Heisenberg groups discussed in this paper. Other examples are the groups isomorphic to Z n p ⋊ Z p studied in [BCD05] and the affine groups [MRRS04] which are isomorphic to Z p ⋊ Z p−1 .
After Fourier sampling and measurement of an irrep label we have the state ρ k (H), where ρ k is an irrep of G and k is its label. We want to apply an operator U B to this state in order to change it to a state ρ k ′ (H ′ ) corresponding to an irrep with label k ′ , possibly with respect to a different subgroup H ′ . In the following we show how this can be done if ρ k (H) = (χ k ↑ G)(H), i. e., if ρ k is an induction of an irrep χ k of A to G. The possible labels k ′ that can be obtained depend on the automorphism group of B, namely on those automorphisms of B that can be extended to automorphisms of G.