AF: Small: Quantum Computational Pseudorandomness with Applications

伪随机性是对真随机性的一种有效逼近，在算法设计、编码理论、密码学和复杂性理论中都占有重要地位。本项目旨在发展量子信息处理中计算伪随机性的综合理论。这些伪随机对象和工具可用于量子算法设计和量子复杂性理论。这个项目的计算方法解决了传统计算领域之外的一些问题，可以促进计算机科学家、量子信息理论家和物理学家之间的进一步合作。课程开发，协助当地“CS女性”分会和“Tech女性”活动的发展，在大学建立量子计算兴趣小组以吸引代表性不足的学生，以及向高中生推广，都是该奖项的组成部分。这个特定的焦点是计算伪随机性，就有效观察者而言，它与真正的随机性是无法区分的。有三个主要目标：1)形式化和设计伪随机量子态和量子算子，类比于两个基本的经典伪随机对象——伪随机生成器和伪随机函数；2)研究它们在计算机科学中的应用，特别是在量子密码学中的应用，如构建量子货币、量子认证和一种新的标记化密码学原语。这需要开发合适的量子安全模型并设计新的方案；3)开发其他量子伪随机对象，探索计算机科学以外的应用，如理解物理学中的黑洞和热化。所提出的伪随机对象和有待开发的技术可以为某些已提出的应用提供更有效的解决方案，甚至可以克服信息理论设置中的一些不可行的结果。这项研究补充了量子态和酉设计的工作，这是量子哈尔随机性的统计近似。总之，它们可以揭示更多关于量子信息基本属性的见解。用计算的视角研究计算机科学以外的问题，在其他领域也能取得丰硕成果。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.