CCF: AF: Small: Quantum Data Structures and Algorithms

量子计算着眼于以量子力学的方式处理信息的潜在好处。由于量子物理的叠加原理与干涉现象相结合，量子算法能够比传统的经典计算机更有效地执行某些任务。由于它使用了不同领域的想法，量子计算的研究涵盖了从实验物理学家到计算机科学再到纯数学的各个领域。相反，这项研究往往会影响到这些不同的领域。首席研究员Wim van Dam博士将开发和分析量子算法使用的新数据结构。正如标准经典计算理论所熟知的那样，信息存储的方式对于提高处理这些数据的算法的效率起着至关重要的作用。虽然到目前为止，量子算法的理论已经相当成熟，但人们对数据结构在增加量子力学处理信息的好处方面可能起到的作用知之甚少。这项建议旨在弥补这种缺乏理解的情况。范·达姆将研究量子计算机的特定架构如何影响数据的最佳存储。他还将研究以量子力学方式对树、图形、模拟数据和散列函数进行编码的数据结构的可能性。最后，Van Dam和他的学生将研究量子软件的特性，在这种软件中，人们可以将量子变换存储为量子态。作为该项目的一部分，Van Dam将在加州大学圣巴巴拉分校校园内主持量子计算、通信和密码学理论年度会议。范·达姆还将参加UCSB的研究导师计划，在该计划期间，有天赋的高中生可以进入首席调查员的研究小组工作。

Quantum computing looks at the potential benefits of processing information in a quantum mechanical manner. Due to the superposition principle of quantum physics in combination with the interference phenomenon, quantum algorithms are capable of performing certain tasks more efficiently than is possible with traditional, classical computers. As it uses ideas from various fields, research in quantum computing spans the spectrum from experimental physicists, through computer science, to pure mathematics. Conversely, this research often affects these various different fields. The principle investigator, Dr Wim van Dam, will develop and analyze new data structures to be used by quantum algorithms. As is well known from standard classical computation theory, the way in which information is stored can play a crucial role in increasing the efficiency of the algorithms that act on this data. While the theory of quantum algorithms is fairly well sophisticated by now, much less is known about the role that data structures might have in increasing the benefits of processing information quantum mechanically. This proposal aims to remedy this lack of understanding. Van Dam will investigate how the specific architecture of a quantum computer affects the optimal storage of data. He will also look at the possibility of data structures to encode trees, graphs, analog data, and hash functions in a quantum mechanical manner. Lastly Van Dam and his students will investigate the properties of quantum software where one stores quantum transformations as quantum states.As part of the project Van Dam will host the Annual Conference on the Theory of Quantum Computation, Communication and Cryptography on the campus of UC Santa Barbara. Van Dam will also participate in UCSB's Research Mentorship Program during which gifted high-school students get to work in the research groups of the principle investigator.