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.