On solving systems of random linear disequations
Gábor Ivanyos · Quantum Information and Computation · 2008
An important special case of the hidden subgroup problem is equivalent to the hidden shift problem over abelian groups. An efficient solution to the latter problem could serve as a building block of quantum hidden subgroup algorithms over solvable groups. The main idea of a promising approach to the hidden shift problem is a reduction to solving systems of certain random disequations in finite abelian groups. By a disequation we mean a constraint of the form $f(x) eq 0$. In our case, the functions on the left hand side are generalizations of linear functions. The input is a random sample of functions according to a distribution which is up to a constant factor uniform over the "linear" functions $f$ such that $f(u) eq 0$ for a fixed, although unknown element $u\in A$. The goal is to find $u$, or, more precisely, all the elements $u'\in A$ satisfying the same disequations as $u$. In this paper we give a classical probabilistic algorithm which solves the problem in an abelian $p$-group $A$ in time polynomial in the sample size $N$, where $N=(\log\size{A})^{O(q^2)}$, and $q$ is the exponent of $A$.