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.
Graph isomorphism is of Goldilocks-like complexity---not so easy as to be known to be in P, but unlikely to be NP-complete 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 non-abelian hidden subgroup problem. All of these approaches attempt to put the "graph" back in quantum graph isomorphism algorithms.