Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

On Models of Quantum Computation

Probability

Speaker: Manny Knill, Los Alamos National Laboratory
Location: 693 Kerr
Start time: Tue, Nov 27 2001, 4:10PM

Quantum computation and information enables more efficient problem solving in four main areas (so far): Experimental number theory (e.g. factoring), quantum physics modelling, combinatorial searching, and communication. Algorithms in these areas are designed for the standard model of quantum computation. There are many other models of quantum computation. These models can be cast in terms of linear representations of monoids presented by generators. What are the relationships between the computational power of these models? For the few examples known, the power is either very weak in a sense to be defined, or equivalent to standard quantum computation. The talk will begin with a short, information-focused introduction to quantum computation. The models of quantum computation will be then introduced from the point of view of monoids. Several possible definitions of computation are possible in each case, two of which are: 1. Non-deterministic computation, which is equivalent to an ability to efficiently calculate certain traces. 2. Standard computation, which corresponds to the ability to sample from probability distributions associated with the representation of the monoid. The known results about the power of these models will be overviewed.

Bruno Nachtergaele is the host.