Tutte Colloquium - Daniel Grier

Zoom (for information email emma.watson@uwaterloo.ca) 

Title: Permanent Hardness from Linear Optics

Abstract:

One of the great accomplishments in complexity theory was Valiant's 1979 proof that the permanent of a matrix is #P-hard to compute.  Subsequent work simplified Valiant's ideas and even began to recast them as problems in quantum computing.  In 2011, this culminated in a striking proof by Aaronson, based solely on quantum linear optics, of the #P-hardness of the permanent. Although this simplified (at least for physicists) aspects of Valiant's proof by off-loading its difficulty onto central and well-known theorems in linear optics, the question remained:  what else was gained by converting Valiant's combinatorial proof into a linear optical one?

In this talk I'll give one possible answer to this question--namely, that these quantum techniques are useful for proving hardness of permanents for matrices that obey classical Lie group structure.  In particular, I will prove that computing the permanent of real orthogonal matrices is #P-hard. The hardness result translates to permanents of orthogonal matrices over finite fields of characteristic not equal to 2 or 3.

No prior knowledge of linear optics is necessary.

Joint work with Luke Schaeffer.