Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > WORD PROBLEM:
Reports tagged with word problem:
TR19-107 | 29th July 2019
Zachary Remscrim

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

Revisions: 1

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 ... more >>>

TR19-182 | 9th December 2019
Zachary Remscrim

#### The Limitations of Few Qubits: One-way and Two-way Quantum Finite Automata and the Group Word Problem

Revisions: 1

The two-way finite automaton with quantum and classical states (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 only a single-qubit can recognize the language \$L_{pal}=\{w \in \{a,b\}^*:w \text{ is ... more >>>

ISSN 1433-8092 | Imprint