CCF: AF: Small: Quantum Data Structures and Algorithms

University Of California-Santa Barbara, Santa Barbara CA

Investigators

Abstract

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.