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

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.