Appendix G: Attempts to solve DHSP by superposition of oracle values

In this section, we try to solve the HSP over $D_N={\mathbb{Z}}_N{⋊}_{\phi }{\mathbb{Z}}_2$, reduced to the case $H=⟨(d,1)⟩$ for some $d\in {\mathbb{Z}}_N$. Contrary to all the other approaches proposed so far, we will not use coset states of the form $\frac{1}{\sqrt{2}}(\mid x⟩\mid 0⟩+\mid x+d⟩\mid 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\text{'}=\frac{N}{M}$ and write the euclidean division $d=Md\text{'}+r$. If we are able to determine $r$ in polynomial time, then we can define the oracle $f\text{'}(x,y)=f(Mx+r,y)$ for $x\in {\mathbb{Z}}_{N\text{'}}$, $y\in {\mathbb{Z}}_2$ and obtain a new dihedral HSP with hidden subgroup $⟨(d\text{'},1)⟩$. Since the prime factorization has only $O\left(\log N\right)$ 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$.

If we fix $b\in \{0,1\}$, the elements $\left(Mi+j,b\right)$ for $i\in {\mathbb{Z}}_{N\text{'}},j\in {\mathbb{Z}}_M$ form a complete set of coset representatives, and so the elements $f\left(Mi+j,b\right)$ are the $N$ possible values of $f\left(D_N\right)$. Moreover, we can consider a partition of $f\left(D_N\right)$ by defining for all $j\in {\mathbb{Z}}_M$ the subsets

$$E_j^b=\{f(Mi+j,b),i\in {\mathbb{Z}}_{N\prime }\}$$

From the equality $f\left(g\left(d,1\right)\right)=f\left(g\right)$ we have the relation:

$$\begin{array}{rl}{E}_j^1& =\{f(Mi+j,1),i\in Z_{N\prime }\}\\ & =\{f\left((Mi+j-d,0)(d,1)\right),i\in Z_{N\prime }\}\\ & =\{f(Mi+j-(Md\prime +r),0),i\in Z_{N\prime }\}\\ & =\{f(Mi+(j-r),0),i\in Z_{N\prime }\}\\ & =E_{(j-r)\text{mod}(M)}^0\end{array}$$

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_0^0$ and $E_0^1$ are respectively

$$\mid {\psi }_0⟩=\frac{1}{\sqrt{N\prime }}\sum _{i=0}^{N\prime -1}\mid f(2i,0)⟩$$

and

$$\mid {\varphi }_0⟩=\frac{1}{\sqrt{N\prime }}\sum _{i=0}^{N\prime -1}\mid f(2i,1)⟩$$

If $r=0$, $\mid {\psi }_0⟩=\mid {\varphi }_0⟩$ is the uniform superposition over $E_0^0$. Otherwise, $r=1$ and $\mid {\varphi }_0⟩$ is the uniform superposition over the complementary set $E_0^1$. We let $f_i^b=f(2i+b,0)$ and measure the product state $\mid {\psi }_0⟩\mid {\varphi }_0⟩$ in the basis ${\mid x⟩\mid x⟩}_{x\in {\mathbb{Z}}_N}$, ${\frac{1}{\sqrt{2}}\left(\mid x⟩\mid y⟩+\mid x⟩\mid y⟩\right)}_{x<y\in {\mathbb{Z}}_N}$, ${\frac{1}{\sqrt{2}}\left(\mid x⟩\mid y⟩-\mid x⟩\mid y⟩\right)}_{x<y\in {\mathbb{Z}}_N}$ . It turns out that this allows to distinguish the two cases:

• If $r=0$, the product contains vectors with the same coordinates $\mid f_i^0⟩\mid f_i^0⟩$ for $i\in {\mathbb{Z}}_N$. For the other vectors, we have a symmetry between the two coordinates. Hence we can group them by pairs $\mid f_{i_1}^0⟩\mid f_{i_2}^0⟩+\mid f_{i_2}^0⟩\mid f_{i_1}^0⟩$ for $i_1<i_2\in {\mathbb{Z}}_N$. Finally, the product state belongs to the space spanned by ${\mid x⟩\mid x⟩}_{x\in {\mathbb{Z}}_N}$ and ${\mid x⟩\mid y⟩+\mid x⟩\mid y⟩}_{x<y\in {\mathbb{Z}}_N}$.
• If $r=1$, the product contains vectors $\mid f_{i_1}^0⟩\mid f_{i_2}^1⟩$ where the two coordinates are not equal. This time, we never have two symmetric vectors i.e. which are the same modulo permutation of the two coordinates. Moreover, each vector $\mid f_{i_1}^0⟩\mid f_{i_2}^1⟩$ is the expression of a sum/difference (according to the respective order of $f_{i_1}^0$ and $f_{i_2}^1$) of two vectors $\mid x⟩\mid y⟩+\mid x⟩\mid y⟩$ and $\mid x⟩\mid y⟩-\mid x⟩\mid y⟩$. So the product state belongs half to ${\mid x⟩\mid y⟩+\mid x⟩\mid y⟩}_{x<y\in {\mathbb{Z}}_N}$ and half to ${\mid x⟩\mid y⟩-\mid x⟩\mid y⟩}_{x<y\in {\mathbb{Z}}_N}$.

Suppose that we have a procedure to create many states $\mid {\psi }_0⟩$ and $\mid {\varphi }_0⟩$. We measure a state in the space ${\frac{1}{\sqrt{2}}\left(\mid x⟩\mid y⟩-\mid x⟩\mid y⟩\right)}_{x<y\in {\mathbb{Z}}_N}$ with probability $\frac{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 $\mid {\psi }_0⟩$ and $\mid {\varphi }_0⟩$ efficiently. With the usual approach, we can start by creating a superposition over the elements $\left(2i,b\right)$ 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\in {\mathbb{Z}}_{N\text{'}}$ as well as the states

$$\mid {\psi }_{j_1}⟩=\frac{1}{\sqrt{N\prime }}\sum _{i=0}^{N\prime -1}{e}^{\frac{2i\pi j_{1}i}{N\prime }}\mid f(2i,0)⟩$$

and

$$\mid {\varphi }_{j_2}⟩=\frac{e^{\frac{2i\pi j_{2}d\prime }{N\prime }}}{\sqrt{N\prime }}\sum _{i=0}^{N\prime -1}{e}^{\frac{2i\pi j_{2}i}{N\prime }}\mid f(2i-r,0)⟩$$

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:

Space	case $r=0$	case $r=1$
${\mid x⟩\mid x⟩}_{x\in {\mathbb{Z}}_N}$	$\frac{1}{N\text{'}}$	0
${\mid x⟩\mid y⟩+\mid x⟩\mid y⟩}_{x<y\in {\mathbb{Z}}_N}$	$\frac{2}{{N\prime }^2}\sum _{i_2=0}^{N\prime -1}\sum _{i_1=0}^{i_2-1}{\cos }^2\frac{\pi }{N\prime }(j_2-j_1)(i_2-i_1)$	$\frac{1}{2}$
${\mid x⟩\mid y⟩-\mid x⟩\mid y⟩}_{x<y\in {\mathbb{Z}}_N}$	$\frac{2}{{N\prime }^2}\sum _{i_2=0}^{N\prime -1}\sum _{i_1=0}^{i_2-1}{\sin }^2\frac{\pi }{N\prime }(j_2-j_1)(i_2-i_1)$	$\frac{1}{2}$

If we repeat the procedure several times, we need to take the means over the choice of $j_1,j_2\in {\mathbb{Z}}_{N\text{'}}$. By classical trigonometric identities, it is possible to write the sums of the first column $\frac{1}{2}+S+o\left(\frac{1}{N\text{'}}\right)$ where $S$ is a sum of cosinus. Unfortunately, evaluating $S$ with a computer suggests that $S=\Theta \left(\frac{1}{N\text{'}}\right)$ . 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\text{'}=2M=\frac{N}{2}$. In this section, we consider for $a\in {\mathbb{Z}}_N$ and $b\in {\mathbb{Z}}_2$ the sets of $N\text{'}$ successive values $$F_a^b=\{f(a+i,b),i\in {\mathbb{Z}}_{N\prime }\}$$

The algorithm is based on the assumption that we can efficiently create uniform superposition over these states. As above, we have $F_a^1=F_{a-d}^0=F_s^0$ with $-N<s<N$ and we measure the tensor product of the uniform superpositions over $F_a^1=F_s^0$ and $F_0^0$ in the basis ${\mid x⟩\mid x⟩}_{x\in {\mathbb{Z}}_N}$, ${\frac{1}{\sqrt{2}}\left(\mid x⟩\mid y⟩+\mid x⟩\mid y⟩\right)}_{x<y\in {\mathbb{Z}}_N}$, ${\frac{1}{\sqrt{2}}\left(\mid x⟩\mid y⟩-\mid x⟩\mid y⟩\right)}_{x<y\in {\mathbb{Z}}_N}$. We define $l=\mid F_0^0\cap F_a^1\mid$ the number of common elements.

The figure 14.1 shows that in the case $0\le s\le N\text{'}$, we have $l=N\text{'}-s$. In general, the expression is

$$l=\mid N\text{'}-\mid s\mid \mid =\mid N\text{'}-\mid d-a\mid \mid$$

The possible vectors in the product of the uniform superpositions over $F_a^1=F_s^0$ and $F_0^0$ are:

• $l$ vectors of the form $\frac{1}{N\text{'}}\left(\mid x⟩\mid x⟩\right)$ for $x\in F_0^0\cap F_a^1$ in the intersection.
• $\left(\genfrac{}{}{0ex}{}{l}{2}\right)=\frac{l\left(l-1\right)}{2}$ vectors of the form $\frac{\sqrt{2}}{N\text{'}}\left(\frac{1}{\sqrt{2}}\left(\mid x⟩\mid y⟩+\mid x⟩\mid y⟩\right)\right)$ for $x,y\in F_0^0\cap F_a^1$ two distinct elements of the intersection.
• ${N\text{'}}^2-l^2$ other vectors $\mid x⟩\mid y⟩$ for $x\ne y$ with one of the vector ouside the intersection $F_0^0\cap F_a^1$, which can be written as a combination of two vectors of the basis. For example if $x<y$, it is $\frac{\sqrt{2}}{2N\text{'}}\left(\frac{1}{\sqrt{2}}\left(\mid x⟩\mid y⟩+\mid x⟩\mid y⟩\right)+\frac{1}{\sqrt{2}}\left(\mid x⟩\mid y⟩-\mid x⟩\mid y⟩\right)\right)$

The probability of measuring $\mid x⟩\mid x⟩$ or $\frac{1}{\sqrt{2}}\left(\mid x⟩\mid y⟩+\mid x⟩\mid y⟩\right)$ is thus

$$\begin{array}{rl}P& =\frac{1}{{N\prime }^2}(l+2\frac{l(l-1)}{2}+\frac{1}{2}({N\prime }^2-l^2))\\ & =\frac{1}{2}[1+{\left(\frac{l}{N\prime }\right)}^2]\end{array}$$

and of course the one of measuring $\frac{1}{\sqrt{2}}\left(\mid x⟩\mid y⟩-\mid x⟩\mid y⟩\right)$ is the complementary:

$$\begin{array}{rl}1-P& =\frac{1}{{N\prime }^2}\left(\frac{1}{2}({N\prime }^2-l^2)\right)\\ & =\frac{1}{2}[1-{\left(\frac{l}{N\prime }\right)}^2]\end{array}$$

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+\dots +X_m$. We take $m={\left(\log N\right)}^{2p+1}$ for some fixed $p$ and $t=\sqrt{\frac{\log N}{m}}=\frac{1}{{\left(\log N\right)}^p}$ i.e. $m{t}^2=\log N$. We have:

$$P(\frac{1}{m}\mid S-E\left(S\right)\mid \ge t)\le 2\exp \left(-2m{t}^2\right)=2\exp \left(-2\log N\right)$$

So if $l_{\exp }$ is the experimental value of $l$ we have with very high probability, $\mid l^2-{l_{\exp }}^2\mid <t{N\text{'}}^2=\frac{{N\text{'}}^2}{{\left(\log N\right)}^p}$. Unfortunately, this does not provide a good precision. Instead, we will turn toward a more modest goal: determine whether $l$ is less than $\frac{N\text{'}}{2}$. This is possible if $l_{\exp }$ is sufficiently far from $\frac{N\text{'}}{2}$. Note that

$$\begin{array}{rl}\mid l_{\exp }^2-{\left(\frac{N\prime }{2}\right)}^2\mid <t{N\prime }^2& \iff l_{\exp }^2={\left(\frac{N\prime }{2}\right)}^2+\epsilon t{N\prime }^2\text{for some}\mid \epsilon \mid <1\\ & \iff l_{\exp }=\frac{N\prime }{2}\sqrt{1+4\epsilon t}\text{for some}\mid \epsilon \mid <1\\ & \iff \sqrt{1-4t}\frac{N\prime }{2}<l_{\exp }<\sqrt{1+4t}\frac{N\prime }{2}\end{array}$$

Hence, if $t$ is small enough, we can decide with certainty whether $l$ is less than $\frac{N\text{'}}{2}$, except if $l_{\exp }$ is in a small interval around $\frac{N\text{'}}{2}$. Unfortunately again, we have $\sqrt{1\pm 4t}=1\pm 2t+o\left(t\right)$ so this interval is approximately of size $tN\text{'}=\frac{N}{{2\left(\log N\right)}^p}$ which is exponentially large...

The algorithm fails in general but still may give a partial hint. For example, if $\log N\ge 2$ and if we take $p=3$, the answer is correct for at least $l_{\exp }$ out of the intervall $]\frac{N\text{'}}{3},\frac{2N\text{'}}{3}[$. This is in contrast to the approximation proposed in appendix C, for which the error seems too difficult to bound in order to get any information.

As a conclusion, both methods above provide improvement over the standard coset sampling approach. It is not clear how we can create efficiently the uniform superpositions over the sets of oracle values $E_j^b$ or $F_a^b$, but they may provide an alternative research direction to solve the dihedral HSP.