A Common Algebraic Description for Probabilistic and Quantum Computations (Extended Abstract)
Martin Beaudry, José M. Fernandez, Markus Holzer · Mathematical Foundations of Computer Science · 2004
Through the study of gate arrays we develop a unified frame- work to deal with probabilistic and quantum computations, where the former is shown to be a natural special case of the latter. On this ba- sis 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 ⊕P, 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.