2016/07/18 by Peter P. Rohde, Rohde, Peter P., Dominic W. Berry +5
Physics and Astronomy · #FOS: Physical sciences #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.1607.04960
6 pages
arxiv created 2016/07/18 · arxiv updated 2016/07/19
Matrix permanents arise naturally in the context of linear optical networks fed with nonclassical states of light. In this letter we tie the computational complexity of a class of multi-dimensional integrals to the permanents of large matrices using a simple quantum optics argument. In this way we prove that evaluating integrals in this class is #P-hard. Our work provides a new approach for using methods from quantum physics to prove statements in computer science.