A common algebraic description for probabilistic and quantum computations (Extended abstract)

Through the study of gate arrays we develop a unified framework to deal with probabilistic and quantum computations, where the former is shown to be a natural special case of the latter. On this basis we show how to encode a probabilistic or quantum gate array into a sum-free tensor formula which satisfies the conditions of the partial trace problem, and vice-versa. In this way complete problems for the classes pr-BPP (promise BPP) and pr-BQP (promise BQP) are given when changing the semiring from (Q(+), +, (.)) to the field (Q, +, (.)). Moreover, by variants of the problem under consideration, classes like circle plusP, NP, C=P, its complement co-C=P, the promise version of Valiant's class UP, its generalization promise SPP, and unique polytime US are captured as problem property and the semiring varies.