AF: Small: Harmonic Analysis for Quantum Complexity

AF：小：量子复杂性的谐波分析

• 批准号: 1618679
• 负责人: Ryan O'Donnell
• 金额: $ 45万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-06-01 至 2019-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1618679&HistoricalAwards=false
• 关键词: AF; Small; Harmonic; Analysis; Quantum

The PI will conduct new research to advance the field of harmonic analysis of Boolean functions. At a high level, harmonic analysis can be described as the theory of using a particular mathematical tool, the Fourier transform, for detecting, analyzing, and representing patterns in large data sets. Applying it in the context of Boolean functions refers to the case where the data comes from 0s and 1s, the basic building blocks in computer science. Harmonic analysis of Boolean functions has proven to be a powerful tool in computer science, with application to theories of machine learning, error-correcting codes, cryptography, privacy, optimization algorithms, and distributed computing. Part of the aim of this project is to further develop the mathematical and computer science foundations of harmonic analysis of Boolean functions. Another aim of the project is to expand its scope to include further applications in the field of quantum computation. If and when quantum computers are built, it is known that they will be able to break cryptographic codes that are secure today; this is fundamentally due to their ability to efficiently perform Fourier transforms on huge data sets. However the full potential power of quantum computation is not well understood, and building quantum computers remains a major engineering challenge. The project will investigate these issues, analyzing the advantages of quantum computers over classical ones, and understanding how to more efficiently test components of quantum computers. A final key outcome of the project will be scientific and educational training for computer science graduate students at Carnegie Mellon University, as well as wide dissemination of the research produced. At a more technical level, the project has several major-stretch-goals that will be used to guide the research in harmonic analysis of Boolean functions. Included among these are conjectures of Aaronson and Ambainis concerning the influence of variables on low-degree Boolean functions, and on the decision tree complexity of checking correlation of a function with its Fourier transform. Proofs of these conjectures would yield new complexity results delimiting the power of quantum computation versus classical computation. Another major technical goal of the project is to develop the theory of learning and testing an unknown quantum state.

PI 将开展新的研究来推进布尔函数调和分析领域的发展。 在高层次上，谐波分析可以描述为使用特定数学工具（傅立叶变换）来检测、分析和表示大型数据集中的模式的理论。 在布尔函数中应用它是指数据来自 0 和 1（计算机科学中的基本构建块）的情况。 布尔函数的调和分析已被证明是计算机科学中的强大工具，可应用于机器学习、纠错码、密码学、隐私、优化算法和分布式计算的理论。 该项目的部分目的是进一步发展布尔函数调和分析的数学和计算机科学基础。 该项目的另一个目标是扩大其范围，以包括量子计算领域的进一步应用。 众所周知，如果量子计算机建成，它们将能够破解当今安全的密码。这从根本上来说是由于它们能够在巨大的数据集上有效地执行傅里叶变换。 然而，量子计算的全部潜在能力尚不清楚，构建量子计算机仍然是一项重大的工程挑战。 该项目将研究这些问题，分析量子计算机相对于经典计算机的优势，并了解如何更有效地测试量子计算机的组件。该项目的最终关键成果将是为卡内基梅隆大学计算机科学研究生提供科学和教育培训，以及广泛传播所产生的研究成果。 在更技术的层面上，该项目有几个主要目标，将用于指导布尔函数调和分析的研究。 其中包括 Aaronson 和 Ambainis 关于变量对低次布尔函数的影响以及对检查函数与其傅里叶变换的相关性的决策树复杂性的影响的猜想。 这些猜想的证明将产生新的复杂性结果，从而界定量子计算与经典计算的能力。 该项目的另一个主要技术目标是发展学习和测试未知量子态的理论。