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

arXiv:1710.05551 · Journal of Physics A Mathematical and Theoretical

Majorization and the time complexity of linear optical networks

Seungbeom Chin, Joonsuk Huh

Published May 17, 2019• 8 citations
arXivHTMLPDF

Abstract

Abstract This work shows that the majorization of photon distributions is related to the runtime of classically simulating multimode passive linear optics, which explains one aspect of the boson sampling hardness. A Shur-concave quantity which we name the Boltzmann entropy of elementary quantum complexity ( ) is introduced to present some quantitative analysis of the relation between the majorization and the classical runtime for simulating linear optics. We compare with two quantities that are important criteria for understanding the computational cost of the photon scattering process, (the runtime for the classical simulation of linear optics) and (the additive error bound for an approximated amplitude estimator). First, for all the known algorithms for computing the permanents of matrices with repeated rows and columns, the runtime becomes shorter as the input and output distribution vectors are more majorized. Second, the error bound decreases as the majorization difference of input and output states increases. We expect that our current results would help in understanding the feature of linear optical networks from the perspective of quantum computation.

DOI
10.1088/1751-8121/ab1cc7

Related papers

Majorization, Entropy and Computational Complexity of Linear Optics

Seungbeom Chin, Joonsuk Huh

One of the most important problems in linear optics quantum computing is to find the origin of its computational complexity. This work shows that the majorization of photon distributions is one of the crucial factors that affect the complexity of multimode passive linear optics, which explains one aspect of the boson sampling hardness. As a preliminary to the main discussion, a majorization-dependent quantity that can measure the quantum complexity of identical particle distributions is introduced, which we name \emph{the Boltzmann entropy of elementary quantum complexity $S_B^q$.} It decreases as the majorization of the photon distribution vector increases (Schur concavity). Using the properties of majorization and $S_B^q$, we analyze two quantities that are important criteria for the photon scattering process, $\cT$ (the runtime of a generalized classical algorithm for calculating the permanent) and $\cE$ (the additive error bound for an approximated permanent estimator). First, for all the known algorithms for computing the permanents of matrices with repeated rows and columns, the runtime $\cT$ becomes shorter as the input and output distribution vectors are more majorized. Second, the error bound $\cE$ decreases as the majorization difference of input and output states increases. In addition, $S_B^q$ turns out to be an underlying quantity of $\cT$ and $\cE$, which implies that $S_B^q$ is an essential resource for the computational complexity of linear optics. We expect that our current results would provide a clue to find the genuine resource of quantum supremacy and its operational mechanism in linear optics.

•Oct 16, 2017•0 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

Efficient classical algorithm for estimating linear statistics of Boson Sampling

Benoit Seron, Hugo Thomas, Eduardo Araujo +3 more

Boson Sampling is a prominent candidate for the demonstration of quantum computational advantage but it remains unclear whether a large-scale boson sampler can find useful computational applications. The challenge is that to use a boson sampler to estimate, for example, a physical observable, it is necessary to coarse grain the outcome distribution, owing to the exponential size of the outcome space and the anti-concentration properties of the Boson Sampling distribution. In this work, we analyse the complexity of a specific type of coarse-graining of Boson Sampling distributions based on linear functions of the output photon occupation numbers, which we refer to as linear statistics. We present an efficient classical algorithm for approximating linear statistics of boson samplers within additive error for different kinds of input states, such as Fock states and squeezed states. This allows us to unify in the same framework recent results on efficient quantum-inspired classical algorithms for simulating molecular vibronic spectra, or efficient classical approximations of coarse-grained distributions based on detector binning. Additionally, we show how our algorithm can be used to classically evaluate a proposed one-way function based on Boson Sampling, while other proposals for cryptographic applications escape our classical simulation techniques. We leave open the question of classical simulability of non-linear statistics and connect it to the problem of computing transition amplitudes of linear-optical circuits with one layer of interactions.

quant-pharXiv:2609.35447•Sep 29, 2026•0 citations

Generalized concurrence in boson sampling

Seungbeom Chin, Joonsuk Huh

