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:2603.02272

Analytic Cancellation of Interference Terms and Closed-Form 1-Mode Marginals in Canonical Boson Sampling

Jiang Liu

quant-phSubmitted Mar 1, 2026• Announced Mar 3, 2026• 0 citations
arXivHTMLPDF

Abstract

Although the $k$-mode marginal distributions of Canonical Boson Sampling (CBS) are known to be computable in polynomial time, the physical mechanism driving this computational efficiency remains mathematically opaque. In this work, we provide a direct, bottom-up physical derivation of the exact 1-mode marginal distribution in CBS, computable in $\mathcal{O}(R^2)$ time, where $R$ is the total number of photons. We explicitly bridge this physical derivation with the mathematical theory of rank-1 matrix permanents, proving that multiphoton interference natively reduces to a symmetric polynomial scaled by a factorial bosonic bunching factor. Crucially, we demonstrate that our recursive combinatorial formulation circumvents the algorithmic overhead of characteristic function methods, entirely bypassing the need for polynomial interpolation or Fourier transforms. Finally, we apply this formula to identify macroscopic signatures of bunching, providing a rigorous, highly scalable metric for distinguishing genuine quantum interference from classical distinguishable-particle models using standard threshold detectors.

Comments
8 pages, 1 figure, 2 tables

Related papers

The Complexity of Bipartite Gaussian Boson Sampling

Daniel Grier, Daniel J. Brod, Juan Miguel Arrazola +2 more

Gaussian boson sampling is a model of photonic quantum computing that has attracted attention as a platform for building quantum devices capable of performing tasks that are out of reach for classical devices. There is therefore significant interest, from the perspective of computational complexity theory, in solidifying the mathematical foundation for the hardness of simulating these devices. We show that, under the standard Anti-Concentration and Permanent-of-Gaussians conjectures, there is no efficient classical algorithm to sample from ideal Gaussian boson sampling distributions (even approximately) unless the polynomial hierarchy collapses. The hardness proof holds in the regime where the number of modes scales quadratically with the number of photons, a setting in which hardness was widely believed to hold but that nevertheless had no definitive proof. Crucial to the proof is a new method for programming a Gaussian boson sampling device so that the output probabilities are proportional to the permanents of submatrices of an arbitrary matrix. This technique is a generalization of Scattershot BosonSampling that we call BipartiteGBS. We also make progress towards the goal of proving hardness in the regime where there are fewer than quadratically more modes than photons (i.e., the high-collision regime) by showing that the ability to approximate permanents of matrices with repeated rows/columns confers the ability to approximate permanents of matrices with no repetitions. The reduction suffices to prove that GBS is hard in the constant-collision regime.

arXiv:2110.06964•Quantum•Nov 28, 2022•47 citations

Near-Optimal Mode Scaling for Finite-Dimensional Boson Sampling via Lie-Algebraic Leakage Bounds

Chon-Fai Kam, En-Jui Kuo

Boson sampling demonstrates quantum advantage through the interference of indistinguishable particles, with output probabilities governed by matrix permanents. Realizing it on deterministic, matter-based platforms requires encoding the bosonic modes in finite-dimensional local Hilbert spaces, which introduces a leakage channel absent in linear optics: multi-particle bunching beyond the local truncation $d$. We develop a unified framework for non-interacting sampling on the irreducible representations of compact Lie groups, in which the transition amplitude is the immanant of a submatrix of the single-particle transition matrix, recovering the permanent in the bosonic case. Within this framework we bound the bunching leakage through a Dyson-series analysis: decomposing the correlated many-body leakage operator into independent random matrices and applying non-commutative concentration inequalities, we prove, in a Gaussian model of the transition matrix, that its spectral norm concentrates at $\tilde{O}(\sqrt{n})$ rather than the $O(n)$ worst-case of prior spin-based emulations; the passage to the physical Haar ensemble is reduced to a single submatrix-comparison input, verified at leading order. Exact numerics across local dimensions $d=2$--$5$ indicate that the bound is tight, the Haar-ensemble norm matching the closed form $\sqrt{d(n-d+1)}$ to sub-percent accuracy. This tightens the required mode number from $m=Ω(n^4)$ to the near-optimal $m=\tildeΩ(n^{1+2/(d-1)})$; for a spin-1 representation ($d=3$) the overhead falls to $m=\tildeΩ(n^2)$, matching the collision-free threshold. The result is independent of particle statistics and applies across finite-dimensional Lie-symmetric architectures, quantifying the spatial resources needed to preserve sampling hardness.

