AF: Small: Graph Isomorphism and Quantum Random Walks by Anyons

University Of Washington, Seattle WA

Investigators

Abstract

Quantum computers offer the potential to exponentially speed up the solution of certain classically hard computational problems. It is already known, for example, that quantum computers can efficiently factor numbers (something modern computers cannot do), and this fact implies that quantum computers can break the majority of cryptographic systems which protect our nation's cyber-infrastructure. The quantum factoring algorithm is the main motivation behind current research into actually building a quantum computer. In this grant, the investigator proposes a new approach to efficiently solving a computational problem--the graph isomorphism problem--which might also admit an exponential speedup over the best classical algorithm for the problem. The graph isomorphism problem is to tell whether two given graphs (a collection of vertices with edges connecting them) can be made to look identical to each other by permuting the different vertices. The approach taken here is different from that taken by the majority of the quantum algorithms community and centers on a novel class of quantum random walks, those in which the walkers carry topological quantum numbers. This approach follows from a series of failed proposals to graph isomorphism based on random walks by hard-core bosons or fermions and is motivated by the form in which these proposals fail. Finding an efficient quantum algorithm for the graph isomorphism problem would be potentially transformative and would provide a major new justification for building a large quantum computer. The approach chosen by the PI also introduces a novel quantum algorithm technique--quantum random walks by anyons--which has the potential to be useful a primitive outside of the graph isomorphism problem. Finally, the award will be used to support the training of graduate students who work on the boundary between computer science and physics, and thus strengthen connections across this interdisciplinary divide.