QnTM: Collaborative Research: The Quantum Complexity of Algebraic Problems

量子计算提供了强大的新方法来解决密码问题，效率远远高于经典计算机。这个项目致力于开发新的量子算法来解决图同构等问题，对于这些问题，在经典计算机上还没有已知的有效算法。我们主要研究隐子群问题(HSP)及其相关问题。HSP框架首次出现在Simon和Shor的开创性工作中，在那里它导致了计算数论中几个基本问题的高效量子算法，包括整数因式分解和计算离散对数。特别地，Shor关于循环群上的HSP的算法使得破解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.