AF: Small: The Quantum Complexity of Physical and Algebraic Problems

这一奖项旨在增加我们对量子计算机能力的了解。目标是确定哪些问题拥有有效的量子算法，哪些没有。问题的一个来源与量子力学系统的模拟有关。另一个方向是确定哪些密码系统是安全的，不受量子计算机的攻击。最常用的密码系统，如基于RSA和椭圆曲线的系统，可以被量子计算机破解，一个重要的问题是确定使用哪种系统来代替。这个问题既涉及了解哪些问题是量子计算机的难点，也涉及如何设计安全协议。PI和他的研究生将考虑三种类型的问题。第一个来自哈密顿复杂性，它解决了物理系统的计算属性。根据设置的不同，这些系统的范围从经典的可解到甚至对量子计算机来说都很难。第二组问题来自使用错误学习问题的量子抵抗密码术的建议。PI将研究最近做出的使这些系统更有效率的假设，以确定它们是否对量子计算机是安全的。第三组问题涉及确定在量子计算机存在的情况下，经典协议的安全论点何时有效。

This award aims to increase our understanding about the power of quantum computers. The goal is to determine which problems have efficient quantum algorithms and which do not. One source of problems relates to the simulation of quantum mechanical systems. Another direction is determining which cryptosystems are secure against quantum computers. The most commonly used cryptosystems, such as systems based on RSA and elliptic curves, can be broken by quantum computers and an important question is to determine which systems to use instead. This question involves both understanding which problems are hard for quantum computers as well as how to design secure protocols.The PI and his graduate students will consider three types of problems. The first comes from Hamiltonian complexity, which addresses computing properties of physical systems. Depending on the setup, these systems range from being solvable classically to being very hard even for quantum computers. The second set of problems comes from proposals for quantum-resistant cryptography using the Learning With Errors problem. The PI will study the recent assumptions that have been made to make these systems more efficient to see if they are secure against quantum computers. The third set of questions involves determining when the security arguments work for classical protocols in the presence of quantum computers.