quant-pharXiv:2607.11708•Jul 14, 2026•0 citations

Partially distinguishable Boson-Sampling and the multi-dimensional permanent

Malte C. Tichy

The collective interference of partially distinguishable bosons in multi-mode networks is studied via double-sided Feynman diagrams. The probability for many-body scattering events becomes a multi-dimensional tensor-permanent, which interpolates between distinguishable particles and identical bosons, and easily extends to mixed initial states. The permanent of the distinguishability matrix, composed of all mutual scalar products of the single-particle mode-functions, emerges as a natural measure for the degree of interference: It yields a bound on the difference between event probabilities for partially distinguishable bosons and the idealized species, and exactly quantifies the degree of bosonic bunching.

•Oct 28, 2014•0 citations

A unified framework for anomalous boson bunching

Léo Pioge, Leonardo Novo, Nicolas J. Cerf

Anomalous bunching is a paradoxical quantum interferometric phenomenon in which partially distinguishable photons exhibit a higher probability of bunching into two or more modes than fully indistinguishable photons [Nat. Photonics 17, 702 (2023)]. While this effect is directly linked to violations of certain conjectures on matrix permanents, the mechanism underlying the anomaly is not yet fully understood. Here, we show that boson bunching is governed not by internal indistinguishability alone, but by the total indistinguishability of the postselected output state. Total indistinguishability combines the internal degrees of freedom, such as polarization or arrival time, with the spatial degrees of freedom of their wave functions restricted to the measured output modes of the interferometer. This reformulation preserves the expected connection between boson bunching and total indistinguishability, while clarifying how anomalous bunching can arise. It also reveals several additional facets of the same phenomenon, which are captured within a unified framework. In particular, we exhibit situations in which adding an independent source of distinguishability, either internal or spatial, can enhance multimode or even single-mode bunching probabilities, offering new insights into the subtle role of distinguishability in multiphoton interference.

quant-pharXiv:2607.19499•Jul 23, 2026•3 citations

Classical sampling from noisy boson sampling and negative probabilities

V. S. Shchesnovich

It is known that, by accounting for the multiboson interferences up to a finite order, the output distribution of noisy boson sampling, with distinguishability of bosons serving as noise, can be approximately sampled from in a time polynomial in the total number of bosons. The drawback of this approach is that the joint probabilities of completely distinguishable bosons, i.e., those that do not interfere at all, have to be computed also. In trying to restore the ability to sample from the distinguishable bosons with computation of only the single-boson probabilities, one faces the following issue: the quantum probability factors in a convex-sum expression, if truncated to a finite order of multiboson interference, have, on average, a finite amount of negativity in a random interferometer. The truncated distribution does become a proper one, while allowing for sampling from it in a polynomial time, only in a vanishing domain close to the completely distinguishable bosons. Nevertheless, the conclusion that the negativity issue is inherent to all efficient classical approximations to noisy boson sampling may be premature. I outline the direction for an enitre new program, which seems to point to a solution. However, its success depends on the asymptotic behavior of the symmetric group characters, which is not known.

arXiv:2307.05344•Physical Review A•Mar 12, 2024•0 citations

The quantum multinomial distribution: a combinatorial formulation of multiphoton interference

Alfonso Martinez, Josep Font-Segura

This paper presents a quantum generalization of the multinomial distribution for the transition probabilities of $m$ identical photons in a $k$-port linear optical interferometer: two multinomial coefficients (one for the input configuration, one for the output) times the squared modulus of a coherent sum over routing matrices, weighted by the multivariate hypergeometric distribution; no Hilbert space formalism is needed to state or evaluate it. The classical multinomial is recovered when all photons enter through a single port, the coherent sum degenerating to a single term with no interference; the quantum family is not a generalization in the Askey sense but a parallel family that departs from classical statistics through the coherence of the amplitude summation. The $r$-th factorial moment carries a squared multinomial coefficient in place of the classical single one, the extra factor arising from the two copies of the amplitude expansion whose indices the Fock state forces to agree; for the beam splitter, the third cumulant is invariant under bosonic interference and the quantum departure first appears in the fourth cumulant as negative excess kurtosis; for multiport interferometers, however, three-body interference breaks this invariance and the departure enters already at the third cumulant. Cross-mode covariances involve the phases of the scattering matrix through coherence terms that strengthen output anti-correlations beyond the classical value; together with the squared-coefficient signature in the single-mode moments, these provide low-order statistical witnesses for boson sampling verification without requiring the full permanent computation.

