AF: Small: Quantum Computational Pseudorandomness with Applications

AF：小：量子计算伪随机性及其应用

• 批准号: 2041841
• 负责人: Fang Song
• 金额: $ 20.21万
• 依托单位: Portland State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-03-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2041841&HistoricalAwards=false
• 关键词: AF; Small; Quantum; Computational; Pseudorandomness

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.

伪随机性是真实随机性的有效近似，在算法设计，编码理论，加密和复杂性理论中已成为必不可少的。该项目旨在在量子信息处理的设置中发展一个综合计算伪随机性理论。这些伪随机对象和工具可用于量子算法设计和量子复杂性理论。该项目对计算领域以外的某些问题的计算方法可以刺激计算机科学家，量子信息理论家和物理学家之间的进一步协作。 课程开发，协助当地的``CS''一章和``技术中的女性''事件的发展，在大学的量子计算中建立利益群体，以吸引不足代表的学生，以及向高中生推广是该奖项不可或缺的一部分。这些特定的重点是对计算机和意义上的重要性，这与真正的观点相关。有三个主要的目标：1）与两个基本的经典伪和量子对象类似，正式化和设计伪量子量子状态和量子运算符 - 伪随机生成器和伪随机函数； 2）研究他们在计算机科学中的应用，尤其是在量子密码学中，例如构建量子资金，量子身份验证和新颖的令牌密码学的原始原始。这需要开发适当的量子安全模型并设计新方案； 3）开发其他量子伪随机物体，并探索超出计算机科学以外的应用程序，例如了解黑洞和物理中的热化。所提出的伪随机对象和要开发的技术可以为某些提出的应用程序提供更有效的解决方案，甚至可以在信息理论设置中克服一些无需的结果。这项研究补充了量子状态和统一设计的工作，这是量子HAAR随机性的统计近似。他们可以一起揭示更多有关量子信息的基本属性的见解。在其他地方，计算机科学以外的研究问题的计算镜头可能是富有成果的。该奖项反映了NSF的法定任务，并且使用基金会的知识分子优点和更广泛的影响审查标准，被认为值得通过评估来获得支持。

项目成果

Oblivious Transfer is in MiniQCrypt

• DOI: 10.1007/978-3-030-77886-6_18
• 发表时间: 2020-11
• 期刊: ArXiv
• 作者: A. Grilo;Huijia Lin;F. Song;V. Vaikuntanathan