Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Valiant:
TR11-043 | 25th March 2011
Scott Aaronson

A Linear-Optical Proof that the Permanent is #P-Hard

One of the crown jewels of complexity theory is Valiant's 1979 theorem that computing the permanent of an n*n matrix is #P-hard. Here we show that, by using the model of linear-optical quantum computing---and in particular, a universality theorem due to Knill, Laflamme, and Milburn---one can give a different and ... more >>>

ISSN 1433-8092 | Imprint