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

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

Research output: Contribution to journalArticle (Academic Journal)peer-review

17 Citations (Scopus)


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 algorithm development.

Original languageEnglish
Article number022329
JournalPhysical Review A
Issue number2
Publication statusPublished - 31 Aug 2017


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