  We construct a quantum-inspired classical algorithm for computing the
permanent of Hermitian positive semidefinite matrices, by exploiting a
connection between these mathematical structures and the boson sampling model.
Specifically, the permanent of a Hermitian positive semidefinite matrix can be
expressed in terms of the expected value of a random variable, which stands for
a specific photon-counting probability when measuring a linear-optically
evolved random multimode coherent state. Our algorithm then approximates the
matrix permanent from the corresponding sample mean and is shown to run in
polynomial time for various sets of Hermitian positive semidefinite matrices,
achieving a precision that improves over known techniques. This work
illustrates how quantum optics may benefit algorithms development.
