[QIP-Sem] QIP seminar, Mon 10/22, 4pm, 36-428, Cris Moore

[Peter Shor]

MIT Quantum Information Processing seminar
Monday 10/22 at 4pm in 36-428
-------------------------------------------------

Cris Moore (UNM)

On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism, and Thoughts on Classical Cryptosystems Secure Against Quantum Attack

Abstract:

It is known that any quantum algorithm for Graph Isomorphism that works within the framework of the hidden subgroup problem must perform highly entangled measurements across many coset states.  One of the only known models for how such a measurement could be carried out efficiently is Kuperberg's "quantum sieve" for the dihedral group.  However, I will discuss joint work with Alex Russell and Piotr Sniady in which we show that no such approach, no matter what rule we use to combine coset states in the sieve, can produce an improvement over known classical algorithms for Graph Isomorphism.

I will then discuss joint work with Alex Russell and Umesh Vazirani in which we assume that the hidden subgroup problem over the general linear group GL_n(q) is hard, and use this to define a one-way function secure against quantum attack: that is, a function f which can be computed classically, but which is hard even for quantum computers to invert.  I will also show that a natural attack on the McEliece cryptosystem leads to a difficult case of the hidden subgroup problem, suggesting that this cryptosystem may be secure against quantum attack.

-------------------------------------------------
http://qis.mit.edu
http://mailman.mit.edu/mailman/listinfo/qip-sem