6533b7d8fe1ef96bd126b7cc

RESEARCH PRODUCT

Implications of quantum automata for contextuality

subject

description

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: There is a promise problem solvable by an exact two way QFA in exponential expected time but not by any bounded error sublogarithmic space probabilistic Turing machine (PTM). There is a promise problem solvable by an exact two way QFA in quadratic expected time but not by any bounded error o(loglogn) 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. 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. There is a family of promise problems such that each promise problem 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 devices with a single qubit of memory that cannot be simulated by any finite memory classical computational model. This provides a computational perspective on results regarding ontological theories of quantum mechanics. As a consequence we find that classical automata based simulation models are not sufficiently powerful to simulate quantum contextuality. We conclude by highlighting the interplay between results from automata models and their application to developing a general framework for quantum contextuality.