A linear-optical proof that the permanent is # P -hard
Scott Aaronson · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · 2011
One of the crown jewels of complexity theory is Valiant's 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 owing to Knill, Laflamme and Milburn—one can give a different and arguably more intuitive proof of this theorem.