Data Structures and other building blocks for Quantum Algorithms

量子计算是计算机科学中的一种新兴范式，其中数据表示和处理遵循量子力学的规则。量子计算机的基本元素是量子比特，它能够做经典比特所能做的一切，此外还具有以叠加态存在并与其他量子比特纠缠的能力。最近，量子计算的兴趣激增，许多国家，学术和工业实验室都在追求构建量子计算机。量子计算的主要动机之一是相对于经典计算的巨大加速潜力。然而，量子计算机并不能加速每一次计算。为了利用它们的力量，仅仅构建它们是不够的，还必须设计新的算法，利用量子效应来解决特定的问题。大多数软件工程师和计算机科学家都不熟悉量子信息的规则，即使在量子计算30年之后，人们也会感觉到设计量子算法是一项极其困难的任务，需要量子计算的深厚专业知识。我的博士学位的目标是在量子算法和数据结构中找到新的想法，一旦量子计算机建成，我们就可以利用它们的力量。博士学位的早期部分将进行两个并行的探索：1）识别已知量子算法背后的关键见解; 2）量子数据结构的设计和分析。对数据结构的关注是战略性的，因为算法的成功通常依赖于精心制作的数据结构，而这方面的现有工作很少。希望这两个并行的探索将导致有趣的联系，从而导致量子计算机算法，数据结构或架构的新建议。另一个指导原则是开发适应性技术，使其他人更容易设计量子算法。

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.