CRII: AF: Theoretical Problems in Quantum Computation

CRII：AF：量子计算中的理论问题

• 批准号: 1755800
• 负责人: Xiaodi Wu
• 金额: $ 17.5万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-05-01 至 2022-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1755800&HistoricalAwards=false
• 关键词: CRII; AF; Theoretical; Problems; Quantum

In anticipation of quantum computers being utilized in the near future, this project seeks to find quantum advantages in machine-learning-like tasks that are ubiquitous in our daily life. Future quantum computers will take advantage of entanglement, a quantum property, that digital computers do not use. It is important to understand the essential role of entanglement in the computational power of quantum computers to be able to use it efficiently. This project consists of two sets of questions that touch upon central topics in quantum information (e.g., entanglement and its impact on complexity theory) and novel topics such as property testing. The first part of the project investigates the possibility of designing fast quantum algorithms for property testing of unknown classical distributions and quantum states, a well-motivated topic related to statistics, data analysis, and machine learning. The project aims to integrate techniques from classical property testing, quantum tomography, quantum walks, and so on. The second part of the project investigates the computational power of the absence of entanglement in the context of quantum Merlin-Arthur protocols with two provers (QMA(2)). It is a well-motivated problem due to its connection to the separability problem within quantum information as well as the Unique Games Conjecture in the field of approximation algorithm. Specific objectives include the study of (1) the k-extendible states and de Finetti theorems for the separability problem and (2) non-trivial error reduction schemes of QMA(2). The techniques used are primarily inspired by ideas from the sum-of-squares techniques in optimization, weak measurements and approximation theory.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.

为了预期在不久的将来使用量子计算机，该项目试图在我们日常生活中无处不在的类似机器学习的任务中找到量子优势。未来的量子计算机将利用数字计算机不使用纠缠（量子属性）。重要的是要了解纠缠在量子计算机的计算能力中的基本作用，以便能够有效地使用它。该项目由两组问题组成，涉及量子信息中的中心主题（例如纠缠及其对复杂性理论的影响）和诸如财产测试之类的新主题。该项目的第一部分研究了设计快速量子算法的可能性，用于对未知经典分布和量子状态的属性测试，这是一个与统计，数据分析和机器学习有关的良好动机主题。该项目旨在整合古典属性测试，量子断层扫描，量子步行等技术。该项目的第二部分调查了在量子梅林·阿瑟（Merlin-Arthur）方案的背景下使用两个摊贩（QMA（2））的计算能力。由于它与量子信息中的可分离性问题以及近似算法领域的独特游戏猜想的联系，这是一个动机的问题。具体目标包括（1）针对可分离性问题的K-扩展状态和DE Finetti定理的研究，以及（2）QMA的非平凡误差减少方案（2）。所使用的技术主要是受到优化，弱测量和近似理论的想法的启发。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子和更广泛的影响的评估来支持的。 。

项目成果

Quantum Query Complexity of Entropy Estimation

熵估计的量子查询复杂度

• DOI: 10.1109/tit.2018.2883306
• 发表时间: 2019
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Li, Tongyang;Wu, Xiaodi
• 通讯作者: Wu, Xiaodi