A common algebraic description for probabilistic and quantum computations

Martin Beaudry, Jose M. Fernandez, Markus Holzer

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…