Introduction
In an optical boson sampler, indistinguishable photons interfere in a network of beam splitters and phase shifters, and detectors record the photon number at each output. The computational task is to sample this joint output distribution for a specified input state and interferometer. Experimental runs provide these samples directly, whereas classical simulation is believed to be intractable under plausible assumptions [1 ] . This makes boson sampling a candidate for demonstrating quantum computational advantage without a universal quantum computer. Photonic implementations toward this goal use single photons [2 ] or squeezed light [3 , 4 , 5 , 6 , 7 , 8 , 9 ] in free-space optics, optical fibers and integrated circuits, with increasing numbers of photons and optical modes.
Photon loss is a severe parameter in experiments. Jiuzhang 4.0, for example, reports an overall system efficiency of 51%, corresponding to detection of only about half the generated photons [8 ] . Assessing quantum computational advantage in these experiments therefore requires understanding the classical cost of sampling from their lossy output distributions. Conditional hardness has been established when only a logarithmic number of photons is lost on average [10 , 11 , 12 ] , whereas efficient classical simulation is known under sufficiently strong loss that the surviving fraction tends to zero [13 , 14 , 15 , 16 , 17 , 18 ] . These earlier results left a broad range between the two regimes unresolved, including the experimentally relevant case of a fixed loss rate. At a fixed rate, both the mean detected count and the mean number of lost photons grow in proportion to the input size.
For two standard families of input states, we show that a classical computer can efficiently sample the lossy output distribution at any fixed rate of uniform photon loss, however small. The first family is Fock state boson sampling with one photon in each occupied input mode and any number of empty modes. The second is Gaussian boson sampling with all input modes squeezed equally, by an amount that stays bounded as the system grows. Accuracy is the total variation distance between the distribution produced by the classical sampler and the lossy output distribution, taken over all output configurations and averaged over Haar random interferometers. Bringing this distance below any target takes time polynomial in the number of modes and in the inverse of the target. The running time therefore stays polynomial even when the error shrinks as an inverse polynomial in system size.
These are exactly the conditions under which the hardness of boson sampling is argued, with the same input states, Haar random interferometers and inverse polynomial total variation error [1 , 12 , 19 ] . Our results differ from those arguments only in the amount of photon loss. In the known hard regime, only a logarithmic number of photons is lost on average, whereas we prove efficient sampling whenever a fixed fraction of the photons is lost. The unresolved range between the two regimes is thereby narrowed to loss rates that decrease toward zero as the system grows. Experiments performed with interferometers close to Haar random at a fixed loss rate therefore cannot guarantee quantum computational advantage.
Problem
In a boson sampling task, an input state of M M M optical modes passes through a passive linear interferometer, and photon number resolving detectors count the photons in every output mode. The interferometer acts on the mode operators through an M × M M \times M M × M unitary matrix U U U . Each photon reaches the detectors with probability η \eta η , independently of the other photons and of its path through the interferometer (Figure 1 a). We call 0 < η < 1 0 < \eta< 1 0 < η < 1 the transmission and 1 − η 1 - \eta 1 − η the loss rate. A run yields an output configuration x = ( x 1 , … , x M ) x = (x_1, \ldots, x_M) x = ( x 1 , … , x M ) with k = ∑ i x i k = \sum_i x_i k = ∑ i x i detected photons, and P U ( x ) P_U(x) P U ( x ) denotes its probability for a given input state. This distribution includes every value of k k k and every configuration with several photons in one output mode. Although we use optical language, the analysis relies only on bosonic statistics and uniform particle loss, so it applies equally to other noninteracting bosons, such as atoms in optical lattices [20 ] .
Figure 1. Loss suppresses correlations among many photons. a, Single photons enter a Haar random interferometer U U U , and each photon reaches the photon number resolving detectors with probability η \eta η . b, Upper bound on the mean squared error, averaged over U U U , from keeping only correlations among at most L L L photons, for n = 100 n = 100 n = 100 single photons. Without loss (η = 1 \eta= 1 η = 1 ) the error decreases only linearly in L L L , whereas loss makes it decay exponentially. c, Cutoff L L L needed for total variation error 1 / n 1/n 1/ n . It grows only logarithmically with the number of detected photons.
The interferometer is drawn once from the Haar measure, the uniform distribution on M × M M \times M M × M unitary matrices, and is then kept fixed for all runs. A classical sampler receives U U U and outputs samples from a distribution Q U Q_U Q U . We measure its error by the total variation distance d T V ( P U , Q U ) = 1 2 ∑ x ∣ P U ( x ) − Q U ( x ) ∣ d_{\mathrm{TV}}(P_U,Q_U) = \frac{1}{2}\sum_x \lvert P_U(x)-Q_U(x)\rvert d TV ( P U , Q U ) = 2 1 ∑ x ∣ P U ( x ) − Q U ( x )∣ , which bounds the error in the probability of every set of output configurations. We consider two input families.
Problem 1 (Lossy Fock state boson sampling). Single photons occupy n ≤ M n \le M n ≤ M distinct input modes, and the remaining modes are in vacuum,
∣ Ψ F ⟩ = ∣ 1 ⟩ ⊗ n ∣ 0 ⟩ ⊗ ( M − n ) . (1) \lvert\Psi_{\mathrm{F}}\rangle= \lvert1\rangle^{\otimes n}\lvert0\rangle^{\otimes(M-n)}. \tag*{(1)} ∣ Ψ F ⟩ = ∣ 1 ⟩ ⊗ n ∣ 0 ⟩ ⊗ ( M − n ) . (1) Given U U U , η \eta η and ϵ > 0 \epsilon> 0 ϵ > 0 , generate samples from a distribution Q U Q_U Q U with E U ∼ H a a r d T V ( P U , Q U ) ≤ ϵ \mathbb{E}_{U\sim\mathrm{Haar}}d_{\mathrm{TV}}(P_U,Q_U) \le\epsilon E U ∼ Haar d TV ( P U , Q U ) ≤ ϵ , where P U P_U P U is the output distribution of this input under uniform loss with transmission η \eta η .
Problem 2 (Lossy Gaussian boson sampling). Squeezed vacuum states with a common squeezing parameter r ≥ 0 r \ge0 r ≥ 0 occupy s ≤ M s \le M s ≤ M input modes, and the remaining modes are in vacuum,
∣ Ψ G ⟩ = ∣ ξ r ⟩ ⊗ s ∣ 0 ⟩ ⊗ ( M − s ) , ∣ ξ r ⟩ = exp [ r 2 ( a † 2 − a 2 ) ] ∣ 0 ⟩ . (2) \lvert\Psi_{\mathrm{G}}\rangle= \lvert\xi_r\rangle^{\otimes s}\lvert0\rangle^{\otimes(M-s)}, \qquad\lvert\xi_r\rangle= \exp\left[\frac{r}{2}(a^{\dagger2}-a^2)\right]\lvert0\rangle. \tag*{(2)} ∣ Ψ G ⟩ = ∣ ξ r ⟩ ⊗ s ∣ 0 ⟩ ⊗ ( M − s ) , ∣ ξ r ⟩ = exp [ 2 r ( a † 2 − a 2 ) ] ∣ 0 ⟩ . (2) Given U U U , η \eta η , r r r and ϵ > 0 \epsilon> 0 ϵ > 0 , generate samples from a distribution Q U Q_U Q U with E U ∼ H a a r d T V ( P U , Q U ) ≤ ϵ \mathbb{E}_{U\sim\mathrm{Haar}}d_{\mathrm{TV}}(P_U,Q_U) \le\epsilon E U ∼ Haar d TV ( P U , Q U ) ≤ ϵ , where P U P_U P U is the output distribution of this input under uniform loss with transmission η \eta η . Our main result considers all squeezed input states, s = M s = M s = M .
An algorithm solves either problem efficiently if its running time per sample is polynomial in M M M and 1 / ϵ 1/\epsilon 1/ ϵ . Unless stated otherwise, η \eta η and r r r are fixed as the system grows, so the mean numbers of detected photons, η n \eta n η n and η s sinh 2 r \eta s \sinh^2 r η s sinh 2 r , grow in proportion to the number of sources. Running times count arithmetic operations, and Appendix D shows that polynomially many bits of precision suffice.
Previous results
Most efficient classical algorithms for lossy boson sampling require the transmission to decrease as the system grows. At fixed total variation error, they apply when the mean number of detected photons grows at most as the square root of the number of sources. For single-photon inputs, the lossy state is then close to an efficiently simulable classical state [13 , 14 ] . For Gaussian inputs, the same scale appears for classical Gaussian approximations, whose bounds hold for every interferometer [15 ] , and in the loss analyses of tensor network methods [16 , 18 ] . A recent Gaussian reset method, also valid for every interferometer, goes beyond this square root regime and allows a mean detected photon number of order s 2 / 3 s^{2/3} s 2/3 for s s s squeezed inputs [17 ] .
Much less is known at inverse polynomial error. The Gaussian approximation and reset bounds then demand even stronger loss, and at the square root boundary the Gaussian tensor network analysis does not establish a cost polynomial in both system size and inverse error.
At a fixed transmission, interference truncation offers a different approach [21 ] . It approximates each output probability by keeping only interference among a limited number of photons, set by the transmission and the target error. The cost of evaluating this approximation grows as the system size raised to the truncation order, which is polynomial at fixed error but quasipolynomial at inverse polynomial error. Samples are then drawn with a Metropolis chain, for which no bound on the number of steps needed to reach a prescribed total variation error is given.
We obtained our results independently and became aware of the related preprint [22 ] after completing this work. That work establishes polynomial-time classical sampling for lossy Fock state boson sampling at any fixed survival probability in a dilute regime, with polynomial dependence on inverse error. In our notation, its full-output guarantee for k k k survivors from n n n input photons is proved under
M ≥ C 0 n k 2 , M ≥ C B k 2 ϵ δ . M \ge C_0 n k^2,\qquad M \ge C_B \frac{k^2}{\epsilon\delta}. M ≥ C 0 n k 2 , M ≥ C B ϵδ k 2 .
where C 0 , C B > 0 C_0,C_B > 0 C 0 , C B > 0 are universal constants, ϵ \epsilon ϵ is the total variation error, and δ \delta δ is the allowed failure probability over Haar random interferometers. At a fixed surviving fraction k / n ∈ ( 0 , 1 ) k/n \in(0,1) k / n ∈ ( 0 , 1 ) , the first bound already imposes M = Ω ( n 3 ) M = \Omega(n^3) M = Ω ( n 3 ) . The second bound makes the total collision probability small. Our result for Fock state boson sampling covers the full output distribution for every M ≥ n M \ge n M ≥ n , including M = n M = n M = n , with no additional condition on the relative scaling of mode and photon numbers. It includes all output collisions, even when they occur with substantial probability. Our Gaussian result further establishes efficient sampling with equal squeezing in all input modes.
Appendices F and G compare our results with these simulation methods and with known hardness results.
Main results
Efficient sampling at a fixed transmission
Both problems of Sec. II admit efficient classical samplers at every fixed transmission. For single-photon inputs, the result is as follows.
Theorem 1 (Efficient classical algorithm for lossy Fock state boson sampling). Fix a transmission η \eta η . For every M ≥ n M \ge n M ≥ n and 0 < ϵ ≤ 1 / 2 0 < \epsilon\le1/2 0 < ϵ ≤ 1/2 , there is a classical randomized algorithm for Problem 1 whose output distribution satisfies
E U ∼ Haar d T V ( P U , Q U ) ≤ ϵ . (3) \mathbb{E}_{U\sim\operatorname{Haar}} d_{\mathrm{TV}}(P_U,Q_U) \le\epsilon. \tag*{(3)} E U ∼ Haar d TV ( P U , Q U ) ≤ ϵ . (3)
Its worst case number of arithmetic operations per sample obeys
T F ( M , n , ϵ ) ≤ poly η ( M , n , 1 / ϵ ) . (4) T_{\mathrm{F}}(M,n,\epsilon) \le\operatorname{poly}_{\eta}(M,n,1/\epsilon). \tag*{(4)} T F ( M , n , ϵ ) ≤ poly η ( M , n , 1/ ϵ ) . (4)
The polynomial’s degree and constants may depend on the fixed transmission. The sampler works with any number of vacuum inputs and generates the full distribution of detected photon numbers. It therefore applies while the mean detected photon number η n \eta n η n increases in direct proportion to the number of sources.
For Gaussian inputs squeezed in every mode, the same result holds at every finite squeezing.
Theorem 2 (Efficient classical algorithm for lossy Gaussian boson sampling). Fix a transmission η \eta η and a squeezing parameter r ≥ 0 r \ge0 r ≥ 0 . For every M ≥ 1 M \ge1 M ≥ 1 and 0 < ϵ ≤ 1 / 2 0 < \epsilon\le1/2 0 < ϵ ≤ 1/2 , there is a classical randomized algorithm for Problem 2 with s = M s=M s = M whose output distribution satisfies
E U ∼ Haar TV ( P U , Q U ) ≤ ϵ . (5) \mathbb{E}_{U\sim\operatorname{Haar}}\operatorname{TV}(P_U,Q_U) \le\epsilon. \tag*{(5)} E U ∼ Haar TV ( P U , Q U ) ≤ ϵ . (5) Its worst case number of arithmetic operations per sample obeys
T G ( M , ϵ ) ≤ poly r , η ( M , 1 / ϵ ) . (6) T_{\mathrm{G}}(M,\epsilon) \le\operatorname{poly}_{r,\eta}(M,1/\epsilon). \tag*{(6)} T G ( M , ϵ ) ≤ poly r , η ( M , 1/ ϵ ) . (6)
At fixed r > 0 r>0 r > 0 , the mean detected photon number η M sinh 2 r \eta M\sinh^2 r η M sinh 2 r grows linearly with M M M , as η n \eta n η n does for single photons. The bound for a given r r r also holds for every smaller squeezing parameter, so the squeezing may decrease with M M M , as in weak-squeezing scalings with r → 0 r \to0 r → 0 . When only s < M s<M s < M inputs are squeezed, Appendix E extends the result under the sufficient condition η cosh ( 2 r ) < 1 \eta\cosh(2r)<1 η cosh ( 2 r ) < 1 , uniformly in s s s .
Both theorems bound the error on average over Haar random interferometers. A randomly drawn circuit therefore has a small error with high probability, although the algorithm cannot tell whether a given circuit does. By Markov’s inequality, running the sampler at ϵ = min { 1 / 2 , M − ( a + b ) } \epsilon=\min\{1/2,M^{-(a+b)}\} ϵ = min { 1/2 , M − ( a + b ) } for fixed a , b > 0 a,b>0 a , b > 0 gives an error at most M − a M^{-a} M − a with probability at least 1 − M − b 1-M^{-b} 1 − M − b over the choice of U U U , still in polynomial time. Because the circuit is drawn once and then held fixed, all samples come from the same distribution Q U Q_U Q U and carry the same error. The error of T T T independent samples taken together is at most T T T times this error. Running the sampler at an error smaller by a factor of T T T therefore keeps polynomially many samples jointly accurate, still in polynomial time, as shown in Appendix A. § 0.5 outlines the proofs, which the appendices complete.
Consequences for computational complexity
Our results settle the regime of constant loss rate at the accuracy used in hardness arguments. For every fixed transmission, the samplers run in time polynomial in the system size and in 1 / ϵ 1/\epsilon 1/ ϵ , which is the notion of efficient approximate sampling used for ideal boson sampling [1 ] . In particular, the error may decrease as an inverse polynomial in the system size, measured by the photon number n n n for single-photon inputs and by the mode number M M M for Gaussian inputs. Choosing ϵ = n − a \epsilon=n^{-a} ϵ = n − a or ϵ = M − a \epsilon=M^{-a} ϵ = M − a with any fixed a > 0 a>0 a > 0 makes 1 / ϵ 1/\epsilon 1/ ϵ polynomial in the system size, so the running time remains polynomial. Earlier rigorous samplers needed the transmission to vanish as the system grows [13 , 14 , 15 , 17 ] , and interference truncation becomes quasipolynomial at inverse polynomial error [21 ] . Our samplers extend efficient sampling to every constant loss rate. For Haar random interferometers, constant loss therefore leaves no asymptotic sampling advantage in either input family.
Hardness survives only when the loss rate vanishes quickly. Consider single-photon inputs with M M M polynomial in n n n and ( 1 − η ) n = O ( log n ) (1-\eta)n=O(\log n) ( 1 − η ) n = O ( log n ) . All n n n photons then survive with probability η n ≥ n − c \eta^n \ge n^{-c} η n ≥ n − c for some constant c c c , so keeping only the n n n -photon outcomes turns a sampler for the lossy distribution with sufficiently small inverse polynomial error into an ideal sampler at polynomial overhead [10 , 11 ] . The lossy problem is then as hard as ideal boson sampling under the same assumptions, and Appendix G gives the error and cost bounds of this reduction. The open range is thus confined to loss rates that vanish more slowly than ( log n ) / n (\log n)/n ( log n ) / n . Our results are consistent with this hardness. The correlation cutoff required by our samplers grows as the transmission approaches one, and at inverse polynomial error it becomes proportional to n n n when only a logarithmic number of photons is lost on average. Because the cost grows exponentially with the cutoff, our bound on the running time is then no longer polynomial. For Gaussian inputs, a hardness comparison must further match the squeezing scale and interferometer ensemble of the relevant hardness result [12 , 23 ] , and Appendix G treats these comparisons separately.
Implications for quantum advantage experiments
Hardness arguments for boson sampling take the interferometer from the Haar measure [1 , 19 ] , and several experiments test their devices against this assumption. Jiuzhang 1.0 and 2.0 compared their measured transformation matrices with Haar random statistics [3 , 5 ] , and a recent single-photon experiment implemented a unitary drawn from the Haar measure [2 ] . Theorems 1 and 2 apply to such experiments whenever their input states belong to the families treated there. In that case, adding photons and modes at a fixed transmission cannot establish an asymptotic sampling advantage, despite large photon counts, output collisions and multiphoton interference. Other large scale experiments use structured interferometers that are not Haar random, such as time domain loop networks [6 ] and hybrid spatiotemporal circuits [8 ] , and our average case result does not directly apply to them.
Because the accuracy bound concerns the complete output distribution, it also holds after any processing applied in the same way to both outputs, such as recording only detector clicks or grouping output configurations into coarser classes. The probability that an output passes any given test therefore differs between the experiment and the classical sampler by at most the total variation distance. Our theorems nevertheless concern asymptotic scaling and do not by themselves show that any particular device can be spoofed. Spoofing a specific experiment would require an implementation that generates samples in a time comparable to that of the experiment, which polynomial bounds with possibly large degrees and constants do not ensure. It would also require an accuracy assessment for the actual circuit and physical noise model, because our bound holds on average over Haar random interferometers under uniform loss.
Sampling algorithms
Our samplers rest on one physical effect, the suppression of correlations among many photons by loss. Let N N N be the total number of photons before loss. It equals n n n for single-photon inputs and fluctuates over even values for Gaussian inputs. Each photon survives independently, so given N N N the detected count k k k is binomially distributed with N N N trials and probability η \eta η . For each detected count, the samplers keep only correlation orders up to a cutoff L L L , evaluate the retained contributions efficiently, and convert them into samples by a rejection procedure with a bounded number of trials. The principle behind the method is that, with loss, the truncation error decays exponentially in L L L , so the required cutoff grows only logarithmically with the number of detected photons (Figure 1 ).
Suppression of high-order correlations
In Figure 1 a, the loss acts in front of the detectors. Because uniform loss commutes with a passive interferometer, the same loss can be moved in front of the interferometer without changing the output distribution. For single-photon inputs, an event with k k k surviving photons then amounts to an ideal experiment in which k k k photons enter a uniformly random subset of the n n n occupied input modes. Because the lost photons are not observed, the detection probabilities average these ideal experiments over all subsets, although each of them still shows full quantum interference.
For given N N N and k k k , let p U ( x ) p_U(x) p U ( x ) be the probability of the output configuration x = ( x 1 , … , x M ) x = (x_1,\ldots,x_M) x = ( x 1 , … , x M ) , which lists the photon number in each output mode, with x 1 + ⋯ + x M = k x_1+\cdots+x_M = k x 1 + ⋯ + x M = k . There are D M , k = ( M + k − 1 k ) D_{M,k} = \binom{M+k-1}{k} D M , k = ( k M + k − 1 ) such configurations, and the rescaled probability F U ( x ) = D M , k p U ( x ) F_U(x) = D_{M,k}p_U(x) F U ( x ) = D M , k p U ( x ) has the uniform average D M , k − 1 ∑ x F U ( x ) = ∑ x p U ( x ) = 1 D_{M,k}^{-1}\sum_x F_U(x) = \sum_x p_U(x) = 1 D M , k − 1 ∑ x F U ( x ) = ∑ x p U ( x ) = 1 . We expand it into orthogonal correlation orders,
F U = 1 + ∑ h = 1 k Π h F U , W h ( k ) = E U ∥ Π h F U ∥ 2 2 . (7) F_U = 1 + \sum_{h=1}^{k}\Pi_hF_U,\qquad W_h(k) = \mathbb{E}_U\lVert\Pi_hF_U\rVert_2^2. \tag*{(7)} F U = 1 + h = 1 ∑ k Π h F U , W h ( k ) = E U ∥ Π h F U ∥ 2 2 . (7)
Here ∥ f ∥ 2 2 = D M , k − 1 ∑ x ∣ f ( x ) ∣ 2 \lVert f\rVert_2^2 = D_{M,k}^{-1}\sum_x|f(x)|^2 ∥ f ∥ 2 2 = D M , k − 1 ∑ x ∣ f ( x ) ∣ 2 is the uniform average of ∣ f ∣ 2 |f|^2 ∣ f ∣ 2 , and Π h \Pi_h Π h projects onto polynomials of degree h h h in x 1 , … , x M x_1,\ldots,x_M x 1 , … , x M that are orthogonal to all lower degrees under this average. The expectation of such a polynomial under p U p_U p U depends only on the reduced state of h h h photons, so Π h F U \Pi_hF_U Π h F U describes the correlations among h h h photons that remain after those among fewer photons are removed. For example, Π 1 F U \Pi_1F_U Π 1 F U records how the mean photon number of each mode differs from the uniform value k / M k/M k / M , and Π 2 F U \Pi_2F_U Π 2 F U records the pair correlations that these means do not explain. The weight W h ( k ) W_h(k) W h ( k ) is its squared size averaged over Haar random interferometers.
For single-photon inputs, a correlation of order h h h involves h h h particular photons. These photons all survive in only a fraction ( k h ) / ( n h ) \binom{k}{h}/\binom{n}{h} ( h k ) / ( h n ) of the possible k k k -photon subsets, and averaging over the subsets bounds W h ( k ) W_h(k) W h ( k ) by this fraction. Its binomial average gives
E k W h ( k ) ≤ η h , E U , k ∥ F U − F U ≤ L ∥ 2 2 ≤ η L + 1 1 − η . (8) \mathbb{E}_k W_h(k) \le\eta^h,\qquad\mathbb{E}_{U,k}\lVert F_U-F_U^{\le L}\rVert_2^2 \le\frac{\eta^{L+1}}{1-\eta}. \tag*{(8)} E k W h ( k ) ≤ η h , E U , k ∥ F U − F U ≤ L ∥ 2 2 ≤ 1 − η η L + 1 . (8)
where F U ≤ L F_U^{\leq L} F U ≤ L keeps the orders h ≤ L h \leq L h ≤ L . The truncation error thus decays exponentially in L L L (Figure 1 b).
Gaussian inputs need one more step, because the number N N N of photons before loss now fluctuates and the decay of the weights depends on the sector ( N , k ) (N,k) ( N , k ) . The weights again decay exponentially with h h h when the photon density is bounded, N ≤ c M N \leq cM N ≤ c M for a fixed c > sinh 2 r c > \sinh^2 r c > sinh 2 r , and the surviving fraction stays away from one, k ≤ ϑ N k \leq\vartheta N k ≤ ϑN for a fixed ϑ \vartheta ϑ with η < ϑ < 1 \eta< \vartheta< 1 η < ϑ < 1 . Sectors outside this range are rare when N N N is large, because N N N concentrates near its mean M sinh 2 r M\sinh^2 r M sinh 2 r and k / N k/N k / N near η \eta η . When N N N is small, all photons may survive with appreciable probability, but such sectors contain few photons and are sampled directly by computing their probabilities. Appendix B proves the bounds for both input families.
The truncated function F U ≤ L F_U^{\leq L} F U ≤ L need not be a probability distribution, but by the Cauchy–Schwarz inequality its mean absolute error is at most the square root of the bound in Eq. (8) . At fixed optical parameters, retaining orders up to
L = O ( 1 + log ( 1 / ϵ ) ) (9) L = O(1 + \log(1/\epsilon)) \tag*{(9)} L = O ( 1 + log ( 1/ ϵ )) (9)
therefore keeps the truncation error below a fixed fraction of ϵ \epsilon ϵ , as shown in Appendix D. Inverse polynomial error requires only a logarithmic cutoff even when the number of detected photons grows linearly with size (Figure 1 c).
Efficient evaluation of low-order correlations
To evaluate the retained orders, we write p U ( x ) p_U(x) p U ( x ) as the overlap between the lossy input state and the projector onto x x x carried back through the interferometer. Its component of order h h h involves sums over h h h -photon configurations of the input and output modes, weighted by squared permanents of h × h h \times h h × h submatrices of U U U for single-photon inputs and by analogous matrix functions for Gaussian inputs. We call these configurations auxiliary, to distinguish them from the k k k -photon output configuration x x x whose probability is being evaluated. Explicitly summing them at orders up to L L L would cost M O ( L ) M^{O(L)} M O ( L ) , giving a quasipolynomial bound when L L L grows logarithmically with size.
Our construction avoids this cost through two techniques. First, we project the factors on both the input and the output side onto the same correlation order before estimating their overlap. Since the projection is orthogonal, this leaves the contribution of that order unchanged, and the cancellations among lower orders are carried out exactly rather than through the random estimate. The estimation error is then controlled by the order weight W h ( k ) W_h(k) W h ( k ) . Second, every mode is assigned at random to one of h h h groups. A set of h h h distinct modes lands in distinct groups with probability h ! / h h ≥ e − h h!/h^h \geq e^{-h} h ! / h h ≥ e − h , and the contributions of all such sets are summed at once by determinant generating functions. Reweighting by the inverse probability gives an unbiased estimate whose variance grows only exponentially in h h h . For single-photon inputs, the input factor also sums over which h h h of the n n n occupied input modes carry the photons, so these modes are grouped in the same way, independently of the output modes.
Auxiliary configurations with several photons in one mode need additional sums over their multiplicities, so we include them only up to a separate cutoff, chosen to keep the resulting bias below ϵ / 16 \epsilon/16 ϵ /16 . When the number of modes is at most a constant multiple of L + log ( 1 / ϵ ) L+\log(1/\epsilon) L + log ( 1/ ϵ ) , all such configurations can be included at polynomial cost. Otherwise they are rare under the uniform average, and a cutoff of order L + log ( 1 / ϵ ) L+\log(1/\epsilon) L + log ( 1/ ϵ ) suffices. The estimator variance is at most exponential in L L L , and one evaluation costs poly ( M , N , L ) exp [ O ( L + log ( 1 / ϵ ) ) ] \operatorname{poly}(M,N,L)\exp[O(L+\log(1/\epsilon))] poly ( M , N , L ) exp [ O ( L + log ( 1/ ϵ ))] at fixed optical parameters. Together with Eq. (9) , these bounds give polynomial dependence on system size and inverse error. Appendix C develops the projection identities, determinant calculations and auxiliary cutoff bounds.
Rejection sampling in polynomial time
The algorithm first draws the source photon number N N N and then the surviving count k k k , so that only the configuration within one photon sector remains to be sampled. The evaluation above yields, for any single output configuration x x x , an estimate of the truncated rescaled probability F ~ U ≤ L ( x ) \widetilde{F}_U^{\leq L}(x) F U ≤ L ( x ) with controlled bias and variance. It does not yield the distribution itself, because the number of configurations grows exponentially with the photon number. Rejection sampling turns these pointwise estimates into samples. Writing F U ( x ) = p U ( x ) / u ( x ) F_U(x)=p_U(x)/u(x) F U ( x ) = p U ( x ) / u ( x ) with u u u the uniform distribution on k k k -photon configurations, a uniformly proposed x x x that is accepted with probability F U ( x ) / A F_U(x)/A F U ( x ) / A , for a constant A ≥ max x F U ( x ) A \geq\max_x F_U(x) A ≥ max x F U ( x ) , is distributed exactly according to p U p_U p U . Each trial is then accepted with probability 1 / A 1/A 1/ A , so the expected number of trials is A A A .
This standard scheme is not efficient by itself, because max x F U ( x ) \max_x F_U(x) max x F U ( x ) can be exponentially large in the photon number. We therefore clip the acceptance weight at a level A A A of order 1 / ϵ 1/\epsilon 1/ ϵ , which underweights the configurations with F U ( x ) > A F_U(x)>A F U ( x ) > A . Their total probability is at most ∥ F U ∥ 2 2 / A \lVert F_U\rVert_2^2/A ∥ F U ∥ 2 2 / A , since F U ≤ F U 2 / A F_U \leq F_U^2/A F U ≤ F U 2 / A on that set, and the second moment E U ∥ F U ∥ 2 2 \mathbb{E}_U\lVert F_U\rVert_2^2 E U ∥ F U ∥ 2 2 is bounded by a constant, 1 / ( 1 − η ) 1/(1-\eta) 1/ ( 1 − η ) for single-photon inputs. Clipping therefore changes the sampled distribution by an amount of order 1 / A 1/A 1/ A in total variation, on average over U U U , while each trial is still accepted with probability close to 1 / A 1/A 1/ A . This bound on the second moment makes uniform proposals efficient.
In place of F U ( x ) F_U(x) F U ( x ) , the algorithm uses the mean of T T T independent estimates of F U ≤ L ( x ) F_U^{\leq L}(x) F U ≤ L ( x ) , clipped to [ 0 , A ] [0,A] [ 0 , A ] . Since the acceptance probability is linear in this weight, averaging over the internal randomness reproduces the intended acceptance probability up to an error set by the estimator variance. This variance is at most exponential in L L L , and since L L L grows only logarithmically with 1 / ϵ 1/\epsilon 1/ ϵ by Eq. (9) , it is polynomial in 1 / ϵ 1/\epsilon 1/ ϵ . Fresh estimates are drawn for every proposal. The number of trials is capped at J J J of order A / ϵ A/\epsilon A / ϵ , and a fixed configuration is output if all trials fail. The running time is therefore bounded for every circuit by J T JT J T evaluations, which is polynomial in the system size and 1 / ϵ 1/\epsilon 1/ ϵ .
A few photon sectors are handled separately. For Gaussian inputs, the source count is restricted to a finite range with a bounded omitted probability, and sectors with a small photon number before loss are sampled by sequential conditional probabilities followed by photon deletion. Other exceptional sectors are assigned fixed output configurations.
Appendix D bounds the total error, whose contributions come from truncating the correlation orders, omitting auxiliary configurations, the estimator noise, clipping at A A A , capping the number of trials at J J J , the exceptional photon sectors and finite numerical precision. With L L L , T T T , A A A and J J J chosen as described above, each contribution is a fixed fraction of ϵ \epsilon ϵ , so that E U d T V ( Q U , P U ) ≤ ϵ \mathbb{E}_U d_{\mathrm{TV}}(Q_U,P_U) \leq\epsilon E U d TV ( Q U , P U ) ≤ ϵ in time polynomial in the system size and 1 / ϵ 1/\epsilon 1/ ϵ . In particular, the error can be made inverse polynomial in the system size while the running time stays polynomial.
Discussion
In experiments, a fixed transmission is the most favorable case that can realistically be reached. Each source, interferometer component and detector loses a fraction of the light that depends on the quality of that component rather than on the size of the system. The transmission approaching one that the known hardness results require thus appears achievable only in theory. A higher fixed transmission raises the degree of our polynomial bound but keeps the scaling polynomial, so reducing loss alone cannot produce an asymptotic advantage for these interferometers and inputs.
Atomic boson samplers illustrate this point. They lose about five percent of the atoms, independently of the evolution time, under approximately Haar random dynamics [20 ] , and therefore operate at a fixed transmission far closer to one than photonic devices. As noted in Sec. II, our conclusion still applies to them asymptotically, but with a much higher polynomial degree, and the mean number of lost particles stays small up to larger sizes.
An asymptotic advantage therefore requires changes beyond the scope of our theorems, for example structured interferometers, other input states, or additional elements such as optical nonlinearities [9 ] . Whether any of these changes makes sampling at a fixed transmission classically hard remains open.
Acknowledgments
The author obtained the main theoretical results. GPT-6 and Fable-5.1 served as assistants under the author’s direction, helping to explore and sharpen mathematical arguments, to check calculations and to edit the text. All final proofs were verified independently by the author, who bears full responsibility for the results and conclusions. This work was supported by the Institute of Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korean government (Ministry of Science and ICT (MSIT)) (No. RS-2024-00437284, No. RS-2025-02283189), and National Research Foundation of Korea (NRF) grant funded by the Korean government (MSIT) (No. RS-2024-00431768).
Appendices
The appendices give the precise sampling statements, the correlation bounds and their evaluation, and the complete sampling error analysis. The extension to Gaussian inputs containing vacuum follows after the sampling construction. The final appendices discuss the scope of the results and comparisons with other simulation methods and hardness results.
Definition of the lossy sampling task
This appendix fixes the conventions behind Theorems 1 and 2 beyond those of Sec. II. We write E U \mathbb{E}_{U} E U for the average over the normalized Haar measure μ H \mu_{H} μ H on U ( M ) \mathrm{U}(M) U ( M ) , so that the error in the theorems is
E U d T V ( P U , Q U ) = ∫ U ( M ) d T V ( P U , Q U ) d μ H ( U ) . (10) \mathbb{E}_{U} d_{\mathrm{TV}}(P_{U},Q_{U}) = \int_{\mathrm{U}(M)} d_{\mathrm{TV}}(P_{U},Q_{U})\,d\mu_{H}(U). \tag*{(10)} E U d TV ( P U , Q U ) = ∫ U ( M ) d TV ( P U , Q U ) d μ H ( U ) . (10)
The two output distributions are thus compared at each fixed U U U before the error is averaged over circuits, and the accuracy can vary between interferometers. Running times count arithmetic operations on the entries of U U U and on the optical parameters, and Sec. D 4 extends the bounds to bit complexity.
We write P U , n , η F P^{\mathrm{F}}_{U,n,\eta} P U , n , η F and P U , s , r , η G P^{\mathrm{G}}_{U,s,r,\eta} P U , s , r , η G for the lossy output distributions of the inputs in Problems 1 and 2, with n ≤ M n \le M n ≤ M single photons and s ≤ M s \le M s ≤ M squeezed inputs. Theorems 1 and 2 bound E U d T V ( Q U , P U , n , η F ) \mathbb{E}_{U}d_{\mathrm{TV}}(Q_{U},P^{\mathrm{F}}_{U,n,\eta}) E U d TV ( Q U , P U , n , η F ) and E U d T V ( Q U , P U , M , r , η G ) \mathbb{E}_{U}d_{\mathrm{TV}}(Q_{U},P^{\mathrm{G}}_{U,M,r,\eta}) E U d TV ( Q U , P U , M , r , η G ) , with worst case running times T F T_{\mathrm{F}} T F and T G T_{\mathrm{G}} T G per sample. The degree and constants of poly depend on the fixed optical parameters and can diverge as η → 1 \eta\to1 η → 1 . Appendix B decomposes both distributions into sectors with fixed photon numbers before and after loss.
For Gaussian inputs, Theorem 2 assumes that every input mode is squeezed, s = M s=M s = M , with the same squeezing parameter r ≥ 0 r \ge0 r ≥ 0 and no coherent displacement. Known squeezing phases may differ. between modes, because their phase rotations, chosen independently of the interferometer, can be absorbed into the supplied matrix U U U without changing its Haar distribution. General mixed Gaussian inputs and unequal nonzero squeezing magnitudes are not covered.
From average error to individual circuits
Theorems 1 and 2 bound the error averaged over Haar interferometers. For any fixed a , b > 0 a,b>0 a , b > 0 , setting ϵ = min { 1 / 2 , M − ( a + b ) } \epsilon=\min\{1/2,M^{-(a+b)}\} ϵ = min { 1/2 , M − ( a + b ) } and applying Markov’s inequality gives
Pr U [ d T V ( P U , Q U ) > M − a ] ≤ M − b . (11) \Pr_{U}\left[d_{\mathrm{TV}}(P_U,Q_U)>M^{-a}\right]\le M^{-b}. \tag*{(11)} U Pr [ d TV ( P U , Q U ) > M − a ] ≤ M − b . (11)
The probability refers to the initial choice of interferometer, and the algorithm does not identify the exceptional circuits.
For T T T independent samples from a fixed circuit, let δ U = d T V ( P U , Q U ) \delta_U=d_{\mathrm{TV}}(P_U,Q_U) δ U = d TV ( P U , Q U ) . Then
d T V ( P U ⊗ T , Q U ⊗ T ) ≤ T δ U . d_{\mathrm{TV}}\left(P_U^{\otimes T},Q_U^{\otimes T}\right)\le T\delta_U. d TV ( P U ⊗ T , Q U ⊗ T ) ≤ T δ U .
Running the sampler at ϵ = min { 1 / 2 , M − ( a + b ) / T } \epsilon=\min\{1/2,M^{-(a+b)}/T\} ϵ = min { 1/2 , M − ( a + b ) / T } therefore gives a joint error at most M − a M^{-a} M − a for a fraction at least 1 − M − b 1-M^{-b} 1 − M − b of circuits, and 1 / ϵ = max { 2 , T M a + b } 1/\epsilon=\max\{2,TM^{a+b}\} 1/ ϵ = max { 2 , T M a + b } remains polynomial in M M M as long as T T T is polynomial in M M M .
Correlation bounds under loss
We first decompose the photon counts and define the correlation orders of the output probabilities. We then state and prove a bound in terms of reduced state purity before deriving the geometric decay for single-photon and Gaussian inputs. The remaining subsections give the normalization calculations used in the Gaussian case.
Bounding correlations by reduced state purity
Photon number decomposition
For single-photon inputs, the photon number before loss is fixed at N = n N=n N = n . For Gaussian boson sampling, let s s s be the number of equally squeezed modes, with the other M − s M-s M − s input modes in vacuum. The main result has s = M s=M s = M , while the extension in Appendix E allows s < M s<M s < M . In the Fock basis, the input in Eq. (2) reads
∣ Ψ G ⟩ = ( sech r ) s / 2 exp ( tanh r 2 ∑ i = 1 s a i † 2 ) ∣ 0 ⟩ ⊗ M , (12) |\Psi_G\rangle=(\operatorname{sech}r)^{s/2}\exp\left(\frac{\tanh r}{2}\sum_{i=1}^{s}a_i^{\dagger2}\right)|0\rangle^{\otimes M}, \tag*{(12)} ∣ Ψ G ⟩ = ( sech r ) s /2 exp ( 2 tanh r i = 1 ∑ s a i † 2 ) ∣0 ⟩ ⊗ M , (12)
a superposition of states with different total photon numbers. Before loss, only even values N = 2 n N=2n N = 2 n occur, with n = 0 , 1 , … n=0,1,\ldots n = 0 , 1 , … counting photon pairs. The photon number distribution is
Pr ( N = 2 n ) = sech s r tanh 2 n r 2 n n ! ∏ ℓ = 0 n − 1 ( s + 2 ℓ ) . (13) \Pr(N=2n)=\frac{\operatorname{sech}^{s}r\,\tanh^{2n}r}{2^{n}n!}\prod_{\ell=0}^{n-1}(s+2\ell). \tag*{(13)} Pr ( N = 2 n ) = 2 n n ! sech s r tanh 2 n r ℓ = 0 ∏ n − 1 ( s + 2 ℓ ) . (13)
Empty products are understood to equal one. The normalized component of the input state in the sector with total photon number N = 2 n N=2n N = 2 n is
∣ Ψ s , 2 n ⟩ = ( A s † ) n ∣ 0 ⟩ 2 − n n ! ∏ ℓ = 0 n − 1 ( s + 2 ℓ ) , A s † = 1 2 ∑ i = 1 s a i † 2 . (14) |\Psi_{s,2n}\rangle=\frac{(A_s^\dagger)^n|0\rangle}{\sqrt{2^{-n}n!\prod_{\ell=0}^{n-1}(s+2\ell)}},\qquad A_s^\dagger=\frac{1}{2}\sum_{i=1}^{s}a_i^{\dagger2}. \tag*{(14)} ∣ Ψ s , 2 n ⟩ = 2 − n n ! ∏ ℓ = 0 n − 1 ( s + 2 ℓ ) ( A s † ) n ∣0 ⟩ , A s † = 2 1 i = 1 ∑ s a i † 2 . (14)
For both input families, each of the N N N photons survives independently with probability η \eta η , so the detected photon number k = ∑ i x i k = \sum_i x_i k = ∑ i x i obeys k ∣ N ∼ Bin ( N , η ) k \mid N \sim\operatorname{Bin}(N,\eta) k ∣ N ∼ Bin ( N , η ) . As in Sec. II, the loss channel acts immediately before the detectors. Let z = ( z 1 , … , z M ) z=(z_1,\ldots,z_M) z = ( z 1 , … , z M ) be the configuration of photon counts at the output of the interferometer before this loss channel, with ∑ i z i = N \sum_i z_i=N ∑ i z i = N , and let x = ( x 1 , … , x M ) x=(x_1,\ldots,x_M) x = ( x 1 , … , x M ) be the detected configuration after loss, with ∑ i x i = k \sum_i x_i=k ∑ i x i = k . Both configurations refer to the same output modes. For a given configuration z z z , the loss channel acts independently on each mode. Before conditioning on the total number of survivors, the probability of obtaining x x x is
Pr ( x ∣ z ) = [ ∏ i ( z i x i ) ] η k ( 1 − η ) N − k , k = ∑ i x i . \operatorname{Pr}(x\mid z)=\left[\prod_i \binom{z_i}{x_i}\right]\eta^k(1-\eta)^{N-k},\qquad k=\sum_i x_i. Pr ( x ∣ z ) = [ i ∏ ( x i z i ) ] η k ( 1 − η ) N − k , k = i ∑ x i .
The probability that exactly k k k photons survive is ( N k ) η k ( 1 − η ) N − k \binom{N}{k}\eta^k(1-\eta)^{N-k} ( k N ) η k ( 1 − η ) N − k for every configuration z z z with total photon number N N N . Conditioning on exactly k k k survivors gives the probability of obtaining x x x from z z z in this sector,
K N → k ( x ∣ z ) = Pr ( x ∣ z ) ( N k ) η k ( 1 − η ) N − k = ∏ i ( z i x i ) ( N k ) , x ≤ z , ∣ x ∣ = k . (15) K_{N\to k}(x\mid z)=\frac{\operatorname{Pr}(x\mid z)}{\binom{N}{k}\eta^k(1-\eta)^{N-k}}=\frac{\prod_i\binom{z_i}{x_i}}{\binom{N}{k}},\qquad x\leq z,\quad|x|=k. \tag*{(15)} K N → k ( x ∣ z ) = ( k N ) η k ( 1 − η ) N − k Pr ( x ∣ z ) = ( k N ) ∏ i ( x i z i ) , x ≤ z , ∣ x ∣ = k . (15)
Here x ≤ z x\leq z x ≤ z means x i ≤ z i x_i\leq z_i x i ≤ z i for every output mode, since loss removes photons within each output mode. Equality is allowed in a mode where no photon is lost. We write ∣ x ∣ = ∑ i x i |x|=\sum_i x_i ∣ x ∣ = ∑ i x i . The probability is zero outside these constraints. The factor η k ( 1 − η ) N − k \eta^k(1-\eta)^{N-k} η k ( 1 − η ) N − k cancels, so K N → k K_{N\to k} K N → k does not depend on the transmission and every set of k k k surviving photons is equally likely.
The interferometer determines the probabilities of the configurations z z z . Let p U ( N ) ( z ) p_U^{(N)}(z) p U ( N ) ( z ) denote the output distribution without loss in the N N N -photon sector. Since the probability of k k k survivors is the same for every z z z , the detected distribution conditioned on N N N and k k k is
p U ( N , k ) ( x ) = ∑ z : ∣ z ∣ = N p U ( N ) ( z ) K N → k ( x ∣ z ) . p_U^{(N,k)}(x)=\sum_{z:\,|z|=N}p_U^{(N)}(z)K_{N\to k}(x\mid z). p U ( N , k ) ( x ) = z : ∣ z ∣ = N ∑ p U ( N ) ( z ) K N → k ( x ∣ z ) .
Thus K N → k K_{N\to k} K N → k describes only the loss transition for a given z z z , while the dependence on U U U enters through p U ( N ) p_U^{(N)} p U ( N ) . This is a decomposition of the measured photon count probabilities for the original circuit.
Within a fixed N N N -photon sector, uniform loss conditioned on k k k survivors gives the normalized k k k -particle reduced state of the state leaving the interferometer. Equation (B.4) describes its action on photon count probabilities, including collisions [24 ] . The adjoint loss channel maps each photon counting effect to an operator diagonal in photon number, so coherence between states with different input photon numbers N N N does not contribute to the measured probabilities. Sampling Eq. (B.2) and then k k k therefore gives an exact classical decomposition of the complete output distribution.
Correlation decomposition of output probabilities
In each photon number sector, the loss acting after the interferometer can be moved to the input, as we now show. Let ρ N \rho_N ρ N be the normalized input state in a fixed N N N -photon sector. The Hilbert space of m m m identical bosons is Sym m ( C M ) \operatorname{Sym}^m(\mathbb{C}^M) Sym m ( C M ) , the subspace of ( C M ) ⊗ m (\mathbb{C}^M)^{\otimes m} ( C M ) ⊗ m invariant under particle permutations. The interferometer acts on this space as
U m = Sym m ( U ) = U ⊗ m ∣ Sym m ( C M ) . \mathcal{U}_m=\operatorname{Sym}^m(U)=U^{\otimes m}\big|_{\operatorname{Sym}^m(\mathbb{C}^M)}. U m = Sym m ( U ) = U ⊗ m Sym m ( C M ) .
Conditioned on k k k surviving photons, the normalized state after the output loss is
ρ U , N , k o u t = Tr N − k ( U N ρ N U N † ) = U k σ N , k U k † , σ N , k = Tr N − k ρ N . (16) \rho_{U,N,k}^{\mathrm{out}}=\operatorname{Tr}_{N-k}\left(\mathcal{U}_N\rho_N\mathcal{U}_N^\dagger\right)=\mathcal{U}_k\sigma_{N,k}\mathcal{U}_k^\dagger,\qquad\sigma_{N,k}=\operatorname{Tr}_{N-k}\rho_N. \tag*{(16)} ρ U , N , k out = Tr N − k ( U N ρ N U N † ) = U k σ N , k U k † , σ N , k = Tr N − k ρ N . (16)
Here Tr N − k \operatorname{Tr}_{N-k} Tr N − k traces out N − k N-k N − k particles in the first-quantized description, leaving a reduced state on all M M M modes. Since U ⊗ N = U ⊗ k ⊗ U ⊗ ( N − k ) U^{\otimes N}=U^{\otimes k}\otimes U^{\otimes(N-k)} U ⊗ N = U ⊗ k ⊗ U ⊗ ( N − k ) , the unitary acting on the traced particles drops out of the partial trace, leaving U k U_k U k on the remaining particles. Thus σ N , k \sigma_{N,k} σ N , k is a reduced state of the original input and is independent of U U U . This is the operator form of the deletion in Eq. (B.4), with the reduction acting on the input. For a fixed ( N , k ) (N,k) ( N , k ) sector, we abbreviate σ N , k \sigma_{N,k} σ N , k as σ k \sigma_k σ k . More generally, the bounds below apply to any normalized k k k -boson state σ k \sigma_k σ k held fixed as U U U varies.
The possible output configurations, their number, and the uniform reference probability are
Ω M , k = { x ∈ N M : ∣ x ∣ = k } , D M , k = ( M + k − 1 k ) , u M , k = D M , k − 1 . (17) \Omega_{M,k}=\{x\in\mathbb{N}^{M}:|x|=k\},\qquad D_{M,k}=\binom{M+k-1}{k},\qquad u_{M,k}=D_{M,k}^{-1}. \tag*{(17)} Ω M , k = { x ∈ N M : ∣ x ∣ = k } , D M , k = ( k M + k − 1 ) , u M , k = D M , k − 1 . (17)
Here the entries of x x x are nonnegative integers, and each configuration labels a Fock basis state ∣ x ⟩ |x\rangle ∣ x ⟩ of the k k k -photon Hilbert space. Thus D M , k D_{M,k} D M , k is also the dimension of this space. With p U ( x ) = ⟨ x ∣ U k σ k U k † ∣ x ⟩ p_U(x)=\langle x|U_k\sigma_kU_k^\dagger|x\rangle p U ( x ) = ⟨ x ∣ U k σ k U k † ∣ x ⟩ denoting the output probability, we define the rescaled output probability
F U ( x ) = p U ( x ) u M , k = D M , k p U ( x ) . (18) F_U(x)=\frac{p_U(x)}{u_{M,k}}=D_{M,k}p_U(x). \tag*{(18)} F U ( x ) = u M , k p U ( x ) = D M , k p U ( x ) . (18)
This rescaling makes the uniform distribution the constant function F U = 1 F_U=1 F U = 1 . For every U U U , F U ≥ 0 F_U\ge0 F U ≥ 0 and E u F U = 1 \mathbb{E}_uF_U=1 E u F U = 1 , where E u \mathbb{E}_u E u denotes the uniform average over Ω M , k \Omega_{M,k} Ω M , k . The superscript in F U ( m ) F_U^{(m)} F U ( m ) specifies the photon number m m m .
Under interferometer conjugation X ↦ U k X U k † X\mapsto U_kXU_k^\dagger X ↦ U k X U k † , the space of linear operators on the k k k -photon Hilbert space decomposes into orthogonal correlation sectors h = 0 , … , k h=0,\ldots,k h = 0 , … , k . These are irreducible sectors, the smallest nonzero operator subspaces preserved by every interferometer, and each occurs once. Orthogonality is with respect to Tr ( X † Y ) \operatorname{Tr}(X^\dagger Y) Tr ( X † Y ) .
Operators of order at most h h h correspond to operators on the h h h -photon space, a space of dimension D M , h 2 D_{M,h}^{2} D M , h 2 , so the full order h h h sector has dimension
R M , h = D M , h 2 − D M , h − 1 2 . (19) R_{M,h}=D_{M,h}^{2}-D_{M,h-1}^{2}. \tag*{(19)} R M , h = D M , h 2 − D M , h − 1 2 . (19)
Restricting to operators diagonal in the Fock basis, which photon counting probes, replaces D M , h 2 D_{M,h}^{2} D M , h 2 by D M , h D_{M,h} D M , h and gives the dimension of the Fock-diagonal part,
Z M , h = D M , h − D M , h − 1 = ( M + h − 2 h ) , (20) Z_{M,h}=D_{M,h}-D_{M,h-1}=\binom{M+h-2}{h}, \tag*{(20)} Z M , h = D M , h − D M , h − 1 = ( h M + h − 2 ) , (20)
where D M , − 1 = 0 D_{M,-1}=0 D M , − 1 = 0 [25 ] .
On output configurations, these sectors correspond to multivariate Hahn polynomials, which have degree h h h in the occupations and are orthogonal to all lower degrees under u M , k u_{M,k} u M , k . Let Π h \Pi_h Π h denote the projection onto order h h h in the space of functions on Ω M , k \Omega_{M,k} Ω M , k , with inner product and norm
⟨ f , g ⟩ u = 1 D M , k ∑ x ∈ Ω M , k f ( x ) ∗ g ( x ) , ∥ f ∥ 2 = ⟨ f , f ⟩ u . \langle f,g\rangle_u=\frac{1}{D_{M,k}}\sum_{x\in\Omega_{M,k}}f(x)^*g(x),\qquad\lVert f\rVert^2=\langle f,f\rangle_u. ⟨ f , g ⟩ u = D M , k 1 x ∈ Ω M , k ∑ f ( x ) ∗ g ( x ) , ∥ f ∥ 2 = ⟨ f , f ⟩ u .
The constant component is Π 0 F U = 1 \Pi_0F_U=1 Π 0 F U = 1 , so
F U = 1 + ∑ h = 1 k Π h F U , W h ( k ) = E U ∥ Π h F U ∥ 2 , (21) F_U=1+\sum_{h=1}^{k}\Pi_hF_U,\qquad W_h(k)=\mathbb{E}_U\lVert\Pi_hF_U\rVert^2, \tag*{(21)} F U = 1 + h = 1 ∑ k Π h F U , W h ( k ) = E U ∥ Π h F U ∥ 2 , (21)
where W h ( k ) W_h(k) W h ( k ) is the mean squared contribution of order h h h . For an integer cutoff L ≥ 0 L\ge0 L ≥ 0 , define
F U ≤ L : = 1 + ∑ h = 1 min ( L , k ) Π h F U . F_U^{\le L}:=1+\sum_{h=1}^{\min(L,k)}\Pi_hF_U. F U ≤ L := 1 + h = 1 ∑ m i n ( L , k ) Π h F U .
The superscript ≤ L \le L ≤ L specifies the cutoff in correlation order, while the detected photon number k k k can still be much larger than L L L . Orthogonality gives
∥ F U − F U ≤ L ∥ 2 2 = ∑ h = L + 1 k ∥ Π h F U ∥ 2 2 \left\|F_U-F_U^{\le L}\right\|_2^2=\sum_{h=L+1}^{k}\left\|\Pi_hF_U\right\|_2^2 F U − F U ≤ L 2 2 = h = L + 1 ∑ k ∥ Π h F U ∥ 2 2
with an empty sum equal to zero. The projections depend only on M M M and k k k and are fixed before averaging over U U U .
A bound from reduced state purity
The weight W h ( k ) W_h(k) W h ( k ) in Eq. (B.10) can be bounded in terms of the normalized h h h -particle reduced state γ h = Tr k − h σ k \gamma_h=\operatorname{Tr}_{k-h}\sigma_k γ h = Tr k − h σ k and its purity τ h = Tr γ h 2 \tau_h=\operatorname{Tr}\gamma_h^2 τ h = Tr γ h 2 . For M ≥ 2 M\ge2 M ≥ 2 and 1 ≤ h ≤ k 1\le h\le k 1 ≤ h ≤ k ,
W h ( k ) ≤ ( k h ) M + h − 1 M + 2 h − 1 ( M + 2 h − 1 ) ! ( M + k − 1 ) ! ( M + h − 1 ) ! ( M + k + h − 1 ) ! τ h ≤ ( k h ) τ h . (22) W_h(k)\le\binom{k}{h}\frac{M+h-1}{M+2h-1}\frac{(M+2h-1)!(M+k-1)!}{(M+h-1)!(M+k+h-1)!}\tau_h\le\binom{k}{h}\tau_h. \tag*{(22)} W h ( k ) ≤ ( h k ) M + 2 h − 1 M + h − 1 ( M + h − 1 )! ( M + k + h − 1 )! ( M + 2 h − 1 )! ( M + k − 1 )! τ h ≤ ( h k ) τ h . (22)
The only quantity in this bound that depends on the state is τ h \tau_h τ h , so the correlation estimate reduces to a calculation on the reduced input state. The bound holds for any normalized bosonic state σ k \sigma_k σ k , and adding vacuum modes leaves τ h \tau_h τ h unchanged. The proof follows in Sec. B 2.
Proof of the purity bound
The proof has two steps. We first evaluate the Haar average of a single correlation sector and then determine how particle reduction rescales each correlation order. Combining the two results for the reduced state γ h \gamma_h γ h gives the bound in Eq. (B.11).
Haar average of a correlation sector
Let ρ \rho ρ be a normalized N N N -photon state and P h o p \mathcal{P}^{\mathrm{op}}_h P h op the orthogonal projection onto the order h h h operator sector defined above. Its correlation components are
ρ [ h ] = P h o p ρ , ρ = ∑ h = 0 N ρ [ h ] , ρ [ 0 ] = I D M , N . \rho^{[h]}=\mathcal{P}^{\mathrm{op}}_h\rho,\qquad\rho=\sum_{h=0}^{N}\rho^{[h]},\qquad\rho^{[0]}=\frac{I}{D_{M,N}}. ρ [ h ] = P h op ρ , ρ = h = 0 ∑ N ρ [ h ] , ρ [ 0 ] = D M , N I .
The index h h h labels the correlation order of ρ [ h ] \rho^{[h]} ρ [ h ] , which acts on the full N N N -photon space. For h > 0 h>0 h > 0 , these components are traceless Hermitian operators, so each nonzero component has both positive and negative eigenvalues and is not a state by itself. The order h h h contribution to F U ( N ) F_U^{(N)} F U ( N ) satisfies
∥ Π h F U ( N ) ∥ 2 2 = D M , N ∑ ∣ x ∣ = N ∣ ⟨ x ∣ U N ρ [ h ] U N † ∣ x ⟩ ∣ 2 . \left\|\Pi_hF_U^{(N)}\right\|_2^2=D_{M,N}\sum_{|x|=N}\left|\langle x|U_N\rho^{[h]}U_N^\dagger|x\rangle\right|^2. Π h F U ( N ) 2 2 = D M , N ∣ x ∣ = N ∑ ⟨ x ∣ U N ρ [ h ] U N † ∣ x ⟩ 2 .
Haar orthogonality gives the same mean squared overlap with each normalized operator direction in the irreducible order h h h sector. Photon counting probes its Z M , h Z_{M,h} Z M , h diagonal directions out of R M , h R_{M,h} R M , h directions in total, yielding
E U ∥ Π h F U ( N ) ∥ 2 2 = D M , N Z M , h R M , h ∥ ρ [ h ] ∥ H S 2 . (23) \mathbb{E}_U\left\|\Pi_hF_U^{(N)}\right\|_2^2=\frac{D_{M,N}Z_{M,h}}{R_{M,h}}\left\|\rho^{[h]}\right\|_{\mathrm{HS}}^2. \tag*{(23)} E U Π h F U ( N ) 2 2 = R M , h D M , N Z M , h ρ [ h ] HS 2 . (23)
Here ∥ X ∥ H S 2 = Tr ( X † X ) \left\|X\right\|_{\mathrm{HS}}^2=\operatorname{Tr}(X^\dagger X) ∥ X ∥ HS 2 = Tr ( X † X ) is the squared Hilbert–Schmidt norm. The factor D M , N D_{M,N} D M , N comes from the normalization of F U ( N ) F_U^{(N)} F U ( N ) , and the sector dimensions are given in Eqs. (B.8) and (B.9) [25 ] .
Effect of particle reduction
By Eq. (B.5), applying U N \mathcal{U}_N U N before reduction gives the same state as applying U k \mathcal{U}_k U k afterwards. Because each correlation sector is irreducible and occurs once, reduction acts separately on each order and rescales all operator directions within that order equally. For $0 \le h \le k \le N$, let s h ( M , N , k ) ≥ 0 s_h(M,N,k) \ge0 s h ( M , N , k ) ≥ 0 denote the resulting norm factor for F U F_U F U ,
∥ Π h F U ( k ) ∥ 2 2 = s h 2 ( M , N , k ) ∥ Π h F U ( N ) ∥ 2 2 , \lVert\Pi_h F_U^{(k)} \rVert_2^2 = s_h^2(M,N,k) \lVert\Pi_h F_U^{(N)} \rVert_2^2, ∥ Π h F U ( k ) ∥ 2 2 = s h 2 ( M , N , k ) ∥ Π h F U ( N ) ∥ 2 2 ,
where each norm uses the uniform reference distribution at its own photon number. This identity holds for each U U U . On photon count probabilities, the reduction is the deletion map in Eq. (B.4).
Since s h ( M , N , k ) s_h(M,N,k) s h ( M , N , k ) is the same for every operator of order h h h , it suffices to follow one nonzero operator of that order. At photon number n ≥ h n \ge h n ≥ h , choose
E n , h = ( a 1 † ) h a M h ∣ S y m n C M . (24) E_{n,h} = (a_1^\dagger)^h a_M^h \big|_{\mathrm{Sym}^n \mathbb{C}^M}. \tag*{(24)} E n , h = ( a 1 † ) h a M h Sym n C M . (24)
Here a i a_i a i annihilates a photon in mode i i i , so E n , h E_{n,h} E n , h transfers h h h photons from mode M M M to mode 1. Its expectation after reduction obeys
Tr [ E k , h Tr N − k ρ ] = ( k h ) ( N h ) Tr ( E N , h ρ ) . \operatorname{Tr}\left[E_{k,h}\operatorname{Tr}_{N-k}\rho\right] = \frac{\binom{k}{h}}{\binom{N}{h}}\operatorname{Tr}\left(E_{N,h}\rho\right). Tr [ E k , h Tr N − k ρ ] = ( h N ) ( h k ) Tr ( E N , h ρ ) .
The ratio is the probability that a specified set of h h h particles is included in a uniformly chosen subset of k k k out of N N N particles. To obtain s h s_h s h , we must also account for the different operator norms at photon numbers N N N and k k k .
The squared Fock basis matrix elements of E n , h E_{n,h} E n , h sum to
∥ E n , h ∥ H S 2 = ( h ! ) 2 ∑ ∣ x ∣ = n ( x 1 + h h ) ( x M h ) = ( h ! ) 2 ( M + n + h − 1 n − h ) , \lVert E_{n,h}\rVert_{\mathrm{HS}}^2 = (h!)^2 \sum_{\lvert x\rvert=n} \binom{x_1+h}{h}\binom{x_M}{h} = (h!)^2 \binom{M+n+h-1}{n-h}, ∥ E n , h ∥ HS 2 = ( h ! ) 2 ∣ x ∣ = n ∑ ( h x 1 + h ) ( h x M ) = ( h ! ) 2 ( n − h M + n + h − 1 ) ,
where the last equality follows from binomial convolution. Dividing the squared norm by D M , n D_{M,n} D M , n gives
∥ E n , h ∥ H S 2 D M , n = ( h ! ) 2 n ! ( M + n + h − 1 ) ! ( M − 1 ) ! ( n − h ) ! ( M + n − 1 ) ! ( M + 2 h − 1 ) ! . (25) \frac{\lVert E_{n,h}\rVert_{\mathrm{HS}}^2}{D_{M,n}} = \frac{(h!)^2 n!(M+n+h-1)!(M-1)!}{(n-h)!(M+n-1)!(M+2h-1)!}. \tag*{(25)} D M , n ∥ E n , h ∥ HS 2 = ( n − h )! ( M + n − 1 )! ( M + 2 h − 1 )! ( h ! ) 2 n ! ( M + n + h − 1 )! ( M − 1 )! . (25)
Combining the expectation ratio with these norms in the normalization relative to the uniform reference yields
s h 2 ( M , N , k ) = ( ( k h ) ( N h ) ) 2 ∥ E N , h ∥ H S 2 / D M , N ∥ E k , h ∥ H S 2 / D M , k = ( k h ) ( N h ) ( M + N + h − 1 ) ! ( M + k − 1 ) ! ( M + N − 1 ) ! ( M + k + h − 1 ) ! . (26) s_h^2(M,N,k) = \left(\frac{\binom{k}{h}}{\binom{N}{h}}\right)^2 \frac{\lVert E_{N,h}\rVert_{\mathrm{HS}}^2/D_{M,N}}{\lVert E_{k,h}\rVert_{\mathrm{HS}}^2/D_{M,k}} = \frac{\binom{k}{h}}{\binom{N}{h}}\frac{(M+N+h-1)!(M+k-1)!}{(M+N-1)!(M+k+h-1)!}. \tag*{(26)} s h 2 ( M , N , k ) = ( ( h N ) ( h k ) ) 2 ∥ E k , h ∥ HS 2 / D M , k ∥ E N , h ∥ HS 2 / D M , N = ( h N ) ( h k ) ( M + N − 1 )! ( M + k + h − 1 )! ( M + N + h − 1 )! ( M + k − 1 )! . (26)
The factorial ratio accounts for the change in normalization between photon sectors.
Combining the two identities
Return to the k k k -photon state σ k \sigma_k σ k and its reduction γ h \gamma_h γ h . Setting the initial and final photon numbers in Eq. (B.15) to k k k and h h h gives
s h 2 ( M , k , h ) = 1 ( k h ) ( M + k + h − 1 ) ! ( M + h − 1 ) ! ( M + k − 1 ) ! ( M + 2 h − 1 ) ! . (27) s_h^2(M,k,h) = \frac{1}{\binom{k}{h}}\frac{(M+k+h-1)!(M+h-1)!}{(M+k-1)!(M+2h-1)!}. \tag*{(27)} s h 2 ( M , k , h ) = ( h k ) 1 ( M + k − 1 )! ( M + 2 h − 1 )! ( M + k + h − 1 )! ( M + h − 1 )! . (27)
On the h h h -photon space, write γ h [ h ] = P h [ h ] γ h \gamma_h^{[h]}=\mathcal{P}_h^{[h]}\gamma_h γ h [ h ] = P h [ h ] γ h for the order h h h component of the reduced state. Applying Eq. (B.12) to γ h \gamma_h γ h yields
s h 2 ( M , k , h ) W h ( k ) = D M , h Z M , h R M , h ∥ γ h [ h ] ∥ H S 2 ≤ D M , h Z M , h R M , h Tr γ h 2 = M + h − 1 M + 2 h − 1 τ h . (28) s_h^2(M,k,h)W_h(k)=\frac{D_{M,h}Z_{M,h}}{R_{M,h}}\lVert\gamma_h^{[h]}\rVert_{\mathrm{HS}}^2\le\frac{D_{M,h}Z_{M,h}}{R_{M,h}}\operatorname{Tr}\gamma_h^2=\frac{M+h-1}{M+2h-1}\tau_h. \tag*{(28)} s h 2 ( M , k , h ) W h ( k ) = R M , h D M , h Z M , h ∥ γ h [ h ] ∥ HS 2 ≤ R M , h D M , h Z M , h Tr γ h 2 = M + 2 h − 1 M + h − 1 τ h . (28)
The inequality follows because orthogonal projection cannot increase the squared norm, and ∥ γ h ∥ H S 2 = Tr γ h 2 \lVert\gamma_h\rVert_{\mathrm{HS}}^2=\operatorname{Tr}\gamma_h^2 ∥ γ h ∥ HS 2 = Tr γ h 2 . Dividing by Eq. (B.16) proves the first inequality in Eq. (B.11). The second follows from ( M + h − 1 ) / ( M + 2 h − 1 ) ≤ 1 (M+h-1)/(M+2h-1)\le1 ( M + h − 1 ) / ( M + 2 h − 1 ) ≤ 1 and the factorial ratio ∏ ℓ = 0 h − 1 ( M + h + ℓ ) / ( M + k + ℓ ) ≤ 1 \prod_{\ell=0}^{h-1}(M+h+\ell)/(M+k+\ell)\le1 ∏ ℓ = 0 h − 1 ( M + h + ℓ ) / ( M + k + ℓ ) ≤ 1 for h ≤ k h\le k h ≤ k .
Fock state boson sampling
For one photon in each of n n n distinct input modes, the normalized h h h particle reduction is
γ h = ( n h ) − 1 ∑ S ⊆ [ n ] ∣ S ∣ = h ∣ 1 S ⟩ ⟨ 1 S ∣ . (29) \gamma_h=\binom{n}{h}^{-1}\sum_{\substack{S\subseteq[n]\\ |S|=h}}\lvert1_S\rangle\langle1_S\rvert. \tag*{(29)} γ h = ( h n ) − 1 S ⊆ [ n ] ∣ S ∣ = h ∑ ∣ 1 S ⟩ ⟨ 1 S ∣ . (29)
The components are orthogonal, hence
τ h = ( n h ) − 1 . (30) \tau_h=\binom{n}{h}^{-1}. \tag*{(30)} τ h = ( h n ) − 1 . (30)
Conditioned on k ∼ Bin ( n , η ) k\sim\operatorname{Bin}(n,\eta) k ∼ Bin ( n , η ) , the input after loss is γ k \gamma_k γ k . For h ≤ k h\le k h ≤ k , its h h h particle reduction is again γ h \gamma_h γ h , and Eq. (B.11) gives
W h ( k ) ≤ ( k h ) ( n h ) . (31) W_h(k)\le\frac{\binom{k}{h}}{\binom{n}{h}}. \tag*{(31)} W h ( k ) ≤ ( h n ) ( h k ) . (31)
For h > k h>k h > k , there is no order h h h component, so W h ( k ) = 0 W_h(k)=0 W h ( k ) = 0 and the bound still holds with ( k h ) = 0 \binom{k}{h}=0 ( h k ) = 0 . The binomial factorial moment identity then gives
E k W h ( k ) ≤ η h . (32) \mathbb{E}_kW_h(k)\le\eta^h. \tag*{(32)} E k W h ( k ) ≤ η h . (32)
Averaging over Haar random U U U and the binomial count k k k , orthogonality and Eq. (B.21) bound the squared truncation error and, after adding the constant component ∥ Π 0 F U ∥ 2 2 = 1 \lVert\Pi_0F_U\rVert_2^2=1 ∥ Π 0 F U ∥ 2 2 = 1 , the second moment,
E U , k ∥ F U − F U ≤ L ∥ 2 2 = ∑ h = L + 1 n E k W h ( k ) ≤ ∑ h = L + 1 ∞ η h = η L + 1 1 − η . (33) \mathbb{E}_{U,k}\lVert F_U-F_U^{\le L}\rVert_2^2=\sum_{h=L+1}^{n}\mathbb{E}_kW_h(k)\le\sum_{h=L+1}^{\infty}\eta^h=\frac{\eta^{L+1}}{1-\eta}. \tag*{(33)} E U , k ∥ F U − F U ≤ L ∥ 2 2 = h = L + 1 ∑ n E k W h ( k ) ≤ h = L + 1 ∑ ∞ η h = 1 − η η L + 1 . (33)
E U , k ∥ F U ∥ 2 2 ≤ 1 1 − η . (34) \mathbb{E}_{U,k}\lVert F_U\rVert_2^2\le\frac{1}{1-\eta}. \tag*{(34)} E U , k ∥ F U ∥ 2 2 ≤ 1 − η 1 . (34)
Both bounds hold at every finite M M M , because they rest on the exact Haar average in Eq. (B.12) rather than on an approximation for large M M M , and the average over k k k includes the lossless event k = n k=n k = n .
Gaussian boson sampling
We now prove the bounds for Theorem 2, in which every input mode is squeezed, s = M s=M s = M , for every fixed r > 0 r>0 r > 0 and η \eta η . We fix a photon number sector N = 2 n N=2n N = 2 n before loss. This suffices, because the measured probabilities are a mixture over such sectors with the weights in Eq. (B.2), as shown in Sec. B 1 a. For the normalized N N N -photon input component ∣ Ψ M , N ⟩ \lvert\Psi_{M,N}\rangle ∣ Ψ M , N ⟩ in Eq. (B.3), let
Γ M , N , h : = E U ∥ Π h F U ( N ) ∥ 2 2 . \Gamma_{M,N,h}:=\mathbb{E}_U\left\|\Pi_h F_U^{(N)}\right\|_2^2. Γ M , N , h := E U Π h F U ( N ) 2 2 .
This is the weight W h ( k ) W_h(k) W h ( k ) of Eq. (B.10) for the lossless case k = N k=N k = N . Odd orders vanish because the input sector is invariant under real orthogonal mode transformations, while for h = 2 j h=2j h = 2 j with 0 ≤ j ≤ n 0\leq j\leq n 0 ≤ j ≤ n ,
Γ M , 2 n , 2 j = b j b n − j b n ∏ v = 0 j − 1 M + 2 v − 1 M + 2 v × M + 2 n + 2 v M + 2 n + 2 v + 1 , b j = 4 − j ( 2 j j ) . (35) \Gamma_{M,2n,2j}=\frac{b_jb_{n-j}}{b_n}\prod_{v=0}^{j-1}\frac{M+2v-1}{M+2v}\times\frac{M+2n+2v}{M+2n+2v+1},\qquad b_j=4^{-j}\binom{2j}{j}. \tag*{(35)} Γ M , 2 n , 2 j = b n b j b n − j v = 0 ∏ j − 1 M + 2 v M + 2 v − 1 × M + 2 n + 2 v + 1 M + 2 n + 2 v , b j = 4 − j ( j 2 j ) . (35)
This is the equal squeezing coefficient of Ref. [26 ] , rescaled to our normalization of F U F_U F U . Section B 5 gives the normalization calculation.
Vandermonde’s identity implies
( 2 n n ) ≥ ( 2 j j ) ( 2 n − 2 j n − j ) . (36) \binom{2n}{n}\geq\binom{2j}{j}\binom{2n-2j}{n-j}. \tag*{(36)} ( n 2 n ) ≥ ( j 2 j ) ( n − j 2 n − 2 j ) . (36)
so the prefactor b j b n − j / b n b_jb_{n-j}/b_n b j b n − j / b n is at most one. Every other factor in Eq. (B.24) is also at most one, so
0 ≤ Γ M , N , h ≤ 1 ( 0 ≤ h ≤ N ) . (37) 0\leq\Gamma_{M,N,h}\leq1\qquad(0\leq h\leq N). \tag*{(37)} 0 ≤ Γ M , N , h ≤ 1 ( 0 ≤ h ≤ N ) . (37)
Without loss, each order up to N N N can therefore carry a weight of order one, so the number of relevant orders can grow with N N N .
Reduction from N N N to k k k photons gives the exact weight
W h ( k ) = Γ M , N , h ( k h ) ( N h ) ( M + N + h − 1 ) ! ( M + k − 1 ) ! ( M + N − 1 ) ! ( M + k + h − 1 ) ! . (38) W_h(k)=\Gamma_{M,N,h}\frac{\binom{k}{h}}{\binom{N}{h}}\frac{(M+N+h-1)!(M+k-1)!}{(M+N-1)!(M+k+h-1)!}. \tag*{(38)} W h ( k ) = Γ M , N , h ( h N ) ( h k ) ( M + N − 1 )! ( M + k + h − 1 )! ( M + N + h − 1 )! ( M + k − 1 )! . (38)
The factor multiplying Γ M , N , h \Gamma_{M,N,h} Γ M , N , h is ∏ ℓ = 0 h − 1 ( k − ℓ ) ( M + N + ℓ ) / [ ( N − ℓ ) ( M + k + ℓ ) ] \prod_{\ell=0}^{h-1}(k-\ell)(M+N+\ell)/[(N-\ell)(M+k+\ell)] ∏ ℓ = 0 h − 1 ( k − ℓ ) ( M + N + ℓ ) / [( N − ℓ ) ( M + k + ℓ )] . Each factor of this product is at most its value at ℓ = 0 \ell=0 ℓ = 0 , so
W h ( k ) ≤ χ h , χ = k ( M + N ) N ( M + k ) . (39) W_h(k)\leq\chi^h,\qquad\chi=\frac{k(M+N)}{N(M+k)}. \tag*{(39)} W h ( k ) ≤ χ h , χ = N ( M + k ) k ( M + N ) . (39)
On the count region N ≤ c M N\leq cM N ≤ c M and k ≤ ϑ N k\leq\vartheta N k ≤ ϑN , where c c c is fixed and η < ϑ < 1 \eta<\vartheta<1 η < ϑ < 1 ,
χ ≤ χ ∗ : = ϑ ( 1 + c ) 1 + ϑ c < 1. (40) \chi\leq\chi_*:=\frac{\vartheta(1+c)}{1+\vartheta c}<1. \tag*{(40)} χ ≤ χ ∗ := 1 + ϑ c ϑ ( 1 + c ) < 1. (40)
For the cutoff L = 2 ℓ L=2\ell L = 2 ℓ , orthogonality and the absence of odd orders bound the squared truncation error and, after adding the constant component, the second moment,
E U ∥ F U − F U ≤ 2 ℓ ∥ 2 2 ≤ χ ∗ 2 ℓ + 2 1 − χ ∗ 2 , (41) \mathbb{E}_U\left\|F_U-F_U^{\leq2\ell}\right\|_2^2\leq\frac{\chi_*^{2\ell+2}}{1-\chi_*^2}, \tag*{(41)} E U F U − F U ≤ 2 ℓ 2 2 ≤ 1 − χ ∗ 2 χ ∗ 2 ℓ + 2 , (41)
E U ∥ F U ∥ 2 2 ≤ 1 1 − χ ∗ 2 . (42) \mathbb{E}_U\left\|F_U\right\|_2^2\leq\frac{1}{1-\chi_*^2}. \tag*{(42)} E U ∥ F U ∥ 2 2 ≤ 1 − χ ∗ 2 1 . (42)
For fixed r r r , the mean input photon number is M sinh 2 r M\sinh^2r M sinh 2 r , and Sec. D 3 treats the sectors outside this count region.
Haar coefficients for equal squeezing
We take M ≥ 2 M \ge2 M ≥ 2 and follow the derivation in Ref. [26 ] to compute the coefficient in Eq. (B.24). Under real orthogonal mode transformations, the k k k -photon space has the Fischer decomposition
S y m k C M = ⨁ q = 0 ⌊ k / 2 ⌋ ( A M † ) q H a r m k − 2 q , (43) \mathrm{Sym}^{k} \mathbb{C}^{M} = \bigoplus_{q=0}^{\lfloor k/2\rfloor} (A_{M}^{\dagger})^{q}\mathrm{Harm}_{k-2q}, \tag*{(43)} Sym k C M = q = 0 ⨁ ⌊ k /2 ⌋ ( A M † ) q Harm k − 2 q , (43)
where H a r m j \mathrm{Harm}_{j} Harm j is the space of j j j -photon states annihilated by the pair annihilation operator A M = 1 2 ∑ i a i 2 A_{M} = \frac{1}{2}\sum_{i} a_{i}^{2} A M = 2 1 ∑ i a i 2 . In the Bargmann representation, these states are the harmonic polynomials of degree j j j . On the h h h -photon space, an operator X X X has correlation order exactly h ≥ 1 h \ge1 h ≥ 1 precisely when Tr 1 X = 0 \operatorname{Tr}_{1} X = 0 Tr 1 X = 0 , where Tr 1 \operatorname{Tr}_{1} Tr 1 traces out one particle. An operator invariant under all real orthogonal mode transformations commutes with their action, so by Schur’s lemma it is a multiple of the identity on each summand of Eq. (B.32). On the h h h -photon space, such operators therefore form a space of dimension ⌊ h / 2 ⌋ + 1 \lfloor h/2\rfloor+ 1 ⌊ h /2 ⌋ + 1 , and those of order at most h − 1 h-1 h − 1 form a space of dimension ⌊ ( h − 1 ) / 2 ⌋ + 1 \lfloor(h-1)/2\rfloor+ 1 ⌊( h − 1 ) /2 ⌋ + 1 . The invariant operators of order exactly h h h thus form a one dimensional space for even h h h and none exist for odd h h h . The state ρ 2 n = ∣ Ψ M , 2 n ⟩ ⟨ Ψ M , 2 n ∣ \rho_{2n} = \lvert\Psi_{M,2n}\rangle\langle\Psi_{M,2n}\rvert ρ 2 n = ∣ Ψ M , 2 n ⟩ ⟨ Ψ M , 2 n ∣ is orthogonally invariant, and so is each of its correlation components. Its odd components therefore vanish, and each even component lies in the one dimensional invariant space of its order.
For j ≥ 1 j \ge1 j ≥ 1 , choose the order 2 j 2j 2 j operator Y j Y_j Y j and average it over real orthogonal mode transformations,
Y j = ∣ 2 j e 1 ⟩ ⟨ 2 j e 2 ∣ , Y ‾ j = ∫ O ( M ) S y m 2 j ( O ) Y j S y m 2 j ( O ) † d O . (44) Y_j = \lvert2j e_1\rangle\langle2j e_2\rvert,\qquad\overline{Y}_j = \int_{O(M)} \mathrm{Sym}^{2j}(O)Y_j\mathrm{Sym}^{2j}(O)^{\dagger}\,\mathrm{d}O. \tag*{(44)} Y j = ∣ 2 j e 1 ⟩ ⟨ 2 j e 2 ∣ , Y j = ∫ O ( M ) Sym 2 j ( O ) Y j Sym 2 j ( O ) † d O . (44)
Here ∣ 2 j e i ⟩ \lvert2j e_i\rangle ∣ 2 j e i ⟩ denotes the Fock state with 2 j 2j 2 j photons in mode i i i and vacuum in every other mode. Since Tr 1 Y j = 0 \operatorname{Tr}_{1}Y_j = 0 Tr 1 Y j = 0 , Y j Y_j Y j lies entirely in order 2 j 2j 2 j , and its average Y ‾ j \overline{Y}_j Y j spans the invariant subspace. The squared Hilbert–Schmidt norm of Y ‾ j \overline{Y}_j Y j is
β M , j = ∫ O ( M ) O 11 2 j O 22 2 j d O = [ ( 2 j ) ! ] 2 4 j ( j ! ) 2 ∏ ℓ = 0 j − 1 M + 2 j + 2 ℓ − 1 ( M + 2 ℓ − 1 ) ( M + 2 ℓ ) ( M + 2 j + 2 ℓ ) . (45) \beta_{M,j} = \int_{O(M)} O_{11}^{2j}O_{22}^{2j}\,\mathrm{d}O = \frac{[(2j)!]^{2}}{4^{j}(j!)^{2}}\prod_{\ell=0}^{j-1}\frac{M+2j+2\ell-1}{(M+2\ell-1)(M+2\ell)(M+2j+2\ell)}. \tag*{(45)} β M , j = ∫ O ( M ) O 11 2 j O 22 2 j d O = 4 j ( j ! ) 2 [( 2 j )! ] 2 ℓ = 0 ∏ j − 1 ( M + 2 ℓ − 1 ) ( M + 2 ℓ ) ( M + 2 j + 2 ℓ ) M + 2 j + 2 ℓ − 1 . (45)
To obtain this integral, condition on the first column x x x of O O O . The second column is then uniform on the unit sphere orthogonal to x x x , and its relevant moment is
( 1 − x 2 2 ) j ( 2 j ) ! 2 2 j j ! ∏ ℓ = 0 j − 1 ( M − 1 + 2 ℓ ) . (1-x_{2}^{2})^{j}\frac{(2j)!}{2^{2j}j!\prod_{\ell=0}^{j-1}(M-1+2\ell)}. ( 1 − x 2 2 ) j 2 2 j j ! ∏ ℓ = 0 j − 1 ( M − 1 + 2 ℓ ) ( 2 j )! .
Expanding the power and averaging over x x x with
E x 1 2 a x 2 2 b = ( 2 a ) ! ( 2 b ) ! 2 a + b a ! b ! ∏ ℓ = 0 a + b − 1 ( M + 2 ℓ ) (46) \mathbb{E}x_{1}^{2a}x_{2}^{2b} = \frac{(2a)!(2b)!}{2^{a+b}a!b!\prod_{\ell=0}^{a+b-1}(M+2\ell)} \tag*{(46)} E x 1 2 a x 2 2 b = 2 a + b a ! b ! ∏ ℓ = 0 a + b − 1 ( M + 2 ℓ ) ( 2 a )! ( 2 b )! (46)
gives a finite series, which the Chu–Vandermonde identity sums to Eq. (B.34).
Write D ( X ) = ∑ i a i X a i † D(X) = \sum_i a_i X a_i^\dagger D ( X ) = ∑ i a i X a i † for unnormalized removal of one particle. On an N N N -photon state, normalized reduction to k k k photons is ( k ! / N ! ) D N − k (k!/N!)D^{N-k} ( k ! / N !) D N − k . Expanding ρ 2 n \rho_{2n} ρ 2 n in the Fock basis and deleting 2 n − 2 j 2n-2j 2 n − 2 j photons gives
μ M , n , j : = ⟨ Y j , D 2 n − 2 j ( ρ 2 n ) ⟩ H S = ( 2 n − 2 j ) ! n ! ( 2 j ) ! 2 2 j ( j ! ) 2 ( n − j ) ! ∏ ℓ = 0 n − j − 1 ( M + 4 j + 2 ℓ ) ∏ ℓ = 0 n − 1 ( M + 2 ℓ ) . (47) \mu_{M,n,j} := \langle Y_j,D^{2n-2j}(\rho_{2n})\rangle_{\mathrm{HS}} = \frac{(2n-2j)!n!(2j)!}{2^{2j}(j!)^{2}(n-j)!}\frac{\prod_{\ell=0}^{n-j-1}(M+4j+2\ell)}{\prod_{\ell=0}^{n-1}(M+2\ell)}. \tag*{(47)} μ M , n , j := ⟨ Y j , D 2 n − 2 j ( ρ 2 n ) ⟩ HS = 2 2 j ( j ! ) 2 ( n − j )! ( 2 n − 2 j )! n ! ( 2 j )! ∏ ℓ = 0 n − 1 ( M + 2 ℓ ) ∏ ℓ = 0 n − j − 1 ( M + 4 j + 2 ℓ ) . (47)
This follows from the Fock coefficients
⟨ 2 q ∣ Ψ M , 2 n ⟩ = n ! 2 n ∏ ℓ = 0 n − 1 ( M + 2 ℓ ) ∏ i ( 2 q i ) ! q i ! . (48) \langle2q|\Psi_{M,2n}\rangle= \sqrt{\frac{n!}{2^n\prod_{\ell=0}^{n-1}(M+2\ell)}}\prod_i\frac{\sqrt{(2q_i)!}}{q_i!}. \tag*{(48)} ⟨ 2 q ∣ Ψ M , 2 n ⟩ = 2 n ∏ ℓ = 0 n − 1 ( M + 2 ℓ ) n ! i ∏ q i ! ( 2 q i )! . (48)
and coefficient extraction in
[ ( 2 j ) ! j ! ( 1 − 4 z ) − j − 1 / 2 ] 2 ( 1 − 4 z ) − ( M − 2 ) / 2 . (49) \left[\frac{(2j)!}{j!}(1-4z)^{-j-1/2}\right]^2(1-4z)^{-(M-2)/2}. \tag*{(49)} [ j ! ( 2 j )! ( 1 − 4 z ) − j − 1/2 ] 2 ( 1 − 4 z ) − ( M − 2 ) /2 . (49)
The Hilbert–Schmidt adjoint D ∗ D^* D ∗ adds one particle, and after 2 n − 2 j 2n-2j 2 n − 2 j additions
∥ ( D ∗ ) 2 n − 2 j Y ‾ j ∥ H S 2 = ( 2 n − 2 j ) ! ( M + 2 n + 2 j − 1 ) ! ( M + 4 j − 1 ) ! β M , j . (50) \left\|(D^*)^{2n-2j}\overline{Y}_j\right\|_{\mathrm{HS}}^2
=
\frac{(2n-2j)!(M+2n+2j-1)!}{(M+4j-1)!}\beta_{M,j}. \tag*{(50)} ( D ∗ ) 2 n − 2 j Y j HS 2 = ( M + 4 j − 1 )! ( 2 n − 2 j )! ( M + 2 n + 2 j − 1 )! β M , j . (50)
Since ( D ∗ ) 2 n − 2 j Y ‾ j (D^*)^{2n-2j}\overline{Y}_j ( D ∗ ) 2 n − 2 j Y j spans the invariant subspace of order 2 j 2j 2 j in the 2 n 2n 2 n -photon space,
∥ ρ 2 n [ 2 j ] ∥ H S 2 = ( M + 4 j − 1 ) ! μ M , n , j 2 ( 2 n − 2 j ) ! ( M + 2 n + 2 j − 1 ) ! β M , j . (51) \left\|\rho_{2n}^{[2j]}\right\|_{\mathrm{HS}}^2
=
\frac{(M+4j-1)!\mu_{M,n,j}^2}{(2n-2j)!(M+2n+2j-1)!\beta_{M,j}}. \tag*{(51)} ρ 2 n [ 2 j ] HS 2 = ( 2 n − 2 j )! ( M + 2 n + 2 j − 1 )! β M , j ( M + 4 j − 1 )! μ M , n , j 2 . (51)
Multiplying by D M , 2 n / R M , 2 j D_{M,2n}/R_{M,2j} D M , 2 n / R M , 2 j as in Eq. (B.12) gives the coefficient
Λ 2 j = [ ( 2 j ) ! n ! j ! ( n − j ) ! ] 2 ( 2 n − 2 j ) ! ( 2 n ) ! × ∏ ℓ = 0 j − 1 M + 2 n + 2 ℓ ( M + 2 ℓ ) 2 ( M + 2 n + 2 ℓ + 1 ) . (52) \Lambda_{2j}
=
\left[\frac{(2j)!n!}{j!(n-j)!}\right]^2
\frac{(2n-2j)!}{(2n)!}
\times
\prod_{\ell=0}^{j-1}
\frac{M+2n+2\ell}{(M+2\ell)^2(M+2n+2\ell+1)}. \tag*{(52)} Λ 2 j = [ j ! ( n − j )! ( 2 j )! n ! ] 2 ( 2 n )! ( 2 n − 2 j )! × ℓ = 0 ∏ j − 1 ( M + 2 ℓ ) 2 ( M + 2 n + 2 ℓ + 1 ) M + 2 n + 2 ℓ . (52)
Multiplying by Z M , 2 j Z_{M,2j} Z M , 2 j , as Eq. (B.12) requires, and separating the even and odd factors yields Eq. (B.24). The constant order has Γ M , N , 0 = 1 \Gamma_{M,N,0}=1 Γ M , N , 0 = 1 .
Evaluation of low-order correlations
Appendix B shows that the output distribution can be approximated by truncating its correlation expansion at order L L L . To turn this approximation into a sampler, we must compute a weight for each proposed output. The task here is therefore to estimate F U ≤ L ( x ) F_U^{\leq L}(x) F U ≤ L ( x ) from the supplied interferometer U U U and a proposed configuration x x x , at fixed photon numbers N N N before loss and k = ∣ x ∣ k=|x| k = ∣ x ∣ after loss.
We construct the estimate one correlation order at a time. First, particle reduction expresses each contribution as a sum over configurations of only h ≤ min { L , k } h\leq\min\{L,k\} h ≤ min { L , k } photons, which we call auxiliary configurations. We then group the mode labels at random so that the terms in this sum can be combined by generating functions. We define the resulting random estimate before proving its error bounds and giving its explicit evaluation for single-photon and Gaussian inputs. Finally, we choose the auxiliary cutoff and bound the total evaluation cost. In Appendix D, these estimates set the acceptance probabilities of the sampler.
Constructing the random estimate
Direct evaluation and its limitations
A direct reconstruction uses reduced photon count probabilities. Let P N → h ( y ) P_{N\to h}(y) P N → h ( y ) be the probability of the h h h -photon configuration y y y obtained by reducing the interferometer output in the fixed N N N -photon sector. The configuration y y y is an auxiliary summation index used to evaluate the weight of the proposed k k k -photon output x x x . We suppress U U U in this notation and write F U ( h ) ( y ) = D M , h P N → h ( y ) F_U^{(h)}(y)=D_{M,h}P_{N\to h}(y) F U ( h ) ( y ) = D M , h P N → h ( y ) . To separate the correlation orders, we use an operator that forgets all but h h h of the k k k photons and then refills the configuration. It acts on functions f f f of k k k -photon configurations by ( T k , h f ) ( x ) = E f ( x ′ ) (T_{k,h}f)(x) = \mathbb{E}f(x') ( T k , h f ) ( x ) = E f ( x ′ ) , where x ′ x' x ′ is obtained from x x x by keeping a uniformly chosen set of h h h photons and then adding k − h k-h k − h photons one at a time. If the current configuration is z z z , choose mode i i i with probability ( z i + 1 ) / ( M + ∣ z ∣ ) (z_i+1)/(M+|z|) ( z i + 1 ) / ( M + ∣ z ∣ ) , increase z i z_i z i by one, and update the probabilities before the next insertion. Under the uniform reference distributions, this rule is the reverse of uniform photon deletion, so reinsertion and deletion are adjoint. The resulting operator preserves u M , k u_{M,k} u M , k and is self-adjoint. As shown in Sec. B 2 b, deletion acts on each correlation order separately and rescales it by a single factor, and the same holds for reinsertion. Each order j ≤ h j \le h j ≤ h is therefore an eigenspace of T k , h T_{k,h} T k , h , and Eq. (B.15) gives its eigenvalue
λ h , j = ( h j ) ( k j ) ( M + k + j − 1 ) ! ( M + h − 1 ) ! ( M + k − 1 ) ! ( M + h + j − 1 ) ! , j ≤ h . (53) \lambda_{h,j}=\frac{\binom{h}{j}}{\binom{k}{j}}\frac{(M+k+j-1)!(M+h-1)!}{(M+k-1)!(M+h+j-1)!},\qquad j\le h. \tag*{(53)} λ h , j = ( j k ) ( j h ) ( M + k − 1 )! ( M + h + j − 1 )! ( M + k + j − 1 )! ( M + h − 1 )! , j ≤ h . (53)
Orders above h h h are annihilated, because only h h h photons are retained. For this reconstruction take 0 ≤ L ≤ k 0 \le L \le k 0 ≤ L ≤ k , replacing a larger cutoff by k k k . A triangular system gives F U L = ∑ h ≤ L c h T k , h F U F_U^L=\sum_{h\le L}c_hT_{k,h}F_U F U L = ∑ h ≤ L c h T k , h F U , where
∑ h = j L c h λ h , j = 1 , 0 ≤ j ≤ L . (54) \sum_{h=j}^{L}c_h\lambda_{h,j}=1,\qquad0\le j\le L. \tag*{(54)} h = j ∑ L c h λ h , j = 1 , 0 ≤ j ≤ L . (54)
Since λ h , h ≠ 0 \lambda_{h,h}\ne0 λ h , h = 0 , these coefficients can be found by backward substitution. Composition of normalized particle reductions gives the direct evaluation formula
( T k , h F U ) ( x ) = D M , h ( k h ) ∑ y ≤ x ∣ y ∣ = h [ ∏ i ( x i y i ) ] P N → h ( y ) . (55) (T_{k,h}F_U)(x)=\frac{D_{M,h}}{\binom{k}{h}}\sum_{\substack{y\le x\\ |y|=h}}\left[\prod_i\binom{x_i}{y_i}\right]P_{N\to h}(y). \tag*{(55)} ( T k , h F U ) ( x ) = ( h k ) D M , h y ≤ x ∣ y ∣ = h ∑ [ i ∏ ( y i x i ) ] P N → h ( y ) . (55)
Direct evaluation costs ( M + N + L ) O ( L ) (M+N+L)^{O(L)} ( M + N + L ) O ( L ) . Moreover, the coefficient
c L = ( k L ) ( M + 2 L − 1 ) ! ( M + k − 1 ) ! ( M + L − 1 ) ! ( M + k + L − 1 ) ! c_L=\binom{k}{L}\frac{(M+2L-1)!(M+k-1)!}{(M+L-1)!(M+k+L-1)!} c L = ( L k ) ( M + L − 1 )! ( M + k + L − 1 )! ( M + 2 L − 1 )! ( M + k − 1 )!
can be large and amplify the errors of independent estimates of the summands. We therefore isolate each correlation order in both factors before estimating the sum.
Two-sided projection
We first rewrite the contribution at order h h h so that the cancellations among lower orders are carried out before random estimation. This will allow the error to be controlled by the order weight W h ( k ) W_h(k) W h ( k ) from Appendix B. Normalization fixes the component of order zero to Π 0 F U = 1 \Pi_0F_U=1 Π 0 F U = 1 , so it requires no estimation. We therefore consider 1 ≤ h ≤ k 1\le h\le k 1 ≤ h ≤ k .
Let D h = D M , h D_h=D_{M,h} D h = D M , h and let H h \mathcal{H}_h H h be the space of functions on h h h -photon configurations, with the uniform inner product used in Appendix B. In this space, Π h \Pi_h Π h projects onto order h h h and removes all lower orders. Its range has dimension Z M , h = D h − D h − 1 Z_{M,h}=D_h-D_{h-1} Z M , h = D h − D h − 1 , as in Eq. (B.9). For a proposed output x x x , the probability of obtaining y y y by selecting h h h photons uniformly without replacement is ∏ i ( x i y i ) / ( k h ) \prod_i\binom{x_i}{y_i}/\binom{k}{h} ∏ i ( y i x i ) / ( h k ) . Define the corresponding weight w x w_x w x and its order h h h part v x v_x v x , and write ψ h ( U ) \psi_h(U) ψ h ( U ) for the order h h h part of the reduced output F U ( h ) F_U^{(h)} F U ( h ) defined above,
w x ( y ) = D h ∏ i ( x i y i ) ( k h ) , v x = Π h w x , ψ h ( U ) = Π h F U ( h ) . (56) w_x(y)=D_h\frac{\prod_i\binom{x_i}{y_i}}{\binom{k}{h}},\qquad v_x=\Pi_hw_x,\qquad\psi_h(U)=\Pi_hF_U^{(h)}. \tag*{(56)} w x ( y ) = D h ( h k ) ∏ i ( y i x i ) , v x = Π h w x , ψ h ( U ) = Π h F U ( h ) . (56)
Thus v x v_x v x is determined by the proposed configuration, while ψ h ( U ) \psi_h(U) ψ h ( U ) is determined by the optical output. With λ h = λ h , h \lambda_h = \lambda_{h,h} λ h = λ h , h from Eq. (C.1), particle reduction gives
f h ( U , x ) : = ( Π h ( k ) F U ( k ) ) ( x ) = λ h − 1 ⟨ v x , ψ h ( U ) ⟩ u h . (57) f_h(U,x) := \left(\Pi_h^{(k)}F_U^{(k)}\right)(x) = \lambda_h^{-1}\langle v_x,\psi_h(U)\rangle_{u_h}. \tag*{(57)} f h ( U , x ) := ( Π h ( k ) F U ( k ) ) ( x ) = λ h − 1 ⟨ v x , ψ h ( U ) ⟩ u h . (57)
The inner product is a uniform sum over the auxiliary configurations y y y . Both factors are projected onto order h h h , so they can have either sign even though the original probabilities are nonnegative.
To verify Eq. (C.5), write ( A k , h g ) ( x ) = ⟨ w x , g ⟩ u h (A_{k,h}g)(x)=\langle w_x,g\rangle_{u_h} ( A k , h g ) ( x ) = ⟨ w x , g ⟩ u h for the average of g g g after selecting h h h photons uniformly from x x x . Its adjoint maps the k k k -photon output to the reduced one, F U ( h ) = A k , h † F U ( k ) F_U^{(h)}=A_{k,h}^{\dagger}F_U^{(k)} F U ( h ) = A k , h † F U ( k ) . The reduction factors in Eq. (C.1) imply Π h A k , h † A k , h Π h = λ h Π h \Pi_hA_{k,h}^{\dagger}A_{k,h}\Pi_h=\lambda_h\Pi_h Π h A k , h † A k , h Π h = λ h Π h . Consequently, applying A k , h A_{k,h} A k , h to ψ h \psi_h ψ h gives λ h \lambda_h λ h times the order h h h component on k k k -photon configurations, which yields Eq. (C.5).
Random grouping of mode labels
Evaluating the inner product in Eq. (C.5) involves many choices of mode labels. To combine their contributions efficiently, place each mode independently into one of h h h labeled groups, with equal probability [27 ] . Group sizes fluctuate, and empty groups are allowed. First consider configurations on h h h distinct modes, and select those with one occupied mode in each group. Their contributions can be combined by multiplying sums over the groups and evaluating determinant generating functions.
For any fixed set of h h h distinct modes, all h h h^h h h group placements are equally likely, and h ! h! h ! of them place one mode in each group. The set is therefore selected with probability h ! / h h h!/h^h h ! / h h . Weighting the selected contribution by the reciprocal of this probability recovers the original contribution on average. When the auxiliary configuration has repeated occupations, use as many groups as there are occupied modes.
For an auxiliary h h h -photon configuration y y y , let ν ( y ) = h − ∣ supp y ∣ \nu(y)=h-|\operatorname{supp}y| ν ( y ) = h − ∣ supp y ∣ , where supp y \operatorname{supp}y supp y is the set of occupied modes, count photons beyond the first photon in each occupied mode. Repeated occupations require additional sums over their multiplicities, so we include only ν ( y ) < b \nu(y)<b ν ( y ) < b and later choose b b b to control their cost and omission error. This cutoff applies to auxiliary configurations used in the calculation. The final output x x x ranges over all k k k -photon configurations, including collisions.
For each value ν < b \nu<b ν < b that occurs, let c ( i ) ∈ { 1 , … , h − ν } c(i)\in\{1,\ldots,h-\nu\} c ( i ) ∈ { 1 , … , h − ν } be the independently and uniformly chosen group index of mode i i i . A configuration with ν ( y ) = ν \nu(y)=\nu ν ( y ) = ν has h − ν h-\nu h − ν occupied modes. The probability that these lie in different groups is
p h − ν = ( h − ν ) ! ( h − ν ) h − ν . (58) p_{h-\nu}=\frac{(h-\nu)!}{(h-\nu)^{h-\nu}}. \tag*{(58)} p h − ν = ( h − ν ) h − ν ( h − ν )! . (58)
Let M h \mathcal{M}_h M h multiply a configuration by 1 / p h − ν 1/p_{h-\nu} 1/ p h − ν if ν ( y ) < b \nu(y)<b ν ( y ) < b and its occupied modes lie in different groups, and set its component to zero otherwise. Let G h G_h G h be the diagonal projector onto all configurations with ν ( y ) < b \nu(y)<b ν ( y ) < b . The selection correction gives E M h = G h \mathbb{E}\mathcal{M}_h=G_h E M h = G h . Our estimate of the contribution at order h h h is
f ^ h = λ h − 1 ⟨ v x , M h ψ h ⟩ . (59) \widehat{f}_h=\lambda_h^{-1}\langle v_x,\mathcal{M}_h\psi_h\rangle. \tag*{(59)} f h = λ h − 1 ⟨ v x , M h ψ h ⟩ . (59)
For fixed U , x U,x U , x , its mean over the random groups is the sum restricted to ν ( y ) < b \nu(y)<b ν ( y ) < b . If no configurations are omitted, E f ^ h = f h ( U , x ) \mathbb{E}\widehat{f}_h=f_h(U,x) E f h = f h ( U , x ) . The grouping introduces variance, while the auxiliary cutoff can introduce bias. All group indices are drawn independently of U U U and x x x .
Accuracy of the random sum
We now bound the two errors in f ^ h \hat{f}_h f ^ h . The proposal x x x is uniform and independent of U U U , and all averages are taken before the acceptance step. The error is controlled by the second moments of the two factors in Eq. (C.5), namely the averaged outer products of v x v_x v x over uniform proposals and of ψ h ( U ) \psi_h(U) ψ h ( U ) over Haar interferometers. Both are proportional to Π h \Pi_h Π h , and they connect the error to the correlation weight W h ( k ) W_h(k) W h ( k ) ,
E x ∼ u k ∣ v x ⟩ ⟨ v x ∣ = λ h Π h , (60) \mathbb{E}_{x\sim u_k}|v_x\rangle\langle v_x|=\lambda_h\Pi_h, \tag*{(60)} E x ∼ u k ∣ v x ⟩ ⟨ v x ∣ = λ h Π h , (60)
E U ∣ ψ h ( U ) ⟩ ⟨ ψ h ( U ) ∣ = λ h W h ( k ) Z M , h Π h . (61) \mathbb{E}_U|\psi_h(U)\rangle\langle\psi_h(U)|=\frac{\lambda_h W_h(k)}{Z_{M,h}}\Pi_h. \tag*{(61)} E U ∣ ψ h ( U )⟩ ⟨ ψ h ( U ) ∣ = Z M , h λ h W h ( k ) Π h . (61)
Here the outer products act on functions in H h \mathcal{H}_h H h . The first identity averages over a uniform proposal x x x , and the second over the Haar interferometer U U U . Each supplies a factor of λ h \lambda_h λ h , canceling the factor λ h − 2 \lambda_h^{-2} λ h − 2 when we bound the squared error of Eq. (C.5). This cancellation relies on projecting both factors onto the same correlation order, and the remaining scale is set by W h ( k ) W_h(k) W h ( k ) .
The first identity follows from Π h A k , h † A k , h Π h = λ h Π h \Pi_h A_{k,h}^{\dagger}A_{k,h}\Pi_h=\lambda_h\Pi_h Π h A k , h † A k , h Π h = λ h Π h , established above. For the second identity, let σ N , h [ h ] = P h o p σ N , h \sigma_{N,h}^{[h]}=\mathcal{P}^{\mathrm{op}}_h\sigma_{N,h} σ N , h [ h ] = P h op σ N , h be the order h h h operator component of the reduced input σ N , h \sigma_{N,h} σ N , h . Haar averaging within this correlation sector, as in Appendix B, gives
E U ∣ ψ h ⟩ ⟨ ψ h ∣ = D h ∥ σ N , h [ h ] ∥ H S 2 R M , h Π h . (62) \mathbb{E}_U|\psi_h\rangle\langle\psi_h|=\frac{D_h\lVert\sigma_{N,h}^{[h]}\rVert_{\mathrm{HS}}^2}{R_{M,h}}\Pi_h. \tag*{(62)} E U ∣ ψ h ⟩ ⟨ ψ h ∣ = R M , h D h ∥ σ N , h [ h ] ∥ HS 2 Π h . (62)
The factor D h D_h D h accounts for the normalization of the rescaled output probability and the uniform inner product, and R M , h R_{M,h} R M , h is the operator sector dimension in Eq. (B.8). Taking the trace and using the particle reduction factor gives E U ∥ ψ h ∥ 2 = λ h W h ( k ) \mathbb{E}_U\lVert\psi_h\rVert^2=\lambda_hW_h(k) E U ∥ ψ h ∥ 2 = λ h W h ( k ) , yielding Eq. (C.9).
These identities lead to the following bounds for the random weights just constructed.
Lemma 1 (Error from random selection). The following bounds apply to any diagonal projector G h G_h G h onto a fixed set of auxiliary configurations and any real diagonal weights M h M_h M h that vanish outside this set and are independent of U , x U,x U , x . If E M h = G h \mathbb{E}M_h=G_h E M h = G h and E ( M h − G h ) 2 ≤ C h G h \mathbb{E}(M_h-G_h)^2\le C_hG_h E ( M h − G h ) 2 ≤ C h G h , the estimator in Eq. (C.7) satisfies
E U , x ∣ f h − E f ^ h ∣ 2 = W h ( k ) Z M , h ∥ Π h ( I − G h ) Π h ∥ H S 2 , (63) \mathbb{E}_{U,x}|f_h-\mathbb{E}\hat{f}_h|^2=\frac{W_h(k)}{Z_{M,h}}\lVert\Pi_h(I-G_h)\Pi_h\rVert_{\mathrm{HS}}^2, \tag*{(63)} E U , x ∣ f h − E f ^ h ∣ 2 = Z M , h W h ( k ) ∥ Π h ( I − G h ) Π h ∥ HS 2 , (63) E U , x Var ( f ^ h ) ≤ C h W h ( k ) . (64) \mathbb{E}_{U,x}\operatorname{Var}(\hat{f}_h)\le C_hW_h(k). \tag*{(64)} E U , x Var ( f ^ h ) ≤ C h W h ( k ) . (64) The inner expectation and variance are over the random weights.
Proof. For any fixed matrix Y Y Y , Eqs. (C.8) and (C.9) give
E U , x ∣ λ h − 1 ⟨ v x , Y ψ h ⟩ ∣ 2 = W h ( k ) Z M , h ∥ Π h Y Π h ∥ H S 2 . \mathbb{E}_{U,x}\left|\lambda_h^{-1}\langle v_x,Y\psi_h\rangle\right|^2=\frac{W_h(k)}{Z_{M,h}}\lVert\Pi_hY\Pi_h\rVert_{\mathrm{HS}}^2. E U , x λ h − 1 ⟨ v x , Y ψ h ⟩ 2 = Z M , h W h ( k ) ∥ Π h Y Π h ∥ HS 2 .
Setting Y = I − G h Y=I-G_h Y = I − G h proves the bias identity. Setting Y = M h − G h Y=M_h-G_h Y = M h − G h and averaging over M h M_h M h gives the variance. The bound follows from ∥ Π h Y Π h ∥ H S 2 ≤ Tr ( Π h Y 2 Π h ) \lVert\Pi_hY\Pi_h\rVert_{\mathrm{HS}}^2\le\operatorname{Tr}(\Pi_hY^2\Pi_h) ∥ Π h Y Π h ∥ HS 2 ≤ Tr ( Π h Y 2 Π h ) for Hermitian Y Y Y , the assumed second moment of M h − G h M_h-G_h M h − G h , and Tr Π h = Z M , h \operatorname{Tr}\Pi_h=Z_{M,h} Tr Π h = Z M , h .
For Fock state boson sampling we will also need a bound on E ∣ f ^ h ∣ 2 \mathbb{E}|\hat{f}_h|^2 E ∣ f ^ h ∣ 2 . The same proof, with Y = M h Y=M_h Y = M h , gives E U , x , M h ∣ f ^ h ∣ 2 ≤ C h ′ W h ( k ) \mathbb{E}_{U,x,M_h}|\hat{f}_h|^2\le C'_hW_h(k) E U , x , M h ∣ f ^ h ∣ 2 ≤ C h ′ W h ( k ) whenever E M h 2 ≤ C h ′ G h \mathbb{E}M_h^2\le C'_hG_h E M h 2 ≤ C h ′ G h .
For the weights from random grouping, each eligible configuration has weight 1 / p h − ν 1/p_{h-\nu} 1/ p h − ν with probability p h − ν p_{h-\nu} p h − ν and zero otherwise. Its variance is p h − ν − 1 − 1 ≤ e h p_{h-\nu}^{-1}-1 \le e^h p h − ν − 1 − 1 ≤ e h , so
E ( M h − G h ) 2 ≤ e h G h . (65) \mathbb{E}(M_h-G_h)^2 \le e^hG_h. \tag*{(65)} E ( M h − G h ) 2 ≤ e h G h . (65)
Thus Lemma 1 bounds the variance averaged over U , x U,x U , x by e h W h ( k ) e^hW_h(k) e h W h ( k ) . The bound also holds when selection events for distinct supports are correlated.
To bound the bias, use ∥ Π h ( I − G h ) Π h ∥ H S 2 ≤ rank ( I − G h ) \lVert\Pi_h(I-G_h)\Pi_h\rVert_{\mathrm{HS}}^2 \le\operatorname{rank}(I-G_h) ∥ Π h ( I − G h ) Π h ∥ HS 2 ≤ rank ( I − G h ) in Eq. (C.11). It remains to count the omitted auxiliary configurations. Applying the insertion rule from the direct reconstruction to the empty configuration h h h times generates a uniform h h h -photon configuration. At step j + 1 j+1 j + 1 , the probability of reusing an occupied mode is at most 2 j / M 2j/M 2 j / M . A union bound over b b b reuse times yields
rank ( I − G h ) Z M , h ≤ M + h − 1 M − 1 min { 1 , [ h ( h − 1 ) / M ] b b ! } . (66) \frac{\operatorname{rank}(I-G_h)}{Z_{M,h}} \le\frac{M+h-1}{M-1}\min\left\{1,\frac{[h(h-1)/M]^b}{b!}\right\}. \tag*{(66)} Z M , h rank ( I − G h ) ≤ M − 1 M + h − 1 min { 1 , b ! [ h ( h − 1 ) / M ] b } . (66)
Together, Eqs. (C.13) and (C.14) control the variance from random grouping and the bias from the auxiliary cutoff.
Computing the random sum
We now give an explicit procedure for evaluating f ^ h \hat{f}_h f ^ h for a supplied interferometer U U U , proposed output x x x , and fixed random groups. We first combine the projected weights into a sum of photon count moments. This sum is then evaluated with a generating function for each input family. Throughout this calculation, V V V denotes the columns of U U U corresponding to the nonvacuum input modes.
Combining the photon count moments
Consider first an auxiliary configuration with one photon in each mode of a set S S S , where ∣ S ∣ = h |S|=h ∣ S ∣ = h . Its contribution is the product of the weight v x ( S ) v_x(S) v x ( S ) of the proposed configuration and the projected output weight ψ h ( S ) \psi_h(S) ψ h ( S ) . To express both factors in terms of moments, let κ 0 , … , κ h \kappa_0,\ldots,\kappa_h κ 0 , … , κ h solve
∑ r = j h κ r λ r , j ( h ) = 1 { j = h } , (67) \sum_{r=j}^{h}\kappa_r\lambda_{r,j}^{(h)}=\mathbf{1}_{\{j=h\}}, \tag*{(67)} r = j ∑ h κ r λ r , j ( h ) = 1 { j = h } , (67)
so that Π h = ∑ r κ r T h , r \Pi_h=\sum_r\kappa_rT_{h,r} Π h = ∑ r κ r T h , r removes all orders below h h h . Applying this projector to the two factors in Eq. (C.4) gives
v x ( S ) = ∑ ℓ = 0 h α ℓ e ℓ ( x S ) , ψ h ( S ) = ∑ r = 0 h β r ∑ S ′ ⊆ S ∣ S ′ ∣ = r ⟨ ∏ i ∈ S ′ n i ⟩ N , (68) v_x(S)=\sum_{\ell=0}^{h}\alpha_\ell e_\ell(x_S),\qquad\psi_h(S)=\sum_{r=0}^{h}\beta_r\sum_{\substack{S'\subseteq S\\ |S'|=r}}\left\langle\prod_{i\in S'}n_i\right\rangle_N, \tag*{(68)} v x ( S ) = ℓ = 0 ∑ h α ℓ e ℓ ( x S ) , ψ h ( S ) = r = 0 ∑ h β r S ′ ⊆ S ∣ S ′ ∣ = r ∑ ⟨ i ∈ S ′ ∏ n i ⟩ N , (68)
where
α ℓ = κ ℓ D ℓ ( h ℓ ) ( k ℓ ) , β r = κ r D r ( h r ) ( N r ) . (69) \alpha_\ell=\frac{\kappa_\ell D_\ell}{\binom{h}{\ell}\binom{k}{\ell}},\qquad\beta_r=\frac{\kappa_rD_r}{\binom{h}{r}\binom{N}{r}}. \tag*{(69)} α ℓ = ( ℓ h ) ( ℓ k ) κ ℓ D ℓ , β r = ( r h ) ( r N ) κ r D r . (69)
Here e ℓ ( x S ) e_\ell(x_S) e ℓ ( x S ) sums products of ℓ \ell ℓ distinct occupations in S S S , n i n_i n i is the photon count in output mode i i i before loss, and ⟨ ⋅ ⟩ N \langle\cdot\rangle_N ⟨ ⋅ ⟩ N is its expectation at fixed total photon number N N N .
The sum of v x ( S ) ψ h ( S ) v_x(S)\psi_h(S) v x ( S ) ψ h ( S ) over all sets S S S with one mode from each group can now be assembled from one polynomial,
⟨ ∏ c = 1 h [ ∑ i : c ( i ) = c ( 1 + z x i ) ( 1 + w n i ) ] ⟩ N . (70) \left\langle\prod_{c=1}^{h}\left[\sum_{i:c(i)=c}(1+zx_i)(1+wn_i)\right]\right\rangle_N . \tag*{(70)} ⟨ c = 1 ∏ h i : c ( i ) = c ∑ ( 1 + z x i ) ( 1 + w n i ) ⟩ N . (70)
Each factor contributes one mode from a group. The powers of z z z and w w w count the occupations selected from x x x and from the optical output, respectively. Multiply the coefficient of z ℓ w r z^\ell w^r z ℓ w r by α ℓ β r \alpha_\ell\beta_r α ℓ β r and sum over ℓ , r \ell,r ℓ , r . Dividing the result by λ h D h p h \lambda_hD_hp_h λ h D h p h gives the contribution of these configurations with distinct modes to f ^ h \hat f_h f ^ h .
To compute the moments in Eq. (C.18), use the output generating function Φ ( Ξ ) = ⟨ ∏ i ξ i n i ⟩ N \Phi(\Xi)=\left\langle\prod_i\xi_i^{n_i}\right\rangle_N Φ ( Ξ ) = ⟨ ∏ i ξ i n i ⟩ N , with one variable ξ i \xi_i ξ i for each output mode, collected in Ξ = diag ( ξ 1 , … , ξ M ) \Xi=\operatorname{diag}(\xi_1,\ldots,\xi_M) Ξ = diag ( ξ 1 , … , ξ M ) . Introduce one commuting bookkeeping variable ω c \omega_c ω c for each group, with ω c 2 = 0 \omega_c^2=0 ω c 2 = 0 , and substitute ξ i = 1 + ω c ( i ) ( 1 + z x i ) \xi_i=1+\omega_{c(i)}(1+zx_i) ξ i = 1 + ω c ( i ) ( 1 + z x i ) . A term that uses a group twice vanishes, so only 2 h 2^h 2 h products of the group variables remain. For each subset R R R of group indices, the coefficient of ω R = ∏ c ∈ R ω c \omega_R=\prod_{c\in R}\omega_c ω R = ∏ c ∈ R ω c sums the moments involving one mode from each group in R R R , including their factors ( 1 + z x i ) (1+zx_i) ( 1 + z x i ) . Multiply this coefficient by ∏ c ∉ R ∑ i : c ( i ) = c ( 1 + z x i ) \prod_{c\notin R}\sum_{i:c(i)=c}(1+zx_i) ∏ c ∈ / R ∑ i : c ( i ) = c ( 1 + z x i ) to include the other groups. Weight its z ℓ z^\ell z ℓ coefficient by α ℓ β ∣ R ∣ \alpha_\ell\beta_{\lvert R\rvert} α ℓ β ∣ R ∣ and sum over ℓ , R \ell,R ℓ , R . The determinant formulas below provide Φ ( Ξ ) \Phi(\Xi) Φ ( Ξ ) for each input family.
For configurations with repeated occupations, the corresponding projection formulas are
v x ( y ) = ∑ ℓ = 0 h α ℓ ∑ μ ≤ y ∣ μ ∣ = ℓ ( y μ ) , ψ h ( y ) = ∑ r = 0 h β r ∑ μ ′ ≤ y ∣ μ ′ ∣ = r ( y μ ′ ) E N ( n ^ μ ′ ) . (71) v_x(y)=\sum_{\ell=0}^{h}\alpha_\ell\sum_{\substack{\mu\leq y\\\lvert\mu\rvert=\ell}}\binom{y}{\mu},\qquad
\psi_h(y)=\sum_{r=0}^{h}\beta_r\sum_{\substack{\mu'\leq y\\\lvert\mu'\rvert=r}}\binom{y}{\mu'}\mathbb{E}_N\binom{\hat n}{\mu'} . \tag*{(71)} v x ( y ) = ℓ = 0 ∑ h α ℓ μ ≤ y ∣ μ ∣ = ℓ ∑ ( μ y ) , ψ h ( y ) = r = 0 ∑ h β r μ ′ ≤ y ∣ μ ′ ∣ = r ∑ ( μ ′ y ) E N ( μ ′ n ^ ) . (71)
where n ^ = ( n 1 , … , n M ) \hat n=(n_1,\ldots,n_M) n ^ = ( n 1 , … , n M ) and multiindex binomials denote products over modes. These binomial moments are the coefficients of Φ ( Ξ ) \Phi(\Xi) Φ ( Ξ ) expanded about ξ i = 1 \xi_i=1 ξ i = 1 .
For each ν < b \nu<b ν < b , explicitly sum over the mode labels with occupations greater than one and their multiplicities m i = ν i + 1 ≥ 2 m_i=\nu_i+1\geq2 m i = ν i + 1 ≥ 2 , with ∑ i ν i = ν \sum_i\nu_i=\nu ∑ i ν i = ν . Use h − ν h-\nu h − ν groups and omit a choice if two of these modes belong to the same group. Each repeated mode is assigned its own variable, with powers above m i m_i m i discarded. Multiply its moment coefficient of degree μ i ′ \mu'_i μ i ′ by ( m i μ i ′ ) \binom{m_i}{\mu'_i} ( μ i ′ m i ) , and use ∑ μ = 0 m i ( m i μ ) ( x i ) μ z μ \sum_{\mu=0}^{m_i}\binom{m_i}{\mu}(x_i)^\mu z^\mu ∑ μ = 0 m i ( μ m i ) ( x i ) μ z μ for the factor of the proposed configuration. The modes occupied once are summed over the unused groups as above. The variables for repeated modes require at most ∏ i ( ν i + 2 ) ≤ 3 ν \prod_i(\nu_i+2)\leq3^\nu ∏ i ( ν i + 2 ) ≤ 3 ν coefficients. Section C 3 b bounds the number of explicit choices of mode labels and multiplicities. Each grouped contribution is divided by λ h D h p h − ν \lambda_hD_hp_{h-\nu} λ h D h p h − ν , as prescribed by Eq. (C.7).
Fock state boson sampling
For Fock state boson sampling, the reduced input γ h \gamma_h γ h is a uniform mixture over h h h -element subsets of the n n n occupied inputs. To compute its generating function, divide the occupied inputs into h h h random groups independently of the output grouping. Let d ( a ) d(a) d ( a ) be the group index of occupied input a a a , chosen independently and uniformly from 1 , … , h 1,\ldots,h 1 , … , h , and form
γ h , d = 1 ( n h ) p h ∑ S ⊆ [ n ] , ∣ S ∣ = h one input per group ∣ 1 S ⟩ ⟨ 1 S ∣ . (72) \gamma_{h,d}=\frac{1}{\binom{n}{h}p_h}\sum_{\substack{S\subseteq[n],\ \lvert S\rvert=h\\\text{one input per group}}}\lvert1_S\rangle\langle1_S\rvert. \tag*{(72)} γ h , d = ( h n ) p h 1 S ⊆ [ n ] , ∣ S ∣ = h one input per group ∑ ∣ 1 S ⟩ ⟨ 1 S ∣ . (72)
Each subset is selected with probability p h p_h p h , so averaging over the input groups restores γ h \gamma_h γ h . Orthogonality of the Fock states also gives
E d γ h , d = γ h , E d Tr γ h , d 2 = 1 p h ( n h ) . (73) \mathbb{E}_d\gamma_{h,d}=\gamma_h,\qquad\mathbb{E}_d\operatorname{Tr}\gamma_{h,d}^{2}=\frac{1}{p_h\binom{n}{h}} . \tag*{(73)} E d γ h , d = γ h , E d Tr γ h , d 2 = p h ( h n ) 1 . (73)
The number of selected subsets fluctuates with the grouping, so Tr γ h , d \operatorname{Tr}\gamma_{h,d} Tr γ h , d equals one only on average. We therefore keep γ h , d \gamma_{h,d} γ h , d unnormalized, since dividing each realization by its trace would bias the average and break the first identity in Eq. (C.21).
For single-photon inputs, V V V has n n n columns. Introduce input group variables t j t_j t j with t j 2 = 0 t_j^2=0 t j 2 = 0 , independent of the output variables ω c \omega_c ω c . With Θ d = diag ( t d ( 1 ) , … , t d ( n ) ) \Theta_d=\operatorname{diag}(t_{d(1)},\ldots,t_{d(n)}) Θ d = diag ( t d ( 1 ) , … , t d ( n ) ) , the output generating function of γ h , d \gamma_{h,d} γ h , d , in the output variables Ξ \Xi Ξ of Sec. C 2 a, is
Φ h , d ( Ξ ) = [ t 1 ⋯ t h ] det ( I − Θ d V † Ξ V ) − 1 ( n h ) P h . (74) \Phi_{h,d}(\Xi)=\frac{[t_1\cdots t_h]\det(I-\Theta_dV^\dagger\Xi V)^{-1}}{\binom{n}{h}P_h}. \tag*{(74)} Φ h , d ( Ξ ) = ( h n ) P h [ t 1 ⋯ t h ] det ( I − Θ d V † Ξ V ) − 1 . (74)
The coefficient notation [ t 1 ⋯ t h ] [t_1\cdots t_h] [ t 1 ⋯ t h ] selects one variable from each input group. By MacMahon’s master theorem [28 ] , this coefficient sums the permanents of the S × S S\times S S × S submatrices of V † Ξ V V^\dagger\Xi V V † Ξ V over subsets S S S containing one input from each group, exactly the weighted output sums of their Fock states. Thus a single evaluation of Eq. (C.22) accounts for all selected input subsets together.
Substituting the output weights from the preceding subsection supplies the moments needed for f ^ h \widehat{f}_h f h . Because γ h , d \gamma_{h,d} γ h , d already contains h h h photons, the source coefficients β r \beta_r β r in this step use N = h N=h N = h . The input and output group variables, the variables for repeated modes, and the powers of z z z require 2 O ( h + ν ) poly ( h ) 2^{O(h+\nu)}\operatorname{poly}(h) 2 O ( h + ν ) poly ( h ) coefficients. The inverse determinant is evaluated by the finite expansion exp [ ∑ j = 1 h Tr ( ( Θ d V † Ξ V ) j ) / j ] \exp\left[\sum_{j=1}^{h}\operatorname{Tr}\left((\Theta_dV^\dagger\Xi V)^j\right)/j\right] exp [ ∑ j = 1 h Tr ( ( Θ d V † Ξ V ) j ) / j ] , with terms that use a group twice discarded. The cost for each fixed choice of repeated modes and their occupations is therefore poly ( M , n , h ) 2 O ( h + ν ) \operatorname{poly}(M,n,h)2^{O(h+\nu)} poly ( M , n , h ) 2 O ( h + ν ) .
It remains to control the extra randomness from grouping the inputs. The second moment argument following Lemma 1 applies to any positive operator X X X on the h h h -photon space, with arbitrary trace. Substitute the rescaled output weights D h ⟨ y ∣ U h X U h † ∣ y ⟩ D_h\langle y|U_hXU_h^\dagger|y\rangle D h ⟨ y ∣ U h X U h † ∣ y ⟩ into that argument. Equations (C.10) and (C.5) give the mean squared reconstructed contribution
W h ( X ) = D h Z M , h R M , h λ h ∥ P h o p X ∥ H S 2 . (75) \mathcal{W}_h(X)=\frac{D_hZ_{M,h}}{R_{M,h}\lambda_h}\left\|P_h^{\mathrm{op}}X\right\|_{\mathrm{HS}}^2. \tag*{(75)} W h ( X ) = R M , h λ h D h Z M , h ∥ P h op X ∥ HS 2 . (75)
The prefactor obeys
D h Z M , h R M , h λ h = ( k h ) M + h − 1 M + 2 h − 1 ( M + 2 h − 1 ) ! ( M + k − 1 ) ! ( M + h − 1 ) ! ( M + k + h − 1 ) ! ≤ ( k h ) , (76) \frac{D_hZ_{M,h}}{R_{M,h}\lambda_h}
=\binom{k}{h}\frac{M+h-1}{M+2h-1}\frac{(M+2h-1)!(M+k-1)!}{(M+h-1)!(M+k+h-1)!}
\le\binom{k}{h}, \tag*{(76)} R M , h λ h D h Z M , h = ( h k ) M + 2 h − 1 M + h − 1 ( M + h − 1 )! ( M + k + h − 1 )! ( M + 2 h − 1 )! ( M + k − 1 )! ≤ ( h k ) , (76)
and orthogonal projection gives W h ( X ) ≤ ( k h ) Tr X 2 \mathcal{W}_h(X)\le\binom{k}{h}\operatorname{Tr}X^2 W h ( X ) ≤ ( h k ) Tr X 2 . The independent output grouping contributes a factor at most e h e^h e h to E ∣ f ^ h ∣ 2 \mathbb{E}|\widehat{f}_h|^2 E ∣ f h ∣ 2 . Setting X = γ h , d X=\gamma_{h,d} X = γ h , d and averaging with Eq. (C.21), using p h − 1 ≤ e h p_h^{-1}\le e^h p h − 1 ≤ e h , yields
E U , x , c , d ∣ f ^ h ∣ 2 ≤ e 2 h ( k h ) ( n h ) . (77) \mathbb{E}_{U,x,c,d}|\widehat{f}_h|^2\le e^{2h}\frac{\binom{k}{h}}{\binom{n}{h}}. \tag*{(77)} E U , x , c , d ∣ f h ∣ 2 ≤ e 2 h ( h n ) ( h k ) . (77)
The same bound holds for empty input groups and groups of unequal size. Since the input average is exact, the only bias remains the omission of auxiliary output configurations with ν ( y ) ≥ b \nu(y)\ge b ν ( y ) ≥ b . For each correlation order and each proposed output, the input and output groups are drawn anew, independently of each other and of all other draws. This independence makes the variances of different orders add, as used in Sec. C 3 a.
Gaussian boson sampling
For Gaussian boson sampling, the output generating function is available directly as a determinant [29 ] . A pure Gaussian output state with no displacement has the form [19 ]
∣ ψ B ⟩ = N B exp ( 1 2 ∑ i , j = 1 M B i j a i † a j † ) ∣ 0 ⟩ |\psi_B\rangle=\mathcal{N}_B\exp\left(\frac{1}{2}\sum_{i,j=1}^{M}B_{ij}a_i^\dagger a_j^\dagger\right)|0\rangle ∣ ψ B ⟩ = N B exp ( 2 1 i , j = 1 ∑ M B ij a i † a j † ) ∣0 ⟩
where a i † a_i^\dagger a i † creates a photon in output mode i i i and N B N_B N B normalizes the state. The matrix B B B of pair creation coefficients is complex symmetric, B T = B B^{\mathsf{T}}=B B T = B . For s s s equally squeezed inputs, V V V has s s s columns and B = ( tanh r ) H B=(\tanh r)H B = ( tanh r ) H , with H = V V T H=VV^{\mathsf{T}} H = V V T . In particular, H = U U T H=UU^{\mathsf{T}} H = U U T when all inputs are squeezed.
To condition this state on N N N photons, extract the coefficient of q N / 2 q^{N/2} q N /2 from its counting determinant and divide by the same coefficient at Ξ = I \Xi=I Ξ = I . Writing [ q m ] f [q^m]f [ q m ] f for the coefficient of q m q^m q m in f f f , the resulting output generating function is
Φ ( Ξ ) = [ q N / 2 ] det ( I − q B † Ξ B Ξ ) − 1 / 2 Z N , Z N = [ q N / 2 ] det ( I − q B † B ) − 1 / 2 . (78) \Phi(\Xi)=\frac{[q^{N/2}]\det(I-qB^\dagger\Xi B\Xi)^{-1/2}}{\mathcal{Z}_N},\qquad\mathcal{Z}_N=[q^{N/2}]\det(I-qB^\dagger B)^{-1/2}. \tag*{(78)} Φ ( Ξ ) = Z N [ q N /2 ] det ( I − q B † Ξ B Ξ ) − 1/2 , Z N = [ q N /2 ] det ( I − q B † B ) − 1/2 . (78)
This is the function required in the common construction above. Substituting the group variables and combining the coefficients as in Eq. (C.18) evaluates the grouped moments. The common squeezing scale cancels between the numerator and denominator at fixed N N N , so the calculation may use H H H in place of B B B .
The determinant can be computed as a finite series. Write det ( I − q B † Ξ B Ξ ) − 1 / 2 = ∑ j ≥ 0 g j q j \det(I-qB^\dagger\Xi B\Xi)^{-1/2}=\sum_{j\geq0}g_jq^j det ( I − q B † Ξ B Ξ ) − 1/2 = ∑ j ≥ 0 g j q j . Its coefficients satisfy
g 0 = 1 , g j = 1 2 j ∑ ℓ = 1 j Tr [ ( B † Ξ B Ξ ) ℓ ] g j − ℓ . (79) g_0=1,\qquad g_j=\frac{1}{2j}\sum_{\ell=1}^{j}\operatorname{Tr}\left[(B^\dagger\Xi B\Xi)^\ell\right]g_{j-\ell}. \tag*{(79)} g 0 = 1 , g j = 2 j 1 ℓ = 1 ∑ j Tr [ ( B † Ξ B Ξ ) ℓ ] g j − ℓ . (79)
Only j ≤ N / 2 j\leq N/2 j ≤ N /2 is needed. Before including q q q , the group variables and z z z require O ( 2 h ( h + 1 ) ) O(2^h(h+1)) O ( 2 h ( h + 1 )) coefficients. Multiplying them costs O ( 3 h poly ( h ) ) O(3^h\operatorname{poly}(h)) O ( 3 h poly ( h )) operations because only disjoint subsets of groups contribute. The cost is therefore poly ( M , N , h ) 2 O ( h ) \operatorname{poly}(M,N,h)2^{O(h)} poly ( M , N , h ) 2 O ( h ) for distinct auxiliary modes. Including variables for repeated modes gives poly ( M , N , h ) 2 O ( h + ν ) \operatorname{poly}(M,N,h)2^{O(h+\nu)} poly ( M , N , h ) 2 O ( h + ν ) for each fixed choice of repeated modes and their occupations, as in the single-photon calculation.
Evaluation at the requested accuracy
We now combine the estimates at different correlation orders and choose the auxiliary cutoff b b b . The goal is to keep the bias from omitted auxiliary configurations at most ϵ / 16 \epsilon/16 ϵ /16 , its share of the total error budget in Appendix D, with evaluation cost polynomial in the system size and 1 / ϵ 1/\epsilon 1/ ϵ .
Combining the correlation orders
Using independent random groups at different orders, form F ^ = 1 + ∑ h = 1 min { L , k } f ^ h \widehat{F}=1+\sum_{h=1}^{\min\{L,k\}}\widehat{f}_h F = 1 + ∑ h = 1 m i n { L , k } f h as the estimate of F U ≤ L ( x ) F_U^{\leq L}(x) F U ≤ L ( x ) . We control both the bias caused by omitting auxiliary configurations with ν ( y ) ≥ b \nu(y)\geq b ν ( y ) ≥ b and the variance from random grouping. The truncation of correlation orders above L L L is a separate error, already bounded in Appendix B.
The bounds below average over the photon sectors in which the estimator is used, each weighted by its original probability. For h ≥ 0 h\geq0 h ≥ 0 , let H h H_h H h be the resulting average of W h ( k ) W_h(k) W h ( k ) , with W 0 ( k ) = 1 W_0(k)=1 W 0 ( k ) = 1 and W h ( k ) = 0 W_h(k)=0 W h ( k ) = 0 for h > k h>k h > k , so that H 0 H_0 H 0 is the total probability of these sectors. We fix a constant C 2 ≥ max { 1 , ∑ h ≥ 0 H h } C_2\geq\max\{1,\sum_{h\geq0}H_h\} C 2 ≥ max { 1 , ∑ h ≥ 0 H h } , which bounds the averaged second moment of F U F_U F U , and write S L = ∑ h > L H h S_L=\sum_{h>L}H_h S L = ∑ h > L H h for the correlation tail. Averages below are taken over Haar random U U U , the photon sectors and the uniform proposal x x x within each sector. By orthogonality, S L S_L S L is then the mean squared error from omitting orders above L L L . Finally, let B a u x B_{\mathrm{aux}} B aux be the root mean squared bias of F ^ \widehat{F} F relative to F U ≤ L F_U^{\leq L} F U ≤ L , and let V L V_L V L be its variance over the random groups, written V L F V_L^F V L F and V L G V_L^G V L G for the two input families.
At each order h h h , the bias E f ^ h − f h \mathbb{E}\widehat{f}_h-f_h E f h − f h is a function of x x x of correlation order h h h , because v x v_x v x is the order h h h part of w x w_x w x . Biases at distinct orders are therefore orthogonal under the uniform average over x x x . Their squared norms add, and Eq. (C.14) gives
B a u x 2 ≤ ∑ h = 1 L H h M + h − 1 M − 1 min { 1 , [ h ( h − 1 ) / M ] b b ! } . (80) B_{\mathrm{aux}}^2 \le\sum_{h=1}^{L} H_h \frac{M+h-1}{M-1} \min\left\{1,\frac{\left[h(h-1)/M\right]^b}{b!}\right\}. \tag*{(80)} B aux 2 ≤ h = 1 ∑ L H h M − 1 M + h − 1 min { 1 , b ! [ h ( h − 1 ) / M ] b } . (80)
Independence of the groups at different orders makes the conditional variances add as well. For Gaussian boson sampling, the bound e h W h ( k ) e^h W_h(k) e h W h ( k ) at order h h h yields
V L G ≤ e L C 2 . (81) V_L^{\mathrm{G}} \le e^L C_2. \tag*{(81)} V L G ≤ e L C 2 . (81)
For Fock state boson sampling, grouping the inputs introduces the additional factor in Eq. (C.25). Since k ∼ Bin ( n , η ) k \sim\operatorname{Bin}(n,\eta) k ∼ Bin ( n , η ) and E k ( h ) = ( n h ) η h \mathbb{E}_k^{(h)} = \binom{n}{h}\eta^h E k ( h ) = ( h n ) η h , summing over orders gives
V L F ≤ ∑ h = 1 L e 2 h η h ≤ e 2 L 1 − η . (82) V_L^{\mathrm{F}} \le\sum_{h=1}^{L} e^{2h}\eta^h \le\frac{e^{2L}}{1-\eta}. \tag*{(82)} V L F ≤ h = 1 ∑ L e 2 h η h ≤ 1 − η e 2 L . (82)
Counting the modes with repeated occupations
The explicit sum over repeated occupations in Sec. C 2 runs over choices of which modes have occupations greater than one and what those occupations are. At order h h h , one such choice consists of distinct labels i 1 < ⋯ < i j i_1 < \cdots< i_j i 1 < ⋯ < i j and occupations ν 1 + 1 , … , ν j + 1 ≥ 2 \nu_1 + 1,\ldots,\nu_j + 1 \ge2 ν 1 + 1 , … , ν j + 1 ≥ 2 , with ∑ a ν a = ν \sum_a \nu_a = \nu ∑ a ν a = ν . This choice uses j + ν j+\nu j + ν photons. The remaining h − j − ν h-j-\nu h − j − ν photons occupy distinct modes and are handled by the grouped sum.
For ν ≥ 1 \nu\ge1 ν ≥ 1 , there are ( M j ) \binom{M}{j} ( j M ) ways to choose the j j j labels and ( ν − 1 j − 1 ) \binom{\nu-1}{j-1} ( j − 1 ν − 1 ) ways to distribute ν \nu ν extra photons among them, with at least one extra photon per mode. Ignoring the restriction j + ν ≤ h j+\nu\le h j + ν ≤ h gives the upper bound
∑ j = 1 min ( M , ν ) ( M j ) ( ν − 1 j − 1 ) = ( M + ν − 1 ν ) . (83) \sum_{j=1}^{\min(M,\nu)} \binom{M}{j}\binom{\nu-1}{j-1} = \binom{M+\nu-1}{\nu}. \tag*{(83)} j = 1 ∑ m i n ( M , ν ) ( j M ) ( j − 1 ν − 1 ) = ( ν M + ν − 1 ) . (83)
There is one empty choice at ν = 0 \nu=0 ν = 0 . Let K b K_b K b count the choices with ν < b \nu<b ν < b at the largest order L L L . This also bounds their number at every h ≤ L h\le L h ≤ L . Summing Eq. (C.31), including ν = 0 \nu=0 ν = 0 , gives
K b ≤ ( M + b − 1 b − 1 ) . (84) K_b \le\binom{M+b-1}{b-1}. \tag*{(84)} K b ≤ ( b − 1 M + b − 1 ) . (84)
Since ν ≤ L − 1 \nu\le L-1 ν ≤ L − 1 , the sum can always be stopped at min { b − 1 , L − 1 } \min\{b-1,L-1\} min { b − 1 , L − 1 } .
For each such choice, the calculation of Sec. C 2 uses h − ν h-\nu h − ν group variables and a variable of degree at most ν a + 1 \nu_a+1 ν a + 1 for each repeated mode. Including the powers of z z z , the number of coefficients is at most
2 h − ν ∏ a ( ν a + 2 ) poly ( h ) ≤ 2 h 3 ν poly ( h ) . (85) 2^{h-\nu}\prod_a(\nu_a+2)\operatorname{poly}(h) \le2^{h}3^\nu\operatorname{poly}(h). \tag*{(85)} 2 h − ν a ∏ ( ν a + 2 ) poly ( h ) ≤ 2 h 3 ν poly ( h ) . (85)
For Fock state boson sampling, the input groups add at most 2 h 2^h 2 h products of variables. The cost per choice is therefore polynomial in M M M , N N N , h h h and exponential in h + ν h+\nu h + ν . To bound the full cost, it remains to control K b K_b K b while making the omission bias small.
Choosing the auxiliary cutoff
If L = 0 L = 0 L = 0 , the estimator is F ^ = 1 \widehat{F} = 1 F = 1 , with zero auxiliary bias and variance and no auxiliary enumeration. For L ≥ 1 L \ge1 L ≥ 1 , increasing b b b reduces the bias in Eq. (C.28) and raises the number K b K_b K b of explicit choices. We balance these two effects through the scale
L e f f = L + 1 + ⌈ log 2 40 ( 1 + C 2 ) ϵ ⌉ . (86) L_{\mathrm{eff}} = L + 1 + \left\lceil\log_2 \frac{40(1+C_2)}{\epsilon} \right\rceil. \tag*{(86)} L eff = L + 1 + ⌈ log 2 ϵ 40 ( 1 + C 2 ) ⌉ . (86)
We will keep K b = 2 O ( L e f f ) K_b = 2^{O(L_{\mathrm{eff}})} K b = 2 O ( L eff ) , which is polynomial in 1 / ϵ 1/\epsilon 1/ ϵ when C 2 = O ( 1 ) C_2 = O(1) C 2 = O ( 1 ) and L = O ( 1 + log ( 1 / ϵ ) ) L = O(1+\log(1/\epsilon)) L = O ( 1 + log ( 1/ ϵ )) .
If M ≤ 64 L e f f M \le64L_{\mathrm{eff}} M ≤ 64 L eff , include every repeated occupation by choosing b = L b = L b = L . Then B a u x = 0 B_{\mathrm{aux}} = 0 B aux = 0 , and Eq. (C.32) gives
K b ≤ ( M + L − 1 L − 1 ) ≤ 2 M + L ≤ 2 65 L e f f . (87) K_b \le\binom{M+L-1}{L-1} \le2^{M+L} \le2^{65L_{\mathrm{eff}}}. \tag*{(87)} K b ≤ ( L − 1 M + L − 1 ) ≤ 2 M + L ≤ 2 65 L eff . (87)
If M > 64 L e f f M > 64L_{\mathrm{eff}} M > 64 L eff , repeated occupations are rare under the uniform distribution of auxiliary configurations. Set d ∗ = ⌊ log 2 ( M / L e f f ) ⌋ ≥ 6 d_* = \left\lfloor\log_2(M/L_{\mathrm{eff}}) \right\rfloor\ge6 d ∗ = ⌊ log 2 ( M / L eff ) ⌋ ≥ 6 and choose b = ⌈ 8 L e f f / d ∗ ⌉ b = \left\lceil8L_{\mathrm{eff}}/d_* \right\rceil b = ⌈ 8 L eff / d ∗ ⌉ . If b ≥ L b \ge L b ≥ L , all configurations are again included. Otherwise, applying the counting bound behind Eq. (C.14) and b ! ≥ ( b / e ) b b! \ge(b/e)^b b ! ≥ ( b / e ) b gives, for each order h ≤ L h \le L h ≤ L ,
Pr U h ( ν ≥ b ) ≤ ( e L 2 M b ) b ≤ ( e d ∗ 8 2 d ∗ ) b ≤ 2 − 4 L e f f . (88) \Pr_{U_h}(\nu\ge b) \le\left(\frac{eL^2}{Mb}\right)^b \le\left(\frac{ed_*}{8\,2^{d_*}}\right)^b \le2^{-4L_{\mathrm{eff}}}. \tag*{(88)} U h Pr ( ν ≥ b ) ≤ ( M b e L 2 ) b ≤ ( 8 2 d ∗ e d ∗ ) b ≤ 2 − 4 L eff . (88)
The middle inequality uses L ≤ L e f f L \le L_{\mathrm{eff}} L ≤ L eff , M ≥ 2 d ∗ L e f f M \ge2^{d_*}L_{\mathrm{eff}} M ≥ 2 d ∗ L eff , and b ≥ 8 L e f f / d ∗ b \ge8L_{\mathrm{eff}}/d_* b ≥ 8 L eff / d ∗ . For the last inequality, d ∗ log 2 − log d ∗ + log 8 − 1 ≥ ( d ∗ / 2 ) log 2 d_* \log2 - \log d_* + \log8 - 1 \ge(d_*/2)\log2 d ∗ log 2 − log d ∗ + log 8 − 1 ≥ ( d ∗ /2 ) log 2 for d ∗ ≥ 6 d_* \ge6 d ∗ ≥ 6 . The remaining prefactor ( M + h − 1 ) / ( M − 1 ) (M+h-1)/(M-1) ( M + h − 1 ) / ( M − 1 ) in Eq. (C.28) is less than two, so
B a u x 2 ≤ 2 C 2 2 − 4 L e f f ≤ ( ϵ / 16 ) 2 . (89) B_{\mathrm{aux}}^2 \le2C_2\,2^{-4L_{\mathrm{eff}}} \le(\epsilon/16)^2. \tag*{(89)} B aux 2 ≤ 2 C 2 2 − 4 L eff ≤ ( ϵ /16 ) 2 . (89)
To bound the cost in the same regime, let ν max = min { b − 1 , L − 1 } < 8 L e f f / d ∗ \nu_{\max} = \min\{b-1,L-1\} < 8L_{\mathrm{eff}}/d_* ν m a x = min { b − 1 , L − 1 } < 8 L eff / d ∗ . If ν max = 0 \nu_{\max} = 0 ν m a x = 0 , there is only the empty choice. Otherwise, the factorial bound used above, M < 2 d ∗ + 1 L e f f M < 2^{d_*+1}L_{\mathrm{eff}} M < 2 d ∗ + 1 L eff , and monotonicity of x log [ e ( M + x ) / x ] x\log[e(M+x)/x] x log [ e ( M + x ) / x ] give
log 2 K b ≤ log 2 ( M + ν max ν max ) ≤ ν max log 2 e ( M + ν max ) ν max ≤ 12 L e f f . (90) \log_2 K_b \le\log_2 \binom{M+\nu_{\max}}{\nu_{\max}} \le\nu_{\max}\log_2\frac{e(M+\nu_{\max})}{\nu_{\max}} \le12L_{\mathrm{eff}}. \tag*{(90)} log 2 K b ≤ log 2 ( ν m a x M + ν m a x ) ≤ ν m a x log 2 ν m a x e ( M + ν m a x ) ≤ 12 L eff . (90)
Hence, for M > 64 L e f f M > 64L_{\mathrm{eff}} M > 64 L eff ,
B a u x ≤ ϵ / 16 , K b ≤ 2 12 L e f f . (91) B_{\mathrm{aux}} \le\epsilon/16,\qquad K_b \le2^{12L_{\mathrm{eff}}}. \tag*{(91)} B aux ≤ ϵ /16 , K b ≤ 2 12 L eff . (91)
Both regimes therefore achieve the required bias with K b = 2 O ( L e f f ) K_b = 2^{O(L_{\mathrm{eff}})} K b = 2 O ( L eff ) . Multiplying by the cost per choice and summing over h ≤ L h \le L h ≤ L gives, for both input families,
T e v a l ≤ poly ( M , N , L ) e O ( L e f f ) , L e f f = O ( L + log ( 1 + C 2 ) + log ( 1 / ϵ ) ) . (92) T_{\mathrm{eval}} \le\operatorname{poly}(M,N,L)e^{O(L_{\mathrm{eff}})},\qquad L_{\mathrm{eff}} = O\bigl(L+\log(1+C_2)+\log(1/\epsilon)\bigr). \tag*{(92)} T eval ≤ poly ( M , N , L ) e O ( L eff ) , L eff = O ( L + log ( 1 + C 2 ) + log ( 1/ ϵ ) ) . (92)
The separate treatment of M ≤ 64 L e f f M \le64L_{\mathrm{eff}} M ≤ 64 L eff makes this bound uniform in the mode count and the requested accuracy.
Construction of the sampler
Appendix B bounds the truncation error, and Appendix C constructs estimators of F U ≤ L ( x ) F_{\mathrm{U}}^{\le L}(x) F U ≤ L ( x ) with controlled error and evaluation cost. We now turn these estimates into the sampling algorithms of Theorems 1 and 2. We average and clip them to obtain acceptance probabilities and bound the number of rejection trials. Bounds on photon number tails and on finite precision complete the error and running time analysis.
Rejection sampling
For a fixed U U U and photon sector, write F = F U F=F_U F = F U and let u u u be the uniform occupation law, so that the target law is p F ( x ) = u ( x ) F ( x ) p_F(x)=u(x)F(x) p F ( x ) = u ( x ) F ( x ) . The truncated expansion and its random estimate can have negative values. To obtain a nonnegative weight with a chosen upper bound A > 0 A>0 A > 0 , we use clipping,
clip [ 0 , A ] ( z ) = min { A , max { 0 , z } } . \operatorname{clip}_{[0,A]}(z)=\min\{A,\max\{0,z\}\}. clip [ 0 , A ] ( z ) = min { A , max { 0 , z }} .
This replaces values below zero by zero and values above A A A by A A A , leaving the others unchanged. Dividing the resulting weight by A A A gives a valid acceptance probability. We use this probability in the standard rejection method [30 ] , with a finite trial cutoff.
To bound the output error, we first fix the acceptance weight.
Lemma 2 (Finite rejection). Let F ≥ 0 F\geq0 F ≥ 0 with E u F = 1 \mathbb{E}_uF=1 E u F = 1 , let 0 ≤ a ≤ A 0\leq a\leq A 0 ≤ a ≤ A be a fixed acceptance weight, and put Δ = E u ∣ a − F ∣ \Delta=\mathbb{E}_u|a-F| Δ = E u ∣ a − F ∣ . Consider the sampler that proposes x ∼ u x\sim u x ∼ u , accepts with probability a ( x ) / A a(x)/A a ( x ) / A , and after J J J rejected trials outputs a fixed configuration with the same total. Its output distribution P J P_J P J obeys
d T V ( P J , p F ) ≤ 2 Δ + A e J . (93) d_{\mathrm{TV}}(P_J,p_F)\leq2\Delta+\frac{A}{eJ}. \tag*{(93)} d TV ( P J , p F ) ≤ 2Δ + e J A . (93) The bound remains valid when the acceptance probability vanishes.
Proof. Let m a = E u a m_a=\mathbb{E}_ua m a = E u a . If m a > 0 m_a>0 m a > 0 , the accepted law is u ( x ) a ( x ) / m a u(x)a(x)/m_a u ( x ) a ( x ) / m a and its distance from p F p_F p F is at most Δ \Delta Δ , since ∣ m a − 1 ∣ ≤ Δ |m_a-1|\leq\Delta ∣ m a − 1∣ ≤ Δ . Failure contributes ( 1 − m a / A ) J (1-m_a/A)^J ( 1 − m a / A ) J . This is at most Δ + m a ( 1 − m a / A ) J \Delta+m_a(1-m_a/A)^J Δ + m a ( 1 − m a / A ) J , and the latter product is bounded by A / ( e J ) A/(eJ) A / ( e J ) . The same bound holds at m a = 0 m_a=0 m a = 0 , when Δ = 1 \Delta=1 Δ = 1 .
For the estimator from Appendix C, let F ^ T ( x ) \widehat{F}_T(x) F T ( x ) be the average of T T T fresh independent copies at the proposed x x x . The sampler accepts with probability clip [ 0 , A ] ( F ^ T ( x ) ) / A \operatorname{clip}_{[0,A]}(\widehat{F}_T(x))/A clip [ 0 , A ] ( F T ( x )) / A . For the error analysis, averaging over the internal estimator randomness gives the weight a ( x ) = E [ clip [ 0 , A ] ( F ^ T ( x ) ) ] a(x)=\mathbb{E}[\operatorname{clip}_{[0,A]}(\widehat{F}_T(x))] a ( x ) = E [ clip [ 0 , A ] ( F T ( x ))] in Lemma 2.
Clipping does not increase distances, ∣ clip [ 0 , A ] ( z ) − clip [ 0 , A ] ( z ′ ) ∣ ≤ ∣ z − z ′ ∣ |\operatorname{clip}_{[0,A]}(z)-\operatorname{clip}_{[0,A]}(z')|\leq|z-z'| ∣ clip [ 0 , A ] ( z ) − clip [ 0 , A ] ( z ′ ) ∣ ≤ ∣ z − z ′ ∣ . Since F ≥ 0 F\geq0 F ≥ 0 , so that clip [ 0 , A ] ( F ) = min { F , A } \operatorname{clip}_{[0,A]}(F)=\min\{F,A\} clip [ 0 , A ] ( F ) = min { F , A } , this implies
∣ clip [ 0 , A ] ( z ) − F ∣ ≤ ∣ z − F ∣ + ( F − A ) + , t + : = max { t , 0 } . |\operatorname{clip}_{[0,A]}(z)-F|\leq|z-F|+(F-A)_+,\qquad t_+:=\max\{t,0\}. ∣ clip [ 0 , A ] ( z ) − F ∣ ≤ ∣ z − F ∣ + ( F − A ) + , t + := max { t , 0 } .
The first term accounts for the approximation error, and the second for the tail removed by the upper bound A A A . To combine photon sectors, first use their original probabilities to form a distribution with the approximate sampler in each sector where it is used and the target law in all other sectors. Its error is bounded by the weighted sector errors. Replacing exceptional sectors by fixed outputs adds at most their total probability, and restricting the photon count distribution adds at most the omitted probability. These contributions form ϵ c o u n t \epsilon_{\mathrm{count}} ϵ count .
For the full output law Q U Q_U Q U , it remains to bound Δ = E u ∣ a − F ∣ \Delta=\mathbb{E}_u|a-F| Δ = E u ∣ a − F ∣ in Lemma 2, averaged as in Sec. C.3a. By the clipping bound and the triangle inequality, Δ \Delta Δ splits into four parts: the truncation error ∣ F − F ^ U L ∣ |F-\widehat{F}^{L}_U| ∣ F − F U L ∣ , the bias of F ^ \widehat{F} F , the fluctuation of F ^ T \widehat{F}_T F T around its mean, and the tail ( F − A ) + (F-A)_+ ( F − A ) + . By the Cauchy–Schwarz inequality, their averages are at most S L \sqrt{S_L} S L , B a u x B_{\mathrm{aux}} B aux , and V L / T \sqrt{V_L/T} V L / T , and ( F − A ) + ≤ F 2 / A (F-A)_+\leq F^2/A ( F − A ) + ≤ F 2 / A bounds the last by C 2 / A C_2/A C 2 / A . Inserting these into Lemma 2 and adding the sector errors gives
E u d T V ( Q U , P U ) ≤ 2 S L + 2 B a u x + 2 V L / T + 2 C 2 A + A e J + ϵ c o u n t + ϵ n u m . (94) \mathbb{E}_u d_{\mathrm{TV}}(Q_U,P_U)\leq2\sqrt{S_L}+2B_{\mathrm{aux}}+2\sqrt{V_L/T}+\frac{2C_2}{A}+\frac{A}{eJ}+\epsilon_{\mathrm{count}}+\epsilon_{\mathrm{num}}. \tag*{(94)} E u d TV ( Q U , P U ) ≤ 2 S L + 2 B aux + 2 V L / T + A 2 C 2 + e J A + ϵ count + ϵ num . (94)
Numerical errors and errors from finite random bits are collected in ϵ n u m \epsilon_{\mathrm{num}} ϵ num and bounded in Sec. D.4.
Choose S L ≤ ϵ / 16 \sqrt{S_L} \le\epsilon/16 S L ≤ ϵ /16 , use the auxiliary cutoff from Sec. C 3c, and take
T ≥ 256 V L / ϵ 2 , A ≥ 16 C 2 / ϵ , J ≥ 16 A / ϵ . (95) T \ge256V_L/\epsilon^2,\quad A \ge16C_2/\epsilon,\quad J \ge16A/\epsilon. \tag*{(95)} T ≥ 256 V L / ϵ 2 , A ≥ 16 C 2 / ϵ , J ≥ 16 A / ϵ . (95)
In the regimes of Theorems 1 and 2, C 2 = O ( 1 ) C_2 = O(1) C 2 = O ( 1 ) and S L S_L S L decays exponentially in L L L . For single-photon inputs, Eq. (B.22) gives S L ≤ ϵ / 16 \sqrt{S_L} \le\epsilon/16 S L ≤ ϵ /16 whenever
L + 1 ≥ log [ 256 / ( ( 1 − η ) ϵ 2 ) ] − log η , (96) L+1 \ge\frac{\log[256/((1-\eta)\epsilon^2)]}{-\log\eta}, \tag*{(96)} L + 1 ≥ − log η log [ 256/ (( 1 − η ) ϵ 2 )] , (96)
and Eq. (B.30) gives the same condition for Gaussian inputs with L = 2 ℓ L=2\ell L = 2 ℓ , ℓ \ell ℓ in place of L L L , and χ ∗ 2 \chi_*^2 χ ∗ 2 in place of η \eta η . In both cases L = O ( 1 + log ( 1 / ϵ ) ) L=O(1+\log(1/\epsilon)) L = O ( 1 + log ( 1/ ϵ )) , with constants that depend on η \eta η and, for the Gaussian theorem, on r r r . By Eqs. (C.40), (C.29), and (C.30), every factor is then polynomial in system size and 1 / ϵ 1/\epsilon 1/ ϵ .
Prefix sampling for small photon sectors
For sectors containing few photons, we evaluate prefix probabilities, the probabilities of the photon counts in the first few output modes, and sample sequentially, following the construction used in exact Gaussian boson sampling algorithms [31 ] . The coefficient calculation below additionally fixes the input photon sector.
Use the matrix B B B of pair creation coefficients introduced in Sec. C 2c. Separate the output modes into the set S S S whose photon counts have been specified and the remaining set R R R , and write
B = ( B S S B S R B S R T B R R ) . (97) B=\begin{pmatrix} B_{SS} & B_{SR} \\ B_{SR}^{T} & B_{RR} \end{pmatrix}. \tag*{(97)} B = ( B S S B S R T B S R B R R ) . (97)
The Bargmann representation [32 ] writes a photon number state ∣ m ⟩ \lvert m\rangle ∣ m ⟩ as t m / m ! t^m/\sqrt{m!} t m / m ! , with one variable per mode. A density operator then becomes a generating function of its photon number matrix elements, called its Bargmann kernel, with separate variables for the ket and bra indices [33 ] . Let u u u and v v v denote these two sets of variables on S S S . Summing over the photon counts in R R R , with a factor z z z for each photon, gives the unnormalized kernel
K z ( u , v ) = Z R ( z ) exp [ 1 2 u T E ( z ) u + u T F ( z ) v + 1 2 v T E ‾ ( z ) v ] , K_z(u,v)=Z_R(z)\exp\left[\frac{1}{2}u^T\mathcal{E}(z)u+u^T\mathcal{F}(z)v+\frac{1}{2}v^T\overline{\mathcal{E}}(z)v\right], K z ( u , v ) = Z R ( z ) exp [ 2 1 u T E ( z ) u + u T F ( z ) v + 2 1 v T E ( z ) v ] ,
where
Z R ( z ) = det ( I − z 2 B R R † B R R ) − 1 / 2 , (98) Z_R(z)=\det\left(I-z^2B_{RR}^{\dagger}B_{RR}\right)^{-1/2}, \tag*{(98)} Z R ( z ) = det ( I − z 2 B R R † B R R ) − 1/2 , (98)
E ( z ) = B S S + z 2 B S R ( I − z 2 B R R † B R R ) − 1 B R R † B S R T , (99) \mathcal{E}(z)=B_{SS}+z^2B_{SR}\left(I-z^2B_{RR}^{\dagger}B_{RR}\right)^{-1}B_{RR}^{\dagger}B_{SR}^{T}, \tag*{(99)} E ( z ) = B S S + z 2 B S R ( I − z 2 B R R † B R R ) − 1 B R R † B S R T , (99)
F ( z ) = z B S R ( I − z 2 B R R † B R R ) − 1 B S R † . (100) \mathcal{F}(z)=zB_{SR}\left(I-z^2B_{RR}^{\dagger}B_{RR}\right)^{-1}B_{SR}^{\dagger}. \tag*{(100)} F ( z ) = z B S R ( I − z 2 B R R † B R R ) − 1 B S R † . (100)
For E ( z ) = ∑ j ≥ 0 E j z j \mathcal{E}(z)=\sum_{j\ge0}\mathcal{E}_jz^j E ( z ) = ∑ j ≥ 0 E j z j , the notation E ‾ ( z ) \overline{\mathcal{E}}(z) E ( z ) means ∑ j ≥ 0 E j z j \sum_{j\ge0}\mathcal{E}_jz^j ∑ j ≥ 0 E j z j . For a configuration x x x on S S S with ∣ x ∣ ≤ N \lvert x\rvert\le N ∣ x ∣ ≤ N , its probability conditioned on N N N total photons is
Pr ( x ∣ N ) = [ z N − ∣ x ∣ ] { Z R ( z ) 1 x ! haf H x ( z ) } Z N , (101) \Pr(x\mid N)=\frac{[z^{N-\lvert x\rvert}]\left\{Z_R(z)\frac{1}{x!}\operatorname{haf}\mathcal{H}_x(z)\right\}}{Z_N}, \tag*{(101)} Pr ( x ∣ N ) = Z N [ z N − ∣ x ∣ ] { Z R ( z ) x ! 1 haf H x ( z ) } , (101)
where
H x ( z ) = ( ( E ( z ) F ( z ) F ( z ) T E ‾ ( z ) ) ) ( x , x ) . (102) \mathcal{H}_x(z)=\left(\begin{pmatrix}\mathcal{E}(z)&\mathcal{F}(z)\\ \mathcal{F}(z)^T&\overline{\mathcal{E}}(z)\end{pmatrix}\right)_{(x,x)}. \tag*{(102)} H x ( z ) = ( ( E ( z ) F ( z ) T F ( z ) E ( z ) ) ) ( x , x ) . (102)
The subscript ( x , x ) (x,x) ( x , x ) repeats the row and column for mode i i i exactly x i x_i x i times in each of the two index sets. To obtain Eq. (D.9), differentiate K z K_z K z exactly x i x_i x i times in each of u i u_i u i and v i v_i v i , and evaluate at u = v = 0 u=v=0 u = v = 0 . These 2 ∣ x ∣ 2|x| 2∣ x ∣ derivatives of a quadratic exponential sum products over all pairings, giving the hafnian of H x ( z ) H_x(z) H x ( z ) . Division by x ! x! x ! accounts for the normalization of the photon number states. Extracting [ z N − ∣ x ∣ ] [z^{N-|x|}] [ z N − ∣ x ∣ ] selects N − ∣ x ∣ N-|x| N − ∣ x ∣ photons in R R R , and division by Z N Z_N Z N normalizes the N N N photon sector.
The hafnian has size 2 ∣ x ∣ ≤ 2 N 2|x|\le2N 2∣ x ∣ ≤ 2 N , and its entries are power series truncated at degree N N N . The hafnian algorithm of Ref. [34 ] applies to such entries. We evaluate it by dynamic programming over subsets and form, from successive prefix probabilities, the finite conditional law of the next count x i x_i x i , which ranges from zero to the number of photons not yet placed. The prefix calculations cost poly ( M , N ) 4 N \operatorname{poly}(M,N)4^N poly ( M , N ) 4 N arithmetic operations per sample. At finite binary matrix inputs, the weights are evaluated by exact rational arithmetic and prefixes of zero probability are omitted. The conditional laws are sampled with finite random bits, with their error allocated to ϵ n u m \epsilon_{\mathrm{num}} ϵ num . After the configuration of all N N N photons is drawn, uniform hypergeometric deletion of N − k N-k N − k photons applies the loss.
Photon number tails at finite dimension
For Gaussian boson sampling, the input photon number N N N takes the values 0 , 2 , 4 , … 0,2,4,\ldots 0 , 2 , 4 , … with the probabilities in Eq. (B.2). We choose a threshold N 0 N_0 N 0 and use prefix sampling for N ≤ N 0 N\le N_0 N ≤ N 0 , applying the correlation approximation to larger sectors where the bounds of Appendix B hold. The bounds below determine N 0 N_0 N 0 and control the probability outside the count region where the approximation is used, uniformly in the number of squeezed inputs.
For s s s equally squeezed modes, write q r = tanh 2 r q_r=\tanh^2r q r = tanh 2 r and c 0 = sinh 2 r c_0=\sinh^2r c 0 = sinh 2 r . The following count estimates hold for every r > 0 r>0 r > 0 and every η \eta η , uniformly in 1 ≤ s ≤ M 1\le s\le M 1 ≤ s ≤ M . Choose constants
c 0 < c 1 < c , η < ϑ < 1. (103) c_0<c_1<c,\qquad\eta<\vartheta<1. \tag*{(103)} c 0 < c 1 < c , η < ϑ < 1. (103)
Choose z > 1 z>1 z > 1 close enough to one that q r z 2 < 1 q_rz^2<1 q r z 2 < 1 and
R r ( z ) : = 1 − q r 1 − q r z 2 ≤ z 2 c 1 . (104) R_r(z):=\frac{1-q_r}{1-q_rz^2}\le z^{2c_1}. \tag*{(104)} R r ( z ) := 1 − q r z 2 1 − q r ≤ z 2 c 1 . (104)
Such a z z z exists because the logarithmic derivative of R r R_r R r at one is 2 c 0 < 2 c 1 2c_0<2c_1 2 c 0 < 2 c 1 . The input law obeys
E z N = R r ( z ) s / 2 ≤ z c 1 s . (105) \mathbb{E}_zN=R_r(z)^{s/2}\le z^{c_1s}. \tag*{(105)} E z N = R r ( z ) s /2 ≤ z c 1 s . (105)
Let α = 1 − c 1 / c > 0 \alpha=1-c_1/c>0 α = 1 − c 1 / c > 0 . Splitting into s ≤ N 0 / c s\le N_0/c s ≤ N 0 / c and s > N 0 / c s>N_0/c s > N 0 / c yields
Pr ( N > N 0 , N > c s ) ≤ z − α N 0 , (106) \Pr(N>N_0,\ N>cs)\le z^{-\alpha N_0}, \tag*{(106)} Pr ( N > N 0 , N > cs ) ≤ z − α N 0 , (106)
Pr ( N > N 0 , k > ϑ N ) ≤ e − 2 ( ϑ − η ) 2 N 0 . (107) \Pr(N>N_0,\ k>\vartheta N)\le e^{-2(\vartheta-\eta)^2N_0}. \tag*{(107)} Pr ( N > N 0 , k > ϑN ) ≤ e − 2 ( ϑ − η ) 2 N 0 . (107)
The second bound follows by applying Hoeffding’s inequality [35 ] to k ∼ Bin ( N , η ) k\sim\operatorname{Bin}(N,\eta) k ∼ Bin ( N , η ) conditional on N N N . Choose even N 0 = O r , η ( 1 + log ( 1 / ϵ ) ) N_0=O_{r,\eta}(1+\log(1/\epsilon)) N 0 = O r , η ( 1 + log ( 1/ ϵ )) so that each bound is at most ϵ / 64 \epsilon/64 ϵ /64 .
To sample from a finite photon number distribution, define N max N_{\max} N m a x as the smallest even integer at least c s + N 0 cs+N_0 cs + N 0 and omit counts above it. The moment bound above gives Pr ( N > N max ) ≤ z c 1 s − N max ≤ z − N 0 \Pr(N>N_{\max})\le z^{c_1s-N_{\max}}\le z^{-N_0} Pr ( N > N m a x ) ≤ z c 1 s − N m a x ≤ z − N 0 .
Generate the input count conditioned on N ≤ N max N\le N_{\max} N ≤ N m a x , followed by the binomial output count. For N ≤ N 0 N\le N_0 N ≤ N 0 , use the prefix sampler of Sec. D.2 and then apply hypergeometric loss. For N > N 0 N>N_0 N > N 0 outside N ≤ c s N\le cs N ≤ cs and k ≤ ϑ N k\le\vartheta N k ≤ ϑN , emit a fixed configuration. For N > N 0 N>N_0 N > N 0 satisfying both bounds, use the sampler of Sec. D.1, whose error obeys Eq. (D.2). As in the mixture argument preceding Eq. (D.2), count truncation contributes at most Pr ( N > N max ) \Pr(N > N_{\max}) Pr ( N > N m a x ) , and exceptional sectors contribute their original probability. Since 0 < α < 1 0 < \alpha< 1 0 < α < 1 , the count tail also obeys z − N 0 ≤ z − α N 0 ≤ ϵ / 64 z^{-N_0} \le z^{-\alpha N_0} \le\epsilon/64 z − N 0 ≤ z − α N 0 ≤ ϵ /64 . Together with Eqs. (D.14) and (D.15), this gives ϵ c o u n t ≤ 3 ϵ / 64 \epsilon_{\mathrm{count}} \le3\epsilon/64 ϵ count ≤ 3 ϵ /64 uniformly in s s s .
With this choice of N 0 N_0 N 0 , the prefix calculations have polynomial cost in M M M and 1 / ϵ 1/\epsilon 1/ ϵ . At fixed r r r , η \eta η , and ϵ \epsilon ϵ , the threshold is independent of M M M .
In Theorem 2, s = M s=M s = M . On N ≤ c M N \le cM N ≤ c M and k ≤ ϑ N k \le\vartheta N k ≤ ϑN , Eqs. (B.30) and (B.31) give the exponentially decaying correlation tail and the bounded second moment required by the approximate sampler, for every choice sinh 2 r < c 1 < c \sinh^2 r < c_1 < c sinh 2 r < c 1 < c and η < ϑ < 1 \eta< \vartheta< 1 η < ϑ < 1 . Together with the count bounds above and prefix sampling for N ≤ N 0 N \le N_0 N ≤ N 0 , this covers every finite M M M at fixed r > 0 r > 0 r > 0 and η \eta η .
To apply the bound of Theorem 2 to every smaller squeezing parameter, write r max r_{\max} r m a x for the squeezing parameter fixed there and choose sinh 2 r max < c 1 < c \sinh^2 r_{\max} < c_1 < c sinh 2 r m a x < c 1 < c . Choose z > 1 z > 1 z > 1 by the preceding argument at r = r max r=r_{\max} r = r m a x . Since R r ( z ) ≤ R r max ( z ) R_r(z) \le R_{r_{\max}}(z) R r ( z ) ≤ R r m a x ( z ) for 0 ≤ r ≤ r max 0 \le r \le r_{\max} 0 ≤ r ≤ r m a x , the same count bounds and threshold N 0 N_0 N 0 hold throughout this interval. The same c c c and η < ϑ < 1 \eta< \vartheta< 1 η < ϑ < 1 give a uniform geometric factor χ ∗ = ϑ ( 1 + c ) / ( 1 + ϑ c ) < 1 \chi_* = \vartheta(1+c)/(1+\vartheta c) < 1 χ ∗ = ϑ ( 1 + c ) / ( 1 + ϑ c ) < 1 in Eqs. (B.30) and (B.31). The sector evaluator is independent of r r r , and Sec. D 4 controls the rounding of r r r . Thus the running time is polynomial with constants depending only on r max r_{\max} r m a x and η \eta η . At r = 0 r=0 r = 0 the output is vacuum.
Finite precision and bit complexity
The theorems count arithmetic operations, and we now show that the same bounds hold in bit complexity. Here the classical input is a matrix U ~ \widetilde{U} U given by finite binary approximations to the real and imaginary parts of U U U , each with absolute error at most 2 − p 2^{-p} 2 − p , at a precision p p p prescribed by the algorithm. This is the usual finite precision convention for matrix inputs [1 Sec. 2] , and the target distribution remains that of the ideal U U U . The fixed optical parameters are computable to absolute error 2 − p 2^{-p} 2 − p in time polynomial in p p p . In the statement uniform over 0 ≤ r ≤ r max 0 \le r \le r_{\max} 0 ≤ r ≤ r m a x , r r r is instead supplied at the prescribed precision, and the target is defined by its ideal value. For single-photon inputs, set N max = n N_{\max}=n N m a x = n , and for Gaussian inputs use the photon count cutoff above. Allocate ϵ n u m = ϵ / 4 \epsilon_{\mathrm{num}}=\epsilon/4 ϵ num = ϵ /4 to matrix rounding, scalar calculations and finite random bits in Eq. (D.2). We show that p = poly ( M + N max + L + log ( 1 / ϵ n u m ) ) p=\operatorname{poly}(M+N_{\max}+L+\log(1/\epsilon_{\mathrm{num}})) p = poly ( M + N m a x + L + log ( 1/ ϵ num )) bits per matrix component suffice.
At finite binary matrix inputs, the coefficient calculations use exact rational arithmetic. Their degrees in the matrix entries and conjugates are polynomial in N max + L N_{\max}+L N m a x + L . The binary input denominators, determinant recurrence factors, and rational projection and grouping coefficients admit a common denominator of polynomial bit length in M + N max + L + p M+N_{\max}+L+p M + N m a x + L + p . The logarithm of the number of expanded terms is polynomial in the cutoffs, so the numerators also have polynomial bit length. Normalizing a rounded photon sector additionally introduces its rational normalization coefficient, whose numerator and denominator satisfy the same bound. Each arithmetic operation therefore has polynomial bit cost.
These expansions also control matrix rounding. A degree d d d monomial in real and imaginary matrix components changes by at most d 2 d − 1 2 − p d2^{d-1}2^{-p} d 2 d − 1 2 − p , since ideal components have magnitude at most one and rounded components at most two. Multiplying by the sum of absolute coefficients bounds each polynomial’s change. The degrees and logarithms of these sums are polynomially bounded in the cutoffs, uniformly over proposed configurations and group assignments. Choosing p p p sufficiently large therefore makes the acceptance errors, summed over the bounded number of trials, smaller than their numerical budget. Clipping cannot increase these errors.
For equal squeezing, the common factor in B = ( tanh r ) H B=(\tanh r)H B = ( tanh r ) H cancels within each fixed photon sector. We evaluate the coefficients using H H H . For the ideal U U U , the sector normalization is
1 2 N / 2 ( N / 2 ) ! ∏ ℓ = 0 N / 2 − 1 ( s + 2 ℓ ) . \frac{1}{2^{N/2}(N/2)!}\prod_{\ell=0}^{N/2-1}(s+2\ell). 2 N /2 ( N /2 )! 1 ℓ = 0 ∏ N /2 − 1 ( s + 2 ℓ ) .
The approximate estimator retains this known normalization. For prefix sampling, we instead normalize the state of N N N photons generated by the rounded matrix before applying loss. Put δ o p = ∥ U ~ − U ∥ o p ≤ 1 / 2 \delta_{\mathrm{op}}=\lVert\widetilde{U}-U\rVert_{\mathrm{op}}\le1/2 δ op = ∥ U − U ∥ op ≤ 1/2 . Every singular value of U ~ \widetilde{U} U is at least 1 / 2 1/2 1/2 , so its induced map on the N N N -photon sector has minimum singular value at least 2 − N 2^{-N} 2 − N . The rounded sector normalization is therefore at least 2 − 2 N 2^{-2N} 2 − 2 N times the ideal coefficient above. That coefficient is at least 2 − N / 2 2^{-N/2} 2 − N /2 for s ≥ 1 s\ge1 s ≥ 1 , so normalization requires only O ( N ) O(N) O ( N ) additional precision bits.
A telescoping sum over the N N N tensor factors bounds the change of a normalized vector in an input sector before renormalization by ( 1 + δ o p ) N − 1 (1+\delta_{\mathrm{op}})^N-1 ( 1 + δ op ) N − 1 . After renormalization, its distance from the ideal output vector is at most 2 [ ( 1 + δ o p ) N − 1 ] 2[(1+\delta_{\mathrm{op}})^N-1] 2 [( 1 + δ op ) N − 1 ] . Photon loss and detection contract trace distance, so this also bounds the output total variation error. Since δ o p ≤ 2 M 2 − p \delta_{\mathrm{op}}\le\sqrt{2}M2^{-p} δ op ≤ 2 M 2 − p , taking p = O ( log ( 2 + M N max / ϵ n u m ) ) p=O(\log(2+MN_{\max}/\epsilon_{\mathrm{num}})) p = O ( log ( 2 + M N m a x / ϵ num )) sufficiently large controls matrix rounding in the prefix branch. These bounds remain uniform as r r r approaches zero.
Rounding the squeezing parameter is controlled in the same way. The squared overlap of the product squeezed vacuum inputs at r r r and r ′ r' r ′ is cosh ( r − r ′ ) − s \cosh(r-r')^{-s} cosh ( r − r ′ ) − s . Their trace distance is at most s / 2 ∣ r − r ′ ∣ \sqrt{s/2}\lvert r-r'\rvert s /2 ∣ r − r ′ ∣ , using log cosh t ≤ t 2 / 2 \log\cosh t\le t^2/2 log cosh t ≤ t 2 /2 and 1 − e − x ≤ x 1-e^{-x}\le x 1 − e − x ≤ x for x ≥ 0 x\ge0 x ≥ 0 . The optical channel cannot increase this distance. Hence O ( log ( M / ϵ n u m ) ) O(\log(M/\epsilon_{\mathrm{num}})) O ( log ( M / ϵ num )) bits of absolute precision suffice for the supplied squeezing throughout any fixed bounded interval, with the resulting error included in ϵ n u m \epsilon_{\mathrm{num}} ϵ num .
The photon count weights are obtained from Eq. (B.2) by dropping the common factor sech s r \operatorname{sech}^{s}r sech s r and normalizing over N ≤ N max N\le N_{\max} N ≤ N m a x . The vacuum weight is one. Evaluating these finite weights and the binomial loss probabilities to sufficient precision has polynomial cost under the input convention above.
Finally, sampling a finite law on a set X \mathcal{X} X of outcomes using a p r a n d p_{\mathrm{rand}} p rand bit uniform grid incurs total variation error at most ∣ X ∣ 2 − p r a n d \lvert\mathcal{X}\rvert2^{-p_{\mathrm{rand}}} ∣ X ∣ 2 − p rand . This applies to group labels, integer ranks of configurations, conditional photon counts, and binary acceptance decisions. The number of choices and the logarithms of their outcome counts are polynomially bounded. Choosing their errors to sum to the remaining ϵ n u m \epsilon_{\mathrm{num}} ϵ num budget therefore requires polynomially many random bits. Additional Bernoulli thinning for the transmission profiles in Sec. F 2 uses at most M + N max M+N_{\max} M + N m a x decisions per sample. An absolute error of O ( ϵ n u m / ( M + N max ) ) O(\epsilon_{\mathrm{num}}/(M+N_{\max})) O ( ϵ num / ( M + N m a x )) per decision suffices by coupling the choices. These scalar errors can be included in the same numerical budget. The resulting sampler has the claimed polynomial bit complexity.
Complete sampling procedure
For the supplied interferometer U U U , the sampler in Theorems 1 and 2 generates one output configuration in the following three steps. The cutoffs, rejection parameters, and numerical precision are chosen as in the preceding subsections.
Choose the photon numbers. For Fock state boson sampling, set N = n N=n N = n . For Gaussian boson sampling, use s = M s=M s = M and draw N N N from Eq. (B.2), conditioned on N ≤ N max N\le N_{\max} N ≤ N m a x . Then draw k k k from Bin ( N , η ) \operatorname{Bin}(N,\eta) Bin ( N , η ) . If k = 0 k=0 k = 0 or M = 1 M=1 M = 1 , output the unique compatible configuration and stop.
Select the sampling method. For Gaussian boson sampling, two branches finish at this step. If N ≤ N 0 N\le N_0 N ≤ N 0 , draw the lossless output configuration using the prefix sampler of Sec. D 2,
then select k k k surviving photons according to Eq. (B.4) and output their configuration. If N > N 0 N > N_0 N > N 0 and either N > c M N > cM N > c M or k > ϑ N k > \vartheta N k > ϑN , output a fixed configuration with total photon number k k k . All remaining sectors, including those of Fock state boson sampling, proceed to step 3.
Generate a configuration by rejection sampling. Propose x x x uniformly among all k k k -photon configurations. Average T T T independent estimates from Appendix C to obtain F ^ T ( x ) \widehat{F}_T(x) F T ( x ) , and accept x x x with probability
clip [ 0 , A ] ( F ^ T ( x ) ) A . \frac{\operatorname{clip}_{[0,A]}(\widehat{F}_T(x))}{A}. A clip [ 0 , A ] ( F T ( x )) .
Output the first accepted configuration. After each rejection, draw a new candidate and use fresh estimator randomness, for at most J J J trials in total. If every trial fails, output a fixed configuration with total photon number k k k .
The count bounds give ϵ c o u n t ≤ 3 ϵ / 64 \epsilon_{\mathrm{count}} \le3\epsilon/64 ϵ count ≤ 3 ϵ /64 , and finite precision and finite random bits contribute at most ϵ n u m = ϵ / 4 \epsilon_{\mathrm{num}} = \epsilon/4 ϵ num = ϵ /4 . With the preceding parameter choices, the first four terms in Eq. (D.2) each contribute at most ϵ / 8 \epsilon/8 ϵ /8 , and the finite trial term contributes at most ϵ / ( 16 e ) \epsilon/(16e) ϵ / ( 16 e ) . Thus
E U d T V ( Q U , P U ) ≤ ( 51 64 + 1 16 e ) ϵ < 0.82 ϵ < ϵ . (108) \mathbb{E}_U d_{\mathrm{TV}}(Q_U,P_U) \le\left(\frac{51}{64}+\frac{1}{16e}\right)\epsilon< 0.82\epsilon< \epsilon. \tag*{(108)} E U d TV ( Q U , P U ) ≤ ( 64 51 + 16 e 1 ) ϵ < 0.82 ϵ < ϵ . (108)
Every branch uses a number of arithmetic operations polynomial in the system size and 1 / ϵ 1/\epsilon 1/ ϵ , uniformly over 0 ≤ r ≤ r max 0 \le r \le r_{\max} 0 ≤ r ≤ r m a x for the Gaussian input, and Sec. D 4 gives the same bound in bit complexity. This completes the proofs of Theorems 1 and 2.
We now apply the sampling construction to s s s equally squeezed inputs and M − s M-s M − s vacuum inputs. The evaluator of Appendix C and the count bounds of Appendix D already apply to this input. The remaining step is to control the correlation tail uniformly in s s s . We first derive the needed reduced purity bound, then combine it with the established sampler.
Let τ h ( s , N ) \tau_h(s,N) τ h ( s , N ) be the purity of the normalized h h h -particle reduction of ∣ Ψ s , N ⟩ |\Psi_{s,N}\rangle ∣ Ψ s , N ⟩ , with N = 2 n N=2n N = 2 n . Adding vacuum modes preserves this reduced purity. For every s ≥ 1 s \ge1 s ≥ 1 and 0 ≤ h ≤ N 0 \le h \le N 0 ≤ h ≤ N , the coefficients in Eq. (B.24) give
D s , h τ h ( s , N ) = ∑ j = 0 h ( D s , j + D s , j − 1 ) Γ s , N , j × ( h j ) ( N j ) ( s + N + j − 1 ) ! ( s + h − 1 ) ! ( s + N − 1 ) ! ( s + h + j − 1 ) ! . (109) D_{s,h}\tau_h(s,N)=\sum_{j=0}^{h}(D_{s,j}+D_{s,j-1})\Gamma_{s,N,j}\times\frac{\binom{h}{j}}{\binom{N}{j}}\frac{(s+N+j-1)!(s+h-1)!}{(s+N-1)!(s+h+j-1)!}. \tag*{(109)} D s , h τ h ( s , N ) = j = 0 ∑ h ( D s , j + D s , j − 1 ) Γ s , N , j × ( j N ) ( j h ) ( s + N − 1 )! ( s + h + j − 1 )! ( s + N + j − 1 )! ( s + h − 1 )! . (109)
For s ≥ 2 s \ge2 s ≥ 2 , this identity follows from Eqs. (B.15) and (B.12) in the occupied s s s -mode space. For s = 1 s=1 s = 1 , Eq. (B.24) gives Γ 1 , N , 0 = 1 \Gamma_{1,N,0}=1 Γ 1 , N , 0 = 1 and Γ 1 , N , j = 0 \Gamma_{1,N,j}=0 Γ 1 , N , j = 0 for j > 0 j>0 j > 0 , so both sides equal one. The odd Γ s , N , j \Gamma_{s,N,j} Γ s , N , j vanish, and the even weights satisfy Eq. (B.26). These facts imply the uniform bound
( N h ) τ h ( s , N ) ≤ 2 ( 1 + 2 N s ) h . (110) \binom{N}{h}\tau_h(s,N)\le2\left(1+\frac{2N}{s}\right)^h. \tag*{(110)} ( h N ) τ h ( s , N ) ≤ 2 ( 1 + s 2 N ) h . (110)
To see the resulting estimate explicitly, multiply one summand of Eq. (E.1), with Γ s , N , j \Gamma_{s,N,j} Γ s , N , j omitted, by ( N h ) / D s , h \binom{N}{h}/D_{s,h} ( h N ) / D s , h . The result is
( h j ) ( N − j ) ! ( s + j − 1 ) ! ( N − h ) ! ( s + h − 1 ) ! × ( s + N + j − 1 ) ! ( s + h − 1 ) ! ( s + N − 1 ) ! ( s + h + j − 1 ) ! D s , j + D s , j − 1 D s , j . (111) \binom{h}{j}\frac{(N-j)!(s+j-1)!}{(N-h)!(s+h-1)!}\times\frac{(s+N+j-1)!(s+h-1)!}{(s+N-1)!(s+h+j-1)!}\frac{D_{s,j}+D_{s,j-1}}{D_{s,j}}. \tag*{(111)} ( j h ) ( N − h )! ( s + h − 1 )! ( N − j )! ( s + j − 1 )! × ( s + N − 1 )! ( s + h + j − 1 )! ( s + N + j − 1 )! ( s + h − 1 )! D s , j D s , j + D s , j − 1 . (111)
For c N = N / s c_N=N/s c N = N / s , the three factors after ( h j ) \binom{h}{j} ( j h ) are at most c N h − j c_N^{h-j} c N h − j , ( 1 + c N ) j (1+c_N)^j ( 1 + c N ) j , and 2, respectively. Using Γ s , N , j ≤ 1 \Gamma_{s,N,j}\leq1 Γ s , N , j ≤ 1 and summing the even j j j gives
( N h ) τ h ≤ 2 ∑ j ≤ h j e v e n ( h j ) c N h − j ( 1 + c N ) j ≤ 2 ( 1 + 2 c N ) h . (112) \binom{N}{h}\tau_h\leq2\sum_{\substack{j\leq h\\ j\ \mathrm{even}}}\binom{h}{j}c_N^{h-j}(1+c_N)^j\leq2(1+2c_N)^h. \tag*{(112)} ( h N ) τ h ≤ 2 j ≤ h j even ∑ ( j h ) c N h − j ( 1 + c N ) j ≤ 2 ( 1 + 2 c N ) h . (112)
Conditions for efficient sampling
Corollary 1. (Gaussian boson sampling with s s s squeezed inputs). Fix r > 0 r>0 r > 0 and a transmission η \eta η such that
η cosh ( 2 r ) < 1. (113) \eta\cosh(2r)<1. \tag*{(113)} η cosh ( 2 r ) < 1. (113) For every 1 ≤ s ≤ M 1\leq s\leq M 1 ≤ s ≤ M , consider the input ∣ Ψ G ⟩ \lvert\Psi_{\mathrm{G}}\rangle ∣ Ψ G ⟩ of Problem 2, with s s s squeezed vacuum states of common squeezing parameter r r r and M − s M-s M − s vacuum states. For every 0 < ϵ ≤ 1 / 2 0<\epsilon\leq1/2 0 < ϵ ≤ 1/2 , there is a classical randomized algorithm satisfying
E U d T V ( Q U , P U , s , r , η G ) ≤ ϵ (114) \mathbb{E}_{U}d_{\mathrm{TV}}(Q_U,P^{\mathrm{G}}_{U,s,r,\eta})\leq\epsilon \tag*{(114)} E U d TV ( Q U , P U , s , r , η G ) ≤ ϵ (114) with worst case running time per sample bounded by poly r , η ( M , 1 / ϵ ) \operatorname{poly}_{r,\eta}(M,1/\epsilon) poly r , η ( M , 1/ ϵ ) arithmetic operations. The polynomial’s degree and constants are independent of s s s .
The high probability bound of Eq. (A.2) and the bound for repeated samples in Appendix A also hold in this region. The running time bound can grow as η cosh ( 2 r ) \eta\cosh(2r) η cosh ( 2 r ) approaches one.
Proof. For s < M s<M s < M , the state ∣ Ψ s , N ⟩ \lvert\Psi_{s,N}\rangle ∣ Ψ s , N ⟩ occupies an s s s dimensional single particle subspace before the interferometer. Its Haar weights W h ( k ) W_h(k) W h ( k ) nevertheless depend on the ambient mode count M M M . For example, the first order has weight
W 1 ( k ) = k ( M − s ) s ( M + k ) . (115) W_1(k)=\frac{k(M-s)}{s(M+k)}. \tag*{(115)} W 1 ( k ) = s ( M + k ) k ( M − s ) . (115)
which is positive for k > 0 k>0 k > 0 and s < M s<M s < M . Vacuum embedding thus introduces odd correlation orders that vanish when every input mode is squeezed.
The reduced purity bound in Eq. (E.2), combined with Eq. (B.11), yields
W h ( k ) ≤ 2 [ k N ( 1 + 2 N s ) ] h . (116) W_h(k)\leq2\left[\frac{k}{N}\left(1+\frac{2N}{s}\right)\right]^h. \tag*{(116)} W h ( k ) ≤ 2 [ N k ( 1 + s 2 N ) ] h . (116)
This step removes any dependence on the vacuum fraction. Choose constants
c > sinh 2 r , ϑ > η , χ ~ = ϑ ( 1 + 2 c ) < 1. (117) c>\sinh^2 r,\qquad\vartheta>\eta,\qquad\widetilde{\chi}=\vartheta(1+2c)<1. \tag*{(117)} c > sinh 2 r , ϑ > η , χ = ϑ ( 1 + 2 c ) < 1. (117)
Such constants exist precisely when Eq. (E.5) holds, because cosh ( 2 r ) = 1 + 2 sinh 2 r \cosh(2r)=1+2\sinh^2r cosh ( 2 r ) = 1 + 2 sinh 2 r . On N ≤ c s N\le cs N ≤ cs and k ≤ ϑ N k\le\vartheta N k ≤ ϑN ,
E U ∥ F U − F U ≤ L ∥ 2 2 ≤ 2 χ ~ L + 1 1 − χ ~ , (118) \mathbb{E}_U\left\|F_U-F_U^{\leq L}\right\|_2^2\leq\frac{2\widetilde{\chi}^{L+1}}{1-\widetilde{\chi}}, \tag*{(118)} E U F U − F U ≤ L 2 2 ≤ 1 − χ 2 χ L + 1 , (118)
E U ∥ F U ∥ 2 2 ≤ 1 + χ ~ 1 − χ ~ . (119) \mathbb{E}_U\left\|F_U\right\|_2^2\leq\frac{1+\widetilde{\chi}}{1-\widetilde{\chi}}. \tag*{(119)} E U ∥ F U ∥ 2 2 ≤ 1 − χ 1 + χ . (119)
These bounds include the odd correlation orders introduced by vacuum inputs and all output configurations with collisions. For small s s s , the event N > c s N>cs N > cs can carry appreciable probability. We therefore use prefix sampling in every sector with N ≤ N 0 = O r , η ( 1 + log ( 1 / ϵ ) ) N\leq N_0=O_{r,\eta}(1+\log(1/\epsilon)) N ≤ N 0 = O r , η ( 1 + log ( 1/ ϵ )) and apply the geometric bound only in the stated region with N > N 0 N>N_0 N > N 0 . Equations (D.14) and (D.15) control the remaining probability uniformly in s s s , as shown in Sec. D 3.
The Gaussian evaluator of Appendix C applies to the same s s s -mode input sector. Together with the count bounds of Sec. D 3, Eqs. (E.10) and (E.11) give C 2 = O r , η ( 1 ) C_2=O_{r,\eta}(1) C 2 = O r , η ( 1 ) and a geometric tail S L S_L S L . Substituting them into Eq. (D.2) and using the finite precision analysis of Sec. D 4 proves the stated error and running time uniformly in s s s .
The optical condition can also be written
η ( 1 + 2 N ‾ i n s ) < 1 , N ‾ i n = s sinh 2 r . (120) \eta\left(1+2\frac{\overline{N}_{\mathrm{in}}}{s}\right)<1,\qquad\overline{N}_{\mathrm{in}}=s\sinh^2r. \tag*{(120)} η ( 1 + 2 s N in ) < 1 , N in = s sinh 2 r . (120)
The sufficient condition also bounds the mean detected photon number per squeezed input as η sinh 2 r < ( 1 − η ) / 2 \eta\sinh^2r<(1-\eta)/2 η sinh 2 r < ( 1 − η ) /2 . For example, r = 1 2 log 3 r=\frac{1}{2}\log3 r = 2 1 log 3 gives sinh 2 r = 1 / 3 \sinh^2r=1/3 sinh 2 r = 1/3 and requires η < 3 / 5 \eta<3/5 η < 3/5 . This corresponds to about 4.77 dB of input squeezing and a mean input photon number s / 3 s/3 s /3 .
Scope of the sampling results
Dependence on Haar averaging
The Haar average enters our analysis in two places. First, the correlation weights W h ( k ) W_h(k) W h ( k ) of Appendix B are Haar averages, so the tail beyond the cutoff is controlled only on average over interferometers. Second, the variance of the random estimate in Lemma 1 is also bounded only on average over interferometers. The running time bound holds for every interferometer, but the accuracy bound does not. Through Eq. (A.2), the average error also yields a bound that holds with high probability for a circuit drawn once.
For a specified interferometer, such as the structured interferometers discussed in Sec. IV, separate bounds on both the correlation tail and the estimator variance are therefore needed.
Mode-dependent transmissions
Theorems 1 and 2 also cover unequal transmissions in the final output channels when they satisfy 0 ≤ η i ≤ η ∗ 0\leq\eta_i\leq\eta_* 0 ≤ η i ≤ η ∗ for a fixed 0 < η ∗ < 1 0<\eta_*<1 0 < η ∗ < 1 . Generate a sample x x x using uniform transmission η ∗ \eta_* η ∗ , then independently draw the count in mode i i i from Bin ( x i , η i / η ∗ ) \operatorname{Bin}(x_i,\eta_i/\eta_*) Bin ( x i , η i / η ∗ ) . Pure-loss channels compose by multiplying their transmissions. This classical thinning therefore gives the desired output law, and total variation error cannot increase. The transmission profile is supplied at the sufficient finite binary precision for the requested error. A measured average transmission alone does not specify the upper bound η ∗ \eta_* η ∗ .
Independent source loss can also be included for single-photon inputs. If a fixed uniform loss is already present, first select which occupied input modes survive the additional source loss, then apply Theorem 1 to the selected input subset. When source loss is the only loss, suppose its transmissions satisfy η i ≤ η ∗ < 1 \eta_i \leq\eta_* < 1 η i ≤ η ∗ < 1 for a fixed η ∗ \eta_* η ∗ . Select input i i i with probability η i / η ∗ \eta_i/\eta_* η i / η ∗ and use uniform transmission η ∗ \eta_* η ∗ in the sampler. Conditional on the selected subset, a permutation of the input columns gives the standard single-photon configuration. For a source profile independent of U U U , Haar invariance under these permutations and convexity of total variation preserve the mean error bound after averaging over the subset. Selecting a subset has polynomial cost and requires one sampler call, including the vacuum case.
General path-dependent loss inside the interferometer requires additional analysis.
Comparison with other simulation methods
Section III summarizes these methods. Here we record the scalings behind that summary and compare the assumptions on the interferometer.
For single-photon inputs, the classical approximation of the lossy state applies when the number of surviving photons grows more slowly than the square root of the number of input photons [13 ] , and thermal noise approximations cover architectures whose transmission decays exponentially with circuit depth [14 ] . For Gaussian inputs at fixed squeezing, the error bounds O r ( s η ) O_r(\sqrt{s}\eta) O r ( s η ) of the Gaussian approximation [15 ] and O r ( s η 3 ) O_r(s\eta^3) O r ( s η 3 ) of the reset method [17 ] give the sufficient scalings η = O ( s − 1 / 2 ) \eta= O(s^{-1/2}) η = O ( s − 1/2 ) and η = O ( s − 1 / 3 ) \eta= O(s^{-1/3}) η = O ( s − 1/3 ) , which permit mean detected photon numbers of order s 1 / 2 s^{1/2} s 1/2 and s 2 / 3 s^{2/3} s 2/3 . In all these cases the fraction of input photons that survives tends to zero. The loss analyses of tensor network methods identify the same square root scale, with logarithmic refinements in the entanglement bounds [16 , 18 ] . Increasing the bond dimension can reduce the error, but at η = Θ ( s − 1 / 2 ) \eta= \Theta(s^{-1/2}) η = Θ ( s − 1/2 ) the Gaussian analysis does not establish a cost polynomial in both system size and 1 / ϵ 1/\epsilon 1/ ϵ [16 ] .
Interference truncation [21 ] evaluates a probability truncated at order L L L through M O ( L ) M^{O(L)} M O ( L ) auxiliary configurations and draws samples with a Metropolis chain. Our construction uses the same physical suppression of high-order correlations but replaces both steps. The two-sided projection and random grouping of Appendix C avoid the M O ( L ) M^{O(L)} M O ( L ) enumeration, with cost polynomial in system size and singly exponential in L L L and log ( 1 / ϵ ) \log(1/\epsilon) log ( 1/ ϵ ) , and the rejection sampler of Sec. D 1 stops after a bounded number of trials with an explicit total variation bound.
The interferometer assumptions also differ. Our accuracy bound is averaged over Haar circuits, while the approximations for single-photon inputs and the Gaussian approximation and reset bounds hold for every U U U , and tensor network methods apply to specified circuits with cost controlled by their entanglement.
Comparison with sampling hardness
Fock state boson sampling
Conditioning on the event that no photon is lost [10 ] yields conditional hardness when the mean loss is logarithmic [11 ] . For n n n single photons in distinct input modes, write P U ( n ) = P U , n , η F P_U^{(n)} = P_{U,n,\eta}^{\mathrm{F}} P U ( n ) = P U , n , η F for the full lossy output distribution. For every U U U ,
P U ( n ) ( x ) = η n P U ( 1 ) ( x ) , ∣ x ∣ = n . (121) P_U^{(n)}(x) = \eta^n P_U^{(1)}(x), \qquad|x| = n. \tag*{(121)} P U ( n ) ( x ) = η n P U ( 1 ) ( x ) , ∣ x ∣ = n . (121)
The event E = { x : ∣ x ∣ = n } E=\{x: |x|=n\} E = { x : ∣ x ∣ = n } therefore has probability p = η n p=\eta^n p = η n , independent of U U U , and conditioning on E E E gives the ideal distribution. If the mean number of lost photons obeys
( 1 − η ) n = O ( log n ) , (122) (1-\eta)n=O(\log n), \tag*{(122)} ( 1 − η ) n = O ( log n ) , (122)
then − log p = − n log η = O ( log n ) -\log p=-n\log\eta=O(\log n) − log p = − n log η = O ( log n ) , so p ≥ n − c p\ge n^{-c} p ≥ n − c for some fixed c > 0 c>0 c > 0 .
For an approximate lossy sampler with output law Q U Q_U Q U , let δ U = d T V ( P U ( η ) , Q U ) \delta_U=d_{\mathrm{TV}}(P_U^{(\eta)},Q_U) δ U = d TV ( P U ( η ) , Q U ) . Whenever Q U ( E ) > 0 Q_U(E)>0 Q U ( E ) > 0 , conditioning gives
d T V ( P U ( 1 ) , Q U ( ⋅ ∣ E ) ) ≤ δ U / p . d_{\mathrm{TV}}(P_U^{(1)},Q_U(\cdot\mid E))\le\delta_U/p. d TV ( P U ( 1 ) , Q U ( ⋅ ∣ E )) ≤ δ U / p .
Draw from Q U Q_U Q U until an outcome in E E E is obtained, with a limit of R R R independent trials. If every trial fails, output a fixed n n n -photon configuration. For δ U ≤ p / 2 \delta_U\le p/2 δ U ≤ p /2 , the acceptance probability is at least p / 2 p/2 p /2 and the failure probability is at most e − p R / 2 e^{-pR/2} e − pR /2 . By Markov’s inequality, the remaining interferometers have Haar probability at most 2 E U δ U / p 2\mathbb{E}_U\delta_U/p 2 E U δ U / p . The output law Q ^ U \widehat{Q}_U Q U of this bounded procedure consequently satisfies
E U d T V ( P U ( 1 ) , Q ^ U ) ≤ 3 E U δ U p + e − p R / 2 . (123) \mathbb{E}_U d_{\mathrm{TV}}(P_U^{(1)},\widehat{Q}_U)\le\frac{3\mathbb{E}_U\delta_U}{p}+e^{-pR/2}. \tag*{(123)} E U d TV ( P U ( 1 ) , Q U ) ≤ p 3 E U δ U + e − pR /2 . (123)
Taking E U δ U ≤ p ϵ / 6 \mathbb{E}_U\delta_U\le p\epsilon/6 E U δ U ≤ p ϵ /6 and R = ⌈ ( 2 / p ) log ( 2 / ϵ ) ⌉ R=\lceil(2/p)\log(2/\epsilon)\rceil R = ⌈( 2/ p ) log ( 2/ ϵ )⌉ gives mean error at most ϵ \epsilon ϵ . Under Eq. (G.2), an inverse polynomial target error requires only inverse polynomial lossy error and polynomially many trials. When M = poly ( n ) M=\operatorname{poly}(n) M = poly ( n ) , the hardness conclusion therefore inherits the ideal sampling assumptions in [1 , 23 ] , in their respective mode scalings.
At fixed η \eta η , the probability p p p decays exponentially with n n n , so recovering ideal samples this way requires exponentially many trials. In this regime, the sampler of Theorem 1 still samples the full lossy distribution efficiently. Its runtime bound depends on η \eta η , as seen from the required correlation cutoff.
The sampler of Theorem 1 uses the cutoff in Eq. (D.4), which keeps the mean squared error from orders above L L L below ( ϵ / 16 ) 2 (\epsilon/16)^2 ( ϵ /16 ) 2 . For ϵ = n − a \epsilon=n^{-a} ϵ = n − a with fixed a > 0 a>0 a > 0 , the right side of Eq. (D.4) is O ( log n ) O(\log n) O ( log n ) at fixed η \eta η . It becomes Θ ( n ) \Theta(n) Θ ( n ) when 1 − η = Θ ( log n / n ) 1-\eta=\Theta(\log n/n) 1 − η = Θ ( log n / n ) . The evaluation cost is exponential in L L L , so our bound on the running time is no longer polynomial in the regime of logarithmic loss. The intermediate range log n ≪ ( 1 − η ) n ≪ n \log n\ll(1-\eta)n\ll n log n ≪ ( 1 − η ) n ≪ n remains open.
Gaussian boson sampling
Conditional hardness under loss has been studied for equal squeezing in all M M M input modes with a Haar random interferometer [12 ] . The analysis uses the dilute scaling M = Θ ( n γ ) M=\Theta(n^\gamma) M = Θ ( n γ ) for sufficiently large γ > 2 \gamma>2 γ > 2 , where n n n now denotes the mean detected photon number. The squeezing is chosen through
n = η M sinh 2 r . (124) n=\eta M\sinh^2 r. \tag*{(124)} n = η M sinh 2 r . (124)
Its hardness result concerns logarithmic mean loss, and its reduction for estimating probabilities uses a range of transmissions. The sampling hardness statement at a specified transmission additionally assumes that increasing loss monotonically reduces simulation complexity at fixed total variation error, alongside the ideal average case hardness conjecture. In this regime of low loss, the specified photon count occurs with inverse polynomial probability, so the hardness conclusion also applies to the full output distribution.
At any fixed η \eta η , the same dilute scaling has r → 0 r\to0 r → 0 and is covered by our sampling construction. Since the bound of Theorem 2 applies to every smaller squeezing parameter, taking any fixed upper value of the squeezing covers this regime, with the bounds on photon counts and source precision proved in Secs. D 3 and D 4. The resulting cost remains polynomial in M M M and 1 / ϵ 1/\epsilon 1/ ϵ , hence in n n n and 1 / ϵ 1/\epsilon 1/ ϵ when M = poly ( n ) M = \operatorname{poly}(n) M = poly ( n ) . The hardness regime of logarithmic loss has η → 1 \eta\to1 η → 1 , where our runtime bound at fixed transmission does not apply.
For s s s equally squeezed inputs and M − s M-s M − s vacuum inputs, Corollary 1 establishes efficient sampling under the sufficient condition in Eq. (E.12). At fixed η \eta η , this condition is eventually satisfied whenever N ‾ i n / s → 0 \overline{N}_{\mathrm{in}}/s \to0 N in / s → 0 , even if N ‾ i n → ∞ \overline{N}_{\mathrm{in}} \to\infty N in → ∞ .
The hardness result for dense bipartite Gaussian boson sampling concerns pairs of modes prepared in two-mode squeezed states and mixed by separate interferometers on the two arms [23 ] . The argument uses a Haar unitary relating the arms and assumptions on the resulting permanent estimation problem. The error bound of Theorem 2 is averaged over Haar unitaries that mix all modes, so it does not establish efficient sampling for the bipartite interferometer ensemble.
A separate result concerns the computation of probabilities rather than sampling. For local noise below a threshold, including photon loss, computing output probabilities of Gaussian boson sampling with Haar random interferometers to exponentially small additive error remains #P-hard on average [36 ] . This hardness of individual probabilities does not imply hardness of approximate sampling and is therefore compatible with the efficient samplers established here.
References