Fully polynomial sampling of boson sampling with constant photon transmission
- Field
- Topics
Problem
For every fixed rational transmission \(0<\eta<1\), is boson sampling with independent photon loss classically samplable in fully polynomial time? Let \(m\geq n\geq1\) and draw \(U\in U(m)\) from normalized Haar measure. Inject one perfectly indistinguishable photon into each of the first \(n\) input modes. Each photon survives independently with probability \(\eta\). The photon-counting distribution is
In Eq. (1), \(U_{s,T}\) selects columns in \(T\) and repeats row \(j\) exactly \(s_j\) times. For a \(k\times k\) matrix \(A\), \(\operatorname{Per}A=\sum_{\pi\in S_k}\prod_{j=1}^kA_{j,\pi(j)}\); the empty permanent equals one. A randomized classical algorithm receives \(n,m,\varepsilon\) and a finite description of \(U\), with \(0<\varepsilon<1\). Use \(\operatorname{poly}(n,m,\log(1/\varepsilon))\) bits to encode the matrix. Choose the precision so that its contribution to total variation is at most \(\varepsilon/2\). For every \(n,m,\varepsilon\), require an output law \(q_U\) satisfying
Can Eq. (2) be achieved in time polynomial in \(n,m,1/\varepsilon\) and the binary input length? The polynomial may depend on the fixed \(\eta\), but its exponent cannot depend on \(\varepsilon\).
Source
This fully polynomial, Haar-average formulation refines the constant-transmission gap after Corollary 3 of Oszmaniec and Brod [OB18]. It specifies the loss-only model and accuracy dependence; it is not a numbered conjecture of that paper.
Progress
Oszmaniec and Brod, Lemma 1 and Corollary 3, give an efficient sampler with
\begin{equation} \operatorname{TV}(q_U,p_{\eta,U}) \leq\Delta(\eta,n) \leq\frac{\eta^2 n+\eta(1-\eta)}2 \tag{3} \end{equation}uniformly in \(U\). Equation (3) vanishes for \(\eta=o(n^{-1/2})\), while \(\eta\) in the question is fixed [OB18].
The interference-truncation approach discussed by Moylett et al., Sections II.C–II.D, has a probability-evaluation cost with an exponent depending on the accuracy-dependent cutoff \(k\). They also describe negative truncated weights and a Metropolised independence sampler whose training cost depends on the distribution. These statements do not establish the fully polynomial sampling guarantee posed here [MGRT20].
Park and Oh’s July 2026 revision proves, in Theorem 1 and Eq. (26), efficient matrix-product-state approximation for transmissions \(\eta=O((\log n/n)^{1/(2\alpha)})\) with fixed \(1/2<\alpha<1\). Their proof controls all passive interferometers and output bipartitions. This is a regime of vanishing transmission and does not settle fixed \(\eta\) [PO26].
Comment
The question concerns perfectly indistinguishable input photons, uniform independent loss, ideal photon counting, and arbitrary mode counts \(m\geq n\). A polynomial-time algorithm at each fixed error, with an error-dependent polynomial degree, does not meet the requested runtime. Bounds for Gaussian input states, restricted-depth circuits, or only a constant number of lost photons have different hypotheses.