Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR19-107 | 29th July 2019 16:32

The Power of a Single Qubit: Two-way Quantum/Classical Finite Automata and the Word Problem for Linear Groups


Authors: Zachary Remscrim
Publication: 18th August 2019 16:27
Downloads: 117


The two-way quantum/classical finite automaton (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA, with a single qubit, can recognize, with one-sided bounded-error, the language $L_{eq}=\{a^m b^m |m \in \mathbb{N}\}$ in expected polynomial time and the language $L_{pal}=\{w \in \{a,b\}^*|w \text{ is a palindrome}\}$ in expected exponential time.

We further demonstrate the power of 2QCFA by showing that they can recognize the word problems of a broad class of groups. In particular, we first restrict our attention to 2QCFA that: $(1)$ have a single qubit, $(2)$ recognize their language with one-sided bounded-error, and $(3)$ have transition amplitudes which are algebraic numbers. We show that such 2QCFA can recognize the word problem of any finitely-generated virtually abelian group in expected polynomial time, as well as the word problem of a large class of linear groups in expected exponential time. This latter class includes all groups whose word problem is a context-free language as well as all groups whose word problem is known to be the intersection of finitely many context-free languages. As a corollary, we obtain a direct improvement on the original Ambainis and Watrous result by showing that $L_{eq}$ can be recognized by a 2QCFA with better parameters.

We also consider those word problems which a 2QCFA can recognize with one-sided unbounded-error, and show that this class includes the word problem of more exotic groups such as the free product of any finite collection of finitely-generated free abelian groups. As a corollary of this result, we demonstrate that a new class of group word problems are co-stochastic languages. Lastly, we exhibit analogous results for 2QCFA with any finite number of qubits or with more general transition amplitudes, as well as results for other classic QFA models.

ISSN 1433-8092 | Imprint