QnTM: Collaborative Research: The Quantum Complexity of Algebraic Problems

QnTM：协作研究：代数问题的量子复杂性

• 批准号: 0524613
• 负责人: Cristopher Moore
• 金额: --
• 依托单位: University of New Mexico
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-08-01 至 2009-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0524613&HistoricalAwards=false
• 关键词: QnTM; Collaborative; Research; Quantum; Complexity

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.

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