Golomb rulers and difference sets for succinct quantum automata

Given a function p : N → [0,1] of period n, we study the minimal size (number of states) of a one-way quantum finite automaton (Iqfa) inducing the stochastic event ap + b, for real constants a>0, b≥0, a+b≤1. First of all, we relate the estimation of the minimal size to the problem of finding a minimal difference cover for a suitable subset of Zn. Then, by observing that the cardinality of a difference cover Δ for a set A Z n, must satisfy $|\Delta| \ge (1 + \sqrt{4|A| - 3})/2$, we investigate the class of sets A admitting difference covers of cardinality exactly $(1 + \sqrt{4|A| - 3})/2$. We relate this problem with the efficient construction of Golomb rulers and difference sets. We design an algorithm which outputs each of the Golomb rulers (if any) of a given set in pseudo-polynomial time. As a consequence, we obtain an efficient algorithm that construct minimal difference covers for a non-trivial class of sets. Moreover, by using projective geometry arguments, we give an algorithm that, for any n=q2+q+1 with q prime power, constructs difference sets for Z n in quadratic time.