Implications of quantum automata for contextuality

Abstract. We construct zero-error quantum finite automata (QFAs) for promise problems which cannot be solved by bounded-error probabilistic finite automata (PFAs). Here is a summary of our results: 1. There is a promise problem solvable by an exact two-way QFA in exponential expected time, but not by any bounded-error subloga-rithmic space probabilistic Turing machine (PTM). 2. There is a promise problem solvable by an exact two-way QFA in quadratic expected time, but not by any bounded-error o(log logn)-space PTMs in polynomial expected time. The same problem can be solvable by a one-way Las Vegas (or exact two-way) QFA with quantum head in linear (expected) time. 3. There is a promise problem solvable by a Las Vegas realtime QFA, but not by any bounded-error realtime PFA. The same problem can be solvable by an exact two-way QFA in linear expected time but not by any exact two-way PFA. 4. There is a family of promise problems such that each promise prob-lem can be solvable by a two-state exact realtime QFAs, but, there is no such bound on the number of states of realtime bounded-error PFAs solving the members this family. Our results imply that there exist zero-error quantum computational de-vices with a single qubit of memory that cannot be simulated by any finite memory classical computational model. This provides a computa-tional perspective on results regarding ontological theories of quantum mechanics [19], [30]. As a consequence we find that classical automata based simulation models [23], [6] are not sufficiently powerful to simu-late quantum contextuality. We conclude by highlighting the interplay between results from automata models and their application to develop-ing a general framework for quantum contextuality