AF: Small: Quantum Theory, Computational Complexity, and Geometry/Topology

本项目的目的是探索量子理论、计算复杂性、几何和拓扑之间的关系，在几何/拓扑与计算复杂性的交叉点上，研究普通三维空间中的纽结和链环的拓扑性质以及三维流形的拓扑性质的计算难度。 例如，什么时候两个三维流形是相同的？或者，给出一个结的示意图，它是解开的结吗？ 该项目将探索两个容易的结果，即某些答案可以快速计算，可能需要人工帮助;和硬度结果，某些答案本质上很难计算。在量子理论和计算复杂性的交叉点上，该项目将考虑量子计算核心问题的容易结果和硬度结果。 我们这个时代最令人兴奋的数学发现之一是一种新型计算机的概念，量子计算机，它将能够运行在标准计算机上无法运行的新算法。 一个基本的问题，这将是解决这项研究是量子计算机将能够做什么，如果他们建成。在量子理论和几何和拓扑学的交叉，该项目将考虑几何问题与量子非局域性的影响所描述的爱因斯坦-波多尔斯基-罗森和约翰贝尔。 该项目还将考虑由量子计算中的量子纠错理论激发的新几何空间。该项目的更广泛影响开始其研究领域的重要性。特别是，如果量子计算机最终建成，那么它们对社会的影响将是巨大的。拟议的研究对量子计算有各种影响。该项目将通过arXiv电子打印服务器传播其结果，并帮助支持arXiv。该项目还将开发量子计算和计算复杂性的博览会。

The aim of the project is to explore relations between quantum theory, computational complexity, and geometry and topology.In the intersection of geometry/topology and computational complexity, the project will research the computational difficulty of topological properties of knots and links in ordinary 3-dimensional space, and of 3-dimensional manifolds. For instance, when are two 3-manifolds the same? Or, given a diagram of a knot, is it the unknot? The project will explore both easiness results, that certain answers can be computed quickly, possibly with artificial help; and hardness results, that certain answers are intrinsically difficult to compute.In the intersection of quantum theory and computational complexity, the project will consider both easiness results and hardness results for core problems in quantum computation. One of the most exciting mathematical discoveries of our era is the concept of a new type of computer, a quantum computer, that would be able to run new algorithms that cannot be run on a standard computer. A fundamental question which will be addressed by this research is what quantum computers would be able to do, if they were built.In the intersection of quantum theory and geometry and topology, the project will consider geometric problems with implications for quantum non-locality as described by Einstein-Podolsky-Rosen and by John Bell. The project will also consider new geometric spaces motivated by the theory of quantum error correction in quantum computation.The broader impacts of the project begin with the importance of its research areas. In particular, if quantum computers are eventually built, then their impact on society will be substantial. The proposed research has various implications for quantum computation. The project will disseminate its results through the arXiv e-print server, and help support the arXiv. The project will also develop expositions in quantum computation and computational complexity.