• Quick access
  • Homepage (fr)
  • International
  • François's Blog
  • Frédéric's Blog
  • Maths (fr)
  • Computer Science (fr)
  • Programming (fr)
  • Our games (fr)
  • Video games (fr)
• Special pages
  • Log in (fr)
  • Forum
  • Authors (fr)
  • Site Map (fr)
• Parent directories
  • International
  • The Hidden Subgroup Problem
  • The Dihedral and Symmetric Hidden Subgroup Problems
• Current directory
  • Index
  • Report
  • Introduction
  • Prerequisites
  • Efficient Quantum Algorithms and The Hidden Subgroup Problem
  • The Standard Method for The Hidden Subgroup Problem
  • The Dihedral and Symmetric Hidden Subgroup Problems
  • The General Hidden Subgroup Problem
  • Conclusion
  • Appendix A
  • Appendix B
  • Appendix C
  • Appendix D
  • Appendix E
  • Appendix F
  • Appendix G
  • Bibliography

The Dihedral and Symmetric Hidden Subgroup Problems

The Dihedral Hidden Subgroup Problem

For any $N\ge 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 $\frac{2\pi }{N}$. It is composed of $2N$ elements: $N$ rotations $r^k$ and $N$ reflections $r^{k}s$ ($0\le k\le N-1$) . The elements satisfy the relation $r^N=s^2=srsr=\mathrm{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 ${\mathbb{Z}}_N⋊{\mathbb{Z}}_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}\left(r^{a_2}s{r}^{a_2}\right)s^{b_2}=r^{a_1-a_2}{s}^{{1+b}_2}$, so the law of this semi-direct product is given by

$$(a_1,b_1)(a_2,b_2)=(a_1+{\left(-1\right)}^{b_1}{a}_2,b_1+b_2)$$

and consequently the inverse operation is

