AF: Small: Quantum Computational Pseudorandomness with Applications

伪随机性是真随机性的一种有效近似，在算法设计、编码理论、密码学和复杂性理论中都是不可或缺的。该项目旨在发展量子信息处理背景下的计算伪随机性的全面理论。这些伪随机对象和工具在量子算法设计和量子复杂性理论中都是有用的。该项目对传统计算领域以外的一些问题的计算方法，可能会促进计算机科学家、量子信息理论家和物理学家之间的进一步合作。这一奖项的一个组成部分是课程开发、协助发展当地的“妇女在CS中”分会和“在科技中的妇女”活动、在大学建立量子计算兴趣小组以吸引代表性不足的学生以及向高中生推广。这一具体重点是计算伪随机性，就有效的观察者而言，这与真正的随机性没有什么区别。主要目标有三个：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.