Uma Prova Linear-Óptica de que o Permanente é #P-Difícil

Uma das joias da coroa da teoria da complexidade é o teorema de Valiant de 1979, que afirma que calcular o permanente de uma matriz n*n é #P-difícil. Aqui mostramos que, ao usar o modelo de computação quântica linear-óptica---e em particular, um teorema de universalidade devido a Knill, Laflamme e Milburn---pode-se fornecer uma prova diferente e, argumentavelmente, mais intuitiva deste teorema.