A quantum polylog algorithm for non-normal maximal cyclic hidden subgroups in the affine group of a finite field


Abstract in English

We give an algorithm to solve the quantum hidden subgroup problem for maximal cyclic non-normal subgroups of the affine group of a finite field (if the field has order $q$ then the group has order $q(q-1)$) with probability $1-varepsilon$ with (polylog) complexity $O(log(q)^{R}log(varepsilon)^{2})$ where $R<infty.$

Download