AF: Small: Quantum Computational Pseudorandomness with Applications

伪随机性作为真实随机性的一种有效近似，已经成为算法设计、编码理论、密码学和复杂性理论中不可或缺的一部分。该项目旨在发展量子信息处理背景下的计算伪随机性的综合理论。这些伪随机对象和工具可以在量子算法设计和量子复杂性理论中使用。该项目对传统计算领域之外的一些问题的计算方法可以刺激计算机科学家，量子信息理论家和物理学家之间的进一步合作。 课程开发、协助当地“计算机科学中的女性”分会和“技术中的女性”活动的发展、在大学建立量子计算兴趣小组以吸引代表性不足的学生以及向高中生推广是该奖项的一个组成部分。该奖项的具体重点是计算伪随机性，就有效观察者而言，它与真正的随机性没有区别。主要目标有三个：1）类比于两个基本的经典伪随机对象--伪随机发生器和伪随机函数，形式化和设计伪随机量子态和量子算符; 2）研究它们在计算机科学，特别是量子密码学中的应用，如构造量子货币、量子认证和一种新的令牌化密码学原语。这就需要开发适当的量子安全模型和设计新的方案; 3）开发其他量子伪随机对象，探索计算机科学以外的应用，如理解物理学中的黑洞和热化。拟开发的伪随机对象和技术可以为一些拟议的应用提供更有效的解决方案，甚至可以克服信息理论环境中的一些不可行的结果。这项研究补充了量子态和幺正设计的工作，这是量子Haar随机性的统计近似。总之，它们可以揭示更多关于量子信息基本性质的见解。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.