Data Structures and other building blocks for Quantum Algorithms

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

Quantum Computing is an emerging paradigm in computer science in which data representation and processing follow the rules of quantum mechanics. The fundamental element of a quantum computer is a quantum bit, which is capable ofdoing everything a classical bit can do, and in addition has the ability to exist in superposition states and entangle with other quantum bits. Recently, quantum computing has exploded in interest and many national, academic, and industriallabs are engaged in the pursuit of building quantum computers. Among the key motivations for quantum computing is the potential for dramatic speedups over classical computing. However, quantum computers do not speed up everycomputation. To harness their power, it is not enough to simply build them, one must also design new algorithms that exploit quantum effects to solve specific problems. Most software engineers and computer scientists are unfamiliar withthe rules of quantum information and even after three decades of quantum computing - there is a sense that designing quantum algorithms is an extremely difficult undertaking requiring deep expertise of quantum computing.The goal of my PhD is to find new ideas in quantum algorithms and data structures that will allow us to harness the power of quantum computers once they are built. The early part of the PhD will proceed in two parallel explorations:1) the identification of the key insight behind known quantum algorithms; and 2) the design and analysis of quantum data structures. The focus on data structures is strategic because the success of an algorithm often relies on well crafted data structures, and there is very little existing work in this area. The hope is that these two parallel explorations will lead to interesting connections that lead to new proposals for algorithms, data structures or architectures for quantum computers. Another guiding principle is to develop adaptable techniques which will make it easier for others to design quantum algorithms.