Quantum computation is an important new area that has shaken the foundations of computational complexity theory and algorithms. This project investigates several aspects of this subject: Use of "negative probabilities" to design efficient quantum algorithms for random generation and approximate counting. Further exploration of the new Fourier transform relationship between the `spins world" and the "subgraphs world" to solve the Ising model Gibbs sampling problem in the case that all interactions are negative. The study of further group theoretic properties of the Fourier transform to design efficient quantum algorithms for problems such as graph isomorphism. In particular, this involves studying the linear representations of non-commutative groups such as the symmetric group. The study of new error models for quantum computers based on NMR experiments in quantum computation currently underway at Berkeley. The formulation of formal criteria to demonstrate that the computation in these experiments is inherently quantum mechanical. The comparison of the class BQP to classical complexity classes, including the polynomial hierarchy, and most notably approximate counting. The study of the quantum analog of NP. In addition this project studies classical randomized algorithms for a fundamental algorithmic task - clustering: A sequence of points is sampled from a probability distribution in R, which may be any member of a family of distributions which have several modes (regions of concentrated probability). Is there an efficient algorithm to infer an accurate estimate of the distribution being sampled? This formalizes a very general problem related to clustering. Given a graph, partition its vertices into two sets such that the ratio of the number of crossing edges to the number of vertices in the smaller sets is with in a constant factor of the minimum. The weighted version of this problem is the famous problem of estimating the conductance of a graph to with in a constant factor. It formulizes a clustering problem in a concrete setting.
