CAREER: Complexity Theory of Quantum States: A Novel Approach for Characterizing Quantum Computer Science

Quantum computing can help solve some of the most complex problems in physics, chemistry, material design, optimization, and machine learning. Quantum complexity theory plays a crucial role in guiding the advancement of quantum computing. Nowadays, the study of quantum computing and quantum physics leads to many new computational tasks for dealing with quantum information. The theoretical framework in standard complexity theory might be insufficient to guide the investigation of these new problems. This award will provide a novel theoretical framework to steer the development of fast quantum algorithms for various new problems in quantum physics and computer science, and construct more secure quantum cryptography. Beyond technology, the award will support the (i) development of new quantum computing courses for science and engineering students that will be shared with nearby Hispanic-serving institutions in Houston, (ii) mentoring of students from underrepresented groups through the Research Emerging Scholars Program and the Quantum Research Experiences for Undergraduates Program, and (iii) institution of a Hybrid Quantum Computing Seminar to deepen the engagement with internal and external stakeholders in the quantum computing community. Quantum computing introduces many well-motivated computational tasks that ask to identify specific properties of input quantum states. For example, state tomography asks to learn the classical description of the input quantum states, and the security of quantum cryptography relies on the hardness of extracting information from quantum messages. However, the standard complexity theory for problems with classical inputs and outputs is inadequate for identifying the computational complexity of these new computational tasks. Therefore, this award seeks to advance the following three thrusts: (i) develop the complexity theory for problems that ask to identify specific properties of input quantum states, (ii) identify the security of quantum cryptographic primitives through the new complexity theory, and (iii) use the framework to characterize the computational hardness of variants of problems with quantum inputs. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.