AF: Small: Quantum Computational Pseudorandomness with Applications

Portland State University, Portland OR

Investigators

Abstract

Pseudo-randomness, an efficient approximation for true randomness, has become indispensable in algorithm design, coding theory, cryptography and complexity theory. This project aims to develop a comprehensive theory of computational pseudo-randomness in the setting of quantum information processing. These pseudo-random objects and tools can be useful in quantum algorithm design and quantum complexity theory. The computational approach of this project to some problems outside the conventional territory of computing could stimulate further collaboration between computer scientists, quantum information theorists and physicists. Course development, assisting the development of local ``Women in CS'' chapter and ``Women in Tech'' events, establishing interest groups in quantum computing at the university to attract underrepresented students, as well as outreach to high school students are an integral part of this award. This specific focus is on computational pseudorandomness, which is indistinguishable from true randomness as far as efficient observers are concerned. There are three major objectives: 1) formalize and design pseudorandom quantum states and quantum operators, in analogy to two basic classical pseudorandom objects -- pseudorandom generators and pseudorandom functions; 2) investigate their applications in computer science, especially in quantum cryptography such as constructing quantum money, quantum authentication, and a novel primitive of tokenized cryptography. This requires developing appropriate quantum security models and designing new schemes; 3) develop other quantum pseudorandom objects and explore applications beyond computer science such as understanding black holes and thermalization in physics. The proposed pseudorandom objects and techniques to be developed can provide more efficient solutions to some proposed applications or even overcome some no-go results in the information-theoretical setting. This study complements the work on quantum state and unitary designs, which are statistical approximations to the quantum Haar randomness. Together, they can reveal more insights to the fundamental properties of quantum information. The computational lens of studying problems beyond computer science can be fruitful elsewhere. 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.