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

Highly available systems

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

F.K. Aliyev, E.G. Bukin, A. V. Korol’kov, E. A. Matveev

Published Jan 1, 2021• 0 citations
Publisher

Abstract

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.

DOI
10.18127/j20729472-202104-03

Related papers

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

Theoretical foundations for creating a quantum photon computer

F.K. Aliev, A.P. Baranov, A.V. Ivakhin +2 more

Currently, significant results have emerged in the field of creation and application of quantum computers. We are talking about the Chinese quantum photonic computers Jiuzhang, Jiuzhang-2 (Jiuzhang 2.0), Jiuzhang-3 (Jiuzhang 3.0), which appeared respectively in 2020, 2021 and 2023, as well as the Canadian quantum photonic computer Borealis, which appeared in 2022. All these computers belong to the class of so-called quantum simulators – variants of quantum computers that solve one problem or a narrow class of problems. In addition to narrow specialization, quantum simulators have another important feature. In quantum simulators, controllable quantum objects simulate and effectively predict the behavior of real quantum systems. For example, in the quantum photonic computers Jiuzhang, Jiuzhang-2, Jiuzhang-3 and Borealis, the photons supplied to the inputs of these computers imitate the behavior of a “system of non-interacting identical bosons.” The Jiuzhang, Jiuzhang-2, Jiuzhang-3, and Borealis quantum simulators solve the problem of sampling bosons from a given distribution. Together they represent a significant scientific, technical and technological breakthrough in the development and creation of quantum computers. However, beyond what has been achieved, a number of important issues that are of interest both theoretically and for the field of practical applications remain unexamined. Among them are the following: about the architecture and composition of the elements of a quantum photonic computer, their number and connection diagram, as well as setting parameters that determine the required probability distribution from which boson samples are taken. The scientific problem addressed in the article is to obtain answers to the above questions by developing the theoretical foundations for creating a quantum photonic computer that solves the problem of sampling bosons from a given distribution in the most general case without restrictions on the distribution. The following results were obtained: the theoretical basis for the creation of a quantum photon computer (called in the article the Fuzuli boson sampler, briefly bsF) was developed that solves the problem of sampling bosons from a given distribution, for use as a quantum computing subsystem of a hybrid computing system to solve the problem of estimating matrix permanents; its constituent elements have been identified and studied, their numbers have been determined, and inter-element connection diagrams have been developed; an algorithm has been developed for tuning the bsF quantum photon computer to solve the problem of estimating matrix permanents; The functioning process of bsF is described. The article assumes that physically, in each cycle of operation of the bsF computer, the process of supplying photons to the inputs of the computer, their “movement” to the detectors, as well as the registration of photons by detectors is organized in such a way that the set of these photons imitates the behavior of a system of non-interacting identical bosons. Physical and engineering issues of ensuring such behavior of photons are not considered in this work. At the same time, the feasibility of such a possibility in practice (experimentally) is assumed to be undeniable. Examples confirming this position are the already created prototypes of quantum photonic computers in China (Jiuzhang, Jiuzhang-2, Jiuzhang-3) and in Canada (Borealis).

Highly available systems•Feb 2, 2024•0 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

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

A deep learning approach to estimating permanents

Britton Chang

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

•Jan 1, 2018•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
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.
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.
Currently, significant results have emerged in the field of creation and application of quantum computers. We are talking about the Chinese quantum photonic computers Jiuzhang, Jiuzhang-2 (Jiuzhang 2.0), Jiuzhang-3 (Jiuzhang 3.0), which appeared respectively in 2020, 2021 and 2023, as well as the Canadian quantum photonic computer Borealis, which appeared in 2022. All these computers belong to the class of so-called quantum simulators – variants of quantum computers that solve one problem or a narrow class of problems. In addition to narrow specialization, quantum simulators have another important feature. In quantum simulators, controllable quantum objects simulate and effectively predict the behavior of real quantum systems. For example, in the quantum photonic computers Jiuzhang, Jiuzhang-2, Jiuzhang-3 and Borealis, the photons supplied to the inputs of these computers imitate the behavior of a “system of non-interacting identical bosons.” The Jiuzhang, Jiuzhang-2, Jiuzhang-3, and Borealis quantum simulators solve the problem of sampling bosons from a given distribution. Together they represent a significant scientific, technical and technological breakthrough in the development and creation of quantum computers. However, beyond what has been achieved, a number of important issues that are of interest both theoretically and for the field of practical applications remain unexamined. Among them are the following: about the architecture and composition of the elements of a quantum photonic computer, their number and connection diagram, as well as setting parameters that determine the required probability distribution from which boson samples are taken. The scientific problem addressed in the article is to obtain answers to the above questions by developing the theoretical foundations for creating a quantum photonic computer that solves the problem of sampling bosons from a given distribution in the most general case without restrictions on the distribution. The following results were obtained: the theoretical basis for the creation of a quantum photon computer (called in the article the Fuzuli boson sampler, briefly bsF) was developed that solves the problem of sampling bosons from a given distribution, for use as a quantum computing subsystem of a hybrid computing system to solve the problem of estimating matrix permanents; its constituent elements have been identified and studied, their numbers have been determined, and inter-element connection diagrams have been developed; an algorithm has been developed for tuning the bsF quantum photon computer to solve the problem of estimating matrix permanents; The functioning process of bsF is described. The article assumes that physically, in each cycle of operation of the bsF computer, the process of supplying photons to the inputs of the computer, their “movement” to the detectors, as well as the registration of photons by detectors is organized in such a way that the set of these photons imitates the behavior of a system of non-interacting identical bosons. Physical and engineering issues of ensuring such behavior of photons are not considered in this work. At the same time, the feasibility of such a possibility in practice (experimentally) is assumed to be undeniable. Examples confirming this position are the already created prototypes of quantum photonic computers in China (Jiuzhang, Jiuzhang-2, Jiuzhang-3) and in Canada (Borealis).
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.
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 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
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.