A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices
arXiv:1609.02416 · doi:10.1103/PhysRevA.96.022329
Abstract
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.
9 pages, 1 figure. Updated version for publication
References in corpus (5)
- Universal Linear Optics
- On-Demand Single Photons with High Extraction Efficiency and Near-Unity Indistinguishability from a Resonantly Driven Quantum Dot in a Micropillar
- Photonic Boson Sampling in a Tunable Circuit
- What can quantum optics say about computational complexity theory?
- Universality of Generalized Bunching and Efficient Assessment of Boson Sampling
Cited by in corpus (12)
- Photonic quantum information processing: a review
- A detailed study of Gaussian Boson Sampling
- Quantum-inspired algorithms in practice
- Distinguishing noisy boson sampling from classical simulations
- Quantum-inspired permanent identities
- Certification of Gaussian Boson Sampling via graph theory
- Simulating arbitrary Gaussian circuits with linear optics
- Experimental linear optical computing of the matrix permanent
- Approximating outcome probabilities of linear optical circuits
- Solving the Gross-Pitaevskii equation on multiple different scales using the quantics tensor train representation
- Quantum estimation bound of Gaussian matrix permanent
- Generalized Interference of Fermions and Bosons