Paper Info
Title
Can one quantum bit separate any pair of words with zero-error?
Abstract
Determining the minimum number of states required by a finite automaton to separate a given pair of different words is an important problem. In this paper, we consider this problem for quantum automata (QFAs). We show that 2-state QFAs can separate any pair of words in nondeterministic acceptance mode and conjecture that they can separate any pair also with zero-error. Then, we focus on (a more general problem) separating a pair of two disjoint finite set of words. We show that QFAs can separate them efficiently in nondeterministic acceptance mode, i.e. the number of states is two to the power of the size of the small set. Additionally, we examine affine finite automata (AfAs) and show that two states are enough to separate any pair with zero-error. Moreover, AfAs can separate any pair of disjoint finite sets of words with one-sided bounded error efficiently like QFAs in nondeterministic mode.
Year
Venue
Field
2016
arXiv: Formal Languages and Automata Theory
Affine transformation,Discrete mathematics,Combinatorics,Finite set,Disjoint sets,Nondeterministic algorithm,Finite-state machine,Qubit,Small set,Conjecture,Mathematics
DocType
Volume
Citations 
Journal
abs/1602.07967
3
PageRank 
References 
Authors
0.44
5
3
Name
Order
Citations
PageRank
Aleksandrs Belovs113114.50
Juan Andrés Montoya260.84
Abuzer Yakaryilmaz316825.31