  We study the computational complexity of the problem SFT (Sum-free Formula
partial Trace): given a tensor formula F over a subsemiring of the complex
field (C,+,.) plus a positive integer k, under the restrictions that all inputs
are column vectors of L2-norm 1 and norm-preserving square matrices, and that
the output matrix is a column vector, decide whether the k-partial trace of
$F\dagg{F}$ is superior to 1/2. The k-partial trace of a matrix is the sum of
its lowermost k diagonal elements. We also consider the promise version of this
problem, where the 1/2 threshold is an isolated cutpoint. We show how to encode
a quantum or reversible gate array into a tensor formula which satisfies the
above conditions, and vice-versa; we use this to show that the promise version
of SFT is complete for the class BPP for formulas over the semiring (Q^+,+,.)
of the positive rational numbers, for BQP in the case of formulas defined over
the field (Q,+,.), and for P in the case of formulas defined over the Boolean
semiring, all under logspace-uniform reducibility. This suggests that the
difference between probabilistic and quantum polynomial-time computers may
ultimately lie in the possibility, in the latter case, of having destructive
interference between computations occuring in parallel.
