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.
Golomb rulers and difference sets for succinct quantum automata / A. Bertoni, C. Mereghetti, B.S. Palano. - In: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. - ISSN 0129-0541. - 14:5(2003), pp. 871-888. [10.1142/S0129054103002060]
Golomb rulers and difference sets for succinct quantum automata
A. BertoniPrimo
;C. MereghettiSecondo
;B.S. PalanoUltimo
2003
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
954.65 kB
Formato
Adobe PDF
|
954.65 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.