Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Frontiers in Optics

Linear optical computing of matrix permanent via thermal light boson sampling

Yosep Kim, Kang-Hee Hong, Joonsuk Huh, Yoon-Ho Kim

Published Jan 1, 2017• 0 citations
Publisher

Abstract

We show linear optical calculation of permanent of Hermitian positive semidefinite matrices via thermal light boson sampling. The experimental results are in good agreement with the calculation and are compared with the Gaussian sampling results.
DOI
10.1364/fio.2017.jw4a.15

Related papers

Experimental linear optical computing of the matrix permanent

Yosep Kim, Kang-Hee Hong, Joonsuk Huh +1 more

Linear optical computing (LOC) with thermal light has recently gained attention because the problem is connected to the permanent of a Hermitian positive semidefinite matrix (HPSM), which is of importance in the computational complexity theory. Despite the several theoretical analyses on the computational structure of an HPSM in connection to LOC, the experimental demonstration and the computational complexity analysis via the linear optical system have not been performed yet. We present, herein, experimental LOC for estimating the permanent of an HPSM. From the linear optical experiments and theoretical analysis, we find that the LOC efficiency for a multiplicative error is dependent on the value of the permanent and that the lower bound of the computation time scales exponentially. Furthermore, our results are generalized and applied to LOC of permanents of unitary matrices, which can be implemented with a multiport quantum interferometer involving single photons at the input ports. We find that LOC with single photons, for the permanent estimation, is on average less efficient than the most efficient classical algorithm known to date, even in ideal conditions.

arXiv:1904.06673•Physical Review A•May 7, 2019•5 citations

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

Levon Chakhmakhchyan, Nicolas J. Cerf, Raúl García−Patrón

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.

arXiv:1609.02416•Physical Review A•Aug 31, 2017•22 citations

New Hardness Results for the Permanent Using Linear Optics

Daniel Grier, Luke Schaeffer

In 2011, Aaronson gave a striking proof, based on quantum linear optics, that the problem of computing the permanent of a matrix is #P-hard. Aaronson's proof led naturally to hardness of approximation results for the permanent, and it was arguably simpler than Valiant's seminal proof of the same fact in 1979. Nevertheless, it did not show #P-hardness of the permanent for any class of matrices which was not previously known. In this paper, we present a collection of new results about matrix permanents that are derived primarily via these linear optical techniques. First, we show that the problem of computing the permanent of a real orthogonal matrix is #P-hard. Much like Aaronson's original proof, this implies that even a multiplicative approximation remains #P-hard to compute. The hardness result even translates to permanents of orthogonal matrices over the finite field F_{p^4} for p != 2, 3. Interestingly, this characterization is tight: in fields of characteristic 2, the permanent coincides with the determinant; in fields of characteristic 3, one can efficiently compute the permanent of an orthogonal matrix by a nontrivial result of Kogan. Finally, we use more elementary arguments to prove #P-hardness for the permanent of a positive semidefinite matrix. This result shows that certain probabilities of boson sampling experiments with thermal states are hard to compute exactly, despite the fact that they can be efficiently sampled by a classical computer.

arXiv:1610.04670•Leibniz international proceedings in informatics•Oct 15, 2016•8 citations

Efficient computation of permanents, with applications to Boson sampling and random matrices

P. H. Lundow, Klas Markström

In order to find the outcome probabilities of quantum mechanical systems like the optical networks underlying Boson sampling, it is necessary to be able to compute the permanents of unitary matrices, a computationally hard task. Here we first discuss how to compute the permanent efficiently on a parallel computer, followed by algorithms which provide an exponential speed-up for sparse matrices and linear run times for matrices of limited bandwidth. The parallel algorithm has been implemented in a freely available software package, also available in an efficient serial version. As part of the timing runs for this package we set a new world record for the matrix order on which a permanent has been computed. Next we perform a simulation study of several conjectures regarding the distribution of the permanent for random matrices. Here we focus on permanent anti-concentration conjecture, which has been used to find the classical computational complexity of Boson sampling. We find a good agreement with the basic versions of these conjectures, and based on our data we propose refined versions of some of them. For small systems we also find noticeable deviations from a proposed strengthening of a bound for the number of photons in a Boson sampling system.

arXiv:1904.06229•Journal of Computational Physics•Jan 19, 2022•21 citations

What Can Quantum Optics Say about Computational Complexity Theory?

Saleh Rahimi-Keshari, Austin P. Lund, Timothy C. Ralph

Considering the problem of sampling from the output photon-counting probability distribution of a linear-optical network for input Gaussian states, we obtain results that are of interest from both quantum theory and the computational complexity theory point of view. We derive a general formula for calculating the output probabilities, and by considering input thermal states, we show that the output probabilities are proportional to permanents of positive-semidefinite Hermitian matrices. It is believed that approximating permanents of complex matrices in general is a #P-hard problem. However, we show that these permanents can be approximated with an algorithm in the BPP^{NP} complexity class, as there exists an efficient classical algorithm for sampling from the output probability distribution. We further consider input squeezed-vacuum states and discuss the complexity of sampling from the probability distribution at the output.

