Collaborative Research: FET: Small: Theoretical Foundations of Quantum Pseudorandom Primitives

伪随机性(看起来比实际更随机的信息)的研究是计算理论的基础，特别是在密码学和计算机安全方面。近年来，由于伪随机性在量子密码学、量子机器学习和高能物理等领域的应用，伪随机性的概念在量子计算领域得到了广泛的关注。这个项目的目标是系统地发展量子伪随机性的理论基础，并探索这一概念的进一步应用。该项目包括教育和宣传部分，包括本科生研究机会和关于这一主题的公开讲座。此外，拟议的研究将通过积极招募和支持代表性不足的群体的成员，促进理论计算机科学社区的发展。该项目分为三个部分。在第一部分中，我们将研究最近引入的量子伪随机性概念--伪随机态生成器的性质和构造。在第二部分，我们将研究量子伪随机性的新概念以及它们之间的关系。在第三部分中，我们将探索量子伪随机性概念的密码应用。为了实现这些目标，将使用从理论计算机科学到量子信息理论的一系列技术。此外，从这个项目中获得的见解将有助于揭示量子信息的基本属性，并可能对量子计算和量子引力的研究产生更广泛的影响。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The study of pseudorandomness (information that appears more random than it actually is) is fundamental in the theory of computing, especially in cryptography and computer security. Recently, the concept of pseudorandomness has gained significant interest in the field of quantum computing because of applications to areas such as quantum cryptography, quantum machine learning, and high energy physics. The goal of this project is to systematically develop the theoretical foundations of quantum pseudorandomness and explore further applications of the concept. The project has educational and outreach components, including undergraduate research opportunities and public lectures on the topic. In addition, the proposed research will contribute to the development of a more diverse and inclusive community in theoretical computer science by actively seeking to recruit and support members of underrepresented groups.The project is divided into three components. In the first component, the properties and the constructions of pseudorandom state generators, a recently introduced quantum pseudorandomness notion, will be investigated. In the second component, novel notions of quantum pseudorandomness and their relationships with each other will be investigated. In the third component, the cryptographic applications of quantum pseudorandomness notions will be explored. A range of techniques from theoretical computer science and quantum information theory will be employed to achieve these goals. Furthermore, the insights gained from this project will shed light on the fundamental properties of quantum information and may have broader implications for quantum computation and the study of quantum gravity.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.