xQIT W. M. Keck Foundation Center For Extreme Quantum Information Theory at the Massachusetts Institute of Technology
News About People Research Publications Events Courses Positions Contact
   
 

Conference Homepage

  Events > 2011 xQIT Conference

 

  David Bacon
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 Beyond the Hidden Subgroup Problem
May 4, 2011 - 11:15 AM - 11:40 AM
RLE Conference Center 36-428

Abstract

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.