

Assistant Research Professor, Department of Computer Science and Engineering, University of Washington
David Bacon is a research assistant professor in the department of computer science & engineering at the University of Washington. His Ph.D. is from Berkeley in theoretical physics, his postdoc experience came from the Institute for Quantum Information at Caltech, and his dog is from Yakima, WA. He spends his days thinking about quantum error correction and his nights thinking about quantum algorithms. In the remaining free time he helps run the quantum computing theory group at the University of Washington with Aram Harrow.
Abstract
Graph isomorphism is of Goldilockslike complexitynot so easy as to be known to be in P, but unlikely to be NPcomplete as this would collapse the polynomial hierarchy. As such, graph isomorphism taunts quantum algorists. Here I will discuss some alternative approaches to quantum algorithms for graph isomorphism that are not based upon the most studied method for solving graph isomorphism on a quantum computer, those based upon solving the nonabelian hidden subgroup problem. All of these approaches attempt to put the "graph" back in quantum graph isomorphism algorithms.
