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; that is, given a tensor formula
F of order
n×1 over a semiring
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6V1G-4GWBC5S-4-9/0?wchp=dGLbVtz-zSkWb)
plus a positive integer
k, deciding whether the
kth partial trace of the matrix
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6V1G-4GWBC5S-4-4/0?wchp=dGLbVtz-zSkWb)
fulfills a certain property. We use this to show that a certain promise version of the sum-free partial trace problem is complete for the class pr- BPP (promise BPP) for formulas over the semiring
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6V1G-4GWBC5S-4-B/0?wchp=dGLbVtz-zSkWb)
of the positive rational numbers, for pr-BQP (promise BQP) in the case of formulas defined over the field
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6V1G-4GWBC5S-4-C/0?wchp=dGLbVtz-zSkWb)
, and if the promise is given up, then completeness for PP is shown, regardless whether tensor formulas over positive rationals or rationals in general are used. This suggests that the difference between probabilistic and quantum polytime computers may ultimately lie in the possibility, in the latter case, of having destructive interference between computations occurring in parallel. Moreover, by considering variants of this problem, classes like
P, NP,
C