Implications of quantum automata for contextuality

Jibran Rashid, Abuzer Yakaryilmaz

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 r…