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