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的开创性工作中首次出现，在那里它导致了计算数论中几个基本问题的有效量子算法，包括整数分解和计算离散代数。 特别是，Shor的循环群上的HSP算法使得破解RSA公钥密码系统成为可能。Simon和Shor算法中出现的隐藏子群问题发生在交换群上，HSP的一个例子现在已经很好地理解。 非交换隐子群问题与几个主要问题密切相关，包括图同构，隐藏移位问题和最短格向量问题的密码学重要案例。 然而，尽管有这些激励，非对易HSP到目前为止在很大程度上抵制了量子计算社区的进步。有效的算法只知道几个家庭的群体，甚至信息-理论方面的问题是知之甚少。这个项目将寻求有效的量子算法和查询复杂度下界的对称组-的HSP相关的图形同构的情况下-和其他群体的算法的兴趣。 我们的方法应用了丰富的数学工具表示论，适应基地，纠缠测量多陪集状态。