AF: Medium: Center for Quantum Algorithms and Complexity

量子计算迫使我们对计算机科学的基础、密码系统的安全性和量子系统的性质的信念发生了巨大的变化。这个奖项关注的是从这个观点中产生的几个基本的算法问题。第一个是新量子算法的设计。这里的挑战是，量子算法设计的主要范式-隐藏子群框架-最近被证明在其适用性方面有严重的局限性。该中心将探索几种方法，包括通过张量网络的量子近似设计量子算法的新框架，以及使用量子算法发现隐藏的非线性结构的最新工作。确定量子算法的极限对于设计有效的经典密码系统的可能性同样重要，这些密码系统不受量子密码分析的影响。这种“后量子”密码系统可能在第一台工作的量子计算机建成之前就产生巨大的实际影响。要做到这一点，有必要更好地理解具体的经典密码系统（如基于格的密码系统或McEliese密码系统）的量子硬度。另一种方法是设计新的密码系统，其安全性基于隐藏子群框架中已经建立的量子硬度结果。该中心还将研究量子复杂性理论中的基本问题，包括量子交互证明系统的复杂性。可以说，最重要的挑战是证明著名的PCP定理的量子模拟。这将有广泛的影响，包括量子硬度的不可近似性的结果，改进的容错结果绝热量子计算，以及理论凝聚态物理的影响。另一个基本问题是多证明者量子交互证明系统的能力。解决这个复杂性类是否是NEXP的著名经典结果MIP = NEXP，预计将提供重要的见解量子纠缠的性质。

Quantum computation has forced a dramatic change in our beliefs about the foundations of computer science, the security of cryptosystems, and the nature of quantum systems. This award focuses on several fundamental algorithmic questions that arise out of this viewpoint. The first is the design of new quantum algorithms. The challenge here is that the major paradigm for the design of quantum algorithms - the hidden subgroup framework - has recently been shown to have severe limitations in its applicability. The center will explore several approaches, including a new framework for the design of quantum algorithms via the quantum approximation of tensor networks, as well as recent work on the use of quantum algorithms for discovering hidden nonlinear structures.Establishing the limits of quantum algorithms is equally important to the possibility of designing efficient classical cryptosystems that are immune to quantum cryptanalysis. Such "post-quantum" cryptosystems could have an enormous practical impact well before the first working quantum computer is ever built. For this to happen it is necessary to better understand the quantum hardness of concrete classical cryptosystems such as the lattice-based cryptosystems or the McEliese cryptosystem. A different approach would involve designing novel cryptosystems whose security is based on already established quantum hardness results in the hidden subgroup framework.The center would also study fundamental questions in quantum complexity theory, including the complexity of quantum interactive proof systems. Arguably the most important challenge is proving the quantum analog of the celebrated PCP theorem. This would have wide implications including quantum hardness of inapproximability results, improved fault-tolerance results for adiabatic quantum computing, as well as implications for theoretical condensed matter physics. Another fundamental question is the power of multi-prover quantum interactive proof systems. Resolving whether or not this complexity class is NEXP as in the celebrated classical result MIP = NEXP, is expected to provide important insights into the nature of quantum entanglement.