Title: New Hardness Results for the Permanent Using Linear Optics
Speaker: Daniel Grier, MIT
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.
Speaker Bio: Daniel Grier is a sixth year PhD student in Computer Science at MIT CSAIL, advised by Scott Aaronson. His research interests include both quantum computation and classical complexity theory, and more generally the connections between physics and the limits of computation. Daniel received his Bachelors degree in Computer Science and Mathematics at the University of South Carolina. He is supported by an NSF Graduate Fellowship.