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

A deep learning approach to estimating permanents

Britton Chang

Published Jan 1, 2018• 0 citations
OpenAlex

Abstract

The permanent of a matrix is a value that can be computed from a square matrix. It is calculated in almost the same way as the determinant, but all of the terms in the permanent are summed. The permanent has an application in a quantum optical experiment known as boson sampling. The probability of the outcome of this experiment can be calculated by taking the permanent of a matrix. It is believed that the complexity of approximating the outcome of this experiment is related to the photon indistinguishability. At full distinguishability, it is expected to follow polynomial complexity as the matrix size increases. At full indistinguishability, it is expected to follow exponential complexity. For partial indistinguishability, the complexity is expected to be somewhere in between. The aim of this research is to use deep learning networks to estimate the permanents for varying levels of photon indistinguishability and to investigate whether the complexity of the networks reflects the expected complexity of estimating the outcome of the boson sampling experiment

Related papers

Quantum photonic computer technology for solving complex computational problems of high availability systems

F.K. Aliyev, E.G. Bukin, A. V. Korol’kov +1 more

We consider the problem of calculating the approximate value (estimate) of the permanent of a square matrix over the field of real numbers using a photonic quantum computer that sampling bosons from a given distribution. It is pointed out that it is possible to effectively solve this problem for the following three classes of matrices: symmetric matrices which eigenvalues do not exceed 1 in absolute value; orthogonal matrices; doubly stochastic matrices. For the last two classes, we are talking about evaluating the square of the permanent. The mathematical basis for solving the problem is the formula, which represents the permanent of the Hermitian matrix as the mathematical expectation of some random variable which values are equal to the products of the powers of the eigenvalues of the Hermitian matrix. And the corresponding probabilities with which these products are accepted as values of a random variable are also completely determined by the same Hermitian matrix. This circumstance allows using the methods of probability theory in order to solve the problem of permanent estimation.

Highly available systems•Jan 1, 2021•0 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

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

Quantum estimation bound of the Gaussian matrix permanent

Joonsuk Huh

Exact calculation and even multiplicative error estimation of matrix permanent are challenging for both classical and quantum computers. Regarding the permanents of random Gaussian matrices, the additive error estimation is closely linked to boson sampling and achieving multiplicative error estimation requires exponentially many samplings. Our formula for matrix permanents and its corresponding quantum expression have enabled better estimation of the average additive error for random Gaussian matrices compared to Gurvits' classical sampling algorithm. The well-known Ryser formula has been converted into a quantum permanent estimator. When dealing with real random Gaussian square matrices of size $N$, the quantum estimator can approximate the matrix permanent with an additive error smaller than $\ensuremath{\epsilon}{(\sqrt{\mathrm{e}N})}^{N}$, where $\ensuremath{\epsilon}$ is the estimation precision. In contrast, Gurvits' classical sampling algorithm has an estimation error of $\ensuremath{\epsilon}{(2\sqrt{N})}^{N}$, which is exponentially larger ($1.{2}^{N}$) than the quantum method. As expected, the quantum additive error bound fails to reach the multiplicative error bound of ${(2\ensuremath{\pi}N)}^{1/4}\ensuremath{\epsilon}{(\sqrt{N/\mathrm{e}})}^{N}$. Additionally, the quantum permanent estimator can be up to quadratically faster than the classical estimator when using quantum phase estimation-based amplitude estimation.

arXiv:2205.01328•Physical Review A•Jan 13, 2025•6 citations

Faster classical boson sampling

Peter Clifford, Raphaël Clifford A

Abstract Since its introduction boson sampling has been the subject of intense study in the world of quantum computing. In the context of Fock-state boson sampling, the task is to sample independently from the set of all n × n submatrices built from possibly repeated rows of a larger m × n complex matrix according to a probability distribution related to the permanents of the submatrices. Experimental systems exploiting quantum photonic effects can in principle perform the task at great speed. For classical computing, Aaronson and Arkhipov (2011) showed that exact boson sampling problem cannot be solved in polynomial time unless the polynomial hierarchy collapses to the third level. Indeed for a number of years the fastest known exact classical algorithm ran in O ( m + n − 1 n n 2 n ) time per sample, emphasising the potential speed advantage of quantum computation. The advantage was reduced by Clifford and Clifford (2018), who gave a significantly faster classical solution taking O ( n 2 n + poly ( m , n ) ) time and linear space, matching the complexity of computing the permanent of a single matrix when m is polynomial in n. We continue by presenting an algorithm for Fock boson sampling whose average-case time complexity is much faster when m is proportional to n. In particular, when m = n our algorithm runs in approximately O(n · 1.69 n ) time on average. This result further increases the problem size needed to establish quantum computational advantage via the Fock scheme of boson sampling.

arXiv:2005.04214•Physica Scripta•May 2, 2024•21 citations

Boson sampling with photons of arbitrary spectral structure

Peter P. Rohde

