2014/04/10 by Jibran Rashid, Rashid, Jibran, Abuzer Yakaryilmaz +1
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Formal Languages and Automata Theory (cs.FL) #Quantum Physics (quant-ph) #cs.CC #cs.FL #quant-ph
paper · pdf · doi:10.48550/arxiv.1404.2761
22 pages
arxiv created 2014/04/10 · arxiv updated 2014/04/11
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(log log n) -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 \citeHardy04, \citeMontina08. As a consequence we find that classical automata based simulation models \citeKleinmann11, \citeBlasiak13 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.