On computation with 'probabilities' modulo k

Original · EN

We propose a framework to study models of computation of indeterministic data, represented by abstract "distributions". In these distributions, probabilities are replaced by "amplitudes" drawn from a fixed semi-ring S, of which the non-negative reals, the complex numbers, finite fields Fₚᵣ, and cyclic rings Zₖ are examples. Varying S yields different models of computation, which we may investigate to better understand the (likely) difference in power between randomised and quantum computation. The "modal quantum states" of Schumacher and Westmoreland [arXiv:1010.2929] are examples of such distributions, for S a finite field. For S = F₂, Willcock and Sabry [arXiv:1102.3587] show that UNIQUE-SAT is solvable by polynomial-time uniform circuit families consisting of invertible gates. We characterize the decision problems solvable by polynomial uniform circuit families, using either invertible or "unitary" transformations over cyclic rings S = Zₖ, or (in the case that k is a prime power) finite fields S = Fₖ. In particular, for k a prime power, these are precisely the problems in the class ModₖP.