We propose definitions of \QAC^0, the quantum analog of the
classical class \AC^0 of constant-depth circuits with AND and OR
gates of arbitrary fan-in, and \QACC^0[q], the analog of the class
\ACC^0[q] where \Mod_q gates are also allowed. We show that it is
possible to make a `cat' state on ... more >>>

In this work we consider the term evaluation problem which involves, given a term over some algebra and a valid input to the term, computing the value of the term on that input. This is a classical problem studied under many names such as formula evaluation problem, formula value problem ... more >>>