Boson sampling has attracted much interest as a simplified approach to implementing a subset of optical quantum computing. Boson sampling requires indistinguishable photons, but far fewer of them than universal optical quantum computing architectures. In reality, photons are never indistinguishable, and exhibit a rich spectral structure. Here we consider the operation of boson sampling with photons of arbitrary spectral structure and relate the sampling statistics of the device to matrix permanents. This sheds light on the computational complexity of different regimes of the photons' spectral characteristics, and provides very general results for the operation of linear optics interferometers in the presence of partially distinguishable photons. Our results apply to both the cases of spectrally resolving and nonspectrally resolving detectors.

arXiv:1410.3979•Physical Review A•Jan 8, 2015•33 citations
The permanent of a matrix is a value that can be computed from a square matrix. It is calculated in almost the same way as the determinant, but all of the terms in the permanent are summed. The permanent has an application in a quantum optical experiment known as boson sampling. The probability of the outcome of this experiment can be calculated by taking the permanent of a matrix. It is believed that the complexity of approximating the outcome of this experiment is related to the photon indistinguishability. At full distinguishability, it is expected to follow polynomial complexity as the matrix size increases. At full indistinguishability, it is expected to follow exponential complexity. For partial indistinguishability, the complexity is expected to be somewhere in between. The aim of this research is to use deep learning networks to estimate the permanents for varying levels of photon indistinguishability and to investigate whether the complexity of the networks reflects the expected complexity of estimating the outcome of the boson sampling experiment
We consider the problem of calculating the approximate value (estimate) of the permanent of a square matrix over the field of real numbers using a photonic quantum computer that sampling bosons from a given distribution. It is pointed out that it is possible to effectively solve this problem for the following three classes of matrices: symmetric matrices which eigenvalues do not exceed 1 in absolute value; orthogonal matrices; doubly stochastic matrices. For the last two classes, we are talking about evaluating the square of the permanent. The mathematical basis for solving the problem is the formula, which represents the permanent of the Hermitian matrix as the mathematical expectation of some random variable which values are equal to the products of the powers of the eigenvalues of the Hermitian matrix. And the corresponding probabilities with which these products are accepted as values of a random variable are also completely determined by the same Hermitian matrix. This circumstance allows using the methods of probability theory in order to solve the problem of permanent estimation.
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.
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.
Exact calculation and even multiplicative error estimation of matrix permanent are challenging for both classical and quantum computers. Regarding the permanents of random Gaussian matrices, the additive error estimation is closely linked to boson sampling and achieving multiplicative error estimation requires exponentially many samplings. Our formula for matrix permanents and its corresponding quantum expression have enabled better estimation of the average additive error for random Gaussian matrices compared to Gurvits' classical sampling algorithm. The well-known Ryser formula has been converted into a quantum permanent estimator. When dealing with real random Gaussian square matrices of size NNN, the quantum estimator can approximate the matrix permanent with an additive error smaller than $\ensuremath{\epsilon}{(\sqrt{\mathrm{e}N})}^{N}$, where $\ensuremath{\epsilon}$ is the estimation precision. In contrast, Gurvits' classical sampling algorithm has an estimation error of $\ensuremath{\epsilon}{(2\sqrt{N})}^{N}$, which is exponentially larger (1.2N1.{2}^{N}1.2N) than the quantum method. As expected, the quantum additive error bound fails to reach the multiplicative error bound of ${(2\ensuremath{\pi}N)}^{1/4}\ensuremath{\epsilon}{(\sqrt{N/\mathrm{e}})}^{N}$. Additionally, the quantum permanent estimator can be up to quadratically faster than the classical estimator when using quantum phase estimation-based amplitude estimation.
Abstract Since its introduction boson sampling has been the subject of intense study in the world of quantum computing. In the context of Fock-state boson sampling, the task is to sample independently from the set of all n × n submatrices built from possibly repeated rows of a larger m × n complex matrix according to a probability distribution related to the permanents of the submatrices. Experimental systems exploiting quantum photonic effects can in principle perform the task at great speed. For classical computing, Aaronson and Arkhipov (2011) showed that exact boson sampling problem cannot be solved in polynomial time unless the polynomial hierarchy collapses to the third level. Indeed for a number of years the fastest known exact classical algorithm ran in O ( m + n − 1 n n 2 n ) time per sample, emphasising the potential speed advantage of quantum computation. The advantage was reduced by Clifford and Clifford (2018), who gave a significantly faster classical solution taking O ( n 2 n + poly ( m , n ) ) time and linear space, matching the complexity of computing the permanent of a single matrix when m is polynomial in n. We continue by presenting an algorithm for Fock boson sampling whose average-case time complexity is much faster when m is proportional to n. In particular, when m = n our algorithm runs in approximately O(n · 1.69 n ) time on average. This result further increases the problem size needed to establish quantum computational advantage via the Fock scheme of boson sampling.
Boson sampling has attracted much interest as a simplified approach to implementing a subset of optical quantum computing. Boson sampling requires indistinguishable photons, but far fewer of them than universal optical quantum computing architectures. In reality, photons are never indistinguishable, and exhibit a rich spectral structure. Here we consider the operation of boson sampling with photons of arbitrary spectral structure and relate the sampling statistics of the device to matrix permanents. This sheds light on the computational complexity of different regimes of the photons' spectral characteristics, and provides very general results for the operation of linear optics interferometers in the presence of partially distinguishable photons. Our results apply to both the cases of spectrally resolving and nonspectrally resolving detectors.