AF: Medium: Center for Quantum Algorithms and Complexity

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