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

点击翻译按钮获取中文摘要

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.