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.
