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

量子信息科学跨学科研究的目标是理解和展示量子现象如何极大地提高信息处理设备的基本能力。在这种情况下，研究人员试图（a）确定量子计算机和经典计算机的计算能力和局限性之间的差异，（B）为经典难题找到新的量子加速。 基于这些结果，本研究探讨了这些量子算法将如何允许一个更有效地解决更大的实例计算困难的现实生活中的问题，如那些出现在优化理论，信号处理，和cryptography.In计算复杂性理论，BPP和BQP表示？有界误差概率时间？然后呢？有界误差量子多项式时间，分别。粗略地说，它们代表了可以在经典计算机和量子计算机上有效解决的问题。它们之间的确切关系仍然未知，尽管有强有力的证据表明BQP严格大于BPP。为了理解这些类别的区别，研究人员将确定线性代数和拓扑中的纯经典（无量子）问题，这些问题表征了BQP的能力。这项研究还涉及一种新的量子方法的潜力（和局限性）的检查，用于解决隐藏的子群和移位问题，为设计量子算法提供了一个通用框架。这种方法依赖于表示理论的工具，如Schur和Clebsch-Gordon变换。

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.