quant-pharXiv:2602.09894•Feb 11, 2026•0 citations
Although the kkk-mode marginal distributions of Canonical Boson Sampling (CBS) are known to be computable in polynomial time, the physical mechanism driving this computational efficiency remains mathematically opaque. In this work, we provide a direct, bottom-up physical derivation of the exact 1-mode marginal distribution in CBS, computable in O(R2)\mathcal{O}(R^2)O(R2) time, where RRR is the total number of photons. We explicitly bridge this physical derivation with the mathematical theory of rank-1 matrix permanents, proving that multiphoton interference natively reduces to a symmetric polynomial scaled by a factorial bosonic bunching factor. Crucially, we demonstrate that our recursive combinatorial formulation circumvents the algorithmic overhead of characteristic function methods, entirely bypassing the need for polynomial interpolation or Fourier transforms. Finally, we apply this formula to identify macroscopic signatures of bunching, providing a rigorous, highly scalable metric for distinguishing genuine quantum interference from classical distinguishable-particle models using standard threshold detectors.
Gaussian boson sampling is a model of photonic quantum computing that has attracted attention as a platform for building quantum devices capable of performing tasks that are out of reach for classical devices. There is therefore significant interest, from the perspective of computational complexity theory, in solidifying the mathematical foundation for the hardness of simulating these devices. We show that, under the standard Anti-Concentration and Permanent-of-Gaussians conjectures, there is no efficient classical algorithm to sample from ideal Gaussian boson sampling distributions (even approximately) unless the polynomial hierarchy collapses. The hardness proof holds in the regime where the number of modes scales quadratically with the number of photons, a setting in which hardness was widely believed to hold but that nevertheless had no definitive proof. Crucial to the proof is a new method for programming a Gaussian boson sampling device so that the output probabilities are proportional to the permanents of submatrices of an arbitrary matrix. This technique is a generalization of Scattershot BosonSampling that we call BipartiteGBS. We also make progress towards the goal of proving hardness in the regime where there are fewer than quadratically more modes than photons (i.e., the high-collision regime) by showing that the ability to approximate permanents of matrices with repeated rows/columns confers the ability to approximate permanents of matrices with no repetitions. The reduction suffices to prove that GBS is hard in the constant-collision regime.
Boson sampling demonstrates quantum advantage through the interference of indistinguishable particles, with output probabilities governed by matrix permanents. Realizing it on deterministic, matter-based platforms requires encoding the bosonic modes in finite-dimensional local Hilbert spaces, which introduces a leakage channel absent in linear optics: multi-particle bunching beyond the local truncation ddd. We develop a unified framework for non-interacting sampling on the irreducible representations of compact Lie groups, in which the transition amplitude is the immanant of a submatrix of the single-particle transition matrix, recovering the permanent in the bosonic case. Within this framework we bound the bunching leakage through a Dyson-series analysis: decomposing the correlated many-body leakage operator into independent random matrices and applying non-commutative concentration inequalities, we prove, in a Gaussian model of the transition matrix, that its spectral norm concentrates at O~(n)\tilde{O}(\sqrt{n})O~(n​) rather than the O(n)O(n)O(n) worst-case of prior spin-based emulations; the passage to the physical Haar ensemble is reduced to a single submatrix-comparison input, verified at leading order. Exact numerics across local dimensions d=2d=2d=2--555 indicate that the bound is tight, the Haar-ensemble norm matching the closed form d(n−d+1)\sqrt{d(n-d+1)}d(n−d+1)​ to sub-percent accuracy. This tightens the required mode number from m=Ω(n4)m=Ω(n^4)m=Ω(n4) to the near-optimal m=Ω~(n1+2/(d−1))m=\tildeΩ(n^{1+2/(d-1)})m=Ω~(n1+2/(d−1)); for a spin-1 representation (d=3d=3d=3) the overhead falls to m=Ω~(n2)m=\tildeΩ(n^2)m=Ω~(n2), matching the collision-free threshold. The result is independent of particle statistics and applies across finite-dimensional Lie-symmetric architectures, quantifying the spatial resources needed to preserve sampling hardness.
The collective interference of partially distinguishable bosons in multi-mode networks is studied via double-sided Feynman diagrams. The probability for many-body scattering events becomes a multi-dimensional tensor-permanent, which interpolates between distinguishable particles and identical bosons, and easily extends to mixed initial states. The permanent of the distinguishability matrix, composed of all mutual scalar products of the single-particle mode-functions, emerges as a natural measure for the degree of interference: It yields a bound on the difference between event probabilities for partially distinguishable bosons and the idealized species, and exactly quantifies the degree of bosonic bunching.
Anomalous bunching is a paradoxical quantum interferometric phenomenon in which partially distinguishable photons exhibit a higher probability of bunching into two or more modes than fully indistinguishable photons [Nat. Photonics 17, 702 (2023)]. While this effect is directly linked to violations of certain conjectures on matrix permanents, the mechanism underlying the anomaly is not yet fully understood. Here, we show that boson bunching is governed not by internal indistinguishability alone, but by the total indistinguishability of the postselected output state. Total indistinguishability combines the internal degrees of freedom, such as polarization or arrival time, with the spatial degrees of freedom of their wave functions restricted to the measured output modes of the interferometer. This reformulation preserves the expected connection between boson bunching and total indistinguishability, while clarifying how anomalous bunching can arise. It also reveals several additional facets of the same phenomenon, which are captured within a unified framework. In particular, we exhibit situations in which adding an independent source of distinguishability, either internal or spatial, can enhance multimode or even single-mode bunching probabilities, offering new insights into the subtle role of distinguishability in multiphoton interference.
It is known that, by accounting for the multiboson interferences up to a finite order, the output distribution of noisy boson sampling, with distinguishability of bosons serving as noise, can be approximately sampled from in a time polynomial in the total number of bosons. The drawback of this approach is that the joint probabilities of completely distinguishable bosons, i.e., those that do not interfere at all, have to be computed also. In trying to restore the ability to sample from the distinguishable bosons with computation of only the single-boson probabilities, one faces the following issue: the quantum probability factors in a convex-sum expression, if truncated to a finite order of multiboson interference, have, on average, a finite amount of negativity in a random interferometer. The truncated distribution does become a proper one, while allowing for sampling from it in a polynomial time, only in a vanishing domain close to the completely distinguishable bosons. Nevertheless, the conclusion that the negativity issue is inherent to all efficient classical approximations to noisy boson sampling may be premature. I outline the direction for an enitre new program, which seems to point to a solution. However, its success depends on the asymptotic behavior of the symmetric group characters, which is not known.
This paper presents a quantum generalization of the multinomial distribution for the transition probabilities of mmm identical photons in a kkk-port linear optical interferometer: two multinomial coefficients (one for the input configuration, one for the output) times the squared modulus of a coherent sum over routing matrices, weighted by the multivariate hypergeometric distribution; no Hilbert space formalism is needed to state or evaluate it. The classical multinomial is recovered when all photons enter through a single port, the coherent sum degenerating to a single term with no interference; the quantum family is not a generalization in the Askey sense but a parallel family that departs from classical statistics through the coherence of the amplitude summation. The rrr-th factorial moment carries a squared multinomial coefficient in place of the classical single one, the extra factor arising from the two copies of the amplitude expansion whose indices the Fock state forces to agree; for the beam splitter, the third cumulant is invariant under bosonic interference and the quantum departure first appears in the fourth cumulant as negative excess kurtosis; for multiport interferometers, however, three-body interference breaks this invariance and the departure enters already at the third cumulant. Cross-mode covariances involve the phases of the scattering matrix through coherence terms that strengthen output anti-correlations beyond the classical value; together with the squared-coefficient signature in the single-mode moments, these provide low-order statistical witnesses for boson sampling verification without requiring the full permanent computation.