Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

8 April 2014, Theoretical Computer Science Seminar, Niel de Beaudrap (CWI)

Speaker: Niel de Beaudrap (CWI)
Title: The computational power of "probabilities" from a finite field
Date: Tuesday 8 April 2014
Time: 11:00-12:00
Location: CWI room L017, Science Park 123, Amsterdam

Abstract

Probability distributions and quantum states are examples of abstract "distributions" over pieces of information, such as bit-strings, in which more than one bit-string may be a possible outcome. Probability distributions are vectors of non-negative reals; quantum states are vectors of complex-valued amplitudes, which may interfere destructively. To investigate the importance of interference in different settings than the real or complex numbers, we consider the power of computational models where the states are vectors over an arbitrary finite field F. We find that the notion of "efficient computation" in these models is captured exactly by powerful, but traditional, complexity classes. For instance, when F is the integers mod 2, the power of this computational model is the class Parity-P, which contains the problems UNIQUE-SAT and GRAPH ISOMORPHISM.

Please note that this newsitem has been archived, and may contain outdated information or links.