  We adapt the Deutsch-Josza algorithm to the context of formal language
theory. Specifically, we use the algorithm to distinguish between trivial and
nontrivial words in groups given by finite presentations, under the promise
that a word is of a certain type. This is done by extending the original
algorithm to functions of arbitrary length binary output, with the introduction
of a more general concept of parity. We provide examples in which properties of
the algorithm allow to reduce the number of oracle queries with respect to the
deterministic classical case. This has some consequences for the word problem
in groups with a particular kind of presentation.

Quantum Physics