[QIP-Sem] MIT QIP Seminar Series - Sean Hallgren

[Isaac Chuang]

----------------------------------------------------------------------
The MIT Quantum Information Processing Seminar Series
----------------------------------------------------------------------

Our tenth seminar of the Fall 2005 semester:

Speaker:  Sean Hallgren
          NEC Labs

Time:     4:00pm (following refreshments)
Date:     Monday, November 28, 2005
Location: CUA conference room, 26-214

Title:  Limitations of Quantum Coset States for Graph Isomorphism

Abstract:

  It has been known for some time that graph isomorphism reduces to
  the hidden subgroup problem (HSP). What is more, most exponential
  speedups in quantum computation are obtained by solving instances of
  the HSP. A common feature of the resulting algorithms is the use of
  quantum coset states, which encode the hidden subgroup. An open
  question has been how hard it is to use these states to solve graph
  isomorphism. It was recently shown by Moore, Russell, and Schulman
  that only an exponentially small amount of information is available
  from one, or a pair of coset states. A potential source of power to
  exploit are entangled quantum measurements that act jointly on many
  states at once. We show that entangled quantum measurements on at
  least Omega(n log n) coset states are necessary to get useful
  formation for the case of graph isomorphism, matching an information
  theoretic upper bound. This may be viewed as a negative result
  because highly entangled measurements seem hard to implement in
  general. Our main theorem is very general and also rules out using
  joint measurements on few coset states for some other groups, such
  as GL(n,FFp^m) and Gn where G is finite and satisfies a suitable
  property.

----------------------------------------------------------------------
Next: 05 Dec -  Chris King: Additivity Problems for Product Channels

http://qis.mit.edu
----------------------------------------------------------------------