{'fraction_non_alphanumeric': 0.042896798716557605, 'fraction_numerical': 0.013679845028324934, 'mean_word_length': 3.905368338557994, 'pattern_counts': {'":': 0, '<': 32, '<?xml version=': 0, '>': 26, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 100, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Hidden Subgroup Problem

We give an overview of the Hidden Subgroup Problem (HSP) as of July 2010, including new results discovered since the survey of arXiv:quant-ph/0411037v1. We recall how the problem provides a framework for efficient quantum algorithms and present the standard methods based on coset sampling. We study the Dihedral and Symmetric HSPs and how they relate to hard problems on lattices and graphs. Finally, we conclude with the known solutions and techniques, describe connections with efficient algorithms as well as miscellaneous variants of HSP. We also bring various contributions to the topic. We show that in theory, we can solve HSP over a given group inductively: the base case is solving HSP over its simple factor groups and the inductive step is building efficient oracles over a normal subgroup N and over the factor group G/N. We apply this analysis to the Dedekindian HSP to get an alternative abelian HSP algorithm based on a change of the underlying group. We also propose a quotient reduction by the normal group obtained via Weak Fourier Sampling. We compute the exact expression of Strong Fourier Sampling over the dihedral group, showing how the previous reduction is natural and matches the standard one. We also give a reduction of rigid graph isomorphism problem to HSP over the alternating group. For this group and other simple groups, we propose maximal subgroup reduction as a possible approach. We also analyse Regev's algorithm for the poly(n)-uniqueSVP, prove how the degree of the polynomial is related to the oracle complexity used and we suggest several variants.

In a second part, we describe in detail the "standard method". We recall the solution to the abelian case as well as some representation theory background that allows to use Fourier Transform over Finite Groups. We also define Fourier Sampling and mention how the weak version extends the abelian case to find normal hidden subgroups and solve the dedekindian HSP.
In a third part, we discuss all the results known so far for the cases of the Dihedral and Symmetric groups, which are expected to provide new efficient algorithms. Solving the dihedral HSP in a particular way gives an algorithm for poly(n)-uniqueSVP while a solution to the symmetric HSP gives an algorithm for the graph isomorphism problem.
Finally, we conclude our study with the general HSP. We make some proposals for a general approach and discuss the solutions and techniques known so far. Next, we indicate how HSP relates to various efficient algorithms. We also give an overview of miscellaneous variants and extensions to the hidden subgroup problem that have been proposed.
In addition to gathering in a single document an introduction to the Hidden Subgroup problem as well as an overview of the state-of-the-art for this research topic, we also bring some contributions: We provide a detailed and corrected computation of the fact that, in the Strong Fourier Sampling, measuring the row yields no information. In the sketchy proof of Grigni et al., a family of vectors was claimed to be orthonormal whereas it is only orthogonal. In appendix B, we compute the exact expression of Strong Fourier Sampling over the dihedral group. When the hidden subgroup is reduced to {(0, 0), (d, 1)}, it has already been mentioned that Strong Fourier Sampling over D N is similar to using the Quantum Fourier Transform over ℤ N ×ℤ 2 and hence a particular case of the dihedral coset problem. For a general hidden subgroup, we prove that the expression of the Strong Fourier Sampling is the same as if we were directly working in the quotient group D N ( H ∩ ( ℤ N ×{0} )) . In appendix G, we propose an entirely new approach to try to find the slope d of the dihedral HSP. Rather than using coset sampling, we consider uniform superpositions over large subsets of f (D N ). In particular, we can solve the case N = 2 n if we have an efficient process to create for b = 0, 1 the states We give more detail on the relation between HSP and lattice problems. In particular, we show that if n ⋊ℤ 2 using a "recursive DCP algorithm". However, we also provide an overview of lattice-based problems in appendix E and warn that Regev's algorithm would only have small impact on lattice-based cryptosystems. Hence, we propose to consider also HSP algorithms for stronger lattice problems.
In appendix D, we give a reduction of Monotone 1-in-3 3SAT to GapCVP ∞ where one step uses the abelian HSP algorithm to find the kernel of group homomorphism. Although the quantum part is not actually needed here, this provides another example where a hidden subgroup problem can be used.
In appendix F, we give an alternative algorithm for the cyclic and abelian hidden subgroup problems, based on a change of the underlying group. Even if it does not generalize, it is a good example of subgroup reduction. We present a general approach to the Hidden Subgroup Problem and show that in theory, we can solve it if we have a solution to HSP over simple groups and a way to build efficient oracles for some reduction techniques. We also propose iterative subgroup and quotient reductions: using a maximal supergroup of H for the former and the normal subgroup obtained by Weak Fourier Sampling for the latter. Maximal subgroup reduction is a possible approach for HSP over simple groups. We indicate how to reduce the rigid graph isomorphism problem to HSP over the alternating group A n , which is simple for n > 4.
We notice how the Hidden Polynomial Problem is a natural extension of the abelian HSP over G = F q m , when the subgroup H is promised to be a hyperplane.

Introduction
The Hidden Subgroup Problem is one of the most prominent topic in quantum computing. Most quantum algorithms running exponentially faster than their classical counterparts fall into this framework. It is expected that finding more solutions to Hidden Subgroup Problems will provide new efficient quantum algorithms.
The first example of a black-box algorithm of this kind was given by Simon [Sim1994]. Classical algorithms can not give the right answer to that black-box problem unless they use an exponential number of oracle calls. This result strengthened the earlier Deutsch-Jozsa algorithm, which is only exponentially more efficient than deterministic classical algorithm. Despite its theoretical importance for demonstrating the power of quantum computer, Simon's algorithm does not lead to practical applications.
However, shortly after Simon published his algorithm, Shor [Sho1995] extended it to find periods of functions over ℤ N and ℤ p − 1 2 . He used these period finding algorithms as key steps to solve two difficult problems: factoring integer and computing discrete logarithms. The hardness of both problems is the assumption on which some cryptographic systems such that the ubiquitous RSA system are based. Hence Shor's algorithms had a strong impact since they proved how quantum computers can break cryptographic systems and it has been one of the great success of quantum computing.
Simon's problem and Shor's algorithms can be better understood in the framework of the Hidden Subgroup Problem. We work on a group G and try to find an unknown subgroup H using calls to a function f . This function is constant on cosets of H and takes different values on distinct cosets. Ettinger, Høyer and Knill proved that the subgroup H can always be determined using only O(log|G|) calls to the oracle f but the whole procedure is not necessarily efficient [EttHøyKni1999].
We recall the "historical" results as well as the definition of the Hidden Subgroup Problem in the first part of this report. Although they are well known by researchers working on this topic, they remain a good introduction and motivate the subsequent work.
Once the framework of the Hidden Subgroup Problem set, the special case of abelian group was addressed. Indeed, the algorithms given by Simon and Shor work on abelian groups and the main ingredients such that entanglement over a coset and Quantum Fourier Transform could easily be extended to solve the abelian Hidden Subgroup Problem. The algorithm requires the knowledge of a decomposition G ≅ ℤ t 1 ×ℤ t 2 ×ℤ t 3 ×…×ℤ t k but if the group is given in a black box form, we can still determine that decomposition. Because the algorithm is fundamental, we start the second part of this report by recalling how the abelian HSP algorithm works. We also sketch the idea of Cheung and Mosca [CheMos2001] to get the decomposition for a black-box group.
The success of the Fourier Sampling to solve the abelian HSP naturally made the researchers study its generalization over non-abelian groups. This is quite technical, so we take care to define precisely Quantum Fourier Transform and Fourier Sampling. We study how they apply to non-abelian HSP in the remainder of the second part of this report.
We first extract the essential points from the reference book on group representation theory by Serre [Ser1971] to show that it is always possible to define a general Quantum Fourier Transform over finite groups as a unitary operation. We indicate how it extends the classical Quantum Fourier Transform used for abelian groups. In the non-abelian case, it turns out that each choice of basis for the set of irreducible representations gives rise to a specific Quantum Fourier Transform. We use the Schur's lemma to show that they are all described modulo basis changes in the space of each irreducible representation.
Next, we turn our attention to the Fourier Sampling over finite groups using the studies of [HalRusTa-2000] and [GriSchVaz2000]. It is the occasion to recall the standard method of coset sampling: we gather information on the hidden subgroup from coset states i.e. uniform superposition over a random coset of H . Then, we apply several Fourier Samplings to these cosets states: a Quantum Fourier Transform followed by a measurement of an irreducible representation. We define the Weak and Strong versions and recall classical expressions on distribution probabilities. In particular, we give a detailed proof of the fact that measuring the row is not relevant for Strong Fourier Sampling.
We then see how the Weak Fourier Sampling is enough to solve the Dedekindian Hidden Subgroup Problem i.e. for groups that have only normal subgroups. In the new framework, the algorithm of the abelian case can be seen as computing the hidden subgroup as the intersection of the kernels of the representations measured by Fourier Sampling. Independently, [HalRusTa-2000] and [GriSchVaz2000] showed that this technique still works when the hidden subgroup is normal, thus solving the dedekindian in theory. [HalRusTa-2000] contains an explicit algorithm for the class of hamiltonian groups which are the only non-abelian dedekindian groups. We also mention briefly more results of [GriSchVaz2000] and [Gav2004] such that extensions to groups that are in some sense not too far from the dedekindian case as well as a black box result to find normal subgroups.
The third part of this report is dedicated to the two most important open non-abelian HSPs: those over the dihedral and symmetric groups. Regev showed that a solution to the Hidden Subgroup Problem over the dihedral group using coset samplings on a particular reduced case would provide an efficient algorithm for the poly(n)-uniqueSVP [Reg2004]. uniqueSVP is an instance of lattice problems, which are involved in many tasks believed to be computationally hard. More specifically, some cryptographic systems are based on lattice problems and some of them use the poly(n)-uniqueSVP. A solution to the Hidden Subgroup Problem over the symmetric group gives a polynomial algorithm to determine whether two given graphs are isomorphic, one of the very rare problems whose exact complexity has remained unknown for many decades.
The dihedral Hidden Subgroup Problem was first considered by Ettinger and Høyer as a first study of the non-abelian case [EttHøy1998]. They gave an interesting reduction of the problem to the case where the hidden subgroup is {(0, 0), (d, 1)} and showed that we can determine d with efficient query and measurement but exponential post-processing. We describe the structure of the dihedral group and explain the techniques of Ettinger and Høyer. We also discuss whether the algorithms of the previous section work. In particular, we give a very detailed description of Fourier Sampling over the dihedral group in appendix B and present some attempts to solve DHSP using this method in appendix C. We introduce the Dihedral Coset Problem which is essentially asking whether we can solve the dihedral HSP using a black box that outputs coset states. This problem encapsulates all the previous approaches. However, we propose a totally new method in appendix G.
In another section, we study the results obtained from this dihedral coset black box. In [Kup2003], Kuperberg gave a subexponential time algorithm to determine the parity of d from a dihedral coset black box, using a new combine-and-measure technique. This algorithm can be easily extended to get a solution to the dihedral HSP with subexponential time. Actually, Kuperberg's algorithm uses exponential space but Regev gave a modification that makes the space requirement polynomial [Reg2004]. More generally, Bacon, Childs and van Dam used tools from quantum-information theory to characterize the measurement on k outputs of the black box that gives the optimal information [BacChiDam2005]. They showed that k must be at least linear even for determining the parity of d as in Kuperberg's algorithm. They also demonstrated a relation between the implementation of the optimal measurement and the subset sum problem. Actually, Regev had already shown such a relation in [Reg2003].
Next we look more carefully to Regev's algorithm [Reg2003] that establishes a connection between the polynomial uniqueSVP and a solution to the dihedral coset problem. We show how the degree of the polynomial complexity of a solution to the dihedral coset problem is related to the degree of the approximation in the uniqueSVP. We notice that mutatis mutandis his algorithm can be applied using more HSP problems over the family of generalized dihedral groups. Similarly, we indicate that the algorithm still holds for some kinds of recursive dihedral coset problem as in the case of Kuperberg's algorithm. We sum up in appendix E the overview of [MicReg2008] and notice that the problem considered is however not of major importance. We suggest some research directions to investigate.
Then we turn our attention to the case of the symmetric group. We recall the definition of the graph isomorphism problem as well as related problems. We describe the straightforward reduction of the equivalent graph automorphism problem to the symmetric hidden subgroup problem, or more specifically to the case where we want to determine whether the hidden subgroup is trivial or not. We also talk about another reduction for the case of rigid graphs given in [MooRusSch2005]: the underlying group is S n ≀ ℤ 2 ⊆ S 2n and the hidden subgroup H = {Id, σ}. Moreover, we prove that the rigid graph isomorphism problem can actually be set in the reduced case of the simple group A 2n . Unfortunately, even these simpler cases have remained unsolved. We recall the negative results on the symmetric group and suggest to split the problem in more separate cases.
In a final part, we study the general hidden subgroup problem. We recall the two fundamental theorems describing how finite groups are built from simple groups using composition series. We state conditions to solve the general HSP: find a way to solve the HSP over simple group and to build efficient oracles when breaking down the group. For the second conditions, we isolate two particular reduction methods: subgroup reduction and quotient reduction. We propose iterative quotient reduction to make the hidden subgroup not contain any non-trivial normal subgroup. We also suggest iterative maximal subgroup reduction as a possible way to solve the HSP over the simple groups. We sum up our ideas in a general schema for a possible HSP algorithm. We notice how these ideas relate to an alternative abelian HSP algorithm proposed in appendix F and to dihedral and symmetric HSP. We explain how the classical attempts for dihedral HSP are using quotient and subgroup reductions. For the symmetric HSP, the reductions give two difficult problems: either solving HSP over the large simple group A n or building a oracle over ℤ 2 from the big initial oracle over S n .
In the next section, we review the solutions and techniques obtained for non-abelian groups. We recall the Fourier Sampling techniques as well as all the methods that have been discovered in order to find a solution to the dihedral HSP. We mention other techniques relying on the blackbox paradigm. We give an overview of efficient HSP algorithms based on these methods. They can essentially be classified into three groups: the extensions to the Dedekindian HSP which apply to groups with a large amount of normal subgroups, the semi-direct products of two abelian groups A⋊ B which are broken down into the abelian groups A and B with respect to the description of the previous section and another category of groups whose normal series structure is simple enough to apply blackbox techniques. In some sense, they are all close to the abelian case. We mention a partial result for an exception which includes the simple group PGL(2, p m ), namely finding 1-point stabilizer of some Lie groups.
The following section is devoted to relation between HSP and efficient algorithms with concrete applications. We recall the results for dihedral and symmetric HSP. We mention Hallgren's generalization to infinite groups ℝ r which allowed him to solve Pell's equation and other number fields problems. We also mention more relationship between HSP an cryptography. Considering that the general HSPs are actually difficult, Moore, Russell, Vazirani constructed a one-way function which is as hard to invert as the graph isomorphism problem. [Dam1988] contains a proposal for a hard problem with application to cryptography: Given l + 1 = O(log p) successive evaluations of the Legendre symbol ( s p ) , ( s + 1 p ) , …, ( s + l p ) predict the next value ( s + l + 1 p ) . We mention how a weaker problem can be set in the HSP framework and has been solved [DamHalIp2002]. The authors say that the solution to this weaker problem allows attacks to some cryptosystems, already broken by Shor's algorithm though. We also discuss the comparaison given in [LomKau2006] between Shor's algorithm and Grover's algorithm. We compare their method with the algorithms for the 1-point stabilizer given in [DenMooRus2008] and wonder whether they can be interpreted as exponentially fast solutions to some concrete search problems.
We conclude our study with some variants and extensions to the hidden subgroup problem which are also expected to yield new efficient quantum algorithms. We mention the generalization to hypergroups and infinite groups. Other extensions include the Hidden Symmetries Problem and the Hidden Covering Space Problem. We describe the quite popular variants of the Hidden Shift Problem which is related to the dihedral and symmetric HSP, as well as its generalizations the Generalized Hidden Shift Problem and the Hidden Coset Problem. We mention three problems introduced in [FriEtAl2002] to solve some instances of HSP: Hidden Stabilizer Problem, Orbit Coset Problem and Orbit Superposition Problem. We also talk about some decision/search versions of hidden subgroup problems. Next, we show how finding hyperplane subgroups of the vector space G = F q m naturally generalizes to the Hidden Polynomial Problem. Finally, we discuss the category of Hidden Shifted Subset Problems.

Prerequisites
Unless otherwise specified, we use the notations described in this section as well as other classical ones not mentioned below. We assume basic knowledge of quantum computing: an excellent introduction is the book of Nielsen and Chuang [NieChu2007]. The paper of Lomont [Lom2004] also contains a presentation of the main ideas as well as a good overview of the Hidden Subgroup Problem and its status as of 2004. Some advanced mathematical concepts will also be required and sometimes recalled as needed.
limit and asymptotic approximation: f → c ( f has limit c), f = O(g) ( f bounded above by a constant times n (Stirling formula) and φ(n) n = Ω ( 1 log(log(n)) ) . Group laws are noted + for abelian groups and by a multiplication for general groups. ℤ 2 n may be seen as n-bits numbers, so in that case ⊕ is sometimes used instead of +. algebraic structures: and H g (left and right coset), ⟨S⟩ (group generated by S), We also simply use the term "Coset" for left coset. We also define the normal subgroup M G = ⋂ H subgroup of G N(H ). some algebraic structures: ℤ k (cyclic group ℤ kℤ ), ℤ p * with p prime (multiplicative group of invertible elements of ℤ p ), ℚ 8 (quaternion group), D N (dihedral group), S N (symmetric group), A N (alternating group), GL n (K) (general linear group of degree n over a field K). F q is the finite field of order q. GL(n, q) = GL n (F q ). vectors and matrices: If f can be implemented using a poly(n) complexity then it is also the case for the quantum version U f . probability theory: P(X) (probability of an event X), P( X Y ) (conditional probability of X given Y ), E(X) (mean). To bound probabilities, we use variants of Hoeffding's inequality: if we have independent bounded variables X k ∈ [0, 1] then their sum S = ∑ k = 1 n X k satisfies P(S − E(S) ≥ t) ≤ exp ( − 2t 2 n ) . number theory: let p be an odd prime, the Legendre symbol ( a p ) is 0 if a is a multiple of p and a ( p −1) 2 mod (p) = ± 1 otherwise.

Simon's Problem
This problem imagined by Simon [Sim1994] demonstrates a quantum algorithm solving a black-box problem exponentially faster than any probabilistic classical algorithm. Contrary to Deutsch-Jozsa algorithm [DeuJoz1992], it is even exponentially faster than probabilistic classical algorithms.

Definition 3.1 (Simon's problem)
Let m ≥ n be natural numbers and f : ℤ 2 n → ℤ 2 m a function. Assume that there is a string s ∈ ℤ 2 n such that The quantum solution to the problem is to repeat enough time the procedure given by the following circuit: After applying U f , we are in the state: Measuring the second register gives a value y and makes the first register collapse to the superposition of its two preimages x, x ⊕ s : After the second Hadamard gate, the state in the first register is Performing a standard measurement on the first register yields a random n-bits vector z such that z.s = 0 i.e. in the subspace orthogonal to s. Repeating the procedure O(n) times gives a set of generators z 1 , …z O(n) for this subspace with probability exponentially close to 1. Said otherwise, we have a system of equations ∑ i = 1 n z i j s i ≡ 0 mod (2) of rank the dimension of the subspace and n unknowns s 1 , …s n . If s = 0, then the rank of the system is n, so we get the unique solution s = 0. Otherwise s ≠ 0 and the rank of the system is n − 1, so solving the system gives a subspace of dimension n − (n − 1) = 1, which is simply {0, s}. In either case, we have obtained s as expected. The procedure is repeated O(n) times, so a polynomial number of queries to the oracle f are used.
What about (probabilistic) classical algorithm? Consider the special case m = n. Let's choose randomly f to be a permutation (s = 0) or a two-to-one function (s ≠ 0). In the former case, we randomly choose a permutation f and in the latter case a nonzero string s. Simon proved that a classical algorithm calling f no more than 2 n 4 times can not determine whether s is zero or not with success probability greater than 1 2 + 2 − n 2 .
Hence for a fixed minimal probability of success 1 2 + δ, no classical algorithm using a polynomial number of queries can solve Simon's problem.

Shor's Factoring Algorithm
Shor's algorithm [Sho1995] allows to factor an integer N 0 in poly(log N 0 ) time. No classical algorithm are currently known to run this task in polynomial time. Actually, some cryptographic protocols are based on the assumption that no efficient algorithm exists for integer factoring and hence Shor's algorithm shows that they can be broken by quantum computation.
Shor's algorithm contains classical parts that can be executed in polynomial time and quantum computation is actually only used in a sub-procedure. More precisely, one step is to choose a random integer a < N 0 (which can be assumed to be coprime with N 0 ). The function defined on ℤ by f (x) = a x mod (N 0 ) is r -periodic and the problem reduces to find the period r. We can restrict our study to the domain ℤ N ⊆ ℤ for some multiple N of the period. Of course, we do not know how to choose N precisely but it is possible to find some value N = O ( N 0 2 ) for which the approximation does not change the final result. For simplicity, let's assume N = r M is an exact multiple of the period. The period-finding submodule can be executed in poly(log N) = poly (log N 0 ) using the circuit of figure 3.2, which is very similar to the one of Simon's problem. We define the Fourier transform F N to be the symmetric matrix It can easily be shown to be unitary and hence a valid quantum operation. We assume that there exists an efficient implementation of poly(log N) elementary gates computing F N . This implementation uses n = ⌈log N⌉ qubits, so we are working in an Hilbert Space of dimension 2 n ≥ N. Hence some basis states may not be used, they are just unchanged by the gate implementing F N .
The first call to F N on 0 n returns the first column of F N i.e. a uniform superposition of basis vectors as in Simon's algorithm. Hence the state after U f is also Measuring the second register gives a value y and makes the first register collapse to the superposition of the preimages of y. If x 0 is such an image all the others are obtained by x 0 + ir for i going from 0 to M − 1: After the second Fourier Transform gate, the state in the first register is Each sum over i is a geometric series of initial term ⅇ 2π ⅈ N x 0 j and ratio ⅇ 2π ⅈ N r j . So the sum is nonzero (and equal to Mⅇ Hence the state can be rewritten: All the vectors in the sum have same amplitude, so measuring the first register yields a uniformly random multiple of M between 0 and N − 1. Using k trials gives j 1 , … j k multiples of M. One can show that gcd ( j 1 , … j k ) = M with success probability ≥ 1 − 2 − k 2 (see Appendix E of [Lom2004] applied to t i =

Shor's Discrete Logarithm Algorithm Definition 3.2 (discrete logarithm)
Let p be a prime number and g a generator of ℤ p * . Any x ∈ ℤ p * can be written uniquely as x = g y for some y ∈ ℤ p − 1 . y = log g x is called the discrete logarithm of x (with respect to g). ◇ Similarly to Shor's algorithm, some cryptographic protocols are based on the difficulty of computing discrete logarithms. In [Sho1995], Shor describes a quantum algorithm to compute these logarithms in polynomial time. So suppose x, g are given and that we want to find y.
We first define the function f (a, b) = g a x b mod (p) going from ℤ p − 1 ×ℤ p − 1 to ℤ p . Each call to f is clearly done in time poly(log(p)). Note that we can rewrite f using the discrete logarithm y: f (a, b) = g a + yb mod (p).
Hence (a 1 , b 1 ) ≡ (a 2 , b 2 ) + λ(y, − 1) mod (p − 1) implies f (a 1 , b 1 ) = f (a 2 , b 2 ). Conversely, if this equality is true, we have a 2 − a 1 ≡ y(b 1 − b 2 ) mod (p − 1) and we can take λ ∈ ℤ p − 1 to be the unique element congruent with b 2 −b 1 modulo p − 1 to recover the previous equality. As a consequence, we can say that (y, − 1) is the period of f and all the values are obtained when λ varies from 0 to p − 2.
We now define a circuit which is really similar to those we saw earlier. Here, the first register is the tensor product of two ⌈log(p − 1)⌉-qubits state and the second a ⌈log(p)⌉-qubits state. On the first register we apply a Fourier transform on each state of the tensor product: On the first register applying the first F p − 1 ⊗ F p − 1 gives, as in Shor's algorithm, a superposition over the whole group Then, applying the U f operator gives the superposition Measuring the second register yields a f (a 0 , b 0 ) and makes the first register collapse to the superposition of the preimages. By the discussion above it is: Now, we apply F p − 1 ⊗ F p − 1 on the first register, giving the state which we can further simplify to The sum over lambda is a geometric series, and its value is nonzero (and of value p − 1) iff yu − v ≡ 0 mod (p − 1). Replacing v by yu in the expression gives the final state: A measurement in the standard basis gives u and yu modulo p − 1. If u and p − 1 are coprime, using the euclidean algorithm we can find v such that uv = 1 modulo p − 1 from the first state. Then, we get y = yuv modulo p − 1 from the second state. So we have obtained y = log g x as expected. Note that u and p − 1 are coprime with probability ) so we only need to repeat the procedure about log(log(p)) times to ensure a success with high probability.

The Hidden Subgroup Problem
In this section, we interpret the algorithms seen in previous sections in a common framework. The hope is to find new algorithms exponentially faster than their classical counterparts.

Definition 3.3 (hidden subgroup problem)
Let G be a group and H ⊆ G one of its subgroup. Let S be any set and f : G → S a function that distinguishes cosets of H i.e. ∀ g 1 , g 2 ∈ G, f (g 1 ) = f (g 2 ) ⇔ g 1 H = g 2 H . The hidden subgroup problem (HSP) is to determine the subgroup H using calls to f . ◇

Example 3.4 (interpretation of previous algorithms)
Problem s is any n-bits strings.
Shor's algorithm (order finding subroutine) N 0 is the number to factor, a < N 0 a random integer coprime with N 0 , r is the order of a modulo N 0 . Ideally, N should be a multiple of r but we can choose some N = ) giving a good approximation. In the remaining of this document, we are only considering the case of a finite group G. In particular, the set S may also be taken to be finite and we may even assume |S| ≤ |G|. Consequently, we can formulate the problem in terms of circuits: we encode the elements of the two sets with at most n = ⌈log|G|⌉ bits and hence f can be viewed as a function f : ℤ 2 n → ℤ 2 n and represented by a quantum logic gate U f . A naive algorithm for the hidden subgroup problem is the following: compute f (g) for all g ∈ G and return those for which f (g) = s 0 i.e. the elements of H . 2.
The runtime complexity of this algorithm is O(|G|comp( f )) so at least O(exp(n)). This is really bad compared with the efficient quantum algorithms previously seen. For instance Shor's algorithm run in poly(log N) = poly(n) i.e. exponentially faster. Hence we are lead to the following definition:

Definition 3.5 (efficient)
An algorithm for the hidden subgroup problem is said to be efficient iff it returns a generating set of elements of H using a complexity polynomial in n = ⌈log |G|⌉. ◇ In particular, we have the following requirements for an efficient solution: f has a polynomial complexity. 1.
f is called a polynomial number of times. 2.
the set generating H has a polynomial size. 3.
Note that not all functions f : ℤ 2 n → ℤ 2 n have a polynomial complexity, as indicated in exercise 3.16 of [NieChu2007]. The idea is that there are (2 n ) ( 2 n ) such functions so one can note encode all of them using only a polynomial number of elementary gates. As a consequence, f has to be chosen carefully to satisfy the first property.
The argument given in appendix A.2.1.1 of [NieChu2007] shows that there is a set of size at most log(|H |) ≤ log(|G|) that generates H . Actually, for any group K, if we pick uniformly at random t + log(|K|) elements of K (for some integer t ≥ 0) then the set obtained generates K with probability ≥ 1 − 2 − t (see Appendix D of [Lom2004]).
Ettinger, Høyer and Knill [EttHøyKni1999] proved that the second requirement can always be satisfied i.e. only a polynomial number of calls to f is needed to identify H . The idea is to prepare the state and measure the second register to get a tensor product of m coset states (see definition 4.8). Then they apply measurements for each g ∈ G, that check whether g ∈ H . They prove that the answers given by the algorithm are correct with high probability for some m = O(n). However, the whole algorithm is not poly(n) since we test |G| = Ω(exp(n)) elements.

Example 3.6
In Simon's problem an efficient algorithm means a poly(n) (i.e. the number of bits in the strings x, s...) complexity and n = log ( | ℤ 2 n | ) . Here, we measure the complexity using the numbers of queries to the oracle rather than elementary operations (because f may not be computed efficiently per comment above).
In Shor's algorithm and the discrete logarithm problem, it means polynomial in the number of bits needed to encode the numbers we work on, i.e. ⌈log(N)⌉ and ⌈log(p)⌉ respectively. f uses basic operations on such numbers so has a polynomial complexity. The sizes of the groups we work with are N and (p − 1) 2 respectively, so their log G's are equivalent to the values we previously used to measure efficiency.
In all cases, there is only one generator to the group H , namely s, r and (y, − 1). ▱ In the particular examples of previous sections, there are natural encoding of the elements and algorithm to compute the product of two elements. For instance, for the cyclic HSP G = ℤ N the elements are encoded as binary number of length ⌈log(N)⌉ and there are well-known algorithms of complexity polynomial in ⌈log(N)⌉ for the group operations. To study the general HSP, it is often useful to see the group G as a black-box where the operations are performed by a group oracle. As in the case of the HSP oracle computing f , replacing the group oracles by polynomial-time operations yields an efficient algorithm.

Definition 3.7 (black-box group, unique encoding, encoding length, input size)
Let n = O(log(N)) and m ≥ 0. n is called the encoding length and mn the input size. A black-box group with unique encoding has the following properties: G is given by generators g 1 , …, g m . 1.
there are oracles to perform multiplication and inversion. 2.
each element can be represented by a binary string of length n.
For a black-box group without unique encoding we replace the point 4 by an oracle performing identity testing (hence equality). ◇ 4. The "Standard Method" for The Hidden Subgroup Problem

The Abelian Hidden Subgroup Problem
This section deals with the abelian HSP and is mostly based on [Dam2001]. We just give the big picture of the general method and show how it generalizes the three previous examples. A more detailed presentation is given in [Lom2004].
In the previous chapter, we have seen three efficient quantum algorithms that fit into the framework of the hidden subgroup problem. Actually, these problems are also sharing the same kind of algorithm. First, they are all based on a particular case of HSP where the group is abelian. As it is well-known, such a group is isomorphic to a product of cyclic groups ℤ t 1 ×ℤ t 2 ×ℤ t 3 ×…×ℤ t k and this is clearly the case in the three previous algorithms. We can then describe the quantum circuit in a general way: The first register is composed of a product of k states of ⌈log(t i )⌉ qubits and we apply to this register the operation F G = F t 1 ⊗ F t 2 … ⊗ F t k i.e. the Fourier transform F t i to the i-th state (note that for Simon's problem, H = F 2 ). First, let's consider the effect of F G on any element g ∈ G: Where we have introduced the characters χ g (g′). Note that g ↦ χ g is a group homomorphism i.e. χ g+ g ' = χ g χ g ' . We also have χ g (g′) = χ g ' (g) and so χ g (g′ + g′′) = χ g (g′) χ g (g′′). Hence we can define the group H ⊥ = g ∈ G χ g (H ) = 1 { } | | . By Theorem 3.10 of [Lom2004], H ⊥ is isomorphic to G H and moreover ( H ⊥ ) As we have already seen many times, the state after the gate U f is the following superposition: Measuring the second register gives a value y = f ( g 0 ) and leaves the first register in the state Then we apply the Fourier transform F G . Using the expression of formula 4.1 and the properties of the characters, we get Moreover, the previous calculation shows that each element of H ⊥ has the same probability to be measured. Hence, measuring the first register yields a uniformly random element of H ⊥ . Repeating the previous circuit about n = ⌈log |G|⌉ times gives with high probability a set of generators g 1 , …, g O(n) of H ⊥ . We . If we denote e the lower common multiple of the t i 's and α . We can put this system in Smith normal form (i.e. write as a diagonal system) in time polynomial of n. Then get O(n) linear congruences i.e. of the form ax ≡ b mod (e). The method to enumerate the list of solution to a linear congruence is well-known. We randomly pick one solution to each linear congruence to get a uniformly random element of H . Repeating this about n times gives with high probability a set of generators of H .
As previously stated, we also need an efficient quantum circuit to compute the Fourier transform F G . Note that such a circuit is known for F 2 x and an approximate one (i.e. measuring the result gives a probability distribution very close to the exact version) for other F x 's. See for instance [Lom2004]. This allows to have an approximate implementation of F G = F t 1 ⊗ F t 2 … ⊗ F t k that does not change too much the measurement of the circuit of figure 4.1.
As a consequence, we have an efficient solution to the abelian HSP if we know a decomposition ℤ t 1 ×ℤ t 2 ×ℤ t 3 ×…×ℤ t k of G. Otherwise, we can get it if we are working in the black-box model with unique encoding. We describe the idea of [CheMos2001], without trying to optimize the computation. We choose randomly k ' = O(n) elements a 1 , …, a k ' of G, so that they generate the group with high probability. Then we x i a i . Each term x i a i is computed using O(log x i ) = O(log|G|) = poly(n) sums (by a double-and-add algorithm), so f has a polynomial complexity. ℤ |G| k ' is abelian and we know its decomposition so we can apply the HSP algorithm to find a set of generators for the hidden subgroup H = Ker f . Alternatively, these generators can be obtained using the algorithm of [BucNei1996]. It can be shown that from this set of generators we can find (classically) in poly(n) a set of generators u 1 ̅̅ , …, u k ̅̅ of H that satisfies: We define an abelian HSP by f i : ℤ |G| → G and f i (x) = xv i (again, f has a poly(n) complexity). As in Shor's algorithm, the hidden subgroup is t i ℤ |G| where t i is the order of v i . Finally, we get G ≅ ℤ t 1 ×ℤ t 2 ×ℤ t 3 ×…×ℤ t k .

Fourier Transform over Finite Groups
In order to generalize the previous algorithm to any finite group, we need a way to define Fourier Transform. First, we give a brief overview of representation theory of groups, based on [Ser1971].

Definition 4.1 (representation)
A representation of a group G is a group homomorphism ρ : G → GL(V ) where GL(V ) is the group of automorphisms over a finite dimensional vector space V . The dimension d ρ of the representation ρ is the and V , we say that ρ is irreducible. Two representations ρ : G → GL ( V ρ) and τ : G → GL(V τ ) of G are equivalent or isomorphic iff there is an isomorphism ψ : V ρ → V τ such that τ(g) = ψ ∘ ρ(g) ∘ψ − 1 for any g ∈ G. Given a representation ρ, we define the character χ ρ by χ ρ (g) = tr(ρ(g)). ◇ In [Ser1971], it is shown that any finite group G has only a finite number of irreducible pairwise non-isomorphic representations. More precisely, if we denote Ĝ a complete set of such representations and V ρ and d ρ the associated vector space and dimension (for any ρ ∈ Ĝ), we have the following equality from 2.4 Décomposition de la représentation régulière -Corollaire 2: In particular for g = 1, because χ ρ (1) = tr ( I d ρ ) = d ρ , we have: For each ρ, we can choose a basis of V ρ and then ρ(g) is represented by a matrix of size d ρ . Again, in view of formula 4.8, we can group all the coefficients ( ρ i j (g) ) 1 ≤ i, j ≤ d ρ , g ∈ G in a square matrix of dimension |G|. To make this matrix unitary, we add the requirement that each ρ(g) is unitary. We will see that it is always possible to choose the basis such that this requirement is satisfied. Once such a basis is chosen and when no confusion is possible, we will also denote ρ(g) the matrix representation of ρ(g) in this basis.

Definition 4.2 (general Fourier Transform)
Let G be a group and Ĝ a complete set of pairwise non-isomorphic representations ρ : G → GL ( V ρ) of size d ρ . For any ρ, we fix a basis of V ρ such that for each g ∈ G we have a unitary matrix representation ( ρ i j (g) ) 1 ≤ i, j ≤ d ρ of ρ(g). Then the Fourier Transform over G in the given basis is defined as a linear operation over a Hilbert space of dimension|G|. More precisely, if we denote the canonical basis either by group elements (|g⟩ g ∈ G ) or by representations/coordinates (|ρi j⟩ ρ ∈ Ĝ, 1 ≤ i, j ≤ d ρ ), we have: or, if Ĝ= { ρ 1 , ⋯, ρ M } and d k = d ρ k , by the images of basis vectors:

Proposition 4.3 (Fourier Transform is unitary)
F G is a unitary transform i.e. the columns (F G |g⟩) g ∈ G of F G form an orthonormal family.

Proposition 4.4 (representations are unitarizable)
be an arbitrary basis of V ρ . We have the canonical hermitian product given by We define ⟨a, b⟩ G = ∑ g ∈ G ⟨ ρ(g)(a), ρ(g)(b)⟩ which is still a inner product because ρ(g) is an automorphism. Using Gram-Schmidt process, we construct a new basis f 1 ρ , …, f d ρ ρ orthonormal for ⟨., .⟩ G in which we express ρ(g). On the one hand, we have by construction ⟨a, b⟩ G = On the other hand, Let's see how the previous definition generalizes the abelian case:

Example 4.5 (Abelian Fourier Transform)
Suppose G is abelian and define for all g ∈ G the 1-dimensional (i.e. d ρ g = 1) representation ρ g : where χ g is the character defined in the previous chapter. The representations are clearly unitary. Note that χ ρ g (h) = χ g (h) so the definition of the character is consistent with what we have seen earlier. Suppose that two representations ρ(g) and ρ(g ') are isomorphic. This means that there is a λ ≠ 0 such that ρ g (h) = λ ρ g ' (h)λ − 1 = ρ g ' (h) for all h ∈ G. With the notation of previous chapter, we have For j going from 1 to k, we evaluate the equality at h = h j = ( δ i, j ) 1 ≤ i ≤ k we get g j − g j ' = 0 and finally g = g '.
is a set of pairwise non-isomorphic 1-dimensional representations. It is complete since it satisfies the equality of formula 4.8. Using the identification |g⟩ ≅ |ρ g 11⟩, and ( ρ g) 11 (h) = χ g (h) we recover the definition of the abelian Fourier Transform. ▱

Remark 4.6 (irreducible representations of non-abelian groups)
In 3.1 Sous-groupes commutatifs -Théorème 9 of [Ser1971], it is shown that G is abelian iff all its irreducible representations are 1-dimensional. So in the nonabelian case, we will always have to deal with at least one representation of dimension greater than 1. △ The proposition 4.4 above shows that there is at least one basis of V ρ . Actually, we obtain all of them by unitary change of basis:

Proposition 4.7
Let τ be an irreducible representation of G and let τ(g) denote an unitary matrix representation. Then the possible unitary matrix representations of all other isomorphic representations ρ are given by ∀ g ∈ G, ρ(g) = U τ(g)U † for any unitary matrix U .
proof: First, it is clear that given a unitary matrix, then ρ(g) = U τ(g)U † is still unitary and is the matrix representation of ρ = τ obtained using U as a change-of-basis matrix. Conversely, suppose ρ is isomorphic to τ and let ρ(g) denote an unitary matrix representation. Then there is an invertible matrix M (the matrix representation of an isomorphism between τ, ρ in their respective basis) such that ∀ g ∈ G ρ(g) = Mτ(g)M − 1 .
This gives: and finally τ(g)M † M = M † Mτ(g) for any g ∈ G. Since τ is irreducible, the Schur's lemma (see Le lemme de Schur ; premières applications -Proposition 4 of [Ser1971]) implies that M † M = λ I for some λ ∈ ℂ. More In this section, we have defined an operation F G for any given group. We know that it is unitary so a valid quantum. However, if we want to to use it in a HSP algorithm, we need to implement it efficiently i.e. using poly(n) elementary gates. As mentioned above, there is an approximate efficient implementation of F N for cyclic group. By taking the tensor product of such operations, we get an approximate efficient implementation for any abelian group G. Other efficient implementations are known for various groups, see [Lom2004] for an overview.
The exact description of the quantum gate F G depends on the design used for the implementation.
Nevertheless, we will suppose in what follows that the gate implementing F G works on n qubits. The input |g⟩ and output |ρi j⟩ are encoded by the integers 0, …, |G| − 1. The possible remaining basis states are not touched by the gate.

Weak and Strong Fourier Sampling
For the generalized version of the Fourier Sampling circuit, we replace the first Fourier Transform by a gate V that computes a superposition 1 |G| √ ∑ g ∈ G |g⟩ from the |0 n ⟩ state. There is no canonical implementation for V but if the elements of G are encoded by the integer 0, …, |G| − 1 (as we have assumed in previous section) we can use the following circuit: We use a hadamard gate to create a superposition over 0, …, 2 n − 1 and a function g to select the values less than |G|: g(i) = 1 if 0 ≤ i < |G| and g(i) = 0 otherwise (It can be implemented efficiently, just by comparing the binary decomposition of i and |G|). We succeed to create the superposition if the result of the measurement is 1. We have 2 n − 1 < |G| ≤ 2 n , so this happens with probability |G| 2 n > 1 2 .
The remaining of the circuit is similar to what we have previously seen, with the use of a general Fourier Transform gate F G : After applying the gate U f we have the superposition We then measure the second register and get y = f ( g 0 ) . We obtain a superposition on a coset g 0 H : Creating this superposition is the starting point for all HSP algorithms currently known. Hence we define: Definition 4.8 (coset sampling, the "standard method", coset state) Coset sampling also known as the "standard method" for HSP consists in creating many states given by formula 4.16, where g 0 ∈ G is chosen uniformly at random. These states are called coset states. ◇ For Fourier Sampling, the next step is to apply the Fourier Transform F G . This gives the state . Finally, we perform a measurement on the first register.

Definition 4.9 (Fourier Sampling Algorithm)
The Fourier Sampling algorithm for the HSP consists in running the circuit of figure 4.3 several times and trying to deduce information on the hidden subgroup H . We distinguish two forms of Fourier Sampling: In the Weak Fourier Sampling for the HSP, we observe a representation ρ ∈ Ĝ with probability P(ρ) = In the Strong Fourier Sampling, we observe a representation ρ ∈ Ĝ as well as coordinates i, j with probability P(ρ, i, j).
What is the distribution probability? First the conditional probability given g 0 is P ( Hence for the Weak Fourier Sampling, we have P ( ) and formula 4.18 can be rewritten: In particular, this probability does not depend on the choice of the basis of V ρ ! For the Strong Fourier Sampling, we first note that the |G|-dimensional vectors where the last line is 2.2 Le lemme de Schur ; premières applications -Corollaire 3 of [Ser1971]. We use this fact to simplify the expression of P(ρ, i, j) as described in [GriSchVaz2000]. Because g 0 has been chosen uniformly it is the mean of P ( ρ, i, j g 0 ) over the elements of the group G: and we finally obtain an expression which is totally independent of i: This means that measuring the row provides no information and the Strong Fourier Sampling can be reduced to observing ρ, j. Note that summing over all the j, we recover formula 4.18.

Remark 4.10 (measurement of
As in the abelian case, the measurement of y = f ( g 0 ) is only used to produce a superposition over one coset. As noted in [GriSchVaz2000], we may discard information by not using this value later. For example, just counting the number of distinct values after many samplings gives an indication on |G| |H| so on the size of the hidden subgroup H . In particular, it is easy to determine whether H is a proper subgroup of G (i.e. the ratio above is at least 2) by repeating several measurements until we find two distinct values or get k times the same value. In the former case we know with certainty that H is a proper subgroup of G and in the latter case we know that H = G with probability at least 1 − 2 − k . For completeness, we give the distribution probability. If It seems difficult to construct an algorithm from these values since we do not know the x k corresponding to the measured value f (x k ). △ As said in remark 4.6, all the irreducible representations are 1-dimensional in the abelian case. Consequently, the Strong Fourier Sampling is the same as the Weak Fourier Sampling: we only take into account the irreducible representations ρ g j measured. More precisely, we measure random elements g 1 , …, Then we solve the systems of equations χ g j (h) = χ h( g j ) = 1 to get elements h in H . Said otherwise, we are looking to random elements in Ker ρ g j . In the next section, we will see that more generally, considering the intersection of irreducible representations measured gives information on H and allows to solve the HSP in some particular cases.

The Dedekindian Hidden Subgroup Problem and its extensions
In this section, we see how the Weak Fourier Sampling can be used to extend the abelian HSP. The idea is to measure ρ 1 , …, ρ O(n) irreducible representations and to consider the intersection ⋂ j = 1

O(n)
Ker ρ j . Let's consider first what is happening in an example: We are considering two hidden subgroups H 1 = {1, rs} and H 2 = {1, r 2 }. Using formula 4.20 and formula 4.23, it is easy to get: Consequently, the direct application of the abelian method does not always work. Note that H 2 is normal (it is the of center D 4 ) but H 1 is not (for example s(rs)s − 1 = sr = r 3 s ∉ H 1 ). In general, tr ( ρ(g − 1 H g) ) = tr As a consequence, we can use this to solve the Dedekindian Hidden Subgroup Problem i.e. over groups that have only normal subgroups. Of course, this includes the Abelian HSP that we have previously studied.
) . They give an application to the semi-direct product ℤ 3 ⋊ℤ 2 n .
Gavinsky [Gav2004] strengthened their result to ∈ poly(log|G|). Actually, he proved that we can even just ∈ poly(log|G|) so that the algorithm still works when H is large.
Note that if the group is given as a black-box group without necessarily unique encoding, there is an alternative way to find the normal subgroup H as described in [IvaMagSan2001]. The algorithm does not require the assumptions on Fourier Transform and systems above. Its complexity is given by the input size + a number v( G H ) that we will define later. We will come back to this method in the last part of this report.

The Dihedral Hidden Subgroup Problem
For any N ≥ 1, the dihedral group D N is the group of isometries of the plane generated by the reflection s about the x-axis and the rotation r of angle 2π N . It is composed of 2N elements: N rotations r k and N reflections r k s (0 ≤ k ≤ N − 1) . The elements satisfy the relation r N = s 2 = srsr = Id. We have already seen the case N = 4 in an example of Fourier Sampling. Alternatively, we can describe D N as a semi-direct product ℤ N ⋊ℤ 2 , where (a, b) represents the isometry r a s b . We have r a 1 s 0 r a 2 s b 2 = r a 1 + a 2 s 0 + b 2 and r a 1 s 1 r a 2 s b 2 = r a 1 − a 2 (r a 2 sr a 2 )s b 2 = r a 1 − a 2 s 1+ b 2 , so the law of this semi-direct product is given by and consequently the inverse operation is

Definition 5.1 (DHSP)
The dihedral HSP (DHSP) is the hidden subgroup problem for the dihedral group G = D N ≅ ℤ N ⋊ℤ 2 . An efficient algorithm for the dihedral HSP has a complexity poly(log(N)) (this is equivalent to our general definition because log(|G|) = log(2N) = 1 + log(N)). ◇ DHSP is by itself a natural candidate for finding efficient quantum algorithm based on a nonabelian HSP: on the one hand it is a nonabelian group with a simple structure (so we can hope it is not too difficult to solve) and on the other hand ⟨(d, 1)⟩ 0 ≤ d ≤ N − 1 is an exponential number of subgroups (so the brute-force guessing is infeasible). We will see another motivation in the next section.
What are the possible hidden subgroups H ? Consider the cyclic subgroup Finally, we have:

Proposition 5.2 (subgroups of D N )
The subgroups of D N are: Moreover, the dihedral HSP reduces to efficiently find d when H = H r, d and r is known.
proof: The first part has been discussed above. The value r can be found with high probability in O(poly(log N)) by the cyclic HSP algorithm using the oracle f |G ' . Hence we may assume that r is known. Suppose we have an algorithm that finds d with high probability when H = H r, d and r is known. We can suppose that this algorithm always returns a value d 0 . If f (d 0 , 1) = f (0, 0) then we return H = H r, d 0 otherwise we return H = H r . Because the sub-routines succeed with high probability, so does the whole algorithm. □ Can we use the general algorithms based on the Weak Fourier Sampling, that we have previously seen?
It is easy to check that they correspond to the intersection of the kernels of representations measured in theorem 9.9 of Appendix B. We notice that Ettinger and Høyer proved in [EttHøy1998] that the dihedral HSP reduces to the case where To see that, suppose we start with the reduced case of the theorem i.e. H = H r, d and r is known. The elements of G H r are (i, 0)H r and (i, 1)H r for 0 ≤ i < r while the elements of H H r are given by H r , (d, 1)H r . Hence, moving to the quotient group we have the hidden subgroup problem for G H r ≅ D r and hidden subgroup ⟨(d, 1)⟩. We see that we have a solution to the hidden subgroup problem with complexity poly (log(N), r) (poly(N) to find r and poly(r) to find d working in D r ). In particular the algorithm is already efficient in the case r = poly(log N) solved by Gavinski's HSP algorithm. We have proved the important reduction:

Proposition 5.3 (reduction to finding a slope)
The dihedral HSP reduces to efficiently find the slope d when (3) Ettinger and Høyer used the same circuit as in HSP over ℤ N ×ℤ 2 and proved that this yields an algorithm for the dihedral HSP. In this quantum circuit, we distinguish two registers for encoding the elements of D N and perform three separate measurements.
As usual, the first part of the circuit produces a superposition The first measurement yields a f (a 0 , b 0 ) and makes the two first registers collapse to since a 0 and b 0 are chosen uniformly at random, this is equivalent to have a state for some x ∈ ℤ N chosen uniformly at random. Applying the Fourier transform F N to the first register gives the state The second measurement returns a k ∈ ℤ N chosen uniformly at random and make the second register collapse to the state Finally, we apply an hadamard gate on the second register to get The measurement given by (2) and (3) is then: The algorithm of Ettinger and Høyer starts by checking the values d = 0 or d = N 2 (just by comparing f (0, 0) with f (0, 1) and f ( The state at the output of coset sampling is important since it is the base of all the other DHSP algorithms. Thus we define the following problem, to which DHSP reduces:

Definition 5.4 (Dihedral Coset Problem)
Let N ∈ ℕ and d ∈ ℤ N . The dihedral coset problem (DCP) is to find the value of d given a black box that outputs a state given in formula 5.5 for a random x ∈ ℤ N . ◇ Note that the circuit of figure 5.1 is not the Fourier Sampling based on group representations. Appendix B studies in detail all the possible distribution obtained by this latter method. One of the main results is that the distribution probability of formula 5.9 can be obtained from the output of a Strong Fourier Sampling in a particular basis and so Ettinger and Høyer 's algorithm applies. The second important result is that Strong Fourier Sampling is less general than DCP, in the sense that a black-box for DCP can simulate a Strong Fourier Sampling. This includes the case where we apply Strong Fourier Sampling with any hidden subgroup H and not only H N , d . Actually, it is quite remarkable that applying Strong Fourier Sampling on the initial group is essentially the same as applying Strong Fourier Sampling on the quotient group. Some attempts to solve DHSP via Strong Fourier Sampling are given in Appendix C and suggest that this method is not likely to work. Indeed, Fourier Sampling uses only measurement on one coset state at once, while we will see later that we require a polynomial number of them. In appendix G, we propose an entirely new approach, based on uniform superpositions over large subsets of f (D N ). In particular, we can solve the case N = 2 n if we have an efficient process to create for b = 0, 1 the states 1 In the next section, we will see in more details the different results obtained for DCP.

The Dihedral Coset Problem
The next successful step after Ettinger and Høyer was the discovery by Kuperberg [Kup2003] of a subexponential-time algorithm to find the slope d and thus the hidden subgroup. First note that ignoring the phase factor, formula 5.7 allows to generate states: We now give a rough description of Kuperberg's algorithm in the particular case N = 2 n . In that case, if we are able to create | |Ψ 2 n −1 ⟩ = 1 2 √ ( |0⟩ + (−1) d |1⟩ ) then a measure in the Hadamard basis gives the parity of d.
Kuperberg noted that the hidden subgroup is necessarily included in the subgroup H 2,0 (if d is even) or H 2,1 (if d is odd). Both are isomorphic to D 2 n −1 so we can restrict to the appropriate subgroup and use an iterative algorithm for finding the other digits of d.
Suppose we have two states |Ψ k ⟩ and |Ψ l ⟩. Taking their tensor product, applying a CNOT gate and ignoring the phase factor gives a state |Ψ k ± l ⟩ on the first register where ± is randomly determined by the measurement of the second register. If both k, l are multiple of 2 i (i.e. have 0's as their i least significant bits) then one of k ± l is multiple of 2 i ' for some i ' > i.
DCP Black Box |Ψ k ⟩ |Ψ *****00 ⟩ |Ψ ***0000 ⟩ |Ψ *000000 ⟩ ... The idea of Kuperberg is to use a pipeline as represented in figure 5.2. At the input, many |Ψ k ⟩'s are created by the DCP black box. At each stage i, we have states |Ψ k ⟩ such that the n i least significant bits of k are zeros. We make many combinations as described above and we get at stage i + 1 a certain amount of states |Ψ k ' ⟩ such that the n i + 1 > n i least significant bits of k are zeros. At the output of the pipeline, we get the state | |Ψ 2 n −1 ⟩ with high probability.
The running time of Kupenberg's algorithm is 2 O ( log N √ ) which is subexponential but unfortunately, the algorithm also requires 2 O ( log N √ ) quantum space. Shortly after that Kupenberg designed its algorithm, Regev [Reg2004] gave an improved version that requires only polynomial space at the price of increasing the running . Note that in both algorithms the query complexity is actually the same as the running time.
In [BacChiDam2005] quantum-information theory is used to see how much information we can get from a DCP black box. If we let | | φ x, d ⟩ = 1 2 √ (|x⟩|0⟩ + |x + d⟩|1⟩) then the density matrix output by the DCP black box is So if we use k = ν log(N) outputs from this black box, our purpose is to identify the density matrix ρ d ⊗k among all the a priori equiprobable values of d. Bacon, Childs and van Dam found the optimal measurement for that purpose (the so-called "pretty good measurement") and showed that we can determine d with exponentially small probability if ν < 1 and a constant probability if ν > 1. Since the algorithm of Ettinger and Høyer gives an algorithm using linear (in log(N)) oracle calls, this means that the query complexity of DCP is exactly Θ(log(N)). Note that Bacon, Childs and van Dam have a similar result in the case where we try to determine only the parity of d.
Finally, let's mention a relationship between DCP and the subset sum problem. Recall that this problem is to find a subset of a given set of k integers that sums to another given integer r. It is well-known that the decision version of the problem is NP-complete. However, in the discussion below, we fix a density k > log(N). We can still hope that it is possible to solve some instances at that density and so that it will help us to get better algorithms for DHSP.

Definition 5.5 (subset sum problem)
Let N > 0 be an integer. The subset sum problem at a fixed density k > 0 is, given a x ∈ ℤ N k and a target value t ∈ ℤ N , to find an element of S t In [Reg2003], Regev proved that if it is possible to solve a fraction 1 poly(log N ) of the legal instances of the subset sum problem if k > 4 + log(N), then we have a solution to DCP. Some algorithms have been proposed after Regev's paper [FlaPrz2004] [Lyu2004], giving an alternative solution for DHSP with subexponential complexity.
Bacon, Childs and van Dam gave a similar result in [BacChiDam2005]. We define the uniform superposition of solutions to a legal instance of the subset sum problem with input (t, x): if we have a quantum circuit that operates on input states |t, x⟩ and sends the legal instances to |S t x , x⟩ then we can implement the optimal measurement and thus solve DCP. Producing these states |S t x ⟩ is stronger than the Regev's condition: not only we need to be able to solve all the legal instances but also for a given input we need to gather all the solutions in one big entangled state. Conversely, Bacon, Childs and van Dam showed that an implementation of the optimal measurement according to their particular schema yields a solution to the subset sum problem.
Note that these DCP solutions based on the subset sum problem are solving DHSP by coset sampling over the whole group. In contrast, Kuperberg's algorithm for DHSP works recursively: we need a DCP black-box which is able to sample over subgroups of D N containing H . However, there is an alternative non recursive version where we use the phase estimation algorithm to approximate d.

Dihedral HSP, Lattice Problems and Cryptosystems
In the two previous sections, we have given an overview of the DHSP results known so far. While we can try to find efficient HSP algorithms for their own sake, Regev showed that the case of the dihedral group is particularly interesting: it is related to some lattice problems whose difficulty is assumed in some cryptographic systems. This section, based on [Reg2003] and [MicReg2008], explains more precisely this relationship. = B ∈ GL n (ℝ)). We define the lattice generated by the basis as the set of all linear combinations of the basis vectors with integer-valued coefficients: An example of a 2-dimensional lattice i.e. generated by a basis b 1 , b 2 of ℝ 2 is given in figure 5.3 (notice that an alternative basis is also given). Lattices are involved in many problems assumed to be hard. The one that we will particularly be interested in is the following:

Definition 5.7 (f(n)-uniqueSVP)
The Shortest vector problem (SVP) is to find in the lattice a non zero vector of minimum length. In the f (n) -uniqueSVP (uniqueSVP) we have the promise that such a vector is necessarily shorter by a factor f (n) than all other non-parallel vectors. ◇ As we have seen at the beginning, Shor's algorithms allow to break cryptosystems based on the hardness of factoring or discrete logarithm's computation. One kind of alternative cryptosystems proposed is based on lattices. In Appendix E, we summarize in one table the overview of [MicReg2008].
In order to establish a connection between one of the f (n)-uniqueSVP and DCP, we need to modify the black-box in a way that allows errorous output. So we introduce:

Definition 5.8 (DCP with failure parameter p)
Let N > 0 be an integer and p > 0. The DCP over D N with failure parameter p is the problem of finding a hidden slope d ∈ ℤ N given a black box that behaves almost always like a DCP black box. More precisely, this black box produces a DCP-state 1 2 √ (|x⟩|0⟩ + |x + d⟩|1⟩) for some uniformly random x ∈ ℤ N with probability at least 1 − 1 (log N ) p and an arbitrary |a⟩|b⟩ ∈ D N otherwise. ◇ We can now state the main theorem, due to Regev [Reg2003]: Let n > 0 an integer and define N = 2 (4n + 1)n . If there is a solution to the DCP over D N with failure parameter p then there is solution to the Θ If there is a solution to DCP over D 2 (4n +1)n whose query complexity can be expressed as a polynomial of degree D, then there is a solution to Θ proof: the probability that the DCP with failure parameter p produces only DCP-states after ∑ When N → + ∞, the limit of the bracket term is 0 if i > p, ⅇ − 1 if i = p and 1 otherwise. So the above value is bounded below by a constant c > 0 iff D ≤ p. In that case, we can repeat the procedure about 1 c times to be sure that we solve DCP over D 2 (4n +1)n with failure parameter p = D and so the Θ The corollary gives the optimal degree of the approximate polynomial for uniqueSVP we can get from Regev's algorithm, assuming that the DCP algorithm does not accept failure at all. By the result of [BacChiDam2005], a DCP algorithm can not work with sublinear query complexity, so the best we can do is ) -uniqueSVP. If we look to figure 12.1, this would be a rather minor result since it affects only Ajtai-Dwork cryptosystem improved by Goldreich/Goldwasser/Halev, which is not likely to be used in practice. Moreover it is important to note that an algorithm for uniqueSVP only invalidates the proof of security but, contrary for example to Shor's algorithm, does not necessarily give a way to break them.
However, solving DCP would give a HSP-related algorithm that invalidates the security proof of a cryptosystem and hence gives hope that more algorithms of this kind could be found. According to figure 12.1, an interesting direction would be to find algorithms for other problems such that SVP, SIVP or LWE. Considering specific version of lattices used in cryptosystems such that "ideal lattices" would maybe help finding efficient algorithms.
It is worth looking to the ideas of Regev's algorithm. First Regev introduces the "two points problem" which is essentially DCP where the scalars x, x + d are replaced by two vectors in ℤ M n with constant difference. The two point problem reduces to DCP over D (2 M ) n by considering the mapping: (a 1 , a 2 , …, a n ) ↦ a 1 + a 2 2M + … +a n (2M) n − 1 (5.14) This is clearly one-to-one and so (modulo some additional wires) can be implemented as a unitary transform permuting the basis states. In general, it is not clear that it can be done efficiently but in Regev's case, M = 2 4n is the power of 2, so this is just adding wires and permuting them. As announced above, we are considering DCP over D 2 (4n +1)n . In particular, we only need a solution to DCP over a power of 2, which may be easier than the general N. We also note another way to solve this step: we can directly find the difference v ∈ ℤ M n if we have an algorithm for a DCP-like problem over This corresponds to a generalized DHSP over ℤ M n with hidden subgroup ⟨(v, 1)⟩.
Then, Regev creates a polynomial number of instances for the two points problem. Among all these instances, there is at least one giving an output from which we can extract the shortest vector. So we only run the procedure many times and keep the shortest vector inside the lattice. The routine uses a funtion F = g ∘ f where f maps elements of ℤ M n to lattice vectors and is very similar to coset sampling: we start by a superposition over ℤ M n , apply U F and measure the result image of F. Regev gives two versions with different g (one based on cube partition of the space and a more efficient based on sphere partition) but in any case it is chosen such that with high probability, we are going to have a superposition over two very close lattice points encoded in a state 1 2 √ (|x⟩|0⟩ + |x + v⟩|1⟩).
This similarity between the coset sampling procedure and Regev's algorithm is really important. While all the studies that have been made so far on DHSP were based on the DCP problem i.e. a standard coset sampling on H = ⟨(d, 1)⟩, it is well possible that modifying our coset sampling procedure will give better results to solve DHSP. Hopefully, the modifications can be applied in a straightforward manner to Regev's procedure, and so our relation with uniqueSVP will still hold. The example 5.11 gives possible modifications we have experimented, but they have not lead to improvements.

Example 5.11 (modified coset samplings)
Modifying the oracle. Fix k > 0 and define the function . Then the coset sampling using f 1 as oracle produces a state 1 2k Modifying the input state on the oracle register: fix some k > 0. Rather than sending the state |0⟩ on the oracle register (i.e. the last register of U f ) send a superposition of k basis states 1 k √ ∑ i = 1 k | | y k ⟩ for some uniformly random distinct elements y k . Then the coset sampling produces a state Making the superposition non-uniform: input the states ∑  H (1,1, …, 1, 2, 1, …, 1), b (with a 2 at the ith position) instead, which is isomorphic to another generalized dihedral ) and by induction, we continue to move to dihedral groups of the form Dih(A) with smaller and smaller complexity. Of course, if we are only working on a specific class of group we have to ensure that we remain in this class at each induction step, contrary to the previous example.
In the case of A = ℤ 2 4n n , this reduction to a smaller group can be translated in a straightforward way to Regev's algorithm: we create the superposition over the new subgroup of A rather than on the whole A. For the dihedral group, we have to look carefully to what is happening with the mapping of formula 5.14. Determining the digit of d in the increasing order of their significance is doing the same for each a i for an increasing i (again, this works well because M is a power of 2). Hence we can again create the superposition over subgroups of the corresponding A. The mapping sends them to the decreasing sequence of groups described above for Kuperberg's algorithm. Finally, we have the following corollary:

Corollary 5.12 (class-preserving recursive DCP algorithm is allowed)
The previous connections between DCP and uniqueSVP hold for class-preserving recursive DCP algorithms over some generalized dihedral groups. More precisely, we mean an algorithm based on coset sampling over a class of generalized dihedral group Dih(A) which includes Dih ( ℤ 2 4n n ) and such that the recursive step moves to a subgroup of the same class. A recursive DCP algorithm is also allowed for A = ℤ 2 n group if the inductive step consists in determining the parity b of d and moving to H 2, b ≅ D N /2 . □ As a final remark, Regev's procedure generates a superposition of two lattice points with constant difference. Maybe we could increase the number of points in the superposition and use another group with larger coset states (for example semi-direct product A⋊ℤ p with A abelian). Allowing more points in one partition could weaken the uniqueSVP promise.

The Symmetric Hidden Subgroup Problem
For any n ≥ 1, let S n denote the symmetric group i.e. the group of permutations on a set of n elements. This group is of order n !, so log|S n | = ∑ i = 2 n log(i) and since 1 ≤ log(i) ≤ i for i ≥ 2, we have n − 1 ≤ log|S n | ≤ n(n + 1) 2 − 1.
This means that n can be used as a measure of efficiency since log|S n | = poly(n) (more precisely, the Stirling formula gives |S n | = 2πn

Definition 5.13 (SHSP)
The symmetric HSP (SHSP) is the hidden subgroup problem for the symmetric group S n . An efficient algorithm for the symmetric HSP has a complexity poly(n). ◇ By Cayley's theorem, every group G is isomorphic to a subgroup of S |G| . Hence to find a subgroup H of G, one can apply a SHSP to the corresponding subgroup of S |G| . However, an efficient algorithm for S |G| would be poly(|G|) while an efficient algorithm for G needs to be poly(log(|G|)).
A more exciting application is that an efficient algorithm for SHSP would give a solution to the graph isomorphism problem, which has remained unsolved for many decades. We recall:

Definition 5.14 (Graph isomorphism and automorphism problems)
Let (V 1 , E 1 ) and (V 2 , E 2 ) be two (undirected) graphs. They are said to be isomorphic iff there is a bijection φ The graph isomorphism problem is to determine whether two such graphs are isomorphic, in time polynomial in the size of the input parameters (the number of vertices for example). The graph automorphism problem is to determine whether a graph has a non-trivial automorphism (i.e. there exists a φ ≠ Id which is a permutation of the vertices of the graph). ◇ Notice that the definition above is the decisional version of the graph isomorphism problem. It turns out that finding an explicit isomorphism or counting the number of isomorphism has the same complexity, so we can restrict ourselves to the decisional version. This version is clearly in the class NP, but it is known neither to be NP-complete nor to belong to the class P. Many problems are computationally equivalent to the graph isomorphism problem. For instance, it is the case of the graph automorphism problem, to the weaker version with connected graphs or to the stronger version with directed graphs. See, [Köb1993] for details.
Let's consider first the reduction of the graph automorphism problem to SHSP. Let (V , E) be a graph and define H to be the set of its automorphisms. Obviously, the identity is an automorphism, the inverse of an automorphism is an automorphism and the composition of two automorphisms is again an automorphism. Hence H is a subgroup of the permutations of V that can itself be viewed as S n for n = |V |. We define the oracle f to be the function that send φ ∈ S n to f (φ) = (φ(V ), φ(E)). As indicated in [Lom2004], f can be computed efficiently. Suppose for instance that we have fixed an enumeration {0, ⋯, n − 1} of the vertices V and we represent the graph (V , E) by an ordered list of pairs (a, b) where a ≤ b ∈ V and {a, b} ∈ E. Given (V , E), we can compute (φ(V ), φ(E)) efficiently by replacing each (a, b) by (φ(a), φ(b)) and then applying classical sorting algorithms on the whole structure.
Finally, we have H a subgroup of S n and clearly ∀ φ 1 , φ 2 ∈ S n , f (φ 1 ) = f (φ 2 ) ⇔ φ 1 H = φ 2 H . So an efficient algorithm for DHSP gives a poly(n) algorithm for determining H . Actually, we only need a weaker version of DHSP where we want to determine whether H is non-trivial i.e. the graph has a non-trivial automorphism.
When the two graphs (V 1 , E 1 ) and (V 2 , E 2 ) are rigid i.e. do not have a non-trivial automorphism, there exists a reduction from the graph isomorphism problem to a somewhat simpler version of HSP. First, if the graphs do not have the same number of vertices, then they are clearly not isomorphic and we are done. So let n be their common number of vertices. It is easy to check whether each graph is connected in time O ( n 2 ) . Again, if one is connected and the other is not then we are done. If both are not connected, then their complement graphs are connected and using these complement graphs instead changes neither the answer to the graph automorphism nor the rigidity of the graphs. Hence we suppose that the two graphs are connected and rigid.
An isomorphism φ : V 1 → V 2 between the two initial graphs can be seen as an element of S n . If we introduce the the involution s n permuting i and n + i for all 1 ≤ i ≤ n, φ can actually be seen as the automorphism ( φ, φ − 1 ) s n ∈ S 2n of the disjoint union of the initial graphs.
As above the set H of all automorphisms of the union graph is a subgroup of S 2n . Since we know that the union graph is made of two connected rigid components, we have either H = {Id} if the two initial graphs are not isomorphic or otherwise H = {Id, σ} where σ = ( φ, φ − 1 ) s is an involution of S 2n permuting the two components. Hence we have obtained a variant of DHSP where the graph is either trivial or a conjugate of H 0 = {Id, s} and whose solution gives an efficient algorithm to determine whether two rigid graphs are isomorphic.
We can actually simplify the problem any further: H is always included in the group G generated by s n and the permutations of S 2n fixing each component (i.e. elements of S n ×S n ⊆ S 2n ). We have (a, b)s n = s n (b, a) and s n is of order 2 so any element of G can be written (a, b)s n c for some (a, b) ∈ S n ×S n and c ∈ ℤ 2 . If τ is the transposition of S 2 then the law of G is defined by :   (a 1 , b 1 , c 1 )(a 2 , b 2 , c 2 ) = ((a 1 , b 1 ) ∘τ c 2 (a 2 , b 2 ), c 1 + c 2 ) (5.15) This is called the wreath product of S n and ℤ 2 and denoted by G ≅ S n ≀ ℤ 2 = (S n ×S n )⋊ℤ 2 . Finally, we now have an instance of HSP over the group S n ≀ ℤ 2 and we only have to distinguish the cases H trivial (the two graphs are not isomorphic) or H = {Id, ( a, a − 1 , 1 ) } ( a ∈ S n is the isomorphism between the two graphs).
We can notice that we have a reduction from the rigid graph isomorphism problem to the simple HSP group A 2n . If ε denotes the signature of permutation, we have ε(σ) = ε(φ) 2 ε(s n ) = 1(−1) n . If n is even, then we can directly work in A 2n . Otherwise, let m = n + 1, add to each initial rigid graph another connected component composed of only one single node, and combine them into a big graph of 2m nodes. If we define the transposition τ = (m, 2m), then the automorphism group H of the big graph is a subgroup of S 2m and is similar to the previous case: either H = ⟨τ⟩ or H = ⟨τ, σ⟩ where σ = ( φ, m ↦ m, φ − 1 , 2m ↦ 2m ) s m . The problem is now to determine whether the subgroup H ∩ A 2m of A 2m is trivial or ⟨σ⟩.
Attempts to solve SHSP, even the restricted versions have not reached any success so far. The first question is whether the classical Fourier Sampling method is helpful. Some negative results were proved for the weak Fourier Sampling [GriSchVaz2000] [HalRusTa-2000], extended to strong Fourier Sampling [MooRusSch2005] and finally to an arbitrary POVM over many entangled coset states [HalRoeSen2005]. More precisely, the last result shows that we need to perform measurement on at least Ω(log(|S n |)) = Ω(nlog n) entangled states at once.
One model for using such an entanglement is Kuperberg's algorithm for DHSP. It can be interpreted as a repetition of combine-and-measure operations on representation state (i.e. given representation states ρ i and ρ j , apply measurement on their tensor product ρ i ⊗ ρ j to get a new representation state) until we reach a representation from which one can extract useful information on the hidden subgroup. [MooRusSni2006], proved however that such an algorithm can not succeed for the symmetric group unless it takes ⅇ Ω ( n √ ) time. This does not give any meaningful improvement over the best known classical algorithms: ⅇ O ( n log n √ ) for general graphs [BabLuk1983] or ⅇ O ( n 1 3 log 2 n ) for strongly regular graph [Spi1996].
Despite intensive study, no quantum algorithm for SHSP are known. It is worth noting that the structure of the symmetric group is very complex (S n contains all the groups of order n as subgroups) and is likely to be much more difficult to solve. It is possible that a straightforward method (i.e. performing coset sampling over the S n or S n ≀ ℤ 2 ) is not appropriate and we should rather distinguish many particular or reduced cases as in the classical algorithms mentioned above, which rely on classification of finite simple groups. Solving HSP for other groups will provide us more techniques and probably help us to find a general method. For example, O'Nan-Scott theorem gives the form of the maximal subgroups of S n and we could use the "maximal subgroup reduction" method given in the next section.

General approach to the Hidden Subgroup Problem
In this section, we recall the two fundamental theorems of group theory describing all finite groups. We show how they can be used to solve the general HSP under certain conditions. We study the special cases of dedekindian, dihedral and symmetric groups in that framework.
A group G is said to be simple, if it contains no other normal subgroups than {1} and G. Finite simple groups are the "building blocks" for all finite groups and their classification are given by a theorem of group theory. More precisely, the theorem states that the possibilities for a finite simple group are: Cyclic groups ℤ p for p prime.
Alternating groups A n for n ≥ 5.
Simple groups of Lie type. 26 sporadic simple groups.
For an arbitrary finite group G, a composition series is a sequence of subgroups of G such that each H i is a maximal normal subgroup of H i + 1 . The integer n is called the composition length, and is clearly O(log|G|). Each H i +1 H i is called a composition factor and is by definition a simple group. Any finite group has a composition series: informally, we can start with {1} ⊲ G and insert normal subgroup H i until we get a composition series. Moreover, the Jordan-Hölder theorem says that all the composition series of a group are equivalent i.e. they all have the same length and are made of the same composition factors (up to isomorphism and permutation).
The consequence of these two theorems is that we know how any finite group G is built. Let's see how they can be used to solve the general HSP. Suppose H is a subgroup hidden by f and N ⊲ G a normal subgroup. Thus, one research direction is to try to solve HSP over simple groups. We can also restrict in a first time to solvable groups (i.e. such that the composition factors are abelian, or more precisely cyclic groups of prime order) and use the HSP algorithm that we already have for the composition factors.
The second research direction is to find reduction methods. We have already seen many times the following subgroup and quotient reduction:

Definition 6.2 (subgroup reduction, quotient reduction)
Let G, H , f be a HSP problem. We have the following reductions: Subgroup reduction: Suppose we can find in polynomial time a subgroup G 1 ⊆ G that contains H and an isomorphism G 2 ≅ g G 1 such that g has polynomial complexity. The oracle f ∘g over G 2 hides the group g -1 (H ). A solution to HSP over G 2 gives a set of generators u 1 , …, u n for g -1 (H ) and so a set of generators Note that the theorem 6.1 uses a combination of generalized versions of these reduction methods with N = G 1 = H 1 and without the constraints H ⊆ G 1 = N and N = H 1 ⊆ H . For the subgroup reduction part, the oracle does not need to be changed and will hide the expected group H ∩ N instead. However, it is less clear how to build the oracle for the quotient reduction part because two elements g 1 , g 2 ∈ G that belong to the same class in G N may not belong to the same preimage of f . Note that if H ≠ G, then it is always included in a maximal subgroup G 1 and thus subgroup reduction is always possible. This is particularly interesting in the case of the simple group, where quotient reduction is not possible. However, the complete description of maximal groups is only known for some groups.

Theorem 6.3 (iterative maximal subgroup reduction)
We have a solution to HSP over a group G if we have an algorithm to find a maximal subgroup G 1 containing H , apply subgroup reduction to G 1 and repeat the operation inductively. We stop when we no longer can find a maximal subgroup i.e. H = G. □ Let's consider the groups we have previously studied. First, in the Dedekindian HSP we work on a group whose subgroups are all normal. An algorithm is given in appendix F for the particular case of abelian group, but should also work for hamiltonian ones. The idea is to use Weak Fourier Sampling to get a sequence of subgroups of G containing H that become smaller and smaller. Because all groups are normal, we have a subsequence of a composition series: In that case, H G k is the trivial group and H ∩ G k = G k , so the algorithm of theorem 6.1 is really only using subgroup reduction. The abelian algorithm of appendix F also shows the importance of "nice" description of groups, such that the one provided by black box groups. In our definition 3.3 of the hidden subgroup problem, we say that we want to determine the hidden subgroup H and definition 3.5 asks for a set of generating elements. However in the abelian case, to be able to iterate the reductions we use at each step a direct ⟩ so that we can have the polynomial-time isomorphism mentioned in definition 6.2 and thus efficient oracles on the new groups.
Another interesting case is the reduction we have made so far for the dihedral group. The possible composition series are given in figure 6.1, where the dots correspond to composition series of the isomorphic groups indicated. where a is a divisor of N and d ≡ b mod(a). In that case, we have H a, b ≅ D N a and the new hidden subgroup is generated by a slope (q, 1) where q is the quotient of the division of d by a. We repeat subgroup reduction until we have determined entirely d and again we need only O(log|G|) reduction steps. Note that variations of this kind are proposed in Kuperberg's paper [Kup2003]. The key step for solving DHSP is thus to determine the remainder of d modulo a divisor a of N. For N = 2 n the procedure will be to determine the bits of d, from the least to the most significant ones. Finally, we recover the techniques that have been used so far. Note that the dihedral is solvable, so we already have a solution for the simple groups involved. Hence a solution to DHSP will either be an algorithm to find the parity of d (or any other remainder of d) or by new reduction techniques.
There is an alternative way to see the first quotient reduction by H r . Using theorem 9.9 one can see that, except in the degenerated cases H = H 2, d , the intersection of the kernels of the representations measured by a Weak Fourier Sampling over the dihedral group is exactly H r . Actually, we know that in general the Weak Fourier Sampling gives the largest normal subgroup of G which is included in H . Hence a general method is to apply Weak Fourier Sampling to find that subgroup and then use a quotient reduction. In the quotient group, we can still repeat this procedure. After O(log|G|) reductions of this kind, we will not be able to reduce the underlying group any further: the largest hidden subgroup of H normal in G is the trivial group {1}. If this group is also H , then we can determine the original hidden subgroup. Otherwise, H is not necessarily simple and we need to use subgroup reduction or other methods as in the case of the dihedral group. We have:

Proposition 6.4 (iterative quotient reduction)
A repetition of quotient reduction using the largest normal subgroup included in the hidden subgroup leads to a hidden subgroup problem where the reduced hidden subgroup H does not contain any non-trivial normal subgroup. If the reduced hidden subgroup is trivial then we can solve HSP using this method. □ Finally, let's consider the symmetric group S n . We may discard small values of n and assume n ≥ 5. In that case, {Id} ⊲ A n ⊲ S n is a composition series and in particular S n is not solvable. Moreover, consider the case of our reduction of rigid graph isomorphism problem in S 2n , where H is trivial or H = ⟨σ⟩ for some involution σ = ( φ, φ − 1 ) s n with signature ε(σ) = (−1) n . If we split the HSP problem between S 2n A 2n ≅ ℤ 2 and A 2n , we have two cases: n is even, so H ∩ A 2n = H ⊆ A 2n and all the information is in A 2n . However, this group is simple so we can not reduce it any further using quotient groups.
n is odd, so H ∩ A 2n = {Id} and all the information is in S 2n A 2n ≅ ℤ 2 . The HSP is trivial on this group and all the hardness consists in the construction of an oracle.
Actually, we have even seen in the previous section that we can reduce the rigid graph isomorphism problem to the simple group A 2n .

Possible algorithm for the general HSP
Input: The group G the oracle f . Output: The hidden subgroup H .
Use at most k coset measurements (remark 4.10) to determine whether H = G with probability of success at least 1 − 2 k or H is a proper subgroup of G with certainty. In the former case, return G.

1.
If we have an efficient HSP algorithm over G, execute it and return the subgroup H found. 2.
If G is simple, determine a maximal subgroup G ' containing H , and use it to apply subgroup reduction.
Call this algorithm recursively and return H .

3.
Apply Weak Fourier Sampling to determine a maximal normal subgroup H ' of G included in H . If H ' is non-trivial, use it to apply quotient reduction. Call this algorithm recursively and return H .

4.
Otherwise, find a way to reduce the problem by using a normal subgroup {1} ⊈ N ⊊ G, subgroup reduction or any other methods... Call this algorithm recursively and return H . 5.

Figure 6.2
As a conclusion of this section, we have seen a general approach to the HSP based on solution to the simple HSP and various reduction methods. A possible algorithm is proposed in figure 6.2. For the problems related to the dihedral and symmetric groups, it seems however that all the known reductions have already been used.

Known solutions to the Hidden Subgroup Problem
In this section, we review miscellaneous solutions and techniques obtained for non-abelian groups. The HSP table of appendix A completes this section with a good overview of the state of the art.
The first non-abelian HSP considered was DHSP. Although still unsolved, many methods were introduced, so let's recall them: enumerating all the subgroups of G: they can all be described by two parameters d < r.
using the abelian Fourier Sampling on abelian subgroups: working on ℤ N ×{0} allows to find r. using quotient reduction: using the normal subgroup H r yields the standard reduction for DHSP.
applying the abelian Fourier Sampling on the whole group, viewed as a cartesian product: this produces coset states and reduces the problem to DCP. using group reduction: as we have seen in previous section, determining the remainder of d modulo a divisor a of N is like moving to a subgroup isomorphic to D N a . pipeline of coset states: this allows to determine d in subexponential time.
pretty good measurement: we consider the tensor product of k coset states ρ d ⊗k and use the optimal measurement to identify it among an equiprobable repartition of d ∈ ℤ N . If it is efficiently implementable for some k > log(N) then we can find d.
superposition of many oracle values: a new approach to determine d proposed in appendix G.
We have presented in details Fourier Sampling based on Fourier Transform over finite groups. It is a natural and elegant extension of the abelian case and was presented as a promising method in the review paper of Lomont [Lom2004]. The non-abelian Fourier Transform has been used as a key element for the Dedekindian HSP [HalRusTa-2000], ℤ 2 n ≀ ℤ 2 [RötBet1998], ℤ 3 ⋊ φ ℤ 2 n [GriSchVaz2000], the affine group Aff(1, p) as well as some particular cases of q-hedral groups [MooEtAl2005]. More recently it has been used to solve the Weyl-Heisenberg group [KroRöt2008] and to find 1-point stabilizer of some finite Lie groups [DenMooRus2008]. However, most efficient non-abelian HSP algorithms currently known do not require it and we know that it would not work for all groups. Again, we recall the methods: Weak Fourier Sampling to find normal subgroups or more generally the largest normal subgroup of G contained in H . As previously said, it is H r for the dihedral group (except for H = H 2, d ) and so it is an alternative way to determine r. Strong Fourier Sampling. It was proved in [MooEtAl2005] that it helps to solve some HSPs on which the weak version fails. Weak Fourier Sampling over subgroups. They are used in the extensions proposed in [GriSchVaz2000] and [Gav2004].
The other fundamental methods are given by black box results and we refer to [Lom2004] for a review. Recall that the degree of a group G is defined to be the smallest integer k > 0 such that there is a one-to-one homomorphism φ : G → S k . For example, we have k ≤ |G| by Cayley's theorem, k = p for a cyclic group G = ℤ p of prime order and more generally k = ∑ i = 1 m |A i | for an abelian group with decomposition A = A 1 × A 2 ×…× A m where each A i is cyclic of prime order. We have seen in previous section that every group has a composition series and we define:

Definition 6.5 (nu of G)
For any group G, ν(G) > 0 is the smallest positive integer bounding the degrees of the nonabelian composition factors. ◇ In particular, if G is solvable all the composition factors are abelian (and even cyclic) so we have ν(G) = 1.
In general, we will be interested in groups for which ν(G) = poly(log|G|). Actually, an extension of the second point is given in [MooEtAl2005].
Assume that G 1 is of size polynomial in log|G 2 | and that we have an efficient HSP algorithm for G 2 , then we also have an efficient HSP algorithm for G.
Unfortunately, this construction can not be iterated more than a constant number of times whereas we would like to repeat this a polynomial number of time for the algorithm of figure 6.2. This extension was used in [DenMooRus2008] to solve some particular cases of Aff(1, p m ). Note that the particular case of the commutator is G 1 = G ' , G 2 is the abelianization of G, to which we can apply the abelian HSP and we have |G 1 | = poly(log|G|) = poly(log|G 1 |, log|G 2 |) = poly(log|G 2 |).
Inui and Le Gall studied the case ℤ p n ⋊ φ ℤ q for p, q prime [InuLeG2004] and gave a complete classification.
One of the class contains groups isomorphic to ℤ p n ⋊ φ ℤ p (p n ≠ 2 2 and φ(b)(a) = a ( p n − 1 + 1 ) b ) which they solved using enumeration of subgroups and blackbox techniques. Chi, Kim and Lee [ChiKimLee2006] noted that the algorithm also works for some groups ℤ 2 p n ⋊ φ ℤ p and extended the algorithm to the class ℤ N ⋊ φ ℤ p under some conditions. The idea is to use a factorization of N to factor out the group and then apply Inui and Le Gall's algorithm. Using a similar approach, Cosme and Portugal [CosPor2007] solved some HSPs over ℤ N ⋊ φ ℤ p 2 . Inui and Le Gall also proposed a different approach for some cases of ℤ p m n ⋊ φ ℤ p , based on blackbox techniques [InuLeG2004].
A general proposal for the semi-direct products A⋊ φ ℤ p for some abelian group A and p prime is made in [BacChiDam2005bis]. The first step is similar to the reduction of the dihedral HSP: you use the abelian HSP algorithm over A to find H 1 = H ∩ (A×{0}) and use a "quotient reduction" (H 1 may not be normal, but they find a way to workaround that issue). This reduces the problem to a semi-direct product A 2 ⋊ φ ℤ N with A 2 a subgroup of A. The hidden subgroup is either trivial or the subgroup of size N generated by (d, 1) for some d ∈ A 2 . Next, we use the pretty good measurement with a product of m coset states and reduce the problem to finding equations of a system with m unknowns and some parameters uniformly chosen at random. The authors called it the matrix sum problem and solved it for various groups A. In particular, they obtained efficient HSP for G = ℤ p k ⋊ φ ℤ p (p prime, k constant) and ℤ N ⋊ φ ℤ q ( N q = poly(log N) and q prime).
More blackbox techniques have also been developed. Using the hidden shift problem, the HSP over some semi-direct products ℤ p k n ⋊ φ ℤ 2 was solved in [FriEtAl2002]. They also introduced orbit coset and orbit superposition problems and use it to solve HSP over some solvable groups. More precisely, they defined:

Definition 6.6 (smoothly solvable)
An abelian group is smoothly solvable if it can be decomposed into the direct product of a subgroup of bounded exponent and a subgroup of polylogarithmic size. A solvable group is smoothly solvable if its derived series is of bounded length and has smoothly abelian factor groups. ◇ They obtained: HSP can be solved in solvable groups having smoothly solvable commutator subgroups Ivanyos, Sanselme, Santha solved HSP over extraspecial groups [IvaSanSan2007] and later extended their result to nil-2 groups [IvaSanSan2007bis] i.e. such that [[G, G], G] = {1}. They first used the concept of hiding procedure defined in [FriEtAl2002] which generalizes the hiding oracle f : hiding procedure for a subgroup H of G: for every g 1 , …, g n ∈ G, given the input |g 1 ⟩|g 2 ⟩…|g N ⟩|0⟩ it outputs The abelian HSP algorithm still works when the oracle is replaced by such a procedure. Then, they reduced the HSP over nil-2 groups to those having exponent p. They showed that in that case we can find a hidden subgroup H if we have a hiding procedure for H [G, G] and succeeded in constructing such a hiding procedure.
Finally, note that all the positive results previously mentioned in this section work for groups which are in some sense almost abelian. This is the case for the extensions of the Dedekindian HSP which work for groups with a large amount of normal subgroups, of the semi-directs product of abelian groups G = A⋊ B which can be broken down into A ≅ A×{0} ⊲ G and G A×{0} = {0}× B ≅ B. More generally, the results obtained from the black box methods break down the groups into abelian pieces through a normal series. However, it does not seem possible to apply this method for groups which contain a non-cyclic simple group in their composition series such that A n or S n . One attempt in that direction is [DenMooRus2008], with algorithms to find some hidden subgroups over the simple group PGL(2, p m ) and other related finite groups of Lie type. More precisely, we have a group G acting on a set S and have the promise that H is a one point stabilizer G s , s ∈ S. Their idea is to restrict to one of this stabilizer G s 0 , apply a Strong Fourier Sampling on this group to determine G s 0 ∩ G s and deduce s. However to make this work, they need some additional hypotheses that do not seem to be satisfied by many groups. Moreover, it is still open whether we can find an efficient HSP taking into account the other subgroups. This may be hard, for example some maximal subgroups of PGL(2, p m ) are dihedral groups for which we do not have solutions yet.

The Hidden Subgroup Problem and Efficient Algorithms
In this section we discuss how HSP is related to some efficient algorithms with concrete applications. We have already mentioned in the first part of this report how particular abelian HSP have been used by Shor to make efficient algorithms for factoring numbers and computing discrete logarithms. In appendix D, we give a reduction of Monotone 1-in-3 3SAT to GapCVP ∞ where one step uses the abelian HSP algorithm to find the kernel of a group homomorphism. Although the quantum part is not actually needed here, this provides another example where a HSP can be used. Hallgren solved particular cases of HSP over the infinite abelian groups ℝ and ℝ r [Hal2002], [Hal2005]. This allowed him to design polynomial-time algorithms for finding solutions (x, y) ∈ ℤ 2 to Pell's equation x 2 − d y 2 = 0 (where d is a positive non-square integer) to which the factoring problem reduces. He also solved many important number fields problems.
The two non-abelian cases always mentioned are dihedral and symmetric groups. The HSP over these groups (or their variants: generalized dihedral HSP, alternating HSP etc) is expected to solve a lattice problem used in cryptography and the graph isomorphism problem. However, the first application requires the dihedral HSP to be solved by coset sampling while the second looks like out of the scope of all the techniques currently known. Hence, there is another point of view which consists in building cryptographic tools assuming the hardness of the HSP. For example, a classical one-way function is proposed in [MooRusVaz2007] and is at least as hard to invert as solving the Graph Isomorphism Problem. Also, inverting the function reduces to HSP over GL(n, q) which is believed to be hard, given the negative results on its subgroup S n .   [Dam1988]. The authors of [DamHalIp2002] solved the shifted Legendre symbol problem as well as other related hidden shift problems. They indicate that they can break certain cryptosystems by a reduction to the shifted Legendre symbol problem. They say that these cryptosystems can also be broken by Shor's algorithm, but the two attacks on the cryptosystems appear to use completely different ideas. Hence this shifted Legendre symbol problem shows another relation between cryptosystems and HSP: it can be reduced to the HSP over G = D p (under certain assumptions) and as we will see in the next section it can also be reduced to a HSP over G = ℤ p ≀ ℤ 2 .
Recall that in Grover's algorithm we have N elements indexed from 0 to N − 1, an oracle φ : {0, …, N − 1} → {0, 1} taking the value 1 for M ≤ N 2 elements and we want to find one of these elements. Here, we take M = 1 and denote j 0 the element that satisfies φ ( j 0) = 1. Lomonaco and Kauffman proposed a comparaison between this case and Shor's algorithm [LomKau2006]. They described Shor's algorithm as an infinite HSP over ℤ with a subgroup p ℤ hidden by an oracle f . They defined a "push" method, used to reduce the problem to some HSP over ℤ q (for some integer q) and a new oracle f. Next, they considered the HSP over S N with hidden subgroup H = Stab j 0 of permutations stabilizing j 0 . They used the subgroup Stab 0 and their "push" method to get a new problem where the oracle f̃= φ is just Grover's oracle. However, from the definition of a "push" given of their paper, it is not obvious that their algorithm is applyable since we are loosing the group structure. They say that the definitions of the "push" and Fourier Sampling can be generalized but still the algorithm fails to provide a solution [Lom2010] . Anyway, Grover's algorithm can be interpreted as an efficient HSP algorithm for otherwise we would have an exponential speedup instead of the known optimal quadratic speedup [Zal1997]. Here, we are working over G = S N and an efficient algorithm is expected to be polynomial in N log N. With the promise H = Stab j 0 , we only need to find the j satisfying f ( σ j) = f (Id) where we use the cycle σ j = (0,1, …, j − 1, j + 1, …, N − 1) moving all elements but j. This can be done in O(N) time classically (brute-force search) or even in O ( N √ ) time quantumly (Grover's algorithm) and thus the HSP in that case is efficiently solvable. This was actually noted in [DenMooRus2008], where efficient algorithms are provided for 1-point stabilizer subgroups of SL(2, q), PGL(2, q), PSL(2, q). Interestingly, the big picture of their algorithm is similar to the "push" method above: rather than working over the whole group, they reduce the sampling to a particular 1-point stabilizer for which they can apply the non-abelian Fourier Sampling. Note that the size (or number of 1-point stabilizers) of these three groups is polynomial in q and the efficient HSP algorithm polynomial in log q. Thus, the following open question: can we interpret these algorithms as concrete search problems with an exponentially fast solution?

Variants and Extensions
In this section, we present various problems related to the Hidden Subgroup Problem. Indeed, there have been several proposals to interpret the efficient algorithms of the first part of this report, other than the abelian HSP. New problems have been defined and solved for some particular cases. These problems are often related to HSP and their study has sometimes lead to solutions to instances of HSP. More generally, it is expected that these problems will also provide new quantum algorithms exponentially faster than the classical ones.
One extension is to allow G to be an infinite group: it was actually already the case for the original Shor's algorithm which reduces the HSP over the infinite group G = ℤ to the HSP over some cyclic group ℤ q , for some q large enough. In general, the abelian HSP algorithm works for any finitely generated abelian group such that G = ℤ n . In order to solve various problem, Hallgren had to introduce HSP over ℝ and ℝ r [Hal2002], [Hal2005]. The HSP he considered is finding a hidden subgroup H = ⟨τ⟩ of ℝ generated by an irrational τ (or said otherwise, determining an irrational period τ of a function f ) as well as finding a hidden lattice H of ℝ r . In both cases, the rough idea is to construct a computable discretized version of the oracle f and show that we can approximate generators for H .
Other extensions to HSP have been proposed in three different papers, but they do not seem to have subsequently been studied. One proposal is the Hidden Subhypergroup Problem [AmiKalRoo2006] where the group G is generalized to an hypergroup i.e. the product of two elements is a subset of G rather than a single element. A second proposal is the Hidden Symmetries Problem [SchUnr2003] where we generalize the condition that f is constant on each left coset to a more general property ∀ x ∈ G, V ( f (x), f (U (x))). For example, saying that f hides H is simply taking V to be the equality and U (x) = x H . The third proposal is the Hidden Covering Space Problem [OsbSev2004] which generalizes the version of HSP given as a coset sampling black-box. This proposal involves topological spaces and is a bit more complicated to define. We will just say that we consider Cayley graph of groups endowed with their natural topology.
A variation that has been extensively studied is the Hidden Shift Problem. In this problem, we have two injective functions f 0 , f 1 on G satisfying ∀ x ∈ G, f 1 (x) = f 0 (x + s) for some s ∈ G. The purpose is to determine the hidden shift s. The problem was solved for many cases, including smoothly solvable groups [FriEtAl2002], bent functions [Röt2008], functions close to a quadratic [Röt2009], Legendre symbol [DamHalIp2002] as well as more general multiplicative characters on finite fields and on ideals ℤ n ℤ [DamHalIp2002]. When G is abelian, the problem is equivalent to HSP over the generalized dihedral group G⋊ℤ N . In particular, for G = ℤ N the problem is equivalent to DHSP. A decision version is considered in [ChiWoc2005]: either a shift s exists or the images of f 0 , f 1 are disjoint. We are asked to determine in which case we are. A solution to this decision version for the symmetric group G = S n would provide an efficient algorithm for the rigid graph isomorphism problem. A Generalized Hidden Shift Problem is considered in [ChiDam2005] and solve for the cyclic group G = ℤ N under certain conditions. The generalization consists in having M injective functions f 0 , …, f M − 1 satisfying ∀ x ∈ G, f i (x) = f 0 (x + is). Note that the generalized hidden shift problem reduces to HSP over the wreath product G ≀ ℤ M [FenZha2006]. Hence, the two solutions to the hidden shift problem from Rötteler mentioned above are particular case of G = ℤ 2 n which is solved from the efficient algorithm he obtained with Beth [RötBet1998]. When the functions f 0 , f 1 are not injective, the set of elements s ∈ G satisfying the shift equality can be proved to be a coset of some subgroup H [DamHalIp2002]. Finding this set is then called the Hidden Coset Problem. It turns out that this problem is actually polynomial-time equivalent to HSP [FenZha2006]. If H is normal, we can work in the quotient group G H and reduce the problem to the hidden shift To solve some HSP instances, Friedl et al. [FriEtAl2002] used several HSP-related problems. In addition to the Hidden Shift Problem discussed above (which is called hidden translation in their paper), they introduced the Hidden Stabilizer Problem, Orbit Coset Problem, and Orbit Superposition Problem. For the first one, we have a group G acting on a set of pairwise orthogonal quantum states. Given such a state we are asked to find its stabilizer subgroup. The second one is a generalization: given two states |Ψ 0 ⟩ and |Ψ 1 ⟩ we have to answer whether the intersection of their orbits is empty or find an element g ∈ G sending |Ψ 0 ⟩ to |Ψ 1 ⟩ as well as the stabilizer subgroup of |Ψ 1 ⟩. One interesting feature of Orbit Coset Problem on a group G is the following self-reductibility property: if N is a solvable normal subgroup of G, then the problem reduces to the Orbit Coset Problem on G N and on subgroups of N. Notice that such a property would be really appreciated for HSP to design an algorithm similar to the one of figure 6.2. Finally, the Orbit Superposition Problem asks to create the uniform superposition over the orbit of a given state |Ψ ⟩. For solvable groups, it reduces to Orbit Coset Problem. Again, in [FenZha2006] it is proved that Orbit Coset is polynomial-time equivalent to the Hidden Subgroup Problem when we allow the oracle f to be a quantum function.
As many other problems, decision and search versions of HSP have also been imagined. [FenZha2006] defines HSP D to be the problem of deciding whether H is trivial and HSP S to be the problem of findind a nontrivial element of H , if there is one. As we have previously seen, this is of particular importance for the dihedral and symmetric HSP. In the paper, they give a reduction of HSP to HSP D for the dihedral group (under certain conditions) and a polynomial-time equivalence between HSP S and HSP D for permutation groups. The latter equivalence suggests that the problem is hard, since we have this property for problems considered to be difficult such that NP-complete or graph isomorphism. Another proposal for a decision version of HSP is the Hidden Subgroup Test Function where we are given G, H , as well as a function f on G and want to decide whether the function hides the subgroup H . In [AblVas2009], the function f is encoded as a particular "input sequence". Similarly in [FriEtAl2002bis], the Large Period Problem is studied: we are given G, a subgroup K and a function f . We want to decide whether K is a proper superset of some subgroup H ⊆ G hidden by f . The problem is solved for abelian subgroups. The paper also defines the Common Coset Range Problem: given H ⊆ G and two functions f 0 , f 1 on G do we have the equality ∀ x ∈ G, f 1 (x H ) = f 0 (x H )? Again, the problem is solved for some particular cases.
Let's consider now the case of the abelian HSP dealing with the vector space G = F q m over the finite field F q , which is studied in [ChiSchVaz2007]. some fixed unknown permutation π of F q . The Hidden Polynomial Problem is to determine the polynomial P whose degree is still bounded, but we now allow this degree to be greater than 1. Similarly to the case of the hyperplane H , we assume that the constant term is P(0) = 0, for otherwise that term can not be determined, since π is arbitrary. The problem can also be viewed as finding the hidden hypersurface defined by the equation P(x) = 0 and the cosets are replaced by level hypersurfaces (defined by equations P(x) = k). One special case is when the polynomial is of the form P(x) = x m − Q(x 1 , …, x m− 1 ) i.e. the hidden hypersurface is defined by the parametric equation x m = Q(x 1 , …, x m− 1 ). In that case, the level hypersurfaces are just obtained by translating along the x m -axis. This problem, called Hidden Polynomial Function Graph Problem is considered in [DecWoc2007], [DecDraWoc2007] and solved for quadratic and cubic polynomial Q.
The authors of [ChiSchVaz2007] also consider other hidden structure problems on G = F q m . They define the Hidden Radius Problem: determine an unknown radius r given a blackbox that outputs superposition over the points of a sphere of radius r whose center is chosen uniformly at random. Similarly they define the Hidden Flat of Center: determine a flat given a blackbox that outputs superposition over unit sphere whose center is chosen uniformly at random in the hidden flat. They give a partial solution to the former and a complete solution to the latter. Other algorithms of this kind are given in [Mon2008] for the group G = {0, 1} n . All these problems are included in the more general category of Hidden Shifted Subset Problems. We have a group G, a subset of elements S and a subset of shifts T the black box outputs uniform superposition of element over the set S + t for a t ∈ T chosen uniformly at random. The purpose is to determine some property of S or T . To compare their power with the one of a classical computer, we would like an approach similar to HSP where we just have an oracle f whose preimages are the possible superpositions output by the black box. This does not seem possible in the general case, since the superpositions considered may intersect but some workarounds are used for the particular problems mentioned above.

Conclusion
In this report we have studied the Hidden Subgroup Problem, whose solution for various groups is expected to provide new efficient quantum algorithms. In a first part, we have reviewed the classical efficient Quantum algorithms of Simon and Shor and identified their main features. We have introduced the Hidden Subgroup Problem and showed how the previous algorithms can be defined in that framework.
In a second part, we have been interested in the standard method based on coset sampling. We have presented the well-known solution to the abelian case which includes the algorithms seen in the first part. We have described precisely a natural extension to the non-abelian case, by defining a Quantum Fourier Transform over finite groups as well as Weak/Strong Fourier Sampling. We have shown that Weak Fourier Sampling is able to find normal hidden subgroups and thus provides a solution to HSP over dedekindian groups. We have mentioned some extensions when the group is, in some sense, not too far from a dedekindian group. However, the Weak Fourier Sampling can not distinguish conjugate groups and thus it is not applyable to an arbitrary group.
In a third part, we have turned our attention to the dihedral and symmetric hidden subgroup problems. We have given a complete presentation of the structure of the dihedral group and recalled the reduction of the dihedral HSP to the search of a hidden slope d. We have presented Kupenberg's subexponential algorithm to find this slope and mentioned the results about the optimal measurement for dihedral coset sampling. We have studied Regev's algorithm for the uniqueSVP and noticed that it can be modified to work for some generalized dihedral groups and "recursive" coset sampling. We have also shown that the approximation factor obtained for the uniqueSVP is strongly related to the degree of the polynomial bounding the complexity of the coset sampling algorithm used. Finally, we have presented the classical reduction from graph isomorphism to symmetric hidden subgroup problems but have also recalled the negative results on the symmetric group: we need at least a linear number of entangled coset states at once but using an algorithm similar to Kupenberg's one does not help.
In the fourth and last part, we have considered the general HSP. We have suggested a general approach to the hidden subgroup problem based on the mathematical description of finite groups. We have shown that we could reduce the general case to a solution over simple groups and construction of some efficient oracles. These two points are precisely where we are stuck on for dihedral and symmetric groups. However, several efficient algorithms have been discovered for other non-abelian groups. We have given an overview of these solutions which are essentially with respect to "almost abelian" groups in some sense or the other. We have described some efficient algorithms with concrete application, including applications in cryptography, which are related to the hidden subgroup problem. Finally, we have mentioned variants and extensions to the HSP which have been solved for some particular cases and are expected to yield new efficient quantum algorithms.
As a conclusion, we have provided a good overview of the hidden subgroup problem going from its origin to the state of the art as of 2010. We have also brought some contributions to the topic. While the general problem still remains difficult, we hope that our work will help people to have a better understanding of the subject and guide them toward some research directions.
give an indication of their magnitudes with respect to the size of the group: capital letters N, M, N i are O(|G|), minuscule letters n, m are O (log|G|) and k is a constant O(1). When some homomorphisms φ used for a semi-direct product are explicitly given, it means that they do not cover all the possibilities unless otherwise specified.
Note: some notions and techniques are defined elsewhere in this report. For blackbox groups, this includes unique encoding and input size (definition 3.7), v(G) (definition 6.5) and smoothly solvable (definition 6.6).

Name Description Examples and applications Methods and remarks References
Cyclic HSP To get the uniqueSVP algorithm, it is enough to consider N = 2 4n Semidirect HSP Polynomial in n, log p, log q All these semi-direct products a(φ(1)(1)) b for all (a, b) ∈ G Moreover, they belong to one of these disjoint classes: n ≥ 1 and q | p − 1 1.
For class 4: enumeration of subgroups, blackbox methods, pretty good measurement See [InuLeG2004] for the classification Class 1 solved when p n q = poly(n, log p) in [BacChiDam2005bis] Class 4 solved in [InuLeG2004] Class 5 solved by abelian HSP = a ( t p n −1 + 1 ) b , p odd and 0 < t < p (these are the only possible non-trivial semi-direct product) Polynomial in n, log p enumeration of subgroups, blackbox methods. enumeration of subgroups, blackbox methods.

Solved in [CosPor2007]
Name Description

Examples and applications Methods and remarks References
Polynomial in log N , log p Semidirect HSP  a, b) = τ c (a, b) and τ permutes the two coordinates.

Polynomial in n
Fourier Sampling over abelian subgroup, Weak Fourier Sampling Solved in [RötBet1998] Semidirect HSP See also [IvaSanSan2007] for extraspecial HSP and [KroRöt2008] for Weyl-Heisenberg HSP

Name Description
Examples and applications Methods and remarks References a ∈ A n /2 is an isomorphism between the two graphs and σ is the product of transpositions Unsolved See this report for a reduction of the graph isomorphism problem for rigid graphs Wreath HSP See also some particular cases for n = 1 in [DenMooRus2008] Lie HSP G is a finite Lie group. Cyclic groups ℤ p for p prime.

1.
Alternating groups A n for n ≥ 5.

2.
Simple groups of Lie type.

Appendix B: Strong Fourier Sampling and the DHSP
In this section, we study the Fourier Sampling over the Dihedral group. We describe all the possible cases of the Strong Fourier Sampling, show the relation to the dihedral coset problem and in particular how to recover the algorithm of [EttHøy1998]. This similarity between Strong Fourier Sampling and dihedral coset sampling has already been noticed in [Kup2003] and [BacChiDam2005].

Lemma 9.1 (distribution probability of the Weak Fourier Sampling)
The distribution probability of the Weak Fourier Sampling over D N for the hidden subgroup H = ⟨(d, 1)⟩ is given by proof: This is a straightforward application of formula 4.20. For the 1-dimensional representations we have If N is odd, then we get no information on d.
If N is even, the best we can get is the parity of d. If M = poly(log (N)), this information is obtained with a success probability exponentially close to 0 i.e. less than K ⅇ − λ log( N ) for some constants K, λ > 0.
proof: If N is odd, the distribution probability is entirely independent of d and so it is impossible to get any information from the samplings. If N is even, the only thing we can know is whether d is even (if we measure ψ 2 ) or odd (if we measure ψ 3 ). If we have M(N) samplings this happens with probability P(N) We have: What about the Strong Fourier Sampling? To answer this question, we need to describe all possible matrix representations of irreducible 2-dimensional representations. We know at least one complete set of such representations given by τ k and we will use proposition 4.7. So we must enumerate all the unitary matrices of dimension 2:

Proposition 9.3 (unitary matrices of dimension 2)
The unitary matrices of dimension 2 are the matrices proof: First of all, such a matrix U is clearly hermitian since its columns are orthonormal. Now, suppose U U † . It is easy to get an explicit formula, as given in the following lemma.

Lemma 9.4
For any representation ρ such that ρ(d, 1) = U τ k (d, 1)U † for some unitary matrix U = u 11 u 12 proof: This is just a matrix product: where we have used the relation of orthogonality u 11 * u 12 + u 21 * u 22 = 0 in the last line. Finally Now, using proposition 9.3, we can simplify the expression of x, z above and get the corresponding probability P(ρ, ., j):
Conversely, it is easy to check that for the ρ k given at the end of the statement, we find the probability with the correct λ k , μ k . □ It is worth noting some facts about these distribution probabilities. As in the Weak Fourier Sampling ψ 0 , ψ 1 are useless. ψ 2 , ψ 3 give the parity of d, but since they are observed with exponentially small probability we can ignore them when designing an efficient algorithm based on Strong Fourier Sampling. The 2-dimensional irreducible representations have equal probability 1 2 N to be observed and for each of them we can spread the probability between the two columns. We have only two degrees of freeness to do that: deciding how much the probability of the two columns differ in the extremal cases (amplitude parameter λ k ) and moving this extremal cases (phase parameter α k ). Note that taking α k = 2π N kd ' allows to have control over d. Since each ρ k has very small probability to be measured, an efficient algorithm for DHSP needs to consider them as a whole (or at least to consider an exponential number of them). Some attempts are given in Appendix C and where we also give some hints on why the Strong Fourier Sampling approach is likely to fail. Note however, that using a particular basis, we recover the distribution of theorem 9.6 and so the algorithm on which it is based:

Proposition 9.7
Take λ = 1 and μ = − π in the theorem 9.6 (this corresponds to ρ(g) = H τ k (g)H ). Apply a Strong Fourier Sampling and return the following value: If ψ 0 is measured, return (0, 0) If ψ 2 or ψ 3 is measured (so in the case where N is even), return ( N 2 , 1 ) If ρ k , j is measured, then flip a coin (or measure an EPR state) to decide to return (k, j − 1) or (N − k, j − 1) Then the distribution probability of the returned value is the same as in formula 5.9.
proof: Let k ' denote the parameter in formula 5.9. In the degenerated case k ' = 0 (respectively k ' = N 2 ) (k ', 0) (respectively (k ', 1)) is returned with probability 1 N and (k ', 1) (respectively (k ', 0)) with probability 0. Since ψ 0 and ψ 2 ∪ ψ 3 happens both with probability 1 N , we get the same result by returning the values of the statement. Now, note that for any 0 < k ' < N 2 (i.e. N 2 < N − k ' < N), the probability to return (k ', j) is the same as the probability to return (N − k ', j) in formula 5.9. This is because cos 2 and similarly for sin. By theorem 9.6, the probability distribution of the Strong Fourier Sampling for the 2-dimensional ρ k is: so taking half these values and sharing between k or N − k we recover formula 5.9. □

Corollary 9.8 (Strong Fourier Sampling solves dihedral HSP)
It is possible to solve the HSP over D N using only a poly(log N) number of Strong Fourier Samplings (but an exponential post-processing) proof: use the previous proposition to simulate the distribution of formula 5.9 and apply the algorithm of Ettinger and Høyer. □ The previous corollary shows that to extract information, the Strong Fourier Sampling is indeed more powerful than the Weak Fourier Sampling. Another well-known fact (see [GriSchVaz2000]) is that a random choice for the basis of Strong Fourier Sampling is not helpful. Intuitively, this can be seen in the expression of theorem 9.6: with a uniform choice of the phase α k ∈ [0,2π) we are totally blurring the parameter d. A random approach could still be useful, for instance randomly choosing α k = 2π N k p for an even integer p leaves only the parity of d. Again, see Appendix C to get some arguments about why this is likely to fail.
proposition 5.2 indicates that solving DHSP by a Fourier Sampling over H = ⟨(d, 1)⟩ yields an algorithm in the most general case. However, it could be possible that the Fourier Sampling can not solve the case H = ⟨(d, 1)⟩ while still being able to find other hidden subgroups H . We could even hope that DHSP reduces to these subgroups. The next theorem clarify this: Theorem 9.9 (distribution probabilities of the Fourier Sampling) For The λ k , μ k can be obtained by the same change-of-basis as in theorem 9.6.
proof: The proof is very similar to the one of theorem 9.6 so we do not give all the detail here. One can  We conclude this section by showing the converse of proposition 9.7: the states generated by DCP allow to simulate any Strong Fourier Sampling. One consequence is that to solve DHSP, the Dihedral Coset Problem method is more general than Strong Fourier Sampling.

Proposition 9.11 (DCP simulates Strong Fourier Sampling)
Any Strong Fourier Sampling over the dihedral group can be simulated using the output of DCP.
proof: The DCP allows to produce states of the form formula 5.7. Applying a unitary gate of the form of proposition 9.3, we obtained (k, j) with probability: For any 0 < k < N 2 , we choose the same θ k , α k for k and N − k, in a way that we recover half the probability P ( ρ k , ., 2 − j ) of Strong Fourier Transform. If one of k, N − k is measured then we return ρ k , ., 2 − j. For k = 0, we choose arbitrary θ, α and we return ψ 0 if it is measured. Finally if N even and k = N 2 we choose α = 0 and θ = π 2 and return ψ 2 + j . □

Appendix C: Attempts to solve DHSP by Fourier Sampling
In this section, we describe several attempts to solve DHSP using a Strong Fourier Sampling. We restrict ourselves to the case H = H N , d = ⟨(d, 1)⟩ and use only 2-dimensional irreducible representations. As previously mentioned, we need to consider them as a whole since each of them as only a small probability to be observed.

Approximation of a trigonometric expression
A first idea is that the sum of the λ k cos ( 2π N kd + μ k ) can be expressed using trigonometric functions whose argument contains l = 2π N d. Trying various values of the parameters, we can obtain the values of l modulo 2π and so the value of d. This sum can be approximated by counting the number of observation (ρ k , ., 1) and so we can hope to get d with a small probability of error. More formally, we define X to be the random variable taking value 1 if a (ρ k , ., 1) is measured and 0 otherwise. This random variable is bounded in an interval of length 1 so we can apply Hoeffding's inequality: S = X 1 + X 2 + … + X m then for any t > 0, we have We start by trying to approximate the trigonometric expression tan ( l 2 ) : For i = 1, 2, we denote S i the random variable where we choose for all k λ k = 1 and μ k = (1 − i) π 2 = μ (i) . We ) is the sum we want to estimate. We let θ = ( M 2 + 1 ) l. By one oracle call, we can check that d ≠ 0 and in that case we have: so θ ≡ ± atan x 2 x 1 mod (2π). Reporting in the expression of x 1 , extracting tan l 2 and after simplification, we get d = ± N 2π f (x 1 , x 2 ) mod (N) where f (x 1 , x 2 ) = atan Then bounding the expression of the first partial derivatives of f on the ball B ε (x 1 , x 2 ) we finally use the Taylor formula to get | f (x 1 , ) . This is a rough bound, so assume we can do better, said the first partial derivative of f are bounded by a constant, and then replace the previous bound by O(ε). Then the error for N 2π f (x 1 , x 2 ) is O(ε N). We see that we must choose t in Hoeffding's inequality to be O ( ) if we want this error poly(log N). In that case d is reachable by calling the oracle around two bands of size poly(log N) with centers ± 1 2π f (x 1 + ε 1 , x 2 + ε 2 ). To summarize we see that, in addition to the technical bound on the first partial derivatives, there are two major difficulties in the previous algorithm: the leading coefficient 1 N in the expression of the probability makes the error of the trigonometric function Ω(N) and the coefficient 1 N inside the trigonometric function increases the error again to Ω ( N 2 ) . So we must at least make m = Ω ( N 2 ) Fourier Sampling if we want this error to be O(N), which is the worse we can tolerate. It seems that trying to extract d with this kind of approach is likely to fail.
Let's mention a way to get cos l and sin l with different parameters i.e. two get only one band rather than two. Take the two same values for μ k and lambda to be λ k = λ k for 0 < λ < 1. We get Using several values of λ we get system of linear equations with cos l, sin l among their unknowns (these unknowns are even related by trigonometric formulas, so we can reduce the number of λ needed to make the system invertible). We have not tried to bound the error but anyway the comment above on the two difficulties are still valid.

Randomized algorithm and parity of d
Rather than trying to approximate d, we try to make the sum of the λ k cos ( 2π N kd + μ k ) reveal the parity of d.
For simplicity, we assume N = 2 n for some n ≥ 2. We take λ k = 1 and randomize the algorithm by uniformly choosing at each sampling some value d ' and let μ k = 2π N k(2d '). The random variable X now takes the value 1 if (ρ k , ., 1) is measured for some odd k and 0 otherwise. If b is the parity of d, then we now have: So to distinguish whether δ b, 0 N is 0 or 1 N we need to take t = 1 2 N and so m = Ω ( N 2 ) . The detail of the calculation shows that the sum over p for the cosinus is nonzero and of value N 4 for only two values (namely 2q +d = 0, N 2 ). The factor 1 N reduces this value to 1 4 . However, if we want to test all the even values, we need to randomize q: this introduces a coefficient 1 N 2 and makes the difference between the cases odd/even exponentially small. So while randomizing allows to test more values, it also decreases the precision by the same order. As previously stated, a stronger randomization of μ k is likely to blur the parameter d and so make the information inaccessible.

Eliminating many values in one call
Once we have computed a = f (0, 0), then for each d ' ∈ ℤ N , we can check d ' = d by one call just by checking f (d ', 1) = a. In this section, we see how many values of d we can eliminate in one call. The idea is to choose λ k = 1 and μ k = − 2π N l k for some integer l k ∈ ℤ N . Suppose that d ' is such that cos ( 2π N (kd ' − l k ) ) = ± 1 then the repartition of the probability of ρ k is 1 2 N in one column and zero in the other. In that case, measuring ρ k , j eliminates all the d ' that satisfy P ( ρ k , ., j ) = 0. Note that the cosinus takes the value ±1 iff kd ≡ l k mod (N) or kd ≡ l k + N 2 mod (N). We now suppose N = 2 n for some n ≥ 2. Each 1 ≤ k ≤ 2 n − 1 − 1 can be written in a unique way as (2x k + 1)2 i k where 0 ≤ i k ≤ n − 1 and 0 ≤ x k ≤ 2 n − i k − 1 − 1 and conversely any such (i k , x k ) define a k in the expected domain. In binary decomposition, the number made with first n − i l − 1 bits is x k , the next bit is a 1 and the i k last bits are 0's. Clearly, we have gcd(k, N) = 2 i k . Because N 2 = 2 n − 1 is a multiple of 2 i k , the previous linear congruence have a solution iff l k = y k 2 i k for some 0 ≤ y k ≤ 2 n − i k − 1. Again, in binary decomposition, the number made with first n − i k bits of l k is y k and the i k last bits are 0's. Let r k , s k such that r k x k + s k 2 n − i k = 1 then the possible solutions are given by r k y k + λ2 n − i k (cos = 1) and r k ( y k + 2 n − 1− i k ) + λ2 n − i k (cos = -1) for 0 ≤ λ ≤ 2 i k −1. So measuring a representation ρ k allows to eliminate with certainty 2 i k values. For the 1-dimensional representation, measuring ψ 2 , ψ 3 eliminates 2 n − 1 possibilities and we get no information from ψ 0 , ψ 1 . As a consequence, in mean we can hope to eliminate with certainty in one call of Fourier Sampling: which is only poly(log(N)). So even in the ideal case where each call eliminates different values for d (for example we could hope to do so by choosing the l k in a clever way at each step), repeating this procedure a polynomial number of time will in mean only discard a poly(log(N)) number of values for d!

Appendix D: Reduction of Monotone 1-in-3 3SAT
In this section, we try to solve a version of the famous boolean satisfiability problem using an abelian HSP. The version considered is the monotone 1-in-3 3-SAT which is known to be NP-complete [Sch1978]. We obtain a reduction of monotone 1-in-3 3-SAT to a lattice problem called GapCVP ∞ using a quantum algorithm. Note however that a (classical) reduction of the subset sum problem to GapCVP 1 is already known [MicGol2002].
Moreover, in our algorithm, the HSP solution is only used to find generators for the kernel of a module homomorphism. However, there exists an efficient classical algorithm for this task [BucNei1996]. Nevertheless, it remains an illustration of general techniques based on HSP, where we use the kernel of a group homomorphism as the hidden subgroup.
Monotone one-in-three 3-SAT is a variant of the boolean satisfiability problem where each clause has only three literals and those literals are not negated. We want to find a truth value where only one literal is true in each clause. More formally:

Definition 11.1 (monotone one-in-three 3-SAT)
Let x 1 , …x n be boolean variables and consider N > 0 different clauses defined for all 0 ≤ i ≤ N − 1 by , where σ i ∈ n {1, 2, 3} is a combination . Define the predicate: The monotone 1-in-3 3-SAT is the following question: can we find a truth value for the x i 's such that exactly one literal is true in each clause (and hence the whole conjunction P is true). ◇ Note that N ≤ n 3 ( ) ≤ n 3 6 (N is at most the number of combination of three variables among n) and n ≤ 3N (each clause contains three variables). As a consequence, a polynomial algorithm for answering the question can be equivalently measured with N or n. Without loss of generality, we are now considering the case where the first clause is x 1 ∨ x 2 ∨ x 3 and the variables x 1 , x 2 , x 3 are not used in other clauses (we will see later why this is needed). We can add such a clause to any given predicate and this changes neither the answer nor the complexity of the initial problem.
Let us define the following function, which is going to be our oracle: Note that the expression of f is quite similar to the one of P if the variables are viewed as the coordinates of a vector x ∈ ℤ 2 n ⊆ ℤ 4 N n . This function allows to characterize all the solutions of the monotone 1-in-3 3-SAT via the following lemma:
proof: For such a vector x ∈ ℤ 2 n , the i-th sum over k is a value between 0 and 3 that indicates the number of literals that are true in the i-th clause. So f (x) can be viewed as a representation of a an integer between 0 to 4 N − 1 in base 4. Hence x is solution to the solution to the monotone 1-in-3 3-SAT iff each digit is 1 i.e. f (x) = 4 N − 1 3 . □ The following lemma is almost straightforward from the definition: f is a module homomorphism.
Similarly, We prove that f (ax) ≡ a f (x) mod ( 4 N ) for any a ∈ ℤ. The set of solutions of the monotone 1-in-3 3-SAT is exactly (p + H ) ∩ ℤ 2 n .
proof: We have f (g 1 ) = f (g 2 ) iff f (g 1 − g 2 ) = 0 iff g 1 − g 2 ∈ H . So f distinguishes cosets of H . The coset p + H corresponds to all the vectors that take the value f (p). By the restriction on the predicate P we discussed earlier, this value is exactly 4 N − 1 3 . By a previous lemma, the solutions are exactly the vectors of ℤ 2 n contained in this coset.

Remark 11.5
Given two subsets S 1 and S 2 of G and g ∈ G, the Coset Intersection Problem is to determine whether ⟨S 1 ⟩ and g⟨S 2 ⟩ have a non-empty intersection. However, the problem to decide whether (p + H ) ∩ ℤ 2 n ≠ ∅ does not exactly fit into that framework, because ℤ 2 n is not a subgroup of ℤ 4 N n . △ Using the efficient algorithm for abelian HSP, we get: There exists a quantum algorithm with a polynomial complexity in n that returns a set of generators for H with probability of success exponentially close to 1.
proof: H = Ker f is a subgroup of G = ℤ 4 N n . f distinguishes cosets of H and each call to f is an operation on integers of ⎡ ⎢ log ( 4 N ) ⎤ ⎥ = O(n) bits, so of polynomial complexity. G is an abelian group of order ( 4 N ) n , so we can apply the abelian HSP algorithm and find a set of t + log( | G | ) = t + 2nN vectors that generate H with probability 1 − 2 t (we can just take t = n). □

Remark 11.7
This kind of interpretation as a HSP works for any group homomorphism. Moreover, the kernel is always a normal subgroup, so G needs not be abelian (we already know an efficient HSP algorithm in that case). △

Remark 11.8
A classical and non-probabilistic algorithm already exists to find a set of generators for the kernel of a module homomorphism [BucNei1996]. The ring is R = ℤ 4 N and, similarly to the call to f , the elementary "ring operations" are polynomial in n. The whole procedure is polynomial. Hence quantum computation is not needed here. △ Rather than searching the solution in ℤ 2 n we are now looking into p + H and try to find a vector with only 0 and 1 coordinates. In some sense, we want to find a non-zero vector of smallest coordinates in p + H (i.e short for the infinity norm), although we need some technical modifications to make this statement exact (vectors with -1 coordinates are also short, we work modulo 4 N ...). Before to do that, let's define our lattice problem: Definition 11.9 (decisional closest vector problem) Let b 1 , …, b n ∈ ℚ n (or equivalently ℤ n ) a basis of ℝ n . The lattice corresponding to this basis is the set of all We can determine them by a Gaussian elimination they are integer (or rational, but since we get a 1-dimensional space of solutions, we can always make them integer). Hence the equality ∑ i = 1 n − 1 a i b i = 0 holds in ℤ 4 N and get that the a i 's are zeros.
As a consequence, we almost have a GapCVP ∞ version. What we want is to find a vector x in the lattice generated by b i such that p + x is a vector of ℤ 2 n (i.e. with only 0's and 1's entries). Equivalently, we want to determine the minimum distance (for the infinity norm) from a vector of the lattice to the the point v = − p + 1 2 . This distance is less or equal to d = 1 2 iff there is a solution to the monotone 1-in-3 3-SAT. We have two problems to overcome: the b i 's are not a basis of ℝ n and we want to allow the result modulo 4 N . First we complete the n − 1 vectors with a vector b n in order to get a basis. We can assume that b n is integer-valued and even that all his coefficients are of the form k i 4 N . Next, we move to ℝ 2n : we extend v, p and each vector b i with n zeros and for all 1 ≤ i ≤ n we define the vector b n + i that has only two nonzero entries: 4 N at position i and a rational ε at position n + i. Clearly, we have a basis of ℝ 2n that we now denote c j (p and v will denote either the initial vectors or those extended with zero, depending on the context). In matrix form, we can write: If we restrict ourselves to the n first coordinates, then the combination of the column of C is exactly the values of H modulo 4 N . The intuition is that if ε is small enough, we can almost stay in the subspace of vectors whose n last coordinates are zero, where the vector v lives and can ignore what is happening in the n last coordinates. This is exactly what the following lemma says:

Lemma 11.10
Let R > 0 be a rational and define B( There exists a rational ε > 0 such that proof: If r is the shortest distance of the GapCVP ∞ problem, we take ε > 0 any rational less than r R . For any x ∈ B(R) and 1 ≤ i ≤ n|x n + i − v n + i | = |u n + i ε − 0| = |u n

Remark 11.11
The proof of the previous lemma can be rewritten in a constructive way. For example we will choose an accurate R in the next theorem. We do not know the value of r. However, we are working with integer values in the n first coordinates so the minimum values for the |x i − v i | is at least 1 2 and thus r ≥ 1 2 . Hence we can take the rational ε = 1 2 R , which can be computed in polynomial time. △ We can now conclude this section: Theorem 11.12 There is some ε > 0, such that a solution to the initial monotone 1-in-3 3-SAT problem exists iff the answer to the GapCVP ∞ with that parameter is true. coordinates v i ± 1 2 are located, the |u j |'s for the n last coordinates need only be less than or equal to M b + 2. Hence we have for all the u j , |u j | ≤ R and thus x ∈ B(R). By the previous lemma, ‖v − x‖ ∞ = max 1 ≤ i ≤ n |x i − v i | = 1 2 = d, so the GapCVP ∞ problem is true.
Conversely, suppose the GapCVP ∞ problem is true. Then there is is a closest vector x = ∑ j = 1 2n u j c j such that d = 1 2 ≥ ‖v − x‖ ∞ ≥ max 1 ≤ i ≤ n |x i − v i |. In the n first coordinates, this means that for all i, |x i + p i − 1 2 | ≤ 1 2 and because we are only working with integer values, x i + p i is 0 or 1. Hence p i + ∑ j = 1 n − 1 u j b i j ≡ 0 or 1 modulo 4 N i.e. p + ∑ j = 1 n − 1 u j b j ∈ (p + H ) ∩ ℤ 2 n . In that case it is a solution to the monotone 1-in-3 3-SAT. □

Appendix E: Table of Lattice-based Cryptosystems
In this section, we sum up in a table the overview of lattice-based cryptosystems given in [MicReg2008]. The coefficient in uniqueSVP problems are according to [Reg2003bis]. We will list many other problems without defining them: Shortest Vector Problem (SVP), unique Shortest Vector Problem (uniqueSVP), Shortest Independent Vectors Problem (SIVP), Closest vector problem (CVP), Learning With Errors (LWE). Also, more assumptions are often made on these problems: particular structure of the lattice (e.g. uniqueSVP rather than SVP), approximate factors etc.
There is often a trade-off between efficient implementation and security insurance: adding assumptions may make the system more vulnerable but also more realizable in practice. An important feature of lattice-based cryptosystems is that a security proof, when we have one, is based on worst-case hardness rather than average-case hardness.

Appendix F: Variant for the Abelian HSP algorithm
In this section, we study an alternative algorithm for the abelian hidden subgroup problem. The idea is to use the information obtained after each call to move to a simpler Hidden Subgroup Problem, built on the original one. It does not generalize to arbitrary group, but is a good example of a subgroup reduction method.

Cyclic Hidden Subgroup Problem
We have already described an algorithm for the Cyclic HSP in the period-finding submodule of Shor's factoring algorithm. Recall that we do a constant number k of Weak Fourier Samplings on G = ℤ N in order to find a hidden subgroup H = d ℤ N for some 1 ≤ d ≤ N. For each sampling, we get a number λ N d for some λ ∈ {0, …d − 1}. Computing the greatest common divisor of these multiples gives N d with probability at least 1 − 2 − k 2 .
The idea of our algorithm is the following. If we compute the irreducible fraction of λ k N d , the denominator is a divisor a 1 of d. This gives H = d ℤ N ⊆ a 1 ℤ N ⊆ G = ℤ N and we can now work in the group a 1 ℤ N instead.
Repeating this several times, we get some a k ℤ N 's which are closer and closer to H . Said otherwise, a k becomes d.
More precisely, we define G 0 = G = ℤ N , H 0 = dℤ N and a 0 = 1. At each step k, we have another cyclic hidden subgroup problem: . Moreover, to build a oracle on G k = ℤ N k from the initial f , we define f k (x) = f (a k x). Now at the step k, applying a Weak Fourier Sampling over G k gives a λ k N k d k for some λ k ∈ {0, …, d k − 1}.
We compute the irreducible fraction proof: First, the probability of failure given that a k has reached d before the mth call is zero. Hence we have: P(a m ≠ d) = P(a m < d) = P(a m < d / ∀ k < m, a k < d)P((∀ k < m, a k < d)) + 0 ≤ P(a m < d / ∀ k < m, a k < d)  . Their algorithm uses the cyclic HSP to compute the orders t i k + 1 of a i k + 1 in poly(log|G|).
To conclude this section, note that the algorithm may also work for Hamiltonian HSP: it is easy to see that the G k 's will remain Dedekindian i.e. isomorphic to either an abelian or a hamiltonian group. The possible irreducible representations are described in [HalRusTa-2000]. However, we have not been able to figure out how to construct the isomorphism from the kernel equations. For more general groups, the H m obtained at the end will be the largest normal subgroup of G containing H , as noted in [GriSchVaz2000]. Thus we may need to continue the procedure, for example by using a quotient reduction as indicated in proposition 6.4.

Appendix G: Attempts to solve DHSP by superposition of oracle values
In this section, we try to solve the HSP over D N = ℤ N ⋊ φ ℤ 2 , reduced to the case H = ⟨(d, 1)⟩ for some d ∈ ℤ N . Contrary to all the other approaches proposed so far, we will not use coset states of the form 1 2 √ (|x⟩|0⟩ + |x + d⟩|1⟩) but superpositions over many oracle values. In particular, this approach will not a priori yield an efficient algorithm for polynomial uniqueSVP.

Finding the parity of d
First let's recall the classical inductive method to determine d. If M is a divisor of N, we let N ' = N M and write the euclidean division d = Md ' + r. If we are able to determine r in polynomial time, then we can define the oracle f '(x, y) = f (M x + r, y) for x ∈ ℤ N ' , y ∈ ℤ 2 and obtain a new dihedral HSP with hidden subgroup ⟨(d ', 1)⟩. Since the prime factorization has only O(log N) factors, we can repeat this inductive step to get an efficient algorithm. Of course, this is likely to be useful only when the factors are small, for otherwise it may be as much difficult to determine r as to determine the whole d. One interesting case is N = 2 n and M = 2: at each step, N remains a power of 2 and we only need to determine one digit of d. From the equality f (g(d, 1)) = f (g) we have the relation: In particular for j = r, we have the equality E 0 0 = E r 1 and so we can hope to get information on r by comparing the superposition over E 0 0 and those over E j 1 . We show that it is possible for M = 2, but it also works for any polynomial value by an obvious modification. In that case, the uniform superposition over E  (2i + b, 0) and measure the product state |ψ 0 ⟩|ϕ 0 ⟩ in the basis |x⟩|x⟩ x ∈ ℤ N , 1 2 √ (|x⟩|y⟩ + |x⟩|y⟩) x < y ∈ ℤ N , 1 2 √ (|x⟩|y⟩ − |x⟩|y⟩) x < y ∈ ℤ N . It turns out that this allows to distinguish the two cases: If r = 0, the product contains vectors with the same coordinates | f |x⟩|y⟩ + |x⟩|y⟩ x < y ∈ ℤ N and half to |x⟩|y⟩ − |x⟩|y⟩ x < y ∈ ℤ N .
Suppose that we have a procedure to create many states |ψ 0 ⟩ and |ϕ 0 ⟩. We measure a state in the space 1 2 √ (|x⟩|y⟩ − |x⟩|y⟩) x < y ∈ ℤ N with probability r 2 . So repeating the procedure a constant number of times allows to determine r with high probability! It is not however clear whether we can create the states |ψ 0 ⟩ and |ϕ 0 ⟩ efficiently. With the usual approach, we can start by creating a superposition over the elements (2i, b) and apply the gate U f . To remove the entanglement between a point and its image by f , we apply a Quantum Fourier Transform to the first coordinate and measure it. We get two random numbers j 1 , j 2 ∈ ℤ N ' as well as the states Note that we can actually ignore the phase factor in the second one. The desired result j 1 = j 2 = 0 only happens with exponentially small probability. Nonetheless, we can still apply the previous measurement. After a bit of calculation, we get the probabilities: If we repeat the procedure several times, we need to take the means over the choice of j 1 , j 2 ∈ ℤ N ' . By classical trigonometric identities, it is possible to write the sums of the first column 1 2 + S + o ( 1 N ' ) where S is a sum of cosinus. Unfortunately, evaluating S with a computer suggests that S = Θ ( 1 N ' ) . Hence, we can not distinguish the two cases with only a polynomial (in log N) number of samplings...

Finding an approximation of d
For convenience, we assume N = 4M and define N ' = 2M = N 2 . In this section, we consider for a ∈ ℤ N and b ∈ ℤ 2 the sets of N ' successive values The algorithm is based on the assumption that we can efficiently create uniform superposition over these states. As above, we have We can try to repeat m times the measurement in order to approximate P and hence also l, s and finally d.
Of course, we can test several values of a and compare the different approximations of d to refine them. Once again, we use Hoeffding's inequality. We define X to be the random variable taking the value 1 with probability P and 0 otherwise and S = X 1 + X 2 + … + X m . We take m = (log N) 2 p + 1 for some fixed p and t = log N m √ = 1 (log N ) p i.e. mt 2 = log N. We have: So if l exp is the experimental value of l we have with very high probability, |l 2 − l exp 2 | < t N ' 2 = N ' 2 (log N ) p . Unfortunately, this does not provide a good precision. Instead, we will turn toward a more modest goal: determine whether l is less than N ' 2 . This is possible if l exp is sufficiently far from N ' 2 . Note that