2016/09/30 by L. Chakhmakhchyan, Levon Chakhmakhchyan, Nicolas J. Cerf +3 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Applied mathematics #Eigenvalues and eigenvectors #Hermitian matrix #Mathematical optimization #Mathematics #Matrix (chemical analysis) #Neural Networks and Reservoir Computing #Physics #Positive-definite matrix #Pure mathematics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum algorithm #Quantum mechanics #Semidefinite programming #quant-ph
paper · pdf · doi:10.1103/physreva.96.022329
published as Phys. Rev. A 96, 022329 (2017) · 9 pages, 1 figure. Updated version for publication
openalex created_date 2016/09/23 · arxiv created 2017/08/31 · openalex publication_date 2017/08/31 · arxiv updated 2017/09/01 · openalex updated_date 2026/08/05
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.