Novel Quantum Algorithms for Problems in Linear Algebra, Topology, and Group Theory

用于解决线性代数、拓扑和群论问题的新型量子算法

• 批准号: 0726771
• 负责人: Pawel Wocjan
• 金额: $ 24.99万
• 依托单位: The University of Central Florida Board of Trustees
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-15 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0726771&HistoricalAwards=false
• 关键词: Novel; Quantum; Algorithms; Problems; Linear

The goals of the interdisciplinary research in quantum information science are to understand and demonstrate how quantum phenomena can dramatically advance the fundamental capabilities of information processing devices. In this context, the investigator seeks to (a) determine the differences between the computational power and limitations of quantum computers and those of classical computers and (b) to find new quantum speed-ups for classically difficult problems. Building upon these results, this research explores how these quantum algorithms will allow one to solve more efficiently larger instances of computationally hard real-life problems, such as those arising in optimization theory, signal processing, and cryptography.In computational complexity theory, BPP and BQP denote ?Bounded error Probabilistic time? and ?Bounded error Quantum Polynomial time, respectively. Roughly speaking, they represent the classes of problems that can be efficiently solved on classical and quantum computers. The exact relationship between them remains unknown, although there is strong evidence that BQP is strictly larger than BPP. To understand what features separate these classes, the investigator will determine purely classical (quantum-free) problems in linear algebra and topology that characterize the power of BQP. This research also involves the examination of the potential (and limitations) of a new quantum method for solving hidden subgroup and shift problems that present a general framework for designing quantum algorithms. This method relies upon tools from representation theory such as the Schur and Clebsch-Gordon transforms.

量子信息科学跨学科研究的目标是理解和展示量子现象如何极大地提高信息处理设备的基本能力。在这种背景下，研究人员试图(A)确定量子计算机和经典计算机之间的计算能力和局限性之间的差异，以及(B)为经典困难问题找到新的量子加速。在这些结果的基础上，本研究探索了这些量子算法将如何使人们能够更有效地解决计算困难的现实问题的更大实例，例如在最优化理论、信号处理和密码学中出现的问题。和？有界误差量子多项式时间。粗略地说，它们代表了在经典和量子计算机上可以有效解决的问题的类别。它们之间的确切关系尚不清楚，尽管有强有力的证据表明，BQP严格地大于BPP。为了理解是什么特征将这些类别区分开来，研究者将在线性代数和拓扑学中确定表征BQP力量的纯经典(量子自由)问题。这项研究还涉及对一种新的量子方法的潜力(和局限性)的检查，该方法用于解决隐藏子群和移位问题，为设计量子算法提供了一个一般框架。这种方法依赖于表示理论中的工具，如Schur变换和Clebsch-Gordon变换。