On solving systems of random linear disequations (pp0579-0594)
          Gabor Ivanyos
          doi: https://doi.org/10.26421/QIC8.6-7-2
Abstracts: 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) = 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) = 0 for a fixed, although unknown element u  belongs to A. The goal is to find u, or, more precisely, all the elements u belongs to 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 |A|)O(q2), and q is the exponent of A.
Key words: Hidden subgroup, Quantum computing, disequation