2014/05/28 by Niel de Beaudrap, de Beaudrap, Niel
Computer Science · #68Q05 #68Q10 #68Q12 #68Q15 #81P16 #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #F.1.1 #F.1.2 #F.1.3 #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.1405.7381
openalex publication_date 2014/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \mathbb Fpr, and cyclic rings \mathbb Zk 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 = \mathbb F2, 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 = \mathbb Zk, or (in the case that k is a prime power) finite fields S = \mathbb Fk. In particular, for k a prime power, these are precisely the problems in the class Modk\mathsf P.