Complexity and Robustness of Quantum Entanglement

量子计算正在极大地影响我们对信息处理的可能性和局限性的理解。利用自然界反直觉量子效应的计算机将能够比任何仅基于经典原理的计算机更快地执行某些任务，例如模拟量子物理，搜索大型数据库或破解广泛使用的密码。 量子信息处理最有趣的方面之一是被称为“量子纠缠”的物理现象，这是两个遥远粒子之间的一种无法用经典解释的相关性。虽然纠缠开始是量子物理学中的一个哲学好奇心，但这些“幽灵般的”相关性已被公认为各种信息处理任务的重要资源。例如，量子纠缠是经典测试随机数生成的协议中的一个关键因素-这在经典世界中是不可能的。在过去的二十年里，我们学到的一个主要教训是，高纠缠复杂性是量子态的一个普遍特征。今天，量子信息理论的前沿挑战是理解这种复杂纠缠的鲁棒性。到目前为止，我们对纠缠复杂性的理解大多与高度理想化的设置有关：例如，无错误的量子计算机的状态，或极低温度下的物理系统，预计无法进行有效的经典模拟。但是，有噪声的量子计算设备，或者室温下的物理系统呢？复杂的纠缠能在这些环境中持续下去吗？ 这项研究计划的总体目标是解决复杂纠缠鲁棒性这一重要主题。我提出了一个研究计划，追求两个主要方向，举例说明了以下问题：（一）复杂的纠缠可以经典认证的噪声容忍的方式？（B）量子关联的计算复杂度是多少？ 发展对纠缠鲁棒性的更深入理解具有重要的理论和实践动机。在理论方面，研究上述问题可能涉及使用密码学，凝聚态物理学，复杂性理论等的概念和技术。这些答案将丰富我们对各种环境中量子纠缠的计算和信息论方面的理解。在实践方面，研究纠缠的鲁棒性是一个及时的话题，因为我们进入了“嘈杂的中等规模量子”时代，谷歌和IBM等公司即将用几百个嘈杂的量子比特构建量子计算机。需要严格的方法来测试有噪声的量子设备，并证明这些设备能够执行超过经典计算机能力的计算。

Quantum computing is dramatically impacting our understanding of the possibilities and limits of information processing. Computing machines taking advantage of the counter-intuitive quantum effects of Nature will be able to perform certain tasks much faster than any computer based only on classical principles, such as simulating quantum physics, searching large databases, or breaking widely used cryptographic codes. One of the most intriguing aspects of quantum information processing is the physical phenomenon known "quantum entanglement," which is a type of correlation between two distant particles that cannot be explained classically. Although entanglement began as a philosophical curiosity within quantum physics, these "spooky" correlations have been recognized as an important resource for a variety of information processing tasks. For example, quantum entanglement is a crucial ingredient in protocols for classically testing random number generation --- a task not possible in the classical world. A primary lesson learned over the past two decades is that high entanglement complexity is a general feature of quantum states. Today, the frontier challenge in quantum information theory is understanding the robustness of such complex entanglement. So far, much of our understanding of the complexity of entanglement pertains to highly idealized settings: for example, the states of an error-free quantum computer, or physical systems at extremely low temperature, are expected to defy efficient classical simulation. But what about noisy quantum computing devices, or physical systems at room temperature? Can complex entanglement persist in these settings? The overarching goal of this research proposal is to address this important theme about the robustness of complex entanglement. I propose a research program that pursues two main directions, exemplified by the following questions: (a) Can complex entanglement be classically certified in a noise-tolerant manner? and (b) What is the computational complexity of quantum correlations? Developing a deeper understanding of the robustness of entanglement has significant theoretical as well as practical motivation. On the theoretical side, studying the questions above will likely involve using concepts and techniques from cryptography, condensed matter physics, complexity theory, and more. The answers will enrich our understanding of the computational and information-theoretic aspects of quantum entanglement in a variety of settings. On the practical side, studying robustness of entanglement is a timely topic as we enter the "Noisy Intermediate-Scale Quantum" era, where companies such as Google and IBM are on the verge of constructing quantum computers with a few hundred noisy qubits. There is a a demand for rigorous methods for testing noisy quantum devices, and furthermore, demonstrating that such devices are capable of performing computations that exceed the capabilities of classical computers.