Complexity and Robustness of Quantum Entanglement

量子计算正在极大地影响着我们对信息处理的可能性和局限性的理解。利用自然界反直觉的量子效应的计算机器将能够比任何只基于经典原理的计算机更快地执行某些任务，例如模拟量子物理、搜索大型数据库或破解广泛使用的密码。******量子信息处理中最有趣的一个方面是被称为“量子纠缠”的物理现象，这是两个遥远的粒子之间的一种无法用经典方法解释的相关性。尽管纠缠最初是量子物理学中的一个哲学好奇，但这些“幽灵般的”相关性已被认为是各种信息处理任务的重要资源。例如，量子纠缠是经典测试随机数生成协议的关键组成部分——这在经典世界中是不可能完成的任务。******过去二十年的主要经验是，高纠缠复杂性是量子态的普遍特征。今天，量子信息理论的前沿挑战是理解这种复杂纠缠的鲁棒性。到目前为止，我们对纠缠复杂性的大部分理解都属于高度理想化的设置：例如，无错误量子计算机的状态，或极低温下的物理系统，预计将无法进行有效的经典模拟。但是嘈杂的量子计算设备，或者室温下的物理系统呢？复杂的纠缠能在这些环境中持续存在吗？******本研究计划的首要目标是解决复杂纠缠的稳健性这一重要主题。我提出了一个研究计划，主要追求两个方向，以以下问题为例：(a)复杂纠缠能否以耐噪声的方式得到经典认证？(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.**