$${\left(a,b\right)}^{-1}=({\left(-1\right)}^{b+1}a,b)$$

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\le d\le 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 $G\text{'}={\mathbb{Z}}_N\times \left\{0\right\}$ of $G$. Then $H\text{'}=G\text{'}\cap H$ is a subgroup of $G\text{'}$ so there is a divisor $r$ of $N$ such that $H\text{'}=\left({r\mathbb{Z}}_N\right)\times \left\{0\right\}$. If $H\text{'}\ne H$ then there exists $\left(d,1\right)\in H$. If $\left(a,1\right)$ is another element of $H$, then $\left(d,1\right)\left(a,1\right)=\left(d-a,0\right)\in H\text{'}$. We have $\left(a,1\right)=\left(d,1\right)\left(d-a,0\right)\in \left(d,1\right)H\text{'}$. As a consequence, $H=H\text{'}\cup \left(d,1\right)H\text{'}$. Note that if $d=rq+d\text{'}$ is the euclidean division of $d$ by $r$, $\left(d\text{'},1\right)=\left(-rq,0\right)\left(d,1\right)\in H$. Replacing $d$ by $d\text{'}$, we can assume $0\le d<r$. Finally, we have:

Can we use the general algorithms based on the Weak Fourier Sampling, that we have previously seen? We note that $\left(a,b\right)\left(rl,0\right){\left(a,b\right)}^{-1}=({\left(-1\right)}^{b}rl,0)$ so $H_r$ is normal. We also have $\left(a,b\right)\left(d+rl,1\right){\left(a,b\right)}^{-1}=\left(2a+{\left(-1\right)}^b\left(d+rl\right),1\right)$ so $H_{r,d}$ is normal iff for all $a,b\in {\mathbb{Z}}_N$ we have $2a+{\left(-1\right)}^{b}d\equiv d\text{ mod }\left(r\right)$ (which is obviously true for $r$ being 1 or 2). The case $a=1$ and $b=0$ shows that $r$ can not be more than 2 if we want this equality to hold. As a consequence, the normal subgroups are $H=H_r$ (for any divisor $r$ of $N$), $H=H_{1,0}=G$ and (if $N$ is even) $H=H_{2,0}$ or $H=H_{\mathrm{2,1}}$. 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 $M_G\subseteq N\left(H_{N,0}\right)=\{\left(a,b\right)\mid 2a\equiv 0\text{ mod }\left(N\right)\}$ so $1\le \mid M_G\mid \le 4$. As a consequence, $\frac{\mid G\mid }{\mid H{M}_G\mid }=\frac{\mid G\mid \mid M_G\cap H\mid }{\mid H\mid \mid M_G\mid }=\frac{2N}{\raisebox{1ex}{$N$}\!\left/ \!\raisebox{-1ex}{$r$}\right.}\frac{\mid M_G\cap H\mid }{\mid M_G\mid }=\Theta \left(r\right)$. So Gavinski's HSP algorithm is successful iff $r=\text{poly}\left(\log N\right)$.

Ettinger and Høyer proved in [EttHøy1998] that the dihedral HSP reduces to the case where $H=H_{N,d}=$$⟨(d,1)⟩$ . 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 $\raisebox{1ex}{$G$}\!\left/ \!\raisebox{-1ex}{$H_r$}\right.$ are $\left(i,0\right)H_r$ and $\left(i,1\right)H_r$ for $0\le i<r$ while the elements of $\raisebox{1ex}{$H$}\!\left/ \!\raisebox{-1ex}{$H_r$}\right.$ are given by $H_r$, $\left(d,1\right)H_r$. Hence, moving to the quotient group we have the hidden subgroup problem for $\raisebox{1ex}{$G$}\!\left/ \!\raisebox{-1ex}{$H_r$}\right.\cong D_r$ and hidden subgroup $⟨(d,1)⟩$. We see that we have a solution to the hidden subgroup problem with complexity $\text{poly}\left(\log \left(N\right),r\right)$ ($\text{poly}\left(N\right)$ to find $r$ and $\mathrm{poly}\left(r\right)$ to find $d$ working in $D_r$). In particular the algorithm is already efficient in the case $r=\text{poly}\left(\log N\right)$ solved by Gavinski's HSP algorithm. We have proved the important reduction:

Ettinger and Høyer used the same circuit as in HSP over ${\mathbb{Z}}_N\times {\mathbb{Z}}_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

$$\sum _{a=0}^{N-1}\sum _{b=0}^1\mid a⟩\mid b⟩\mid f(a,b)⟩$$

The first measurement yields a $f(a_0,b_0)$ and makes the two first registers collapse to

$$\frac{1}{\sqrt{2}}(\mid a_0⟩\mid b_0⟩+\mid a_0+{(-1)}^{b_0}d⟩\mid b_0+1⟩)=\{\begin{array}{ll}\frac{1}{\sqrt{2}}(\mid a_0⟩\mid 0⟩+\mid a_0+d⟩\mid 1⟩)& \text{if}{b}_0=0\\ \frac{1}{\sqrt{2}}(\mid (a_0-d)⟩\mid 0⟩+\mid (a_0-d)+d⟩\mid 1⟩)& \text{if}{b}_0=1\end{array}$$ since $a_0$ and $b_0$ are chosen uniformly at random, this is equivalent to have a state

$$\frac{1}{\sqrt{2}}(\mid x⟩\mid 0⟩+\mid x+d⟩\mid 1⟩)$$

for some $x\in {\mathbb{Z}}_N$ chosen uniformly at random. Applying the Fourier transform $F_N$ to the first register gives the state

$$\frac{1}{\sqrt{2N}}\sum _{k=0}^{N-1}(e^{\frac{2i\pi kx}{N}}\mid k⟩\mid 0⟩+e^{\frac{2i\pi k(x+d)}{N}}\mid k⟩\mid 1⟩)$$

The second measurement returns a $k\in {\mathbb{Z}}_N$ chosen uniformly at random and make the second register collapse to the state

$$\frac{1}{\sqrt{2}}{e}^{\frac{2i\pi kx}{N}}(\mid 0⟩+e^{\frac{2i\pi kd}{N}}\mid 1⟩)$$

Finally, we apply an hadamard gate on the second register to get

$$\begin{array}{rl}\frac{1}{2}{e}^{\frac{2i\pi kx}{N}}((\mid 0⟩+\mid 1⟩)+e^{\frac{2i\pi kd}{N}}(\mid 0⟩-\mid 1⟩))& =\frac{1}{2}{e}^{\frac{2i\pi kx}{N}}{e}^{\frac{i\pi kd}{N}}((e^{\frac{i\pi kd}{N}}+e^{-\frac{i\pi kd}{N}})\mid 0⟩+(-e^{\frac{i\pi kd}{N}}+e^{-\frac{i\pi kd}{N}})\mid 1⟩)\\ & =e^{\frac{2i\pi kx}{N}}(\cos \left(\frac{k\pi d}{N}\right)\mid 0⟩-i\sin \left(\frac{k\pi d}{N}\right)\mid 1⟩)\end{array}$$

The measurement given by (2) and (3) is then:

$$P\left(k,j\right)=\{\begin{array}{ll}\frac{1}{N}{\cos }^2\left(\frac{k\pi d}{N}\right)& \text{if }j=0\\ \frac{1}{N}{\sin }^2\left(\frac{k\pi d}{N}\right)& \text{if }j=1\end{array}$$

The algorithm of Ettinger and Høyer starts by checking the values $d=0$ or $d=\frac{N}{2}$ (just by comparing $f(0,0)$ with $f(0,1)$ and $f\left(\frac{N}{2},1\right)$). Otherwise, they show that there is some $m=O\left(\log N\right)$ such that from $k_1,\dots ,k_m$ samples of the previous algorithm we can find $d$, just by searching the minimum of a function $x\mapsto g(x,k_1,\dots ,k_m)$ over the domain $\{\mathrm{1,2},\dots ,\lfloor \frac{N}{2}\rfloor \}$. The whole algorithm allows to solve the dihedral HSP using $O\left(\log N\right)$ calls to $f$. However, to find the minimum of the function $g$ we test $O\left(N\right)$ elements.

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:

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\left(D_N\right)$. In particular, we can solve the case $N=2^n$ if we have an efficient process to create for $b=0,1$ the states $\frac{1}{\sqrt{N\prime }}\sum _{i=0}^{N\prime -1}\mid f(2i,b)⟩$.

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:

$$\mid {\Psi }_k⟩=\frac{1}{\sqrt{2}}(\mid 0⟩+e^{\frac{2i\pi kd}{N}}\mid 1⟩)$$

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 $\mid {\Psi }_{2^{n-1}}⟩=\frac{1}{\sqrt{2}}(\mid 0⟩+{\left(-1\right)}^d\mid 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_{\mathrm{2,0}}$ (if $d$ is even) or $H_{\mathrm{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 $\mid {\Psi }_k⟩$ and $\mid {\Psi }_l⟩$. Taking their tensor product, applying a CNOT gate and ignoring the phase factor gives a state $\mid {\Psi }_{k\pm 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\pm l$ is multiple of $2^{i\text{'}}$ for some $i\text{'}>i$.

The idea of Kuperberg is to use a pipeline as represented in figure 5.2. At the input, many $\mid {\Psi }_k⟩$'s are created by the DCP black box. At each stage $i$, we have states $\mid {\Psi }_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 $\mid {\Psi }_{k\text{'}}⟩$ 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 $\mid {\Psi }_{2^{n-1}}⟩$ with high probability.

The running time of Kupenberg's algorithm is $2^{O\left(\sqrt{\log N}\right)}$ which is subexponential but unfortunately, the algorithm also requires $2^{O\left(\sqrt{\log N}\right)}$ 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 time to $2^{O\left(\sqrt{\log \left(\log N\right)\log N}\right)}$. 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 $\mid {\phi }_{x,d}⟩=\frac{1}{\sqrt{2}}(\mid x⟩\mid 0⟩+\mid x+d⟩\mid 1⟩)$ then the density matrix output by the DCP black box is ${\rho }_d=\frac{1}{N}\sum _{x\in {\mathbb{Z}}_N}\mid {\phi }_{x,d}⟩⟨{\phi }_{x,d}\mid$. So if we use $k=\nu \log \left(N\right)$ outputs from this black box, our purpose is to identify the density matrix ${\rho }_d^{\otimes 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 $\nu <1$ and a constant probability if $\nu >1$. Since the algorithm of Ettinger and Høyer gives an algorithm using linear (in $\log \left(N\right)$) oracle calls, this means that the query complexity of DCP is exactly $\Theta \left(\log \left(N\right)\right)$. 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 \left(N\right)$. 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.

In [Reg2003], Regev proved that if it is possible to solve a fraction $\frac{1}{\mathrm{poly}\left(\log N\right)}$ of the legal instances of the subset sum problem if $k>4+\log \left(N\right)$, 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 $\left(t,x\right)$:

$$\mid S_t^x⟩=\frac{1}{\sqrt{\mid S_t^x\mid }}\sum _{b\in S_t^x}\mid b⟩$$

if we have a quantum circuit that operates on input states $\mid t,x⟩$ and sends the legal instances to $\mid S_t^x,x⟩$ then we can implement the optimal measurement and thus solve DCP. Producing these states $\mid 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.

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:

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\left(n\right)$-uniqueSVP and DCP, we need to modify the black-box in a way that allows errorous output. So we introduce:

(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\in {\mathbb{Z}}_N$ given a black box that behaves almost always like a DCP black box. More precisely, this black box produces a DCP-state $\frac{1}{\sqrt{2}}(\mid x⟩\mid 0⟩+\mid x+d⟩\mid 1⟩)$ for some uniformly random $x\in {\mathbb{Z}}_N$ with probability at least $1-\frac{1}{{\left(\log N\right)}^p}$ and an arbitrary $\mid a⟩\mid b⟩\in D_N$ otherwise.

We can now state the main theorem, due to Regev [Reg2003]:

Let $n>0$ an integer and define $N=2^{\left(4n+1\right)n}$. If there is a solution to the DCP over $D_N$ with failure parameter $p$ then there is solution to the $\Theta \left(n^{\frac{1}{2}+2p}\right)$-uniqueSVP.

Regev said that if we have a solution to the exact DCP, then by taking $p$ large enough the black-box outputs only DCP-states. He concluded that a solution to DCP gives a solution to the $\text{poly}\left(n\right)$-uniqueSVP. Let's state a slightly stronger version of its corollary:

If there is a solution to DCP over $D_{2^{\left(4n+1\right)n}}$ whose query complexity can be expressed as a polynomial of degree $D$, then there is a solution to $\Theta \left(n^{\frac{1}{2}+2D}\right)$-uniqueSVP.

proof: the probability that the DCP with failure parameter $p$ produces only DCP-states after $\sum _{i=0}^D{a}_i{\left(\log N\right)}^i$ oracle calls is at least

$${(1-\frac{1}{{(\log N)}^p})}^{\sum _{i=0}^D{a}_i{(\log N)}^i}=\prod _{i=0}^D{\left[{(1-\frac{1}{{(\log N)}^p})}^{{(\log N)}^i}\right]}^{a_i}$$

When $N\to +\infty$, the limit of the bracket term is 0 if $i>p$, $e^{-1}$ if $i=p$ and 1 otherwise. So the above value is bounded below by a constant $c>0$ iff $D\le p$. In that case, we can repeat the procedure about $\frac{1}{c}$ times to be sure that we solve DCP over $D_{2^{\left(4n+1\right)n}}$ with failure parameter $p=D$ and so the $\Theta \left(n^{\frac{1}{2}+2D}\right)$-uniqueSVP.

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 $\Theta \left(n^{\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}\right)$-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 ${\mathbb{Z}}_M^n$ with constant difference. The two point problem reduces to DCP over $D_{{\left(2M\right)}^n}$ by considering the mapping:

$$(a_1,a_2,\dots ,a_n)\mapsto a_1+a_{2}2M+\dots +a_n(2M{)}^{n-1}$$

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^{\left(4n+1\right)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\in {\mathbb{Z}}_M^n$ if we have an algorithm for a DCP-like problem over $\mathrm{Dih}\left({\mathbb{Z}}_{2^{4n}}^n\right)={\mathbb{Z}}_{2^{4n}}^n⋊{\mathbb{Z}}_2$ in place of $D_N\cong {\mathbb{Z}}_N⋊{\mathbb{Z}}_2$. This corresponds to a generalized DHSP over ${\mathbb{Z}}_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\circ f$ where $f$ maps elements of ${\mathbb{Z}}_M^n$ to lattice vectors and is very similar to coset sampling: we start by a superposition over ${\mathbb{Z}}_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 $\frac{1}{\sqrt{2}}(\mid x⟩\mid 0⟩+\mid x+v⟩\mid 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.

(modified coset samplings)

• Modifying the oracle. Fix $k>0$ and define the function $f_1\left(a,b\right)=f\left(a,b\text{ mod }\left(2\right)\right)$ where $a\in {\mathbb{Z}}_N$, $b\in {\mathbb{Z}}_{2k}$ ($f$ is the DCP oracle). Then the coset sampling using $f_1$ as oracle produces a state $\frac{1}{\sqrt{2k}}\sum _{i=1}^{2k}(\mid x_i⟩\mid 2i⟩+\mid x_i+d⟩\mid 2i+1⟩)$ for some uniformly random elements $x_i\in {\mathbb{Z}}_N$.
• Modifying the input state on the oracle register: fix some $k>0$. Rather than sending the state $\mid 0⟩$ on the oracle register (i.e. the last register of $U_f$) send a superposition of $k$ basis states $\frac{1}{\sqrt{k}}\sum _{i=1}^k\mid y_k⟩$ for some uniformly random distinct elements $y_k$. Then the coset sampling produces a state $\frac{1}{\sqrt{2k}}(\left(\sum _{i=1}^k\mid x_i⟩\right)\mid 0⟩+\left(\sum _{i=1}^k\mid x_i+d⟩\right)\mid 1⟩)$ for some uniformly random distinct elements $x_i\in {\mathbb{Z}}_N$.
• Making the superposition non-uniform: input the states $\sum _{a=0}^{N-1}\sum _{b=0}^1{p}_{a,b}\mid a⟩\mid b⟩$ for a distribution probability $p_{a,b}$. The coset sampling produces a state $\frac{1}{\sqrt{2}}(p_{x,0}\mid x⟩\mid 0⟩+p_{x+d,1}\mid x+d⟩\mid 1⟩)$.

One important variant is DCP over another hidden slope problem for the dihedral group, derived from the initial $D_N$. For example in Kuperberg's algorithm, we use a coset sampling over $D_N$ to determine the parity $b$ of $d$, over $D_{N/2}\cong H_{2,b}\subseteq D_N$ and so forth... Similarly for $\mathrm{Dih}\left({\mathbb{Z}}_{2^{4n}}^n\right)$, we can get information on $v$ and move to a smaller subgroup. For example if we determine the parity of $b$ of the $i$th coordinate of $v$ then we can work in $H_{\left(\mathrm{1,1},\dots ,1,2,1,\dots ,1\right),b}$ (with a 2 at the $i$th position) instead, which is isomorphic to another generalized dihedral group $\mathrm{Dih}\left({\mathbb{Z}}_N^{i-1}\times {\mathbb{Z}}_{N/2}\times {\mathbb{Z}}_N^{N-i-1}\right)$ and by induction, we continue to move to dihedral groups of the form $\mathrm{Dih}\left(A\right)$ 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={\mathbb{Z}}_{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:

(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 $\mathrm{Dih}\left(A\right)$ which includes $\mathrm{Dih}\left({\mathbb{Z}}_{2^{4n}}^n\right)$ and such that the recursive step moves to a subgroup of the same class. A recursive DCP algorithm is also allowed for $A={\mathbb{Z}}_{2^n}$ group if the inductive step consists in determining the parity $b$ of $d$ and moving to $H_{2,b}\cong 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⋊{\mathbb{Z}}_p$ with $A$ abelian). Allowing more points in one partition could weaken the uniqueSVP promise.

The Symmetric Hidden Subgroup Problem

For any $n\ge 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 \mid S_n\mid =\sum _{i=2}^n\log \left(i\right)$ and since $1\le \log \left(i\right)\le i$ for $i\ge 2$, we have $n-1\le \log \mid S_n\mid \le \frac{n\left(n+1\right)}{2}-1$. This means that $n$ can be used as a measure of efficiency since $\log \mid S_n\mid =\text{poly}\left(n\right)$ (more precisely, the Stirling formula gives $\mid S_n\mid =\sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n\left(1+o\left(1\right)\right)$ so $\log \mid S_n\mid \underset{n\to \infty }{\sim }n\log n$).

(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 $\text{poly}\left(n\right)$.

By Cayley's theorem, every group $G$ is isomorphic to a subgroup of $S_{\mid G\mid }$. Hence to find a subgroup $H$ of $G$, one can apply a SHSP to the corresponding subgroup of $S_{\mid G\mid }$. However, an efficient algorithm for $S_{\mid G\mid }$ would be $\text{poly}\left(\mid G\mid \right)$ while an efficient algorithm for $G$ needs to be $\text{poly}\left(\log \left(\mid G\mid \right)\right)$.

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:

(Graph isomorphism and automorphism problems)

Let $\left(V_1,E_1\right)$ and $\left(V_2,E_2\right)$ be two (undirected) graphs. They are said to be isomorphic iff there is a bijection $\phi :V_1\to V_2$ such that for any two vertices $a,b\in V_1$ we have $\{a,b\}\in E_1$ iff $\{\phi \left(a\right),\phi \left(b\right)\}\in E_2$. 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 $\phi \ne \mathrm{Id}$ which is a permutation of the vertices of the graph).

The figure 5.4 shows an example of three isomorphic graphs. Clearly, the automorphisms are given by the bijections fixing the vertex of degree 4.

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 $\left(V,E\right)$ 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=\mid V\mid$. We define the oracle $f$ to be the function that send $\phi \in S_n$ to $f\left(\phi \right)=(\phi \left(V\right),\phi \left(E\right))$. As indicated in [Lom2004], $f$ can be computed efficiently. Suppose for instance that we have fixed an enumeration $\{0,\cdots ,n-1\}$ of the vertices $V$ and we represent the graph $\left(V,E\right)$ by an ordered list of pairs $\left(a,b\right)$ where $a\le b\in V$ and $\{a,b\}\in E$. Given $\left(V,E\right)$, we can compute $(\phi \left(V\right),\phi \left(E\right))$ efficiently by replacing each $\left(a,b\right)$ by $(\phi \left(a\right),\phi \left(b\right))$ and then applying classical sorting algorithms on the whole structure.

Finally, we have $H$ a subgroup of $S_n$ and clearly $\forall {\phi }_1,{\phi }_2\in S_n,f({\phi }_1)=f({\phi }_2)\iff {\phi }_{1}H={\phi }_{2}H$. So an efficient algorithm for DHSP gives a $\text{poly}\left(n\right)$ 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 $\left(V_1,E_1\right)$ 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\left(n^2\right)$. 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.

We now build a 2-component graph of $2n$ vertices by taking the disjoint union of $\left(V_1,E_1\right)$ and $\left(V_2,E_2\right)$ . We suppose $V_1=\{1,\cdots ,n\}$ and $V_2=\{n+1,\cdots ,2n\}$. The permutations of $V_1\cup V_2$ can be viewed as the group $S_{2n}$. An isomorphism $\phi :V_1\to 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\le i\le n$, $\phi$ can actually be seen as the automorphism $\left(\phi ,{\phi }^{-1}\right)s_n\in 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=\left\{\mathrm{Id}\right\}$ if the two initial graphs are not isomorphic or otherwise $H=\{\mathrm{Id},\sigma \}$ where $\sigma =\left(\phi ,{\phi }^{-1}\right)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=\{\mathrm{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\times S_n\subseteq S_{2n}$). We have $\left(a,b\right)s_n=s_n\left(b,a\right)$ and $s_n$ is of order $2$ so any element of $G$ can be written $\left(a,b\right){s_n}^c$ for some $\left(a,b\right)\in S_n\times S_n$ and $c\in {\mathbb{Z}}_2$. If $\tau$ 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)\circ {\tau }^{c_2}(a_2,b_2),c_1+c_2)$$

This is called the wreath product of $S_n$ and ${\mathbb{Z}}_2$ and denoted by $G\cong S_n\wr {\mathbb{Z}}_2=\left(S_n\times S_n\right)⋊{\mathbb{Z}}_2$. Finally, we now have an instance of HSP over the group $S_n\wr {\mathbb{Z}}_2$ and we only have to distinguish the cases $H$ trivial (the two graphs are not isomorphic) or $H=\{\mathrm{Id},\left(a,a^{-1},1\right)\}$ ( $a\in 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 $\epsilon$ denotes the signature of permutation, we have $\epsilon \left(\sigma \right)={\epsilon \left(\phi \right)}^2\epsilon \left(s_n\right)=1{\left(-1\right)}^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 $\tau =\left(m,2m\right)$, then the automorphism group $H$ of the big graph is a subgroup of $S_{2m}$ and is similar to the previous case: either $H=⟨\tau ⟩$ or $H=⟨\tau ,\sigma ⟩$ where $\sigma =(\phi ,m\mapsto m,{\phi }^{-1},2m\mapsto 2m)s_m$. The problem is now to determine whether the subgroup $H\cap A_{2m}$ of $A_{2m}$ is trivial or $⟨\sigma ⟩$.

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 $\Omega \left(\log \left(\mid S_n\mid \right)\right)=\Omega \left(n\log n\right)$ 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 ${\rho }_i$ and ${\rho }_j$, apply measurement on their tensor product ${\rho }_i\otimes {\rho }_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 $e^{\Omega \left(\sqrt{n}\right)}$ time. This does not give any meaningful improvement over the best known classical algorithms: $e^{O\left(\sqrt{n\log n}\right)}$ for general graphs [BabLuk1983] or $e^{O\left(n^{\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$3$}\right.}{\log }^{2}n\right)}$ 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\wr {\mathbb{Z}}_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.

previous

back to index

next

This page is W3C-compliant - Author: Frédéric WANG