# New Hardness Results for the Permanent Using Linear Optics

Date and time |
Feb 08, 2019 from 11:00 AM to 12:30 PM |
---|---|

Location | 3rd Floor Stewart Library, Fields Institute, 222 College Street, Toronto |

Host | Henry Yuen |

## Daniel Grier

**
MIT
**

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.

Contact Name | Helen Iyer |
---|