Note on Hidden Shifts as Hidden Subgroups
On of the key insights I acquired in the talks at QCPQA this last week was that a hidden shift over some finite abelian $A$ (usually $\mathbb{F}_2^n$) can be recast as a hidden dihedral subgroup problem via $$ \mathsf{Dih}(A) = A \rtimes \mathbb{Z}_2 \cong \mathbb{Z}_2^{n+1} $$ This notation was a little new to me, but I knew that $$ \mathbb{Z}_2 = \{0,1\} $$ Here, $A \rtimes \mathbb{Z}_2$ is the twisted product , and $Dih(A)$ is the dihedral group of $A$ from that product. The product itself allows nontrivial elements of $\mathbb{Z}_2$ to act on elements of $A$ by by inversion $$ a \mapsto a^{-1} $$ and so as a set we would get $$ Dih(A) = A \times \mathbb{Z}_2 $$ however we have to twist the multiplication such that for $a,b \in A$ and $\epsilon, \delta \in \mathbb{Z}_2$, we let $\eta = (-1)^\epsilon$ and use the product $$ (a,\epsilon)(b, \delta) = (ab^{\eta}, \epsilon \otimes \delta) $$ where $\alpha \otimes \beta$ is XOR which for bits is just addition $\alpha + \beta ...
