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

量子计算可以帮助解决物理、化学、材料设计、优化和机器学习中的一些最复杂的问题。量子复杂性理论对量子计算的发展起着至关重要的指导作用。目前，量子计算和量子物理的研究为处理量子信息带来了许多新的计算任务。标准复杂性理论的理论框架可能不足以指导对这些新问题的研究。该奖项将为指导量子物理和计算机科学中各种新问题的快速量子算法的发展提供一个新的理论框架，并构建更安全的量子密码学。除了技术方面，该奖项还将支持(i)为科学和工程专业的学生开发新的量子计算课程，这些课程将与休斯顿附近的西班牙裔服务机构共享；（ii）通过新兴学者研究项目和本科生量子研究经验项目为代表性不足的群体的学生提供指导。（iii）举办混合量子计算研讨会，以加深与量子计算社区内部和外部利益相关者的接触。量子计算引入了许多动机良好的计算任务，这些任务要求识别输入量子态的特定属性。例如，状态层析成像要求学习输入量子态的经典描述，量子密码术的安全性依赖于从量子信息中提取信息的难度。然而，具有经典输入和输出问题的标准复杂性理论不足以识别这些新的计算任务的计算复杂性。因此，该奖项旨在推进以下三个重点：(i)发展要求识别输入量子态特定属性的问题的复杂性理论，（ii）通过新的复杂性理论识别量子密码原语的安全性，以及（iii）使用框架来表征具有量子输入的问题变体的计算硬度。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.