QnTM: Collaborative Research EMT: The Quantum Complexity of Algebraic Problems

量子计算提供了强大的新方法来解决密码问题，其效率远远高于经典计算机。该项目侧重于开发新的量子算法来解决图同构等问题，这些问题在经典计算机上没有已知的有效算法。我们主要研究隐子群问题（HSP）及其相关问题。HSP框架首次出现在Simon和Shor的开创性工作中，在那里它导致了计算数论中几个基本问题的有效量子算法，包括整数分解和计算离散对数。特别是，循环组上的HSP的Shor算法使得破解RSA公钥密码系统成为可能。在Simon和Shor算法中出现的隐藏子群问题发生在交换群上，这是HSP的一个例子，现在已经很好地理解了。非交换隐子群问题与几个重要的问题密切相关，包括图同构、隐移位问题和最短格向量问题的重要密码学案例。然而，尽管有这些激励措施，非交换HSP迄今为止在很大程度上抵制了量子计算社区的进步。有效的算法只适用于少数群体，甚至对问题的信息理论方面也知之甚少。该项目将寻求有效的量子算法和对称群的查询复杂度下界-与图同构相关的HSP的情况-以及其他算法感兴趣的组。我们的方法应用了丰富的数学工具，包括表示理论、自适应基和多个协集状态的纠缠测量。

Quantum computing offers powerful new ways to solve cryptographic problems far more efficiently than classical computers can. This project focuses on the development of new quantum algorithms for problems such as Graph Isomorphism, for which there is no known efficient algorithm on classical computers. We focus on the Hidden Subgroup Problem (HSP) and its relatives. The HSP framework made its first appearance in the seminal work of Simon and Shor, where it led to efficient quantum algorithms for several basic problems in computational number theory, including integer factoring and computing discrete logarithms. In particular, Shor's algorithm for the HSP on the cyclic group makes it possible to break the RSA public-key cryptosystem.The hidden subgroup problems appearing in Simon's and Shor's algorithms take place over commutative groups, a case of the HSP that is now well-understood. The noncommutative hidden subgroup problem is intimately linked to several problems of major interest, including Graph Isomorphism, hidden shift problems, and cryptographically important cases of the Shortest Lattice Vector problem. Despite these incentives, however, the noncommutative HSP has largely resisted the quantum computing community's advances thus far. Efficient algorithms are only known for a few families of groups, and even the information--theoretic aspects of the problem are poorly understood. This project will seek both efficient quantum algorithms and query-complexity lower bounds for the symmetric group---the case of the HSP relevant to Graph Isomorphism---and other groups of algorithmic interest. Our approach applies the rich mathematical tools of representation theory, adapted bases, and entangled measurements over multiple coset states.