AF: Small: Quantum Computational Pseudorandomness with Applications

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

• 批准号: 1921047
• 负责人: Fang Song
• 金额: $ 26.88万
• 依托单位: Texas A&M Engineering Experiment Station
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-09-01 至 2020-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1921047&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.

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

项目成果

Pseudorandom Quantum States

伪随机量子态

• DOI: 10.1007/978-3-319-96878-0_5
• 发表时间: 2018-10
• 期刊: Part III
• 作者: Ji, Zhengfeng;Liu, Yi;Song, Fang
• 通讯作者: Song, Fang

General Linear Group Action on Tensors: A Candidate for Post-Quantum Cryptography

张量上的一般线性群作用：后量子密码学的候选者

• DOI: 10.1007/978-3-030-36030-6_11
• 发表时间: 2019-01
• 期刊: 17th Theory of Cryptography Conference
• 作者: Ji, Z.;Qiao, Y.;Song, F.;Yun, A.
• 通讯作者: Yun, A.

Zero-Knowledge Proof Systems for QMA

QMA 的零知识证明系统

• DOI: 10.1109/focs.2016.13
• 发表时间: 2016-04-11
• 期刊: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: Anne Broadbent;Zhengfeng Ji;F. Song;John Watrous
• 通讯作者: John Watrous