Quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices

L. Chakhmakhchyan, N. J. Cerf, R. Garcia-Patron

Research output: Contribution to journalArticlepeer-review


We construct a quantum-inspired classical algorithm for computing the permanent of Hermitian positivesemidefinite matrices by exploiting a connection between these mathematical structures and the boson samplingmodel. Specifically, the permanent of a Hermitian positive semidefinite matrix can be expressed in terms of theexpected value of a random variable, which stands for a specific photon-counting probability when measuring alinear-optically evolved random multimode coherent state. Our algorithm then approximates the matrix permanentfrom the corresponding sample mean and is shown to run in polynomial time for various sets of Hermitianpositive semidefinite matrices, achieving a precision that improves over known techniques. This work illustrateshow quantum optics may benefit algorithm development.
Original languageEnglish
Article number022329
Number of pages8
JournalPhysical Review A
Issue number2
Publication statusPublished - 31 Aug 2017

Fingerprint Dive into the research topics of 'Quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices'. Together they form a unique fingerprint.

Cite this