AF: Small: Quantum Algorithms and Complexity

AF：小：量子算法和复杂性

• 批准号: 1618287
• 负责人: Sean Hallgren
• 金额: $ 45万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-07-01 至 2020-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1618287&HistoricalAwards=false
• 关键词: AF; Small; Quantum; Algorithms; Complexity

This project studies the power of quantum computers. The main goal is to determine which problems have efficient quantum algorithms andwhich ones remain hard in the presence of quantum computers. This is a fundamental question in computer science. One objective is to find new applications for quantum computers. A second objective is to understand which cryptosystems are secure against quantum computers. These systems must be based on problems that cannot be solved efficiently by quantum computers. The PI and his graduate students are considering these types of problems.The project considers new approaches for the dihedral hidden subgroup problem. A quantum algorithm for this problem, if found, would break some candidates for quantum-secure cryptosystems. If more evidence is found that the problem is difficult to solve, then it increases the confidence in the security of the proposed systems. Another type of potential speedup is for optimization problems. The work addresses whether certain settings for the approximate adiabatic algorithm exist for which the quantum algorithm achieves a betterapproximate solution than the best classical algorithm. The last problem deals with understanding Hamiltonian complexity.

这个项目研究量子计算机的能力。 主要目标是确定哪些问题具有有效的量子算法，哪些问题在量子计算机的存在下仍然很难解决。 这是计算机科学中的一个基本问题。 目标之一是为量子计算机找到新的应用。 第二个目标是了解哪些密码系统对量子计算机是安全的。这些系统必须基于量子计算机无法有效解决的问题。 PI和他的研究生正在考虑这些类型的问题。该项目考虑二面角隐藏子群问题的新方法。 这个问题的量子算法，如果找到，将打破量子安全密码系统的一些候选人。 如果发现更多的证据表明问题难以解决，那么它会增加对拟议系统安全性的信心。另一种潜在的加速是针对优化问题。 工作地址是否存在某些设置的近似绝热算法的量子算法实现了一个betterapproximate的解决方案比最好的经典算法。 最后一个问题涉及理解哈密顿复杂性。