Personal tools
/ Research / Quantum Optics / CQIQC Seminars / New Hardness Results for the Permanent Using Linear Optics

New Hardness Results for the Permanent Using Linear Optics

— filed under: , ,
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


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
Document Actions