## Quantum Graph Isomorphism

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