Abstract A fundamental question in linear optical quantum computing is to understand the origin of the quantum supremacy in the physical system. It is found that the multimode linear optical transition amplitudes are calculated through the permanents of transition operator matrices, which is a hard problem for classical simulations (boson sampling problem). We can understand this problem by considering a quantum measure that directly determines the runtime for computing the transition amplitudes. In this paper, we suggest a quantum measure named “Fock state concurrence sum” C S , which is the summation over all the members of “the generalized Fock state concurrence” (a measure analogous to the generalized concurrences of entanglement and coherence). By introducing generalized algorithms for computing the transition amplitudes of the Fock state boson sampling with an arbitrary number of photons per mode, we show that the minimal classical runtime for all the known algorithms directly depends on C S . Therefore, we can state that the Fock state concurrence sum C S behaves as a collective measure that controls the computational complexity of Fock state BS. We expect that our observation on the role of the Fock state concurrence in the generalized algorithm for permanents would provide a unified viewpoint to interpret the quantum computing power of linear optics.

arXiv:1605.08506•Scientific Reports•Apr 11, 2018•26 citations

What can quantum optics say about 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 new results that are of interest from both quantum theory and the complexity theory point of view. We derive a general formula for calculating the output probabilities. By considering input thermal states, we show that the output probabilities are proportional to permanents of positive definite 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 within the third level of the polynomial hierarchy, as there exists an efficient classical algorithm for sampling from the output probability distribution. On the other hand, considering input squeezed-vacuum states, we show the output probabilities are proportional to a quantity which is, for at least a specific configuration, #P-hard to approximate.

•Aug 16, 2014•6 citations

Classical Algorithms for Function Computation in Gaussian Boson Sampling

Ruoting Dou, Hao Zhan, Shengjun Wu +2 more

Gaussian boson sampling (GBS) seeks quantum advantage by sampling photon-number patterns generated with squeezed inputs and passive linear optics. Many proposed GBS applications instead target function computation by applying functions to mode-resolved photon-number outcomes---a natural form of experimental postprocessing that produces classical outputs. Sampling hardness alone, however, does not determine the complexity of these tasks. By analyzing the irreducible decomposition of fixed-photon-number operator spaces, we prove that the expectation value of every such function in the average case over passive linear-optical networks can be classically evaluated for inputs with finite squeezing strength. We also provide a classical algorithm that estimates this value to inverse-polynomial additive error. The result provides new theoretical tools for analyzing linear-optical quantum systems, helps clarify the origin of current GBS hardness evidence, and inspires new applications of GBS with genuine quantum advantages.

