CAREER: Quantum Complexity and Polynomial Approximations of Boolean Functions

这个项目调查两个不同但相互交织的研究领域：（A）量子计算复杂性，（B）布尔函数的多项式逼近及其在量子和经典复杂性中的应用。目标是：（1）开发基本的数学工具来分析量子计算的内在能力和局限性，（2）丰富布尔函数的多项式近似与量子和经典复杂性理论的联系，以及开发解决相应近似问题的基本技术。为了实现这两个目标，量子和经典复杂性的广泛问题，以及相关的近似问题正在研究中，与来自近似理论，调和分析，矩阵分析，凸性等技术。方向（B）也是PI的长期目标的一部分，即发展布尔函数的多项式逼近理论，在其目前阶段仍有基本障碍需要克服。布尔函数多项式逼近的研究将为计算机科学提供来自经典数学的强大工具，并促进近似理论和计算理论两个领域的合作。量子计算有望带来革命性的变化，通过其在信息处理的效率和安全性方面优于当前技术的优势，对社会产生深远的影响。该项目可以为量子信息处理的基础做出重大贡献。

This project investigates two different but intertwined linesof research: (A) quantum computational complexity, and, (B) polynomial approximation of Boolean functions and its applications in quantum and classical complexity. The goals are: (1) to develop fundamental mathematical tools for analyzing the inherent power and limitations of quantum computing, and (2)to enrich the connections of polynomial approximations of Booleanfunctions with quantum and classical complexity theory, as well as to develop fundamental techniques to solve the corresponding approximation problems. Towards these tow goals, a wide range of problems in both quantum and classical complexity, as well as related approximation problems are being investigated, with techniques drawn from approximation theory, harmonic analysis, matrix analysis, convexity, etc.. Direction (B) is also part of the PI's longer term objective to develop a theory of polynomial approximations of Boolean functions, which at its current stage still has fundamental obstacles to overcome.The research on polynomial approximations of Boolean functions would provide powerful tools from classical mathematics for computer science, and promote collaborations between the twocommunities from approximation theory and theory of computation.Quantum computing promises revolutionary, far-reaching impacts on the society through its paramount superiority over current technologies in the efficiency and the security of information processing. This project could contribute significantly to the foundations of quantum information processing.