CRII: AF: Theoretical Problems in Quantum Computation

预计量子计算机将在不久的将来被使用，该项目旨在寻找在我们日常生活中无处不在的机器学习任务中的量子优势。未来的量子计算机将利用纠缠，这是一种量子特性，而数字计算机没有使用。重要的是要理解纠缠在量子计算机计算能力中的重要作用，以便能够有效地使用它。该项目包括两组涉及量子信息中心主题的问题（例如，纠缠及其对复杂性理论的影响）和新的主题，如属性测试。该项目的第一部分研究了设计快速量子算法用于未知经典分布和量子态的属性测试的可能性，这是一个与统计，数据分析和机器学习相关的积极主题。该项目旨在整合经典性质测试、量子层析成像、量子漫步等技术。项目的第二部分研究了量子Merlin-Arthur协议中没有纠缠的计算能力，其中有两个证明器（QMA（2））。由于它与量子信息中的可分性问题以及近似算法中的唯一博弈猜想有关，因此是一个很有意义的问题。具体目标包括研究（1）k-可扩展状态和de Finetti定理的可分性问题和（2）非平凡的错误减少计划QMA（2）。所使用的技术主要是从最优化、弱测量和近似理论的平方和技术中获得灵感。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.