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.