权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

CAREER: Quantum Complexity and Polynomial Approximations of Boolean Functions

职业：布尔函数的量子复杂性和多项式逼近

基本信息

批准号：
0347078
负责人：
Yaoyun Shi
金额：
$ 40万
依托单位：
Regents of the University of Michigan - Ann Arbor
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2004
资助国家：
美国
起止时间：
2004-03-15 至 2010-02-28
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=0347078&HistoricalAwards=false
关键词：
CAREER Quantum Complexity Polynomial Approximations

项目摘要

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.

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