AF: CIF: Small: Theoretical Studies in Quantum Information and Computation

这个项目旨在加深我们对量子信息处理的两个基本方面的理解。(1)纠缠操作和分类。量子纠缠在量子信息处理中起着核心作用。量子纠缠理论的一个目标是通过不需要量子通信的操作，根据不同类型的纠缠的相互可转换性对不同类型的纠缠进行分类。虽然在这个框架中很好地理解了两部分纠缠，但三个或更多子系统之间的纠缠本质上要困难得多。PI正在研究多体，特别是三体纠缠的性质，重点是算法/计算复杂性的角度。(2)沟通的复杂性。通信复杂性研究分布式计算固有的通信代价。这个项目解决了三个重要的和相关的公开问题：描述确定性复杂性的Log-Rank猜想；寻找量子复杂性和经典复杂性之间可能存在的最大差距；以及纠缠是否可以显著降低量子通信的成本的问题。解决这些难题的计划是将重点放在一些受限制的功能类上，这些功能很简单，但在这些功能上问题仍然是开放和具有挑战性的。

This project aims to deepen our understanding on two fundamental aspects of quantum information processing.(1) Entanglement manipulations and classifications. Quantum entanglement plays a central role in quantum information processing. An objective of the theory of quantum entanglement is to classify different types of entanglement according to their inter-convertibility through manipulations that do not require quantum communication. While bipartite entanglement is well understood in this framework, entanglement among three or more subsystems is inherently much more difficult. The PI is investigating properties of multipartite, especially tripartite, entanglement, with an emphasis of the algorithmic/computational complexity perspective. (2) Communication complexity. Communication complexity studies the inherent communication cost for distributed computing. This project addresses three important and related open problems: the Log-Rank Conjecture for characterizing the deterministic complexity; finding the largest possible gaps between the quantum and classical complexities; and the question if entanglement can dramatically reduce the cost for quantum communication. The plan to attack those difficult problems is to focus on some restricted classes of functions that are simple yet on which the problems remain open and challenging.