A Common Algebraic Description for Probabilistic and Quantum Computations

摘要

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 ⊕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.