arXiv:1408.3712•Physical Review Letters•Feb 11, 2015•87 citations

Correlation functions and matrix permanents

Vincenzo Tamma, Florian Nägele

The connection between the boson sampling problem in a linear optical interferometer with single photon sources and the computation of matrix permanents has recently brought a strong interest for quantum computing applications. In this work we explore the physics of N-order interference in terms of N-order correlation functions in a generic linear optical interferometer with both Fock states sources and thermal sources. We will show how also in this case the connection of such a problem with matrix permanents play a fundamental role.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Sep 26, 2013•3 citations
Linear optical computing (LOC) with thermal light has recently gained attention because the problem is connected to the permanent of a Hermitian positive semidefinite matrix (HPSM), which is of importance in the computational complexity theory. Despite the several theoretical analyses on the computational structure of an HPSM in connection to LOC, the experimental demonstration and the computational complexity analysis via the linear optical system have not been performed yet. We present, herein, experimental LOC for estimating the permanent of an HPSM. From the linear optical experiments and theoretical analysis, we find that the LOC efficiency for a multiplicative error is dependent on the value of the permanent and that the lower bound of the computation time scales exponentially. Furthermore, our results are generalized and applied to LOC of permanents of unitary matrices, which can be implemented with a multiport quantum interferometer involving single photons at the input ports. We find that LOC with single photons, for the permanent estimation, is on average less efficient than the most efficient classical algorithm known to date, even in ideal conditions.
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.
In 2011, Aaronson gave a striking proof, based on quantum linear optics, that the problem of computing the permanent of a matrix is #P-hard. Aaronson's proof led naturally to hardness of approximation results for the permanent, and it was arguably simpler than Valiant's seminal proof of the same fact in 1979. Nevertheless, it did not show #P-hardness of the permanent for any class of matrices which was not previously known. In this paper, we present a collection of new results about matrix permanents that are derived primarily via these linear optical techniques. First, we show that the problem of computing the permanent of a real orthogonal matrix is #P-hard. Much like Aaronson's original proof, this implies that even a multiplicative approximation remains #P-hard to compute. The hardness result even translates to permanents of orthogonal matrices over the finite field F_{p^4} for p != 2, 3. Interestingly, this characterization is tight: in fields of characteristic 2, the permanent coincides with the determinant; in fields of characteristic 3, one can efficiently compute the permanent of an orthogonal matrix by a nontrivial result of Kogan. Finally, we use more elementary arguments to prove #P-hardness for the permanent of a positive semidefinite matrix. This result shows that certain probabilities of boson sampling experiments with thermal states are hard to compute exactly, despite the fact that they can be efficiently sampled by a classical computer.
In order to find the outcome probabilities of quantum mechanical systems like the optical networks underlying Boson sampling, it is necessary to be able to compute the permanents of unitary matrices, a computationally hard task. Here we first discuss how to compute the permanent efficiently on a parallel computer, followed by algorithms which provide an exponential speed-up for sparse matrices and linear run times for matrices of limited bandwidth. The parallel algorithm has been implemented in a freely available software package, also available in an efficient serial version. As part of the timing runs for this package we set a new world record for the matrix order on which a permanent has been computed. Next we perform a simulation study of several conjectures regarding the distribution of the permanent for random matrices. Here we focus on permanent anti-concentration conjecture, which has been used to find the classical computational complexity of Boson sampling. We find a good agreement with the basic versions of these conjectures, and based on our data we propose refined versions of some of them. For small systems we also find noticeable deviations from a proposed strengthening of a bound for the number of photons in a Boson sampling system.
Considering the problem of sampling from the output photon-counting probability distribution of a linear-optical network for input Gaussian states, we obtain results that are of interest from both quantum theory and the computational complexity theory point of view. We derive a general formula for calculating the output probabilities, and by considering input thermal states, we show that the output probabilities are proportional to permanents of positive-semidefinite Hermitian matrices. It is believed that approximating permanents of complex matrices in general is a #P-hard problem. However, we show that these permanents can be approximated with an algorithm in the BPP^{NP} complexity class, as there exists an efficient classical algorithm for sampling from the output probability distribution. We further consider input squeezed-vacuum states and discuss the complexity of sampling from the probability distribution at the output.
The connection between the boson sampling problem in a linear optical interferometer with single photon sources and the computation of matrix permanents has recently brought a strong interest for quantum computing applications. In this work we explore the physics of N-order interference in terms of N-order correlation functions in a generic linear optical interferometer with both Fock states sources and thermal sources. We will show how also in this case the connection of such a problem with matrix permanents play a fundamental role.