CAREER: Quantum Complexity and Polynomial Approximations of Boolean Functions

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

This project investigates two different but intertwined lines of 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 Boolean functions 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 two communities 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.