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's和Shor的算法中出现的隐藏子组问题发生在交换群体上，而HSP的一个案例现在已被忽略了。 非交通性的隐藏子组问题与主要兴趣的几个问题密切相关，包括图形同构，隐藏的移位问题以及最短的晶格向量问题的密码重要案例。 尽管如此，尽管这些激励措施，但非共同的HSP在很大程度上抵制了迄今为止量子计算社区的进步。有效的算法仅以几个群体的家庭而闻名，甚至信息的理论方面也很少理解。该项目将寻求对称组的有效量子算法和查询复杂性的下限 - - 与图同构相关的HSP的情况 - 以及其他算法兴趣的组。 我们的方法应用了代表理论的丰富数学工具，改编的基础以及对多个固定状态的纠缠测量。