Quantum Computation and Complexity Theory

PI: Steven homer提案号：9988310机构：Boston university摘要计算复杂性理论的两个互补领域将被研究。首先是量子计算的复杂性，这是我和我的同事在过去两年中开始研究的一个项目。到目前为止，已经完成了两个项目，都是关于寻找量子计算类的下界。我建议继续探索量子计算的力量，并尝试通过将量子类与经典复杂性理论联系起来，获得下界和上界。第二个领域涉及PSPACE中自然组合函数的复杂性理论研究。这里的目标是利用多项式层次结构的扩展，这些扩展在之前关于超多项式层次结构的文章中已经定义和说明过。为了对PSPACE中的计数问题和其他自然复杂问题进行分类，将研究和扩展NP-jump和Toda定理等工具。我们打算探索这个新的框架来分类优化问题，并研究旧的概念，如交替和我们已经定义的扩展多项式层次之间的关系。

PI: Steven HomerProposal Number: 9988310Institution: Boston UniversityAbstractTwo complementary areas of computational complexity theory will be studied. The first is the complexity of quantum computing, a project that my colleagues and I have begun work on during the past two years. To this point two projects have been completed, both concern finding lower bounds for classes of quantum computations. I propose to continue to explore the power of quantum computation and try to obtain both lower and upper bounds by relating quantum classes to classical complexity theory. The second area concerns the study of the complexity theory of natural combinatorial functions in PSPACE. Here the goal is to make use of the extensions of the polynomial hierarchy, which were defined and explicated in an earlier paper on the hyperpolynomial hierarchy. Tools such as the NP-jump and the methods of Toda's theorem will be studied and extended in order to classify counting problems and other natural complex problems in PSPACE. We intend to explore this new framework for the classification of optimization problems and to study the relationship between older notion such as alternation and the extended polynomial hierarchies which we have defined.