AF: Small: Harmonic Analysis for Quantum Complexity

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

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.