A Proposal for Research on Quantum Computation and Clustering Algorithms

量子计算是一个重要的新领域，它动摇了计算复杂性理论和算法的基础。本项目研究了该主题的几个方面：使用“负概率”来设计用于随机生成和近似计数的高效量子算法。进一步探索“自旋世界”和“子图世界”之间的新傅立叶变换关系，以解决所有相互作用为负的情况下Ising模型Gibbs抽样问题。进一步研究傅里叶变换的群论性质，为图同构等问题设计有效的量子算法。特别地，这涉及到研究非交换群（如对称群）的线性表示。基于核磁共振实验的量子计算机新误差模型的研究目前正在伯克利进行。正式标准的表述，以证明这些实验中的计算本质上是量子力学的。类BQP与经典复杂性类的比较，包括多项式层次结构，最显著的是近似计数。NP的量子模拟的研究。此外，本项目研究了一个基本算法任务-聚类的经典随机算法：从R中的概率分布中采样一系列点，该概率分布可以是具有多个模式（集中概率区域）的分布族的任何成员。是否存在一种有效的算法来推断被采样分布的准确估计？这形式化了一个与集群相关的非常普遍的问题。给定一个图，将其顶点划分为两个集合，使得交叉边的数量与较小集合中顶点的数量之比为最小的常数因子。这个问题的加权版本是著名的估计图的电导到一个常数因子的问题。它将一个具体的聚类问题公式化。

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.