CAREER: Algebraic Approach to the Design of Novel Quantum Algorithms

职业：新型量子算法设计的代数方法

• 批准号: 0746600
• 负责人: Pawel Wocjan
• 金额: $ 40万
• 依托单位: The University of Central Florida Board of Trustees
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-02-01 至 2015-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0746600&HistoricalAwards=false
• 关键词: CAREER; Algebraic; Approach; Design; Novel

The investigator seeks to discover novel ways of harnessing quantum phenomena to advance the computational capabilities of information processing devices. This fundamental research leads to new efficient quantum algorithms for problems that cannot be solved efficiently by any known classical algorithm. These quantum algorithms make it possible to solve more efficiently larger instances of computationally hard real-life problems, such as those arising in optimization theory, machine learning, and signal processing. A second component of the research focuses on developing new quantum algorithms for algebraic problems which helps to design more secure cryptographic protocols that are immune to quantum attacks. This is important as today's encryption schemes have to withstand attacks employing more advanced computational devices in the future. More fundamentally, this research provides a deeper understanding of the computational capabilities of information processing devices operating in the quantum regime. As the end of scalability of conventional silicon-based devices approaches, it is essential to explore such novel paradigms of information technologies.The investigator finds new quantum algorithms for computing with large matrices. This research leads to new applications in machine learning, signal processing, and data analysis by achieving speed-ups for principal component analysis and kernel methods. These quantum algorithms also find applications in optimization theory and topology by providing better approximate solutions for NP-hard optimization and counting problems and more accurate evaluations of topological invariants, respectively. A second component of the research focuses on quantum algorithms for identifying group-theoretic and non-linear structures. The research goal is to extend them to a broad collection of structures arising in number theory and algebraic geometry, especially those that are relevant to cryptographic applications.

研究者寻求发现利用量子现象的新方法来提高信息处理设备的计算能力。这一基础研究导致新的高效量子算法无法有效地解决任何已知的经典算法的问题。这些量子算法使得更有效地解决计算困难的现实问题成为可能，例如优化理论、机器学习和信号处理中出现的问题。研究的第二个组成部分侧重于为代数问题开发新的量子算法，这有助于设计更安全的不受量子攻击的加密协议。这一点很重要，因为今天的加密方案必须经得起未来使用更先进的计算设备的攻击。更重要的是，这项研究提供了对在量子体制下运行的信息处理设备的计算能力的更深层次的理解。随着传统硅基器件可扩展性的终结，探索这种新的信息技术范式是必不可少的。研究者发现新的量子算法计算与大矩阵。这项研究通过实现主成分分析和核方法的加速，导致了机器学习，信号处理和数据分析方面的新应用。这些量子算法还通过为NP-hard优化和计数问题提供更好的近似解以及更准确的拓扑不变量评估，分别在优化理论和拓扑学中得到应用。研究的第二个组成部分侧重于识别群论和非线性结构的量子算法。研究目标是将它们扩展到数论和代数几何中出现的广泛结构集合，特别是那些与密码学应用相关的结构。