C[omp]ute

From: andrew cooke <andrew@...>

Date: Sun, 9 Oct 2011 07:27:29 -0300

After reading http://news.ycombinator.com/item?id=3087969 - in particular, the
comment at http://news.ycombinator.com/item?id=3088794 - I wondered if there
is a quantum algorithm for GI.

Some google searching turned up http://dabacon.org/pontiff/?p=4148 which seems
to be a recent overview of the field.  That says:

  A Quantum Observable for the Graph Isomorphism Problem by Mark Ettinger and
  Peter Hoyer (1999) http://arxiv.org/abs/quant-ph/9901029  This paper
  establishes that there is a measurement one can perform on a polynomial
  number of qubits that solves the graph isomorphism problem.  Unfortunately
  it is not known how to efficiently implement this measurement (by a circuit
  of polynomial depth.)  Even more unfortunately there is a negative result
  that says that you really have to do something non-trivial across the entire
  system when you implement this measurement.

Andrew