quant-pharXiv:2609.38882•Oct 1, 2026•0 citations
Abstract This work shows that the majorization of photon distributions is related to the runtime of classically simulating multimode passive linear optics, which explains one aspect of the boson sampling hardness. A Shur-concave quantity which we name the Boltzmann entropy of elementary quantum complexity ( ) is introduced to present some quantitative analysis of the relation between the majorization and the classical runtime for simulating linear optics. We compare with two quantities that are important criteria for understanding the computational cost of the photon scattering process, (the runtime for the classical simulation of linear optics) and (the additive error bound for an approximated amplitude estimator). First, for all the known algorithms for computing the permanents of matrices with repeated rows and columns, the runtime becomes shorter as the input and output distribution vectors are more majorized. Second, the error bound decreases as the majorization difference of input and output states increases. We expect that our current results would help in understanding the feature of linear optical networks from the perspective of quantum computation.
One of the most important problems in linear optics quantum computing is to find the origin of its computational complexity. This work shows that the majorization of photon distributions is one of the crucial factors that affect the complexity of multimode passive linear optics, which explains one aspect of the boson sampling hardness. As a preliminary to the main discussion, a majorization-dependent quantity that can measure the quantum complexity of identical particle distributions is introduced, which we name \emph{the Boltzmann entropy of elementary quantum complexity SBqS_B^qSBq​.} It decreases as the majorization of the photon distribution vector increases (Schur concavity). Using the properties of majorization and SBqS_B^qSBq​, we analyze two quantities that are important criteria for the photon scattering process, $\cT$ (the runtime of a generalized classical algorithm for calculating the permanent) and $\cE$ (the additive error bound for an approximated permanent estimator). First, for all the known algorithms for computing the permanents of matrices with repeated rows and columns, the runtime $\cT$ becomes shorter as the input and output distribution vectors are more majorized. Second, the error bound $\cE$ decreases as the majorization difference of input and output states increases. In addition, SBqS_B^qSBq​ turns out to be an underlying quantity of $\cT$ and $\cE$, which implies that SBqS_B^qSBq​ is an essential resource for the computational complexity of linear optics. We expect that our current results would provide a clue to find the genuine resource of quantum supremacy and its operational mechanism in linear optics.
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.
Boson Sampling is a prominent candidate for the demonstration of quantum computational advantage but it remains unclear whether a large-scale boson sampler can find useful computational applications. The challenge is that to use a boson sampler to estimate, for example, a physical observable, it is necessary to coarse grain the outcome distribution, owing to the exponential size of the outcome space and the anti-concentration properties of the Boson Sampling distribution. In this work, we analyse the complexity of a specific type of coarse-graining of Boson Sampling distributions based on linear functions of the output photon occupation numbers, which we refer to as linear statistics. We present an efficient classical algorithm for approximating linear statistics of boson samplers within additive error for different kinds of input states, such as Fock states and squeezed states. This allows us to unify in the same framework recent results on efficient quantum-inspired classical algorithms for simulating molecular vibronic spectra, or efficient classical approximations of coarse-grained distributions based on detector binning. Additionally, we show how our algorithm can be used to classically evaluate a proposed one-way function based on Boson Sampling, while other proposals for cryptographic applications escape our classical simulation techniques. We leave open the question of classical simulability of non-linear statistics and connect it to the problem of computing transition amplitudes of linear-optical circuits with one layer of interactions.
Abstract A fundamental question in linear optical quantum computing is to understand the origin of the quantum supremacy in the physical system. It is found that the multimode linear optical transition amplitudes are calculated through the permanents of transition operator matrices, which is a hard problem for classical simulations (boson sampling problem). We can understand this problem by considering a quantum measure that directly determines the runtime for computing the transition amplitudes. In this paper, we suggest a quantum measure named “Fock state concurrence sum” C S , which is the summation over all the members of “the generalized Fock state concurrence” (a measure analogous to the generalized concurrences of entanglement and coherence). By introducing generalized algorithms for computing the transition amplitudes of the Fock state boson sampling with an arbitrary number of photons per mode, we show that the minimal classical runtime for all the known algorithms directly depends on C S . Therefore, we can state that the Fock state concurrence sum C S behaves as a collective measure that controls the computational complexity of Fock state BS. We expect that our observation on the role of the Fock state concurrence in the generalized algorithm for permanents would provide a unified viewpoint to interpret the quantum computing power of linear optics.
Considering the problem of sampling from the output photon-counting probability distribution of a linear-optical network for input Gaussian states, we obtain new results that are of interest from both quantum theory and the complexity theory point of view. We derive a general formula for calculating the output probabilities. By considering input thermal states, we show that the output probabilities are proportional to permanents of positive definite 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 within the third level of the polynomial hierarchy, as there exists an efficient classical algorithm for sampling from the output probability distribution. On the other hand, considering input squeezed-vacuum states, we show the output probabilities are proportional to a quantity which is, for at least a specific configuration, #P-hard to approximate.
Gaussian boson sampling (GBS) seeks quantum advantage by sampling photon-number patterns generated with squeezed inputs and passive linear optics. Many proposed GBS applications instead target function computation by applying functions to mode-resolved photon-number outcomes---a natural form of experimental postprocessing that produces classical outputs. Sampling hardness alone, however, does not determine the complexity of these tasks. By analyzing the irreducible decomposition of fixed-photon-number operator spaces, we prove that the expectation value of every such function in the average case over passive linear-optical networks can be classically evaluated for inputs with finite squeezing strength. We also provide a classical algorithm that estimates this value to inverse-polynomial additive error. The result provides new theoretical tools for analyzing linear-optical quantum systems, helps clarify the origin of current GBS hardness evidence, and inspires new applications of GBS with genuine quantum advantages.