Looking for Pairs that Hard to Separate: A Quantum Approach
Determining the minimum number of states required by a deterministic finite automaton to separate a given pair of different words (to accept one word and to reject the other) is an important challenge. In this paper, we ask the same question for quantum f
- PDF / 202,410 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 25 Downloads / 172 Views
3
CWI, Amsterdam, The Netherlands [email protected] 2 Universidad Nacional de Colombia, Bogot´ a, Colombia [email protected] National Laboratory for Scientific Computing, Petr´ opolis, RJ, Brazil [email protected]
Abstract. Determining the minimum number of states required by a deterministic finite automaton to separate a given pair of different words (to accept one word and to reject the other) is an important challenge. In this paper, we ask the same question for quantum finite automata (QFAs). We classify such pairs as easy and hard ones. We show that 2-state QFAs with real amplitudes can separate any easy pair with zero-error but cannot separate some hard pairs even in nondeterministic acceptance mode. When using complex amplitudes, 2-state QFAs can separate any pair in nondeterministic acceptance mode, and here we 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. Keywords: Quantum finite automaton · Zero-error · Nondeterminism · Succinctness · Promise problems
1
Introduction
Determining the minimum number of states required by a deterministic finite automaton (DFA) to separate any given pair of words is one of the famous open problems in automata theory [5]. We can generalize this question in a straightforward way by considering different computational models (e.g. see [16]). We focus on quantum finite automata (QFAs). We classify such pairs as easy and hard ones. We show that 2-state QFAs with real amplitudes can separate any easy pair with zero-error but cannot separate some hard pairs even in nondeterministic acceptance mode. When using complex amplitudes, 2-state QFAs can separate any pair in nondeterministic acceptance mode and here we 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. c Springer International Publishing Switzerland 2016 Y.-S. Han and K. Salomaa (Eds.): CIAA 2016, LNCS 9705, pp. 213–223, 2016. DOI: 10.1007/978-3-319-40946-7 18
214
A. Belovs et al.
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. In the next section, we provide the necessary background. The results on separating pairs are given in Sect. 3. The results on separating two finite sets are presented in Sect. 4.
2
Background
We refer the reader to [13] for a pedagogical introduction to quantum finite automata (QFAs), to [2] for a comprehensive survey on QFAs, and to [11] for a complete reference on quantum computation. We denote the alphabet by Σ, and we suppose that it does not contain the right end-marker $. For any given word x ∈ Σ, |x| represents the length of x, |x|σ represents the number of occurrences of symbol σ in x, and xj represe
Data Loading...
