betaFeedback

WorksPhysics and Astronomy

Exact sampling beyond Fock inputs and linear optics: photon-number superpositions, photonic matrix-product states, adaptive and non-linear circuits

Abstract

Clifford and Clifford's algorithm samples single-photon boson sampling exactly, one output mode at a time, by adding the input photons in a uniformly random order. We extend this construction to other input states and to adaptive and non-linear circuits. It applies whenever non-negative weights on output prefixes and input sets satisfy one marginal identity, a set-chain lemma: the random-order sampler is then exact at one weight evaluation per candidate mode, and it gives the posterior over the hidden input set. We build four exact samplers on it. For sources in a superposition of vacuum and one photon, the weights are rectangular permanents on an offset input set, and the cost has the exponent of single photons under loss. For photonic matrix-product states of bond dimension χχ, a gap-by-gap Kraus contraction turns each weight into a short sum of squared amplitudes. For adaptive linear optics, the chain starts from the posterior given the adaptive counts and rejects chains that contradict them. For a single-mode non-linear phase the identity fails, and rejection from linear branches is exact with acceptance 1/∥c∥121/\|c\|_1^2. All four samplers agree with strong simulation on small instances, and cost models put adaptive sampling with up to three adaptive modes within 10%10\% of single photons and a non-linear site at φ=π/2φ=π/2 at about 4×4\times.

chain_rules.pdf

Introduction

Claims of quantum advantage with photons rest on the gap between what a device samples and what a classical computer can sample exactly. For standard boson sampling, nn single photons in an mm-mode linear interferometer UU, the output probabilities are permanents, #P-hard to compute in the worst case, and a polynomial-time exact classical sampler would collapse the polynomial hierarchy [1]. Real photonic devices differ from this model: their sources can be partially excited or entangled, and their circuits can include mid-circuit measurements with feed-forward or non-linear elements. Where exact classical simulation stops for such devices depends on exact samplers built for them.

Clifford and Clifford [2] gave the standard exact sampler for single photons. They observed that if the photons are given a uniformly random order, the marginal law of the output modes of the first jj photons (the first jj output rows) is the average, over the jj input columns those photons used, of a single squared permanent. The output can then be drawn row by row, and a sample costs about as much as two permanents of the full size, O(n22n)O(n^{2}2^{n}). Their 2020 refinement [3] exploits repeated output rows and brings the average cost over Haar interferometers to O(nϱ)O(n^{\varrho}), the growth ϱ\varrho depending on the mode ratio m/nm/n (ϱ≈1.81\varrho\approx1.81 at m=2nm=2n).

The proof uses three properties of this setting: the input is a product of single photons; the interferometer acts on them as U⊗nU^{\otimes n}; and the columns of UU are orthonormal, ∑rUrxU‾rx′=δxx′\sum_r U_{rx}\overline{U}_{rx'}=\delta_{xx'}, the identity that turns the Laplace expansion of a squared permanent along its last row into a sum over the permanents of the smaller column sets. We consider four kinds of devices. The first two break the product input, the last two the action U⊗nU^{\otimes n}:

  • Superposed sources. Partially excited sources emit a coherent superposition of vacuum and one photon [5], so the photon number is not fixed.

  • Photonic matrix-product states. A quantum emitter with a χ\chi-dimensional internal memory, such as a quantum-dot spin, emits photons one after another, entangled through that memory: a photonic matrix-product state (MPS) of bond dimension χ\chi [7], such as linear cluster and caterpillar states [8, 9].

  • Adaptive linear optics. Mid-circuit photon counting with feed-forward makes the interferometer depend on earlier outcomes [10, 11].

  • Non-linear sites. A single-mode non-linearity between interferometers makes the circuit itself non-linear [12].

None of them breaks orthonormality directly, but it is the property that fails inside the last two samplers: on the non-adaptive modes of an adaptive circuit, and between the linear branches of a non-linear one (§ 2.3 and § 2.4). Uniform loss and partial distinguishability in the mixture model are handled by every sampler, as a mixture drawn before the chain (§ 1.2).

Prior work. Renema [6] writes the chain rule for an arbitrary input state. Its marginal is a double sum over input components and hidden subsets, so a step costs up to (nk)2\binom{n}{k}^{2} component pairs for nn superposed sources with kk photons, and a number exponential in the length of the train for an emitter. Dias and König [15] sample any measurement of a coherent superposition by rejection from the mixture of its components, with an expected number of proposals set by the number of components (2n2^{n} for nn superposed sources) and the 2-norm of their coefficients. Rejection or reweighting over a decomposition into classically easy terms, at a cost set by the 1-norm of the coefficients, is also the principle of quasi-probability and stabilizer-rank simulators of quantum circuits [26, 27, 28]. Oh and Lim [11] sample adaptive circuits exactly and efficiently when the input and the final measurement are Gaussian and O(log⁡m)O(\log m) modes are read adaptively. Bravyi, Gosset and Liu [16] sample any circuit from prefix amplitudes, without marginals (cost models compared in the Supplementary Material, Sec. ??). Moylett et al. [29] build on the Clifford–Clifford sampler to simulate single photons under loss and partial distinguishability. Further exact methods — repeated input modes [4], Gaussian chains [14, 13, 19], bounded treewidth [17], phase-space representations [18] and a linear-optical Kerr gadget [12] — are compared in the Supplementary Material (Table ??). To our knowledge none of them specialises the random-order chain to superposed sources, to photonic MPS with a cost set by the bond dimension and the number of traced runs, or to Fock inputs with photon-number-resolved feed-forward and final detection.

Contributions. We state the property the random order provides as a lemma about set-indexed weights, which also gives the posterior over the hidden input set (§ 1.2), and build four samplers on it:

  1. for superposed sources, a rectangular permanent on an active set started at n−kn-k sources, at the cost exponent of single photons under loss η=sin⁡2α\eta=\sin^{2}\alpha (§ 2.1, Proposition 1);

  1. for photonic MPS, a gapwise Kraus contraction that writes each weight as RjR_j squared amplitudes evaluated by matrix-valued Glynn sums; on the trains we measured, RjR_j is 1–2 on the last steps, which carry the cost (§ 2.2, Proposition 2);

  1. for adaptive linear optics, a conditional chain started from the lemma’s posterior given the adaptive counts, with rejection of the chains that place a further photon on an adaptive mode (§ 2.3);

  1. for non-linear sites, where the natural weight fails the lemma, the branch-rejection principle applied to linear branches, exact with acceptance probability 1/∥c∥121/\lVert\boldsymbol{c}\rVert_{1}^{2} (§ 2.4).

Lemma 1, Propositions 1 and 2 and the conditioning step of the adaptive sampler are formalised and machine-checked in Lean 4 (Supplementary Material, Sec. ??). All four samplers run in one GPU code base; they are validated against strong simulation (§ 2.6.1), and their cost is compared, measured or modelled, with the single-photon sampler on instances of the same size (§ 2.6.2). What these costs imply for the size of photonic devices that can be simulated exactly is the subject of a companion study [25].

The set-chain lemma

Setting. An output sample of kk detected photons in mm modes is drawn as an ordered tuple of rows z=(z1,…,zk)∈[m]kz=(z_1,\ldots,z_k)\in[m]^k from a law qq, one output mode per photon; forgetting the order gives the occupation pattern that the detectors record, sr=∣{i:zi=r}∣s_r=|\{i:z_i=r\}| photons in mode rr. The lemma does not need qq to be exchangeable, q(zπ(1),…,zπ(k))=q(z)q(z_{\pi(1)},\ldots,z_{\pi(k)})=q(z) for every permutation π\pi (the pattern listed in a uniformly random order); the laws of this paper are, and Sec. 5 uses it. There are NN slots (input columns: photons, sources, emission events), and a non-negative integer offset s0s_0: the chain starts from s0s_0 slots and adds one per placed row, so that after jj rows its active set holds sj=s0+js_j=s_0+j slots.

Notation: [N]={1,…,N}[N]=\{1,\ldots,N\}; A[z,T]A[z,T] is the sub-matrix of rows zz (with repetition) and columns TT, A[:,t]A[:,t] keeps all rows; z<j=(z1,…,zj−1)z_{<j}=(z_1,\ldots,z_{j-1}); p!=∏lpl!p!=\prod_l p_l! for counts pp.

Definition 1 (Chain-consistent set weights). A family fj(z;T)≥0f_j(z;T)\geq0, defined for j=0,…,kj=0,\ldots,k, z∈[m]jz\in[m]^j and T⊆[N]T\subseteq[N] with ∣T∣=sj|T|=s_j, is chain-consistent if

f0(∅;T)=1for every ∣T∣=s0,(1)f_0(\varnothing;T)=1\quad\text{for every }|T|=s_0, \tag*{(1)}
∑r∈[m]fj(z1…zj−1r;T)=∑x∈Tfj−1(z1…zj−1;T∖{x})(1≤j≤k).(2)\sum_{r\in[m]}f_j(z_1\ldots z_{j-1}r;T)=\sum_{x\in T}f_{j-1}(z_1\ldots z_{j-1};T\setminus\{x\})\quad(1\leq j\leq k). \tag*{(2)}

Its target is q(z)=(Nsk)−1s0!sk!∑∣T∣=skfk(z;T)q(z)=\binom{N}{s_k}^{-1}\frac{s_0!}{s_k!}\sum_{|T|=s_k}f_k(z;T).

Lemma 1 (Set-chain lemma). Let ff be chain-consistent (Definition 1), with s0+k≤Ns_0+k\leq N. Draw a uniformly random order σ\sigma of [N][N]; for j=1,…,kj=1,\ldots,k set Tj={σ1,…,σsj}T_j=\{\sigma_1,\ldots,\sigma_{s_j}\} and draw zjz_j with probability fj(z1…zj−1zj;Tj)∑rfj(z1…zj−1r;Tj)\frac{f_j(z_1\ldots z_{j-1}z_j;T_j)}{\sum_{r}f_j(z_1\ldots z_{j-1}r;T_j)}. Then

(a) qq is a probability law, and its marginal on the first jj rows is qj(z≤j)=(Nsj)−1s0!sj!∑∣T∣=sjfj(z≤j;T)q_j(z_{\leq j})=\binom{N}{s_j}^{-1}\frac{s_0!}{s_j!}\sum_{|T|=s_j}f_j(z_{\leq j};T);

(b) the algorithm outputs zz with law qq;

(c) at every step, the law of the active set given the rows drawn so far is Pr⁡[Tj=T∣z≤j]∝fj(z≤j;T)\Pr[T_j=T\mid z_{\leq j}]\propto f_j(z_{\leq j};T).

Proof. By induction on jj with (C2), ∑z∈[m]jfj(z;T)=sj!/s0!\sum_{z\in[m]^j}f_j(z;T)=s_j!/s_0! for every TT, so qq sums to one. Summing qjq_j over the last row and using (C2), each (sj−1)(s_j-1)-set T′T' is reached from the N−sj−1N-s_{j-1} sets T′∪{x}T'\cup\{x\}, and (Nsj)=(Nsj−1)N−sj−1sj\binom{N}{s_j}=\binom{N}{s_{j-1}}\frac{N-s_{j-1}}{s_j} gives ∑rqj(zr)=qj−1(z)\sum_r q_j(zr)=q_{j-1}(z), which is (a). For (b) and (c) we show by induction that Pr⁡[z≤j,Tj=T]=(Nsj)−1s0!sj!fj(z≤j;T)\Pr[z_{\leq j},T_j=T]=\binom{N}{s_j}^{-1}\frac{s_0!}{s_j!}f_j(z_{\leq j};T). It holds at j=0j=0 by (C1), T0T_0 being a uniform s0s_0-set. The set TjT_j is Tj−1T_{j-1} plus a uniform element of its complement, so

Pr⁡[z<j,Tj=T]=∑x∈TPr⁡[z<j,Tj−1=T∖{x}]N−sj−1=(Nsj−1)−1s0!sj−1!1N−sj−1∑rfj(z<jr;T),\Pr[z_{<j},T_j=T]=\sum_{x\in T}\frac{\Pr[z_{<j},T_{j-1}=T\setminus\{x\}]}{N-s_{j-1}}=\binom{N}{s_{j-1}}^{-1}\frac{s_0!}{s_{j-1}!}\frac{1}{N-s_{j-1}}\sum_r f_j(z_{<j}r;T),

the last step by (C2). The step probability is therefore needed only where ∑rfj(z<jr;T)>0\sum_r f_j(z_{<j}r;T)>0: a pair (z<j,T)(z_{<j},T) with a zero denominator is reached with probability zero. Multiplying by the step probability fj(z≤j;T)/∑rfj(z<jr;T)f_j(z_{\leq j};T)/\sum_r f_j(z_{<j}r;T) gives the claim, which yields (c) directly and (b) after summing over TT at j=kj=k. □

Weighted start. If (C1) is replaced by f0(∅;T)=g(T)≥0f_0(\varnothing;T)=g(T)\geq0 and T0T_0 is drawn with probability g(T)/W0g(T)/W_0, W0=∑∣T∣=s0g(T)W_0=\sum_{|T|=s_0}g(T), the remaining slots being added in a uniformly random order, the same induction gives Pr⁡[z≤j,Tj=T]=W0−1(N−s0sj−s0)−1fj(z≤j;T)\Pr[z_{\leq j},T_j=T]=W_0^{-1}\binom{N-s_0}{s_j-s_0}^{-1}f_j(z_{\leq j};T), with unchanged step probabilities; g≡1g\equiv1 is the lemma statement.

Remark 1 (Scope of the lemma). The step weight depends on the set TjT_j, not on the order inside it, and the identity (C2) is used only after summing over the sets: the pointwise identity ∑rfj(zr;Tj)=fj−1(z;Tj−1)\sum_r f_j(zr;T_j)=f_{j-1}(z;T_{j-1}) along one realised chain is false already for single photons, so a random order cannot be tested step by step on one chain. Conversely, chain-consistent weights always exist: fj=cjqjf_j=c_jq_j with cj=sjcj−1c_j=s_jc_{j-1} satisfies (C1)–(C2) for any qq. The lemma is therefore a criterion for cheap steps rather than for exact sampling, since every law has a chain rule. A step costs one evaluation of fj(z<jr;Tj)f_j(z_{<j}r;T_j) for all mm candidate rows rr, so the sampler is as fast as the chain-consistent family it uses. We know no lower bound on the cost of such families, for any of the inputs considered here.

Remark 2 (Fock inputs). For nn single photons in input modes tt, A=U[:,t]A=U[:,t], take N=nN=n, s0=0s_0=0 and fj(z;T)=∣Per⁡A[z,T]∣2f_j(z;T)=|\operatorname{Per} A[z,T]|^2. Condition (C2) is the Laplace expansion of the permanent along the last row followed by the orthonormality of the columns of AA, and q(z)=∣Per⁡A[z,[n]]∣2/n!q(z)=|\operatorname{Per} A[z,[n]]|^2/n! is the law of the ordered output. This is Clifford and Clifford’s algorithm B [2]; the mm candidate weights of a step share the jj cofactors Per⁡A[z<j,Tj∖{x}]\operatorname{Per} A[z_{<j},T_j\setminus\{x\}], all obtained from one Glynn sum over 2j−12^{j-1} sign vectors [2], collapsed to ∏ν(μν+1)\prod_\nu(\mu_\nu+1) terms when the placed rows repeat with multiplicities μν\mu_\nu [3] (Algorithm ??, Supplementary Material).

The lemma is used in three ways in what follows. Sections 3 and 4 construct a weight: one squared amplitude per set for superposed sources, a sum of RjR_j of them for photonic MPS. Section 5 conditions a chain: the Fock weight is kept, and part (c) starts the chain from given first rows. Section 6 does not use the lemma: the natural weight of a non-linear circuit is not chain-consistent, and the sampler is a rejection from linear branches. Figure 1 shows the four samplers next to the single-photon one.

Samplers of this paper shown as chains, including single-photon C&C reference, superposed sources, photonic matrix-product state, adaptive optics, and non-linear site

Figure 1. The samplers of this paper as chains, with the single-photon sampler of Clifford and Clifford as reference. Each panel shows the input preparation, the weight of the chain (a new weight, or the standard Fock weight), the row-by-row draw and, for adaptive optics and non-linear sites, the rejection loop: early abort with a new prefix for adaptive optics, rejection of the complete sample from the branch mixture for a non-linear site. Superposed sources and photonic MPS construct a weight (Secs. 3, 4), adaptive optics conditions the Fock chain (Sec. 5), and a non-linear site is sampled by rejection outside it (Sec. 6).

Loss and partial distinguishability

Uniform loss, one transmission η\eta per photon at the input where it commutes with the passive interferometer, is a mixture: every sampler first draws which photons survive and then runs on them, at the cost of the survivors. A lossy superposed source is a mixture of vacuum and a weaker superposed source, and for a photonic MPS the labels of the lost emissions are drawn first, which keeps the state of the kept emissions pure. Partial distinguishability is treated in the mixture (xx-)model, each photon or source independently in a common internal mode with probability xx and otherwise in an orthogonal mode of its own. For product inputs (single photons, superposed sources) a photon in its own mode is routed independently. For the other three samplers it is not independent of the rest and enters a joint draw: for a photonic MPS its output row is drawn with the lost labels and its slot becomes a fixed operator of the train; in an adaptive circuit it is drawn level by level inside the feed-forward, whose counts it changes; at a non-linear site it shares the branch index, and its amplitude enters the coherent branch sum. Details, and the cases not covered (a general Gram matrix of internal states, loss between two non-linear sites, inefficient adaptive detectors), are in the Supplementary Material, Sec. ??.

Superposed sources

Model. Each of nn sources emits the same state cos⁡α∣0⟩+sin⁡α∣1⟩\cos\alpha|0\rangle+\sin\alpha|1\rangle, source ii into input mode tit_i (unequal sources at the end of this section); the photons pass through an mm-mode interferometer UU and are detected with photon-number resolution [5]. A passive interferometer conserves photon number, so the detected count is exactly k∼Bin⁡(n,sin⁡2α)k\sim\operatorname{Bin}(n,\sin^2\alpha) whatever UU, and given kk the input is the Dicke state (nk)−1/2∑∣S∣=k∏i∈Sati†∣0⟩\binom{n}{k}^{-1/2}\sum_{|S|=k}\prod_{i\in S}a^\dagger_{t_i}|0\rangle. With A=U[:,t]A=U[:,t] (m×nm\times n, orthonormal columns), the amplitude of an ordered kk-row output zz is the rectangular permanent

Per⁡□A[z,[n]]=∑f:[k]↪[n]∏t=1kAztf(t)=∑∣S∣=kPer⁡A[z,S],\operatorname{Per}_{\Box} A[z,[n]]=\sum_{f:[k]\hookrightarrow[n]}\prod_{t=1}^{k}A_{z_t f(t)}=\sum_{|S|=k}\operatorname{Per} A[z,S],

and q(z)=(n−k)!n!∣Per⁡□A[z,[n]]∣2q(z)=\frac{(n-k)!}{n!}\left|\operatorname{Per}_{\Box}A[z,[n]]\right|^2. Here, as throughout, qq is a law on ordered tuples, collisions included: an occupation pattern ss with ∣s∣=k|s|=k has probability k!∏isi!q(z)\frac{k!}{\prod_i s_i!}q(z) for any ordering zz of ss.

At α=π/4\alpha=\pi/4 the mean count is n/2n/2 and the binomial upper tail carries the cost. The incoherent mixture of the same sources — each source firing with probability sin⁡2α\sin^2\alpha, which source fired being recorded — has the same photon-number law; it is single photons under input loss η=sin⁡2α\eta=\sin^2\alpha.

The offset-start order. A random order over the sources, not the photons, gives chain-consistent weights once the active set starts with n−kn-k sources instead of none: after the kk steps it then holds all nn, and the weight of a set is the rectangular permanent of the rows placed so far.

Proposition 1. For superposed sources conditioned on kk photons, N=nN=n, s0=n−ks_0=n-k and fj(z;T)=∣Per⁡□A[z,T]∣2f_j(z;T)=|\operatorname{Per}_{\Box}A[z,T]|^2 (jj rows, n−k+jn-k+j columns) are chain-consistent weights with target qq.

Proof. (C1): the empty rectangular permanent is 1. (C2): expand ∣Per⁡□A[z<j,T]∣2|\operatorname{Per}_{\Box}A[z_{<j},T]|^2 over the column xx used by the last row in each of the two injections; summing over rr, ∑rArxA‾rx′=δxx′\sum_r A_{rx}\overline{A}_{rx'}=\delta_{xx'} removes the cross terms and leaves ∑x∈T∣Per⁡□A[z<j,T∖{x}]∣2\sum_{x\in T}|\operatorname{Per}_{\Box}A[z_{<j},T\setminus\{x\}]|^2. Target: at j=kj=k the only set is T=[n]T=[n], and (nk)−1(n−k)!n!fk(z;[n])=q(z)\binom{n}{k}^{-1}\frac{(n-k)!}{n!}f_k(z;[n])=q(z). □\square

At k=nk=n the offset vanishes and the chain is Clifford and Clifford’s. At k<nk<n the n−kn-k sources that supply no photon are never identified. Part (a) of the lemma recovers the true marginal qj(z)∝∑∣R∣=k−j∣Per⁡□A[z<j,[n]∖R]∣2q_j(z)\propto\sum_{|R|=k-j}|\operatorname{Per}_{\Box}A[z_{<j},[n]\setminus R]|^2, the residual-set form that a direct sampler would have to enumerate.

The step. With j−1j-1 rows placed, the mm candidate weights share the cofactors Px=Per⁡□A[z<j,Tj∖{x}]P_x=\operatorname{Per}_{\Box}A[z_{<j},T_j\setminus\{x\}], x∈Tjx\in T_j, and w(r)=∣∑x∈TjArxPx∣2w(r)=|\sum_{x\in T_j}A_{rx}P_x|^2. Glynn’s identity [20] with one sign per placed row gives every cofactor at once,

Px=2−(j−1)∑δ∈{±1}j−1(∏tδt)ej−1(a(δ)∖ax(δ)),ai(δ)=∑tδtAzti,P_x=2^{-(j-1)}\sum_{\delta\in\{\pm1\}^{j-1}}\left(\prod_t\delta_t\right)e_{j-1}\bigl(a(\delta)\setminus a_x(\delta)\bigr),\qquad a_i(\delta)=\sum_t\delta_t A_{z_ti},

ej−1e_{j-1} the elementary symmetric polynomial of degree j−1j-1 of the ∣Tj∣−1|T_j|-1 values other than axa_x. Since ej−1e_{j-1} is homogeneous, the global flip δ→−δ\delta\to-\delta leaves the summand invariant and 2j−22^{j-2} signs suffice. The leave-one-out value ej−1(a∖ax)e_{j-1}(a\setminus a_x) is the coefficient of λj−1\lambda^{j-1} in ∏i≠x(1+λai)\prod_{i\ne x}(1+\lambda a_i), and since the offset is constant along the chain, ∣Tj∣−j=s0|T_j|-j=s_0, also the coefficient of μs0\mu^{s_0} in ∏i≠x(μ+ai)\prod_{i\ne x}(\mu+a_i). Prefix and suffix products of the linear factors, truncated at degree d=min⁡(j−1,s0)d=\min(j-1,s_0) in whichever variable is shorter, give every leave-one-out value without division in O(∣Tj∣(d+1))O(|T_j|(d+1)); a cheaper division, stable in one direction, is described in Sec. ??. At s0=0s_0=0 this is the all-but-one product of the single-photon step, so at k=nk=n the chain is Clifford and Clifford’s step for step, payload included. The collapse of repeated rows [3] applies unchanged to the sign sum: placed rows repeated with multiplicities μν\mu_\nu contribute ∏ν(μν+1)\prod_\nu(\mu_\nu+1) terms instead of 2j−12^{j-1}, walked in the same reflected Gray order as for single photons. The cost of a step is O(∏ν(μν+1)∣Tj∣(d+1)+m∣Tj∣)O(\prod_\nu(\mu_\nu+1)|T_j|(d+1)+m|T_j|) and of a sample at most

C(k)=O(2kn2+mnk),Ek[C]≤O(E[2k]n2+mn2)=O((1+sin⁡2α)n2+mn2),C(k)=O(2^k n^2+mnk),\qquad\mathbb{E}_k[C]\le O\left(\mathbb{E}[2^k]n^2+mn^2\right)=O\left((1+\sin^2\alpha)n^2+mn^2\right),

the exponent of single photons under loss η=sin⁡2α\eta=\sin^2\alpha; the collapse lowers the term count as it does for single photons [3]. Loss and partial distinguishability are drawn before the chain (Sec. 2). Algorithm ?? (Supplementary Material); validation in Sec. 8.1.

Unequal sources. Proposition 1 extends to sources ai∣0⟩+bi∣1⟩a_i|0\rangle+b_i|1\rangle with different amplitudes, ai≠0a_i\ne0. With ui=bi/aiu_i=b_i/a_i and the scaled columns A~=U[:,t]diag⁡(u)\widetilde{A}=U[:,t]\operatorname{diag}(u), the output amplitude given kk photons is Per⁡□A~[z,[n]]\operatorname{Per}_{\square}\widetilde{A}[z,[n]] up to a constant, and the weights fj(z;T)=g(T)∣Per⁡□A~[z,T]∣2f_j(z;T)=g(T)|\operatorname{Per}_{\square}\widetilde{A}[z,T]|^2, g(T)=∏i∈T∣ui∣−2g(T)=\prod_{i\in T}|u_i|^{-2}, satisfy (C2): expanding the last row now leaves ∑x∈T∣ux∣2∣Per⁡□A~[z<j,T∖{x}]∣2\sum_{x\in T}|u_x|^2|\operatorname{Per}_{\square}\widetilde{A}[z_{<j},T\setminus\{x\}]|^2, and g(T)∣ux∣2=g(T∖{x})g(T)|u_x|^2=g(T\setminus\{x\}). With the weighted start of Sec. 2, T0T_0 drawn among the (n−k)(n-k)-sets with probability ∝∏i∈T0∣ui∣−2\propto\prod_{i\in T_0}|u_i|^{-2} (a polynomial draw by elementary symmetric polynomials), the chain samples the output law conditioned on kk, whose photon number is the Poisson-binomial law of the ∣bi∣2|b_i|^2. The factor gg cancels in every step, so a step is that of equal sources on the columns of A~\widetilde{A}: dim sources are more likely to start in the unused set. A source with bi=0b_i=0 never fires and is removed; one with ai=0a_i=0 always fires and never enters T0T_0. An exact enumeration of this chain over initial sets, orders and output rows reproduces the output law of five random instances with unequal sources, n≤5n\le5, to 2×10−162\times10^{-16}; our GPU implementation covers equal sources.

Photonic matrix-product states

Model. A quantum emitter with an internal memory of dimension χ\chi (a spin, χ=2\chi=2; for instance a quantum-dot spin driven to emit linear graph states [9]) emits nn photons one after the other; emission ss puts one photon into one of LL input modes ts,lt_{s,l} with operator Ml(s)M_l^{(s)} (χ×χ\chi\times\chi), and the photonic state is the matrix-product state [7]

∣ψ⟩=∑x∈[L]n⟨out∣Mxn(n)⋯Mx1(1)∣in⟩∣x⟩,∣x⟩=∏sats,xs†∣0⟩,|\psi\rangle=\sum_{x\in[L]^n}\langle\mathrm{out}|M_{x_n}^{(n)}\cdots M_{x_1}^{(1)}|\mathrm{in}\rangle|x\rangle,\qquad|x\rangle=\prod_s a_{t_{s,x_s}}^\dagger|0\rangle,

with ∣in⟩|\mathrm{in}\rangle and ∣out⟩|\mathrm{out}\rangle the initial and final emitter states and all nLnL input modes distinct (dual-rail time bins for L=2L=2); a traced final emitter state is a first draw. The caterpillar (spin-photon cluster) states [8] are Ml(s)=∣l⟩⟨l∣GsM_l^{(s)}=|l\rangle\langle l|G_s with spin gates GsG_s. The model contains single-photon boson sampling (χ=1\chi=1, L=1L=1, M1(s)=1M_1^{(s)}=1), so exact sampling from it is at least as hard, in the worst case, as from Fock inputs [1]; what is known for a fixed train is summarised in the Supplementary Material, Sec. ??.

We assume ⟨ψ∣ψ⟩=1\langle\psi|\psi\rangle=1: the emissions are isometric, ∑lMl(s)†Ml(s)=1\sum_l M_l^{(s)\dagger}M_l^{(s)}=1, and a traced final emitter state is drawn first, with probability poutp_{\mathrm{out}}; the displayed amplitudes are then divided by pout\sqrt{p_{\mathrm{out}}}, ψ(x)=⟨out∣Wx∣in⟩/pout\psi(x)=\langle\mathrm{out}|W_x|\mathrm{in}\rangle/\sqrt{p_{\mathrm{out}}} with Wx=Mxn(n)⋯Mx1(1)W_x=M_{x_n}^{(n)}\cdots M_{x_1}^{(1)}, or equivalently ⟨out∣\langle\mathrm{out}| is rescaled.

Weights. The slots are the emissions, N=nN=n, s0=0s_0=0. For a set TT of emissions let ρT=Tr⁡T∣ψ⟩⟨ψ∣\rho_T=\operatorname{Tr}_T|\psi\rangle\langle\psi|, a state of ∣T∣|T| photons, and for z∈[m]∣T∣z\in[m]^{|T|} let ⟨vz∣\langle v_z| be the covector

⟨vz∣ϕ⟩=∑xTPer⁡U[z,tT,xT]ϕ(xT),\langle v_z|\phi\rangle=\sum_{x_T}\operatorname{Per}U[z,t_{T,x_T}]\phi(x_T),

the amplitude of the ordered output zz for a ∣T∣|T|-photon state ϕ\phi on the modes tTt_T; the components of the ket ∣vz⟩|v_z\rangle are the conjugates Per⁡U[z,tT,xT]‾\overline{\operatorname{Per}U[z,t_{T,x_T}]}. Then fj(z;T)=⟨vz∣ρT∣vz⟩f_j(z;T)=\langle v_z|\rho_T|v_z\rangle is chain-consistent: (C1) is the trace; for (C2), expand both permanents of fj(z<j;T)f_j(z_{<j};T) along the last row, Per⁡U[z<j,tT,xT]=∑c∈TUr,tc,xcPer⁡U[z<j,tT∖c,xT∖c]\operatorname{Per} U[z_{<j},t_T,x_T]=\sum_{c\in T}U_{r,t_c,x_c}\operatorname{Per} U[z_{<j},t_{T\setminus c},x_{T\setminus c}]; the sum over rr gives ∑rUr,tc,xcU‾r,tc′,yc′=δcc′δxcyc\sum_r U_{r,t_c,x_c}\overline{U}_{r,t_c',y_c'}=\delta_{cc'}\delta_{x_cy_c} because the nLn_L input modes are distinct, and ∑xTρT(xT,yT)∣yc=xc=ρT∖c\sum_{x_T}\rho_T(x_T,y_T)|_{y_c=x_c}=\rho_{T\setminus c} leaves ∑c∈Tfj−1(z<j;T∖c)\sum_{c\in T}f_{j-1}(z_{<j};T\setminus c). The target is the output law of ψ\psi. The order must be uniformly random: with a fixed emission order the weights are not the marginals of one law (TVD 0.22 against a floor of 0.05 on a three-photon linear cluster).

Gapwise Kraus contraction. ρT\rho_T is mixed because the emissions outside TT are traced, and for a random order TT is an arbitrary subset of the train: its complement splits into disjoint maximal runs of traced emissions, the gaps. A contraction of ρT\rho_T with the transfer map X↦∑lMlXMl†X\mapsto\sum_l M_lXM_l^\dagger handles a gap in time linear in its length — it is how a matrix-product state is sampled site by site with a chain rule over its own modes [22, §6.2.4] — but it yields a density matrix, not the sum of squared amplitudes that our chain over output rows and Glynn’s sum need; a pure-state unravelling of the traced labels would enumerate the L∣g∣L^{|g|} label strings of every gap gg. The following proposition compresses each gap’s transfer map into at most χ2\chi^2 Kraus operators, whatever its length, and so keeps a sum of squared amplitudes with few terms.

Proposition 2 (Gapwise Kraus contraction). Let T={c1<⋯<cj}T=\{c_1<\cdots<c_j\}, and for a gap gg (a maximal run of emissions not in TT) let Axg(g)A_{x_g}^{(g)} be the ordered product of its emission operators and Eg(X)=∑xgAxg(g)XAxg(g)†E_g(X)=\sum_{x_g}A_{x_g}^{(g)}XA_{x_g}^{(g)\dagger} its map on χ×χ\chi\times\chi matrices. Choose any Kraus decomposition Eg(X)=∑iQg,iXQg,i†E_g(X)=\sum_i Q_{g,i}XQ_{g,i}^\dagger of every inner gap (between c1c_1 and cjc_j), any vectors with ∑xAx∣in⟩⟨in∣Ax†=∑i∣ξi⟩⟨ξi∣\sum_x A_x|{\rm in}\rangle\langle{\rm in}|A_x^\dagger=\sum_i|\xi_i\rangle\langle\xi_i| for the prefix gap (before c1c_1) and any covectors with ∑xAx†∣out⟩⟨out∣Ax=∑i∣ϕi⟩⟨ϕi∣\sum_x A_x^\dagger|{\rm out}\rangle\langle{\rm out}|A_x=\sum_i|\phi_i\rangle\langle\phi_i| for the suffix gap (after cjc_j). For a choice ee of one index per gap let

ψe(xT)=⟨ϕisuf∣Mxcj(cj)Qgj−1,ij−1⋯Qg1,i1Mxc1(c1)∣ξipre⟩.\psi_e(x_T)=\langle\phi_{i_{\rm suf}}|M_{x_{c_j}}^{(c_j)}Q_{g_{j-1},i_{j-1}}\cdots Q_{g_1,i_1}M_{x_{c_1}}^{(c_1)}|\xi_{i_{\rm pre}}\rangle.

(an absent gap contributes the identity, or ∣in⟩|{\rm in}\rangle, ⟨out∣\langle{\rm out}| at the ends). Then ρT=∑e∣ψe⟩⟨ψe∣\rho_T=\sum_e|\psi_e\rangle\langle\psi_e|, and every ψe\psi_e is a matrix-product state of bond dimension χ\chi on the emissions of TT. Inner gaps have Kraus rank at most χ2\chi^2 and end gaps at most χ\chi, so the number of terms is Rj≤min⁡(Ln−j,χ2gin+gend)R_j\le\min(L^{n-j},\chi^{2g_{\rm in}+g_{\rm end}}), with ging_{\rm in} inner and gend≤2g_{\rm end}\le2 end gaps.

Proof. ρT(xT,yT)=∑xTcψ(xTxTc)ψ(yTxTc)‾\rho_T(x_T,y_T)=\sum_{x_{T^c}}\psi(x_Tx_{T^c})\overline{\psi(y_Tx_{T^c})}. Read ψ(x)ψ(y)‾\psi(x)\overline{\psi(y)} as ⟨out∣Wx∣in⟩⟨in∣Wy†∣out⟩\langle{\rm out}|W_x|{\rm in}\rangle\langle{\rm in}|W_y^\dagger|{\rm out}\rangle with Wx=Mxn(n)⋯Mx1(1)W_x=M_{x_n}^{(n)}\cdots M_{x_1}^{(1)}, and contract from the right: starting from X=∣in⟩⟨in∣X=|{\rm in}\rangle\langle{\rm in}|, a kept emission cc maps X↦Mxc(c)XMyc(c)†X\mapsto M_{x_c}^{(c)}XM_{y_c}^{(c)\dagger}, and the labels of a gap occur only in that gap’s factors, once on each side, so summing them maps X↦Eg(X)X\mapsto E_g(X). Each EgE_g may be replaced by any of its Kraus decompositions, the prefix gap by the vectors ∣ξi⟩|\xi_i\rangle and the suffix gap by the covectors ⟨ϕi∣\langle\phi_i|; expanding the products of sums gives ∑eψe(xT)ψe(yT)‾\sum_e\psi_e(x_T)\overline{\psi_e(y_T)}. The Choi matrix of EgE_g is χ2×χ2\chi^2\times\chi^2, which bounds an inner gap’s Kraus rank by χ2\chi^2; the end gaps produce positive χ×χ\chi\times\chi matrices, rank at most χ\chi. The bound Ln−jL^{n-j} is the explicit sum over the traced labels. □\square

We take the minimal decompositions, by an SVD of the stacked Axg(g)A_{x_g}^{(g)} reduced emission by emission, so the cost of a gap is linear in its length. For instance, with n=3n=3 and T={1,3}T=\{1,3\}, the middle emission is a gap of length one, E(X)=∑lMl(2)XMl(2)†E(X)=\sum_l M_l^{(2)}XM_l^{(2)\dagger}, and ψe(x1,x3)=⟨out∣Mx3(3)QeMx1(1)∣in⟩\psi_e(x_1,x_3)=\langle{\rm out}|M_{x_3}^{(3)}Q_eM_{x_1}^{(1)}|{\rm in}\rangle with e≤min⁡(L,χ2)e\le\min(L,\chi^2) terms.

Matrix-valued Glynn sums. So fj=∑e∣⟨vz∣ψe⟩∣2f_j=\sum_e|\langle v_z|\psi_e\rangle|^2, a sum of RjR_j squared amplitudes, and each amplitude factorises through the matrix product inside Glynn’s sum. With column sums sc,l(δ)=∑iδiUzi,tc,xcs_{c,l}(\delta)=\sum_i\delta_iU_{z_i,t_c,x_c} and Gc(δ)=∑lsc,l(δ)M~l(c)G_c(\delta)=\sum_l s_{c,l}(\delta)\widetilde{M}_l^{(c)}, M~l(c)\widetilde{M}_l^{(c)} the kept emission’s operator with the Kraus operator of the gap before it absorbed,

⟨vz∣ψe⟩=2−(j−1)∑δ∈{+1}×{−1}j−1(∏iδi)⟨oute∣Gcj(δ)⋯Gc1(δ)∣ine⟩.\langle v_z|\psi_e\rangle=2^{-(j-1)}\sum_{\delta\in\{+1\}\times\{-1\}^{j-1}}\left(\prod_i\delta_i\right)\langle{\rm out}_e|G_{c_j}(\delta)\cdots G_{c_1}(\delta)|{\rm in}_e\rangle.

because Glynn’s formula Per⁡B=2−(j−1)∑δ1=1(∏iδi)∏c(∑iδiBic)\operatorname{Per} B=2^{-(j-1)}\sum_{\delta_1=1}\left(\prod_i\delta_i\right)\prod_c(\sum_i\delta_iB_{ic}), applied to Bic=Uzi,tc,xcB_{ic}=U_{z_i,t_c,x_c}, is multilinear in the columns and the sum over xTx_T passes inside the product. For the Laplace step the last row is left out: the candidate amplitude is ∑c∈T∑lUr,tc,lTr⁡(M~l(c)Kc)\sum_{c\in T}\sum_l U_{r,tc,l}\operatorname{Tr}(\widetilde{M}^{(c)}_l K_c) with the matrix cofactors

Kc=2−(j−2)∑δ∈{+1}×{±1}j−2(∏iδi)pc(δ)qc(δ)T,K_c = 2^{-(j-2)} \sum_{\delta\in\{+1\}\times\{\pm1\}^{j-2}} \left(\prod_i \delta_i\right) p_c(\delta)q_c(\delta)^{T},
pc=Gc−1⋯Gc1∣ine⟩,qcT=⟨oute∣Gcj⋯Gc+1,p_c = G_{c-1}\cdots G_{c_1}\lvert\mathrm{in}_e\rangle,\qquad q_c^{T} = \langle\mathrm{out}_e\lvert G_{c_j}\cdots G_{c+1},

where c−1c-1 and c+1c+1 denote the kept emissions before and after cc in TT (not the emissions c∓1c\mp1), and the Glynn sum runs over the j−1j-1 placed rows (the global flip leaves the summand of a (j−1)×(j−1)(j-1)\times(j-1) permanent invariant) — the scalar prefix and suffix products of the Fock kernel replaced by χ×χ\chi\times\chi ones. For j≥2j\ge2; at j=1j=1 no row is placed and Kc1=∣ine⟩⟨oute∣K_{c_1}=\lvert\mathrm{in}_e\rangle\langle\mathrm{out}_e\lvert. The 2020 collapse acts on δ\delta only and carries over unchanged. Algorithm ?? (Supplementary Material).

The term count. With CjC_j Glynn terms (2j−22^{j-2}, fewer after the collapse), a step costs O(Rj(CjjLχ2+mjL))O(R_j(C_jjL\chi^2+m_jL)): per term and sign vector, jj matrices GcG_c and the prefix and suffix sweeps, then the mm candidates. Measured means of RjR_j are far below the bound of Proposition 2, peaking at j≈n/2.5j\approx n/2.5 (7 at n=8n=8, 30 at n=12n=12, 96 at n=16n=16 on a linear cluster) and falling to 1–2 on the last steps, which carry the 2j2^j weight. The per-gap decomposition is minimal gap by gap but not globally; comparing RjR_j with the rank of ρT\rho_T over all steps, the surplus is up to 16×16\times on single early steps but, weighted by step cost, 1.021.02–1.11×1.11\times for n=8n=8–20. Since the rank is the smallest number of terms any decomposition of ρT\rho_T can have, a better decomposition would save at most about 10% of the run time.

Adaptive linear optics

Model. nn single photons enter U0U_0; KK output modes a1…aKa_1\ldots a_K are read with photon-number resolution in Λ\Lambda levels, and after each level a classical function of the counts p≤λp_{\le\lambda} read so far chooses the unitary VλV_\lambda applied to the unmeasured modes [10]. Each adaptive outcome pp has its cumulative unitary UpU^p and P(p,s)=∣Per⁡Up[(p,s),t]∣2/(p!s!)P(p,s)=\lvert\operatorname{Per}U^p[(p,s),t]\rvert^2/(p!s!), with (p,s)(p,s) the output occupations read as a tuple of rows and p!p!, s!s! the products of the factorials of the counts. Oh and Lim [11] show that mean values of a restricted class of observables are estimable in polynomial time for K=O(1)K=O(1) and BQP-complete for K=poly⁡(n)K=\operatorname{poly}(n), and sample exactly and efficiently when the input and the final measurement are Gaussian and K=O(log⁡m)K=O(\log m); for Fock input with photon-number-resolved final detection they give marginals and mean values, not a sampler.

Stage 1: the adaptive outcome. P(p≤λ)P(p_{\le\lambda}) depends on Up<λU^{p_{<\lambda}} only, since later VV act on modes that are traced in it; the outcomes form a chain over levels whose conditionals are KλK_\lambda-mode marginals of a non-adaptive sampler. We compute them exactly with the generating-function algorithm of Ivanov and Gurvits [21], as used by Oh and Lim [11]: the generating function of the counts on a set A\mathcal{A} of adaptive modes is Per⁡(1+V†(Z−1)V)\operatorname{Per}(1+V^\dagger(Z-1)V), V=U[A,t]V=U[\mathcal{A},t], Z=diag⁡(ζa)a∈AZ=\operatorname{diag}(\zeta_a)_{a\in\mathcal{A}} formal variables, whose coefficients are the binomial moments M[p]M[p], accumulated photon by photon on a table graded by total degree and inverted. This fits for K≤4K\le4 at n=38n=38. Beyond, the counts of level λ\lambda can be read from a stage-2 chain on Up<λU^{p_{<\lambda}} conditioned on the earlier counts p<λp_{<\lambda} and accepted with probability P(p≤λ)/M[p≤λ]P(p_{\le\lambda})/M[p_{\le\lambda}]; the later unitaries act on unmeasured modes, so the draw is exact. We did not implement this case.

Stage 2: conditioning by the lemma. The final counts given pp are the Fock output of UpU^p conditioned on “the adaptive modes show exactly pp”. By exchangeability of the ordered law this is the conditional given “the first r=∣p∣r=|p| rows are apa^p (the adaptive modes with multiplicity) and no later row is adaptive”. Part (c) of the lemma turns the first half into a draw: the active set after rr rows has law ∝∣Per⁡Up[ap,S]∣2\propto\lvert\operatorname{Per}U^p[a^p,S]\rvert^2. Because apa^p has only KK distinct rows, a permanent with repeated rows is a coefficient of a product of linear forms, Per⁡Up[ap,S]=p![xp]∏j∈S(Bj⋅x)\operatorname{Per}U^p[a^p,S]=p![x^p]\prod_{j\in S}(B_j\cdot x) with Bj=Up[a,tj]∈CKB_j=U^p[a,t_j]\in\mathbb{C}^K and p!=∏ipi!p!=\prod_i p_i!, and deciding the columns one by one from suffix tables of ∏i≥j(1+(Bi⋅x)(Bˉi⋅w))\prod_{i\ge j}(1+(B_i\cdot x)(\bar{B}_i\cdot w)) draws SS from this posterior with tables of ∏i(pi+1)2\prod_i(p_i+1)^2 entries, polynomial for fixed KK (proof in the Supplementary Material, Sec. ??). The chain then continues with ordinary Clifford–Clifford steps. The remaining constraint. The second half — no later photon on an adaptive mode — is not a chain-consistent weight: restricting the rows to the non-adaptive modes makes the columns of the interferometer sub-orthonormal, and the Gram matrix 1−V†V1-V^\dagger V then couples different hidden sets, so (C2) fails. It is enforced by rejection with early abort: a chain is discarded at the first photon that lands on an adaptive mode. A chain is accepted with probability P(p)/M[p]P(p)/M[p], MM the binomial moments: by exchangeability, P(p)P(p) and M[p]M[p] are the probabilities that the first rr rows are apa^p with and without the constraint, each multiplied by the same factor n!/((n−r)!p!)n!/((n-r)!p!).

Cost. A branch pp starts MUp[p]/P(p)M_{U^p}[p]/P(p) chains, MUpM_{U^p} the binomial moments of its own interferometer, so the mean number of chains started per sample is ∑p:P(p)>0MUp[p]\sum_{p:P(p)>0} M_{U^p}[p], over the outcomes that occur. For a fixed interferometer, Up=UU^p=U, and when every outcome has positive probability, the generating function of the binomial moments turns this into E[2r]=Per⁡(1+V†V)\mathbb{E}[2^r]=\operatorname{Per}(1+V^\dagger V), r=∣p∣r=|p| the number of photons the adaptive modes receive; with feed-forward the moments of different outcomes come from different interferometers and no such closed form holds. Most rejected chains stop early: given the forced prefix, the remaining n−rn-r rows are exchangeable, so a chain with h≥1h\ge1 further photons on the adaptive modes places them at a uniformly random hh-subset of its free steps and stops at the first, JJ, at step (n−r+1)/(h+1)(n-r+1)/(h+1) on average; with a step cost growing like ϱj\varrho^j, it is charged (ϱr+J−ϱr)/(ϱn−1)(\varrho^{r+J}-\varrho^r)/(\varrho^n-1) of a full chain. A cost model built on the first-level interferometer, at m=2nm=2n and n=38n=38, gives E[2r]=2.0\mathbb{E}[2^r]=2.0, 3.8, 6.8 chains for K=1,2,3K=1,2,3 and a time per sample X=1.03X=1.03, 1.07, 1.10 times the plain sampler’s; with a Haar policy we measure 2.1 and 4.1 chains per sample on average for K=1,2K=1,2 at n=30n=30–38 (1.8–2.3 and 3.5–4.7 per point, 256 samples each). Algorithms ?? and ?? (Supplementary Material).

Non-linear sites

Model. A single-mode phase e−if(n^x)e^{-if(\hat n_x)} acts on mode xx between Haar interferometers U0U_0 and U1U_1; the response is a Kerr phase, f(j)=φj2f(j)=\varphi j^2 [12], or any response diagonal in the photon number. On nn photons n^x\hat n_x has eigenvalues 0..n0..n, so the response is exactly a finite sum of phase shifters, e−if(n^x)=∑ℓcℓeiθℓn^xe^{-if(\hat n_x)}=\sum_\ell c_\ell e^{i\theta_\ell\hat n_x}, and the circuit is a coherent sum of BB linear interferometers Ub=U1Dx(θb)U0U_b=U_1D_x(\theta_b)U_0 with weights cbc_b. The decomposition is not unique; we use the shortest periodic one: the response e−if(j)e^{-if(j)} on j=0..nj=0..n is a linear phase eiaje^{iaj} times a function of smallest period q≤nq\le n, expanded on its qq-point discrete Fourier transform, θℓ=a+2πℓ/q\theta_\ell=a+2\pi\ell/q, so that B≤qB\le q and ∥c∥2=1\lVert c\rVert_2=1. B=1B=1 at φ=0\varphi=0 and φ=π\varphi=\pi, 2 at π/2\pi/2, 4 at π/4\pi/4, and nn for a response without short period, such as φ=1\varphi=1; several sites multiply the branches.

Failure of (C2). For a linear circuit the traced photons contribute Per⁡[G[Tc,Sc]]=δST\operatorname{Per}[G^{[T^c,S^c]}]=\delta_{ST} with G=U†U=1G=U^\dagger U=1 (Remark 2), so the marginal is diagonal in the hidden set. Here two branches meet through Gbb′=Ub′†Ub=1+(ei(θb−θb′)−1)ww†G_{bb'}=U_{b'}^\dagger U_b=1+(e^{i(\theta_b-\theta_{b'})}-1)ww^\dagger, w=U0†exw=U_0^\dagger e_x, whose rank-one term couples different hidden sets. The natural set weight fj(z;T)=∣∑bcbPer⁡Ub[z,T]∣2f_j(z;T)=\left|\sum_b c_b\operatorname{Per} U_b[z,T]\right|^2 therefore violates (C2): the random-order chain built on it misses the law by a TVD of 0.115 at n=3n=3, m=4m=4, Kerr 0.9, where the same enumeration reproduces a linear circuit to 10−1510^{-15}. The marginal, the cost of the true-marginal chain and the purifications we tried are in the Supplementary Material, Sec. ??.

Rejection from the branch mixture. Draw a branch bb with probability ∣cb∣/∥c∥1|c_b|/\lVert c\rVert_1, an ordinary Fock sample ss of UbU_b (the Fock kernels unchanged), and accept with probability ∣∑bcbab(s)∣2/(∥c∥1∑b∣cb∣∣ab(s)∣2)|\sum_b c_ba_b(s)|^2/(\lVert c\rVert_1\sum_b|c_b||a_b(s)|^2), ab(s)=Per⁡Ub[s,t]/s!a_b(s)=\operatorname{Per}U_b[s,t]/\sqrt{s!} the amplitude of the occupation ss. By Cauchy–Schwarz, ∣∑bcbab∣2≤∥c∥1∑b∣cb∣∣ab∣2|\sum_b c_ba_b|^2\le\lVert c\rVert_1\sum_b|c_b||a_b|^2, so this is a probability. The proposal draws ss with probability ∥c∥1−1∑b∣cb∣∣ab∣2\lVert c\rVert_1^{-1}\sum_b|c_b||a_b|^2, so is proposed and accepted with probability ∣∑bcbab(s)∣2/∥c∥12|\sum_b c_ba_b(s)|^2/\lVert c\rVert_1^2: proportional to the target, and summing to 1/∥c∥121/\lVert c\rVert_1^2 because ∑s∣∑bcbab(s)∣2=∥∑bcbUb∣t⟩∥2=1\sum_s|\sum_b c_ba_b(s)|^2=\lVert\sum_b c_bU_b|t\rangle\rVert^2=1, the circuit being unitary. The sampler is exact, with acceptance probability exactly 1/∥c∥121/\lVert c\rVert_1^2 (measured 0.43–0.59 against 0.50 at ∥c∥12=2\lVert c\rVert_1^2=2; 0.054–0.077 against 0.0625 at B=16B=16). An accepted sample costs (1+κB)∥c∥12(1+\kappa B)\lVert c\rVert_1^2 Fock samples, κ=0.55±0.08\kappa=0.55\pm0.08 the measured cost of one branch permanent. For a fixed number of sites and a response of bounded period (B=O(1)B=O(1)) this is a constant factor and the exponential rate in nn is that of single photons; for a generic response B=O(n)B=O(n) and the factor is polynomial. Algorithm ?? (Supplementary Material). This is the ∣cb∣\lvert c_b\rvert-weighted specialisation of the rejection principle of Dias and König [15], applied to the branch decomposition with weights ∣cb∣\lvert c_b\rvert instead of ∣cb∣2\lvert c_b\rvert^2: by Cauchy–Schwarz ∥c∥12≤B∥c∥22\lVert c\rVert_1^2 \le B\lVert c\rVert_2^2, and for a given decomposition the weights ∣cb∣\lvert c_b\rvert minimise the constant (at φ=π/2\varphi= \pi/2 the two coincide, ∥c∥12=B=2\lVert c\rVert_1^2 = B = 2; at φ=1\varphi= 1, n=40n = 40, 33.2 against 40). The constant ∥c∥12\lVert c\rVert_1^2 depends on the decomposition: another set of phase shifters, not restricted to the discrete Fourier frequencies, can lower it, possibly with more branches; all the numbers here use the shortest periodic one. Spagnolo et al.’s exact simulation replaces the site by a linear-optical gadget with ancillary photons and postselection [12]; the branch form needs no ancilla, and its acceptance probability is known in closed form.

Weak non-linearities and several sites. For a fixed nn the rejection factor ∥c∥12\lVert c\rVert_1^2 tends to one as φ→0\varphi\to0, but it is governed by φn2\varphi n^2 rather than φ\varphi. A Kerr phase φ=0.01\varphi= 0.01 already costs ∥c∥12=8.6\lVert c\rVert_1^2 = 8.6 at n=40n = 40, while φ=π/2\varphi= \pi/2 costs 2. Over LL sites at φ=π/2\varphi= \pi/2 the rejection factor is 2L2^L, and each proposal evaluates 2L2^L branch amplitudes, about 4L4^L in all, so the exponent changes once the number of sites grows with nn. A chain-consistent family for ∑bcbUb\sum_b c_b U_b with polynomially many terms per set would avoid the rejection and make a weak non-linearity cheap; we know none, and no lower bound that would exclude one.

Comparison of the samplers

Table 1 compares the samplers and evaluates their step cost and overhead over single photons.

input / circuitslotss0s_0weight fj(z;T)f_j(z;T)termsstep costoverhead over single photons
single photonsphotons0∣Per⁡A[z,T]∣2\lvert\operatorname{Per} A[z,T]\rvert^21$2^j j + m j$—
superposed sourcessourcesn−kn-k∣Per⁡□A[z,T]∣2\lvert\operatorname{Per}_{\Box} A[z,T]\rvert^212j∣T∣(d+1)+m∣T∣2^j \lvert T\rvert(d+1) + m\lvert T\rvertpayload factor ∣T∣(d+1)/j\lvert T\rvert(d+1)/j, d=min⁡(j−1,s0)d=\min(j-1,s_0)
photonic MPSemissions0⟨vz∣ρT∣vz⟩\langle v_z\vert\rho_T\vert v_z\rangleRjR_jRj(2jjLχ2+mjL)R_j(2^j j L\chi^2 + m j L)term count RjR_j
adaptive opticsphotons0∣Per⁡Up[z,T]∣2\lvert\operatorname{Per} U^p[z,T]\rvert^2, started by (c)1$2^j j + m j$rejection of chains that put a further photon on an adaptive mode: ∑pMUp[p]\sum_p M_{U^p}[p] chains
non-linear sitephotons—none known—$2^j j + m j$ per branch samplerejection, (1+κB)∥c∥12(1+\kappa B)\lVert c\rVert_1^2
any input, generic chain [6]photons0the true marginal cjqjc_j q_j—(input pairs) ×\times subsetsnone of its own; no speed-up
any superposition [15]——none (rejection)—one component sample and the target amplitudemixture of NcN_c components: Nc∥β∥22N_c\lVert\beta\rVert_2^2

Table 1. How the four methods use — or depart from — the set chain; step costs up to constants, jj placed photons, mm candidate rows, before the collision collapse of Ref. [3]. Loss is drawn before the chain in every row; indistinguishability as in § 1.2.

Numerical evaluation

Validation

Every sampler is checked on small instances, within reach of strong simulation, through the same call and GPU backend as the cost measurements of § 2.6.2. The statistic is the total variation distance (TVD) between the empirical distribution of S=4⋅104S = 4 \cdot10^4 samples and the oracle’s. Its reference is the TVD of an exact draw of the same size: we draw 40 multinomial samples of size SS from the oracle’s distribution and take the mean and the standard deviation of their TVD, so that a correct sampler gives a ratio near one and a deviation zz of order one. This reference stays valid when the output space is large against SS, where the normal approximation of the shot noise overestimates it.

Oracles. Each oracle shares no code with the sampler it checks. The strong simulation is SLOS [23], in kernels of our code base: on the Fock input for single photons; on the coherent product state, layer by layer in the photon number, for superposed sources, with loss as a thinning of the layers and the xx-model as an enumeration over the sources in the common mode; on the matrix-product state, traced or projected, for photonic MPS, with loss by thinning; once per adaptive outcome for adaptive optics; and once per branch, summed coherently, for non-linear sites, where it agrees to 10−1610^{-16} with two dense references, the gate-by-gate state and the branch sum of permanents. Two further checks use none of our code. For superposed sources, Perceval’s SLOS backend [24] on the coherent product StateVector agrees within shot noise (Supplementary Material, Sec. ??), and the exact law of the algorithm, enumerated over every source order and every branch, equals qq to 10−1310^{-13} on six instances with n≤5n \le5.

The Supplementary Material (Sec. ??, Table ??) lists 19 instances: single photons, superposed sources with loss and partial distinguishability, traced and projected MPS trains up to L=3L = 3 and χ=3\chi= 3, lossy trains, adaptive circuits with one to three levels, and one or two non-linear sites. On all of them the measured TVD stays within 1.7 standard deviations of an exact draw.

Cost

Table 2 gives the cost of each sampler relative to the single-photon sampler [3] on an instance of the same size, both run on one NVIDIA H100 with Haar interferometers at m=2nm = 2n; what these factors imply for the size of the devices that can be simulated at a given rate is the subject of Ref. [25]. Each nn uses one Haar unitary, the QR decomposition of a complex Ginibre matrix with the phases of the diagonal of RR fixed. The time of a sample is the wall-clock time of a sampling call, the GPU synchronised before and after; the first call, which compiles the kernels, is excluded. Arithmetic is IEEE double precision (complex128).1 The superposed-source costs are averages, over the binomial law of the photon number kk, of the cost measured at each kk: the cost of a shot grows like 2k2^k, and a plain mean over a short run would miss the rare large-kk shots.

The cost of superposed sources falls with the photon number at the exponent of single photons under loss η=sin⁡2α\eta= \sin^2 \alpha, and the coherence enters the cost of a step through the offset: s0=n−ks_0 = n - k grows as the sources dim, and each Glynn term carries the factor ∣Tj∣(d+1)/j|T_j|(d + 1)/j of Table 1; at sin⁡2α=1\sin^2 \alpha= 1 the offset is empty and the sampler runs the single-photon step at 1.051.05–1.151.15 times its cost (n=30n = 30; 1.04±0.091.04 \pm0.09 at n=34n = 34). Against single photons under loss η=sin⁡2α\eta= \sin^2 \alpha on the same n=34n = 34 instance the time ratio is 1.1±0.11.1 \pm0.1, 1.6±0.11.6 \pm0.1, 2.2±0.12.2 \pm0.1 and 4.1±0.14.1 \pm0.1 at sin⁡2α=0.99\sin^2 \alpha= 0.99, 0.950.95, 0.90.9 and 0.80.8. For photonic MPS the overhead is the term count RjR_j, which is small on the last steps that carry the cost on the trains we measured (n≤20n \le20); how it grows with nn is open. For adaptive optics the overhead is set by the photons read adaptively, rˉ=nK/m\bar{r} = nK/m, not by the number of adaptive modes, and only K∝mK \propto m changes the exponent. A non-linear site costs (1+κB)∥c1∥2(1 + \kappa B)\lVert c_1\rVert^2, a constant for a response of short period and polynomial for a generic one. For a fixed number of sites and adaptive modes, adaptive optics and non-linear sites keep the exponential rate of the single-photon chain, superposed sources take that of single photons under loss η=sin⁡2α\eta= \sin^2 \alpha, and for photonic MPS the rate depends on the growth of RjR_j.

Competing exact algorithms. None of the exact samplers of Sec. 1 has a public implementation specialised to these inputs; generic Fock-space simulators handle mid-circuit photon counting at the cost of strong simulation. A cost-model comparison at the sizes of Table 2 (Supplementary Material, Sec. ??) finds every alternative slower by one to several orders of magnitude, conditional on its assumptions. For photonic MPS the prefix-amplitude sampler [16] has a polynomial overhead

sampler (Sec.)instancekindcost, relative to the single-photon sampler of the same size
single photons [3]n=30n = 30 / 34 photonstime1
superposed sources (3)n=30n = 30 sources, sin⁡2α=1\sin^2 \alpha= 1 (offset empty)time1.05–1.15
n=34n = 34 sources, sin⁡2α=1\sin^2 \alpha= 1 / 0.99 / 0.95 / 0.9 / 0.8time1.04 ± 0.09 / 0.97 / 0.75 / 0.52 / 0.23
photonic MPS (4)linear cluster, L=χ=2L = \chi= 2, n=8n = 8 / 12 / 16counta step costs Rjχ2R_j\chi^2 single-photon steps; mean RjR_j peaks at 7 / 30 / 96 near j≈n/2.5j \approx n/2.5 and falls to 1–2 on the last steps, which carry the cost
adaptive (5)n=30n = 30–38, K=1K = 1 / 2, Haar policycount2.1 / 4.1 chains per sample (mean)
n=38n = 38, K=1K = 1 / 2 / 3modeltime X=1.03X = 1.03 / 1.07 / 1.10
non-linear site (6)one site, φ=π/2\varphi= \pi/2 (B=2B = 2)countacceptance 0.43–0.59 against 1/∥c∥1=0.51/\lVert c\rVert_1 = 0.5; branch permanent κ=0.55±0.08\kappa= 0.55 \pm0.08 samples
model(1+κB)∥c∥1=2(1+2κ)≈4.2(1 + \kappa B)\lVert c\rVert_1 = 2(1 + 2\kappa) \approx4.2
B=16B = 16countacceptance 0.054–0.077 against 0.0625

caption: Cost of the samplers on one H100, m=2nm = 2n, Haar interferometers, relative to the single-photon sampler on an instance of the same size (for superposed sources: nn sources against nn photons); the single-photon sampler takes 6.2 ms (n=30n = 30) and 69 ms (n=34n = 34) per sample. “kind” separates measured times, measured counts (term counts, chains, acceptances) and model estimates. All samplers are exact (in the sense of footnote 1) and are validated in § 2.6.1.

:::

over single photons, ours the term count RjR_j: if RjR_j grows exponentially with nn, the prefix-amplitude sampler is faster at large nn (Supplementary Material, Sec. ??).

Conclusion

Of the three properties behind Clifford and Clifford’s sampler, the random order does not need the product input. The set-chain lemma asks only for an identity between weights on input sets, and superposed sources and photonic MPS satisfy it although neither is a product of photons; the hidden set of sources that supplied no photon, or of emissions traced out, is carried by the chain and never has to be enumerated. The chain does need the orthonormality of the columns. Where it fails — on the non-adaptive modes of an adaptive circuit, between the branches of a non-linear site — the weights couple different hidden sets and the identity breaks; the samplers keep the chain for the part where it holds and correct the rest by rejection, whose acceptance probability is known exactly.

A source in a coherent superposition of vacuum and one photon is sampled at the exponential rate of a lossy single photon of the same brightness, and adaptive measurements on a fixed number of modes or a non-linear phase of short period multiply the single-photon cost by a constant. None of these features, at that scale, moves the exponential rate of exact simulation. For photonic MPS the question remains open. The cost of our sampler is set by the term count RjR_j, small on the trains we measured, and whether it stays small as the trains grow decides whether it or the prefix-amplitude sampler, whose overhead over single photons is polynomial, is the faster one on long trains.

Four questions remain open. The first is the growth of RjR_j with nn, which sets the rate for photonic MPS. The second is whether a chain-consistent family exists for a coherent sum of linear branches with polynomially many terms per set; it would make a weak non-linearity cheap where the rejection makes it costly, and we know neither such a family nor an argument against one. The third is a lower bound on the cost of chain-consistent families for any of these inputs, since the lemma says when a step is cheap but not that no cheaper sampler exists. The fourth concerns adaptive circuits whose number of adaptive modes grows in proportion to the number of modes, where the rejection changes the exponent and we know no sampler that avoids it.

The samplers are part of a larger study of the exact classical simulation of photonic devices [25]. Their code is open source (MIT licence) at https://github.com/Quandela/photonic-engines and on PyPI as photonic-engines; the Lean proofs are available at doi:10.5281/zenodo.24023537.

Acknowledgements

We thank Timothée Goubault de Brugière for useful conversations, and Rawad Mezher for his insightful feedback and inspiration. This work has been co-funded by the European Commission by the Horizon-CL4 program under the grant agreement 101135288 for the EPIQUE project, by the PROQCIMA and TUF-TOPIQC programs within the French National Quantum Strategy (France 2030). The sampler code, the Lean proofs (Supplementary Material, Sec. ??), and the manuscript were written with the assistance of generative models from Anthropic (Claude). The algorithms, the formalisation choices, the code architecture, the main definitions, the lemma and the propositions were designed and written or reviewed by the authors, who take responsibility for the whole.

Exact sampling beyond Fock inputs and linear optics: photon-number superpositions, photonic matrix-product states, adaptive and non-linear circuits — supplementary material

Jean Senellart; Stephen Wein; Pierre-Emmanuel Emeriau

Sections S1–S5 give the pseudo-code, a cost comparison with the other exact algorithms, the check against Perceval, the proof of the adaptive column draw and the list of related samplers. Sections S6–S11 treat the complexity of photonic matrix-product states (MPS), the failure of the chain at a non-linear site, the validation table, loss and partial distinguishability, the leave-one-out values by division, and the formal proofs in Lean. The notation is that of the main text; sections, tables, lemmas, propositions and remarks numbered without the prefix S are those of the main text.

chain_rules_supp.pdf

Pseudo-code

We give the single-photon reference (Remark 2 of the main text) and the four samplers: superposed sources (Sec. 3), photonic MPS (Sec. 4), adaptive linear optics (Sec. 5) and non-linear sites (Sec. 6). The boxes show the lossless or lossy basic case; partial distinguishability is the extension of Sec. S9, except in Algorithm S2, which includes it.

Algorithm S1 Reference: single photons, Clifford and Clifford with the collapse of repeated rows [1, 2].

Require: UU (m×mm \times m), input modes t1…tnt_1 \ldots t_n; A←U[:,t]A \leftarrow U[:,t] (m×nm \times n)

  1. σ←\sigma\leftarrow uniform order of the nn columns

  2. for k=1…nk = 1 \ldots n do T←{σ1…σk}T \leftarrow\{\sigma_1 \ldots\sigma_k\}; B←A[z<k,T]B \leftarrow A[z_{<k},T] ▹\triangleright (k−1k-1) ×k\times k, rows may repeat

  3. Pc←Per⁡B∖cP_c \leftarrow\operatorname{Per} B_{\setminus c} (BB without column cc) for all c∈Tc \in T ▹\triangleright Cofactors(BB)

  4. amp⁡(r)←∑c∈TArcPc\operatorname{amp}(r) \leftarrow\sum_{c \in T} A_{rc}P_c for every output mode rr; draw zk∝∣amp⁡∣2z_k \propto|\operatorname{amp}|^2

  5. end for

  6. return occupation of (z1…zn)(z_1 \ldots z_n)

  7. function Cofactors(BB) ▹\triangleright one Glynn sum gives all kk cofactors

  8. (bν,μν)←(b_\nu,\mu_\nu) \leftarrow distinct rows of BB and their multiplicities

  9. v←0v \leftarrow0; w←1w \leftarrow1; s←∑νμνbνs \leftarrow\sum_\nu\mu_\nu b_\nu; acc⁡c←0\operatorname{acc}_c \leftarrow0 for all cc ▹\triangleright vνv_\nu: rows of group ν\nu signed −1-1

  10. for each v∈∏ν{0…μν}v \in\prod_\nu\{0 \ldots\mu_\nu\} in reflected mixed-radix Gray order do ▹∏ν(μν+1)\triangleright\prod_\nu(\mu_\nu+1) terms

  11. on the step vν→vν±1v_\nu\to v_\nu\pm1: s←s∓2bνs \leftarrow s \mp2b_\nu; w←w⋅w \leftarrow w \cdot (ratio of (−1)vν(-1)^{v_\nu})

  12. acc⁡c←acc⁡c+w∏j≠csj\operatorname{acc}_c \leftarrow\operatorname{acc}_c + w \prod_{j \ne c} s_j for all cc ▹\triangleright all-but-one products

  13. end for

  14. return acc⁡/2k−1\operatorname{acc}/2^{k-1} ▹\triangleright full sum as written; pairing vv with μ−v\mu-v halves it (as in [1])

  15. end function

Algorithm S2 Superposed sources: random source order with offset start.

Require: UU (m×mm \times m), source modes t1…tnt_1 \ldots t_n, α\alpha; transmission η\eta, common-mode probability xx

  1. draw the live sources (each with prob. cos⁡2α+ηsin⁡2α\cos^2\alpha+\eta\sin^2\alpha), and among them those in the common internal mode (each with prob. xx); no live source: return the vacuum

  2. α′←atan2⁡(ηsin⁡α,cos⁡α)\alpha^{\prime} \leftarrow\operatorname{atan2}(\sqrt{\eta}\sin\alpha,\cos\alpha) ▷ tan⁡α′=ηtan⁡α\tan\alpha^{\prime}=\sqrt{\eta}\tan\alpha, defined at α=π/2\alpha=\pi/2

  3. for each live source ii in its own internal mode do ▷ factorises out of the Dicke coherence

  4. with prob. sin⁡2α′\sin^2\alpha^{\prime}: one photon on output r∼∣Ur,ti∣2r \sim\lvert U_{r,t_i}\rvert^2 ▷ otherwise vacuum

  5. end for

  6. L←L \leftarrow live sources in the common mode; draw k∼Bin⁡(∣L∣,sin⁡2α′)k \sim\operatorname{Bin}(\lvert L\rvert,\sin^2\alpha^{\prime})

  7. σ←\sigma\leftarrow uniform order of LL; A←U[:,tσ]A \leftarrow U[:,t_{\sigma}]

  8. for j=1…kj=1\ldots k do

  9. T←T \leftarrow first ∣L∣−k+j\lvert L\rvert-k+j columns of AA

  10. Px←Per⁡□A[z<j,T∖x]P_x \leftarrow\operatorname{Per}_{\square} A[z_{<j},T\setminus x] for all x∈Tx\in T ▷ RectCofactors⁡(A[z<j,T])\operatorname{RectCofactors}(A[z_{<j},T])

  11. w(r)←∣∑x∈TArxPx∣2w(r) \leftarrow\left\lvert\sum_{x\in T} A_{rx}P_x\right\rvert^2 for r∈[m]r\in[m]; draw zj∝wz_j\propto w

  12. end for

  13. return occupation of (z1…zk)(z_1\ldots z_k) plus the photons of the sources in their own mode

  1. function RectCofactors⁡(B)\operatorname{RectCofactors}(B) ▷ BB: q=j−1q=j-1 rows, N=∣T∣N=\lvert T\rvert columns, s0=N−1−qs_0=N-1-q

  2. if q=0q=0 then return P≡1P\equiv1

  3. P←0P\leftarrow0

  4. (bν,μν)←(b_\nu,\mu_\nu)\leftarrow distinct rows of BB and their multiplicities; a←∑νμνbνa\leftarrow\sum_\nu\mu_\nu b_\nu; w←1w\leftarrow1

  5. for each v∈∏ν{0…μν}v\in\prod_\nu\{0\ldots\mu_\nu\} in reflected mixed-radix Gray order do ▷ as in Algorithm S1

  6. on the step vν→vν±1v_\nu\to v_\nu\pm1: a←a∓2bνa\leftarrow a\mp2b_\nu; w←w⋅(ratio of (−1)vν(μνvν))w\leftarrow w\cdot\left(\text{ratio of }(-1)^{v_\nu}\binom{\mu_\nu}{v_\nu}\right)

  7. Px←Px+w Loo⁡(a,x)P_x\leftarrow P_x+w\,\operatorname{Loo}(a,x) for all xx

  8. end for

  9. return P/2qP/2^q ▷ full sum as written; eqe_q homogeneous, so pairing vv with μ−v\mu-v halves it

  10. end function

  1. function Loo⁡(a,x)\operatorname{Loo}(a,x) ▷ eq(a∖ax)e_q(a\setminus a_x), d=min⁡(q,s0)d=\min(q,s_0)

  2. if s0=0s_0=0 then return ∏i≠xai\prod_{i\ne x}a_i ▷ all-but-one product: the single-photon payload

  3. else if s0≤qs_0\le q then return [μs0]Pre⁡x(μ)Suf⁡x(μ)[\mu^{s_0}]\operatorname{Pre}_x(\mu)\operatorname{Suf}_x(\mu) ▷ ∏i<x∏i>x\prod_{i<x}\prod_{i>x} of (μ+ai)(\mu+a_i), degree ≤s0\le s_0

  4. else return [λq]Pre⁡x(λ)Suf⁡x(λ)[\lambda^q]\operatorname{Pre}_x(\lambda)\operatorname{Suf}_x(\lambda) ▷ ∏i<x∏i>x\prod_{i<x}\prod_{i>x} of (1+λai)(1+\lambda a_i), degree ≤q\le q

  5. end if

  6. end function

Algorithm S3 Photonic MPS: reduced-state chain with purified terms and matrix cofactors.

Require: UU, emission operators Ml(s)M_l^{(s)} (χ×χ\chi\times\chi) and input modes ts,lt_{s,l} (s=1..ns = 1..n, l=1..Ll = 1..L), ∣in⟩|\mathrm{in}\rangle; transmission η\eta

  1. draw the lost emissions (each with probability 1−η1-\eta); K←\mathcal{K} \leftarrow the kept ones, k←∣K∣k \leftarrow|\mathcal{K}|

  2. draw the labels xx of the lost emissions and the final emitter state ⟨out∣\langle\mathrm{out}| from their exact joint marginal ▷ label unravelling: each lost emission now carries one operator Mxs(s)M_{x_s}^{(s)}; lossless: ⟨out∣\langle\mathrm{out}| only ▷ the kept state given these draws is normalised; its scale cancels from the row draws below

  3. σ←\sigma\leftarrow uniform order of K\mathcal{K}

  4. for j=1..kj = 1..k do

  5. T←{σ1..σj}T \leftarrow\{\sigma_1..\sigma_j\} in emission order; {(∣ine⟩,⟨oute∣,M~e)}e≤Rj←GapTerms⁡(T)\{(|\mathrm{in}_e\rangle,\langle\mathrm{out}_e|,\widetilde{M}_e)\}_{e\le R_j} \leftarrow\operatorname{GapTerms}(T)

  6. for each term ee do

  7. Kce←MatrixCofactors⁡(e,z<j,T)K_c^e \leftarrow\operatorname{MatrixCofactors}(e,z_{<j},T) for c∈Tc \in T

  8. amp⁡e(r)←∑c∈T∑lUr,tc,lTr⁡(M~l(c)Kce)\operatorname{amp}_e(r) \leftarrow\sum_{c\in T}\sum_l U_{r,t_{c,l}}\operatorname{Tr}(\widetilde{M}_l^{(c)}K_c^e) for every output mode rr

  9. end for

  10. w(r)←∑e∣amp⁡e(r)∣2w(r) \leftarrow\sum_e |\operatorname{amp}_e(r)|^2; draw zj∝wz_j \propto w ▷ w(r)=fj(z<jr;T)w(r)=f_j(z_{<j}r;T)

  11. end for

  12. return occupation of (z1..zk)(z_1..z_k)

  1. function GapTerms⁡(T)\operatorname{GapTerms}(T) ▷ purification of ρT\rho_T: ρT=∑e∣ψe⟩⟨ψe∣\rho_T=\sum_e|\psi_e\rangle\langle\psi_e|

  2. for each gap (maximal run of emissions a+1..b−1a+1..b-1 not in TT, prefix and suffix runs included) do

  3. Kraus operators {Qi}\{Q_i\} of ρ↦∑xAxρAx†\rho\mapsto\sum_x A_x\rho A_x^\dagger, Ax=Mxb−1(b−1)⋯Mxa+1(a+1)A_x=M_{x_{b-1}}^{(b-1)}\cdots M_{x_{a+1}}^{(a+1)} lost emissions inside the run enter AxA_x with their drawn operator, not summed by SVD of the matrix with columns vec⁡(Ax)\operatorname{vec}(A_x) (the Choi matrix), reduced emission by emission (rank ≤χ2\le\chi^2; ≤χ\le\chi at the ends; Prop. 2)

  4. end for

  5. one term per choice of ii in every gap: M~l(a)←QiMl(a)\widetilde{M}_l^{(a)}\leftarrow Q_iM_l^{(a)} for the kept emission aa before the gap, prefix gap into ∣ine⟩|\mathrm{in}_e\rangle, suffix gap into ⟨oute∣\langle\mathrm{out}_e|; drop zero-norm chains

  6. return the RjR_j terms

  7. end function

  1. function MatrixCofactors⁡(e,z<j,T)\operatorname{MatrixCofactors}(e,z_{<j},T) ▷ Glynn over the j−1j-1 placed rows, χ×χ\chi\times\chi products

  2. if j=1j=1 then return Kc=∣ine⟩⟨oute∣K_c=|\mathrm{in}_e\rangle\langle\mathrm{out}_e| for the single c∈Tc\in T ▷ no placed row

  3. Kc←0K_c\leftarrow0 for c∈Tc\in T

  4. for δ∈{+1}×{±1}j−2\delta\in\{+1\}\times\{\pm1\}^{j-2} in Gray order do ▷ 2020 collapse on repeated rows: mixed-radix walk

  5. sc,l←∑iδiUzi,tc,ls_{c,l}\leftarrow\sum_i\delta_iU_{z_i,t_{c,l}}; Gc←∑lsc,lM~l(c)G_c\leftarrow\sum_l s_{c,l}\widetilde{M}_l^{(c)}

  6. pc←Gc−1⋯G1∣ine⟩p_c\leftarrow G_{c-1}\cdots G_1|\mathrm{in}_e\rangle, qcT←⟨oute∣Gj⋯Gc+1q_c^T\leftarrow\langle\mathrm{out}_e|G_j\cdots G_{c+1} ▷ prefix / suffix sweeps

  7. Kc←Kc+(∏iδi)pcqcTK_c\leftarrow K_c+\left(\prod_i\delta_i\right)p_cq_c^T

  8. end for

  9. return 2−(j−2)Kc2^{-(j-2)}K_c

  10. end function

Algorithm S4 Adaptive linear optics: exact samples $\omega = (p, s)$.

Require: $U_0$ ($m \times m$), input modes $t$ ($n$ photons), levels $A_1..A_\Lambda$ (adaptive modes $a_1..a_K$ in measurement order), policy $V_\lambda(p_{\leq\lambda})$
1: $p \leftarrow (),\ U \leftarrow U_0$
2: for $\lambda = 1.. \Lambda$ do ▷ stage 1: the adaptive outcome, level by level
3: if the $K_\lambda$-mode graded table fits then
4: $M \leftarrow \operatorname{BinomialMoments}(U,t,a_1..a_{K_\lambda});\ P \leftarrow$ binomial inverse of $M$
5: draw the level-$\lambda$ counts from $P[p_{<\lambda}, \cdot]/\sum P[p_{<\lambda}, \cdot]$
6: else ▷ beyond the tables: a level chain
7: repeat $\rho \leftarrow \operatorname{PrefixChain}(U,t,a^{p_{<\lambda}},\{a_1..a_{K_{\lambda-1}}\})$
8: until $\rho \ne \operatorname{ABORT}$
9: level-$\lambda$ counts $\leftarrow$ counts of $\rho$ on $A_\lambda$
10: end if
11: $p \leftarrow p \oplus$ (level-$\lambda$ counts); $U \leftarrow E(V_\lambda(p))U$ ▷ feed-forward on the unmeasured modes
12: end for
13: $a^p \leftarrow (a_1^{\times p_1},\ldots,a_K^{\times p_K}),\ r \leftarrow |p|$ ▷ stage 2: the final counts given $p$
14: repeat $\rho \leftarrow \operatorname{PrefixChain}(U,t,a^p,\{a_1..a_K\})$
15: until $\rho \ne \operatorname{ABORT}$ ▷ acceptance $P(p)/M[p]$
16: $s \leftarrow$ counts of $\rho_{r+1..n}$ on the final modes; return $(p,s)$
17: function $\operatorname{BinomialMoments}(U,t,A)$ ▷ Ivanov and Gurvits {citep}`[16]`, as used in {citep}`[3]`
18: $V \leftarrow U[A,t];\ G \leftarrow 1$ ▷ polynomial in $x_1..x_{|A|},\ w_1..w_{|A|}$, graded by total degree
19: for $i = 1..n$ do $G \leftarrow G \cdot (1 + (\sum_l \overline{V}_{li}x_l)(\sum_l V_{li}w_l))$
20: end for
21: return $M[c] = c! [x^c w^c]G$ ▷ $= \mathbb{E}[\prod_l \binom{N_l}{c_l}]$
22: end function
Algorithm S5 The chain started from a forced prefix ({xref}`Lemma 1(c)` of the main text), with early abort.

1: function $\operatorname{PrefixChain}(U,t,\operatorname{prefix}\ (r\ \text{rows}),\operatorname{avoid})$
2: $S \leftarrow \operatorname{PrefixColumns}(U,t,\operatorname{prefix})$ ▷ $\Pr[S] \propto |\operatorname{Per}U[\operatorname{prefix},S]|^2$
3: column order $\leftarrow S$, then the other $n-r$ columns in uniform random order; $\rho_1..\rho_r \leftarrow \operatorname{prefix}$
4: for $k = r+1..n$ do ▷ ordinary Clifford–Clifford steps
5: $w_j \leftarrow |\operatorname{Per}U[(\rho_{<k},j),\operatorname{columns}_{\leq k}]|^2$ for every output mode $j$ ▷ Laplace, one Glynn sum
6: draw $\rho_k \propto w$; if $\rho_k \in \operatorname{avoid}$ then return $\operatorname{ABORT}$
7: end for
8: return $\rho$
9: end function
10: function $\operatorname{PrefixColumns}(U,t,\operatorname{prefix})$ ▷ polynomial: the prefix has $K$ distinct rows
11: $B_j \leftarrow U[a,t_j]$ for $j = 1..n$ ▷ $K$-vectors
12: $F_{n+1} \leftarrow 1$; for $j = n..1$: $F_j \leftarrow F_{j+1}\cdot(1+(B_j\cdot x)(\overline{B}_j\cdot w))$, truncated at degree $p$
13: $g \leftarrow 1;\ S \leftarrow \varnothing$ ▷ $g$: polynomial in $x$, degree $\leq p$
14: for $j = 1..n$ do
15: $g_{\mathrm{in}} \leftarrow g\cdot(B_j\cdot x)$
16: $w_{\mathrm{in}} \leftarrow \sum_{a,b}g_{\mathrm{in}}[a]g_{\mathrm{in}}[b]F_{j+1}[p-a,p-b];\ w_{\mathrm{out}} \leftarrow$ the same with $g$
17: with probability $w_{\mathrm{in}}/(w_{\mathrm{in}}+w_{\mathrm{out}})$: $S \leftarrow S\cup\{j\},\ g \leftarrow g_{\mathrm{in}}$
18: end for
19: return $S$ ▷ $|S| = r$
20: end function

Algorithm S6 Non-linear sites: rejection from the incoherent branch mixture.

Require: interferometers U0…ULU_0 \ldots U_L, sites (ℓ,x,f)(\ell, x, f) (response e−if(n^x)e^{-if(\hat{n}_x)} between Uℓ−1U_{\ell-1} and UℓU_\ell), input modes tt; transmissions η\eta (before the sites), ηpost\eta_{\mathrm{post}} (after)

  1. draw the surviving photons (each with probability η\eta); n←n \leftarrow their number, t←t \leftarrow their modes

  2. if n=0n = 0 then return the vacuum

  3. for each site: (θℓ,cℓ)←Branches⁡(f,n)(\theta_\ell, c_\ell) \leftarrow\operatorname{Branches}(f,n) ▷ the expansion of this stream’s own photon count

  4. Ub←ULDL(θb)⋯D1(θb)U0U_b \leftarrow U_L D_L(\theta_b) \cdots D_1(\theta_b) U_0, cb←∏sitescℓ(site)c_b \leftarrow\prod_{\text{sites}} c_\ell(\text{site}) for every branch bb

  5. repeat

  6. draw bb with probability ∣cb∣/∥c∥1|c_b|/\lVert c\rVert_1; s←s \leftarrow one Fock sample of UbU_b on tt ▷ Clifford–Clifford, 2020 kernels

  7. ab′←Per⁡Ub′[s,t]a_{b'} \leftarrow\operatorname{Per}_{U_{b'}}[s,t] for every branch b′b' ▷ batched Laplace cofactors

  8. accept with probability ∣∑b′cb′ab′∣2/(∥c∥1∑b′∣cb′∣∣ab′∣2)\left|\sum_{b'} c_{b'}a_{b'}\right|^2/\left(\lVert c\rVert_1 \sum_{b'} |c_{b'}| |a_{b'}|^2\right)

  9. until accepted ▷ acceptance exactly 1/∥c∥121/\lVert c\rVert_1^2

  10. thin ss binomially with ηpost\eta_{\mathrm{post}}; return ss

  11. function Branches⁡(f,n)\operatorname{Branches}(f,n) ▷ e−if(n^x)=∑ℓcℓeiθℓn^xe^{-if(\hat{n}_x)}=\sum_\ell c_\ell e^{i\theta_\ell\hat{n}_x} exactly on ≤n\le n photons

  12. g(j)←e−if(j)g(j) \leftarrow e^{-if(j)} for j=0…nj=0\ldots n

  13. q←q \leftarrow smallest q≤nq \le n with g(j+q)/g(j)g(j+q)/g(j) constant =eiaq=e^{ia_q} on j=0…n−qj=0\ldots n-q ▷ q=nq=n always works

  14. h(j)←g(j)e−iajh(j) \leftarrow g(j)e^{-iaj} (qq-periodic); cℓ←1q∑j<qh(j)e−2πiℓj/qc_\ell\leftarrow\frac{1}{q}\sum_{j<q}h(j)e^{-2\pi i\ell j/q}, θℓ←a+2πℓ/q\theta_\ell\leftarrow a+2\pi\ell/q

  15. return {(θℓ,cℓ):cℓ≠0}\{(\theta_\ell,c_\ell):c_\ell\ne0\} ▷ every non-zero coefficient: the expansion is exact

  16. end function

Implementation note. In floating point the transform returns coefficients at rounding level where the exact ones vanish (e.g. at φ=π/2\varphi=\pi/2). Our code drops those with ∣cℓ∣<10−14|c_\ell|<10^{-14} and checks that the remaining expansion reproduces e−if(j)e^{-if(j)} on j=0…nj=0\ldots n to ε=10−12\varepsilon=10^{-12}. The site is then replaced by a diagonal operator within ε\varepsilon of it on every Fock state of at most nn photons in mode xx, so the output state moves by at most ε\varepsilon per site in norm and the output law by at most 2ε2\varepsilon per site in total variation.

Comparison with other exact algorithms

Each sampler is compared with the other exact samplers that apply to its input (§ 1.1 of the main text and Table S3). We did not benchmark a public implementation of these alternatives; Table S1 compares cost models, in units of single-photon samples (or steps) of the same size, the unit of each cell being stated in it. Assumptions: a Haar interferometer on m=2nm=2n modes decomposed into g≈m2/2=2n2g\approx m^2/2=2n^2 beam splitters for the prefix-amplitude sampler of [6], with O(1)O(1) amplitudes per beam splitter, each a permanent of the circuit truncated after that beam splitter and costing half a single-photon sample (the last chain step), times χ2\chi^2 for a matrix-valued Glynn sum. This is our adaptation of the gate-by-gate construction of [6] to linear optics, not a cost stated there. A branch permanent costs κ=0.55\kappa=0.55 single-photon samples (measured).

sampler, sizebest prior exact alternativeits cost (estimate)ours
superposed sourcesgeneric chain [4]; component rejection [5]; prefix amplitudes [6](n2)\binom{n}{2} pairs per step; acceptance (n2)−1\binom{n}{2}^{-1} per sector; ∼2n2\sim2n^2 amplitudes of cost 2kkn2^kkn2kn22^kn^2 per sample (the exponent of lossy single photons)
photonic MPS, n=20n = 20prefix amplitudes [6]≈4n2≈1.6⋅103\approx4n^2 \approx1.6 \cdot10^3 per stepRjχ2≈4R_j\chi^2 \approx4–88 per step where the cost is (measured Rj=1R_j = 1–22)
adaptive, K≤3K \le3, n=38n = 38prefix amplitudes [6]; Gaussian model only [3]∼2n2\sim2n^2 permanents2.0–6.8 chains started (cost model), mostly aborted early: time ratio X=1.03X = 1.03–1.101.10
non-linear, φ=π/2\varphi= \pi/2, n=36n = 36gadget [7]; prefix amplitudes [6]gadget: ∼ϱn≈2⋅109\sim\varrho^n \approx2 \cdot10^9 before the herald rate; 22nBκ≈3⋅1032^{2n}B\kappa\approx3 \cdot10^3(1+κB)∥c∥12=4.2(1 + \kappa B)\lVert c\rVert_1^2 = 4.2
non-linear, generic φ\varphi, n=40n = 40component rejection [5]; prefix amplitudes [6]B(1+κB)∥c∥22≈9.2⋅102B(1+\kappa B)\lVert c\rVert_2^2 \approx9.2\cdot10^2; ≈7⋅104\approx7 \cdot10^4(1+40κ)33.2≈7.6⋅102(1 + 40\kappa)33.2 \approx7.6 \cdot10^2

Table S1. Cost-model comparison with the exact alternatives, in single-photon-sample units at the stated sizes (assumptions in the text). The “ours” column is measured on our implementation, except the MPS row (the step cost of Table 1 of the main text with the measured term count) and the adaptive row (the cost model of Sec. 5 of the main text); the alternatives are cost models, not timed. Under these assumptions no alternative is cheaper at these sizes; the MPS row may cross over at large nn (text).

methodapplies tocost structure, and relation to the main text
chain over the true marginal [4]any input statepairs of input components ×\times hidden subsets per step: up to (nk)2\binom{n}{k}^2 for superposed sources (direct expansion, late steps), up to L2nL^{2n} for an MPS train (Remark 1)
component rejection [5]coherent superposition of NcN_c componentsNc∣β∣2N_c|\beta|^2 proposals; Nc=2nN_c=2^n for nn superposed sources in the Fock basis; its principle, reweighted, in Sec. 6
prefix amplitudes [6]any circuitO(q)O(q) amplitudes per sample, no marginals; Sec. S2
repeated input modes [11]Fock input with repeated modesClifford–Clifford extended
Gaussian chains [12, 13, 14]Gaussian inputsloop hafnians over output modes, 2N/22^{N/2} in the detected photons; out of scope
bounded treewidth [15]; phase space [17]structured interferometers; classical or noisy lighttractable marginals; efficient
adaptive Gaussian [3]Gaussian input and measurement, O(log⁡m)O(\log m) adaptive modesefficient exact sampler; Fock input with PNR final detection in Sec. 5
adaptive linear optics [20]Fock input, adaptive measurementsestimates output probabilities and overlaps; not a sampler of the full output
noisy adaptive circuits [18]Fock input, feed-forward, noisestrong simulation: output probabilities, amplitudes or derivatives of a polynomial; not a sampler
Kerr gadget [7]one Kerr sitelinear optics with ancillas and postselection; Sec. 6 needs no ancilla

Table S3. Exact samplers related to the inputs and circuits of the main text (sections and remarks refer to the main text).

Under the assumptions above, every modelled alternative is slower at these sizes by one to several orders of magnitude. The comparison is conditional on them: none of the alternatives was timed on our machine, and a better implementation of one could narrow the gaps.

Photonic MPS at large nn. At large nn the prefix-amplitude sampler may become the faster one. It works with amplitudes of the pure photonic state and never forms the reduced states of § 2.2 of the main text, so its overhead over single photons is polynomial (∼4n2\sim4n^2 single-photon steps), while ours is the term count, a step costing about Rjχ2R_j\chi^2 single-photon steps. How RjR_j grows with nn is not known. On the trains we measured (n≤20n \le20) it is 1–2 on the last steps, which carry the cost, and our gapwise decomposition is within 1.02–1.11× of the rank of ρT\rho_T weighted by step cost; but the bound of Proposition 2 grows exponentially with the number of gaps. If RjR_j stays small on the costly steps, our overhead is a constant factor; if it grows exponentially with nn, the prefix-amplitude sampler is faster once Rjχ2R_j\chi^2 exceeds ∼4n2\sim4n^2. A cost model of RjR_j would locate the crossover, and a sampler that uses the term expansion where RjR_j is small and pure-state amplitudes where it is large would combine the two.

Superposed sources against Perceval

nnmmα\alphaη\etaTVD to Percevalshot noisecoherent vs incoherent
48π/4\pi/410.02570.02630.374
612π/4\pi/410.09910.10020.394
561.110.03650.03620.193
77π/4\pi/410.05860.05800.421
58π/4\pi/40.70.02810.02750.268

Table S2. The superposed-source sampler (Sec. 3 of the main text) against Perceval’s SLOS backend [8] on the coherent product StateVector, an oracle outside our code base; lossy points as the enumerated mixture over live sources. 4 · 10410^4 samples per point (bench/sbs_chain.rso.py, CPU). Shot noise: TVD of an exact multinomial draw of the same size. Last column: TVD between the coherent law and the incoherent mixture of the same sources.

The same test separates the coherent law from the incoherent mixture by a TVD of 0.19–0.42 (last column). Beyond strong-simulation reach (n=14n = 14, m=28m = 28) the mean occupation of every output mode matches the coherent prediction ∑i∣Uji∣2(p−γ2)+∣∑iUjiγ∣2\sum_i |U_{ji}|^2(p-\gamma^2)+|\sum_i U_{ji}\gamma|^2, with brightness p=sin⁡2αp=\sin^2\alpha and coherence γ=cos⁡αsin⁡α\gamma=\cos\alpha\sin\alpha, to ∣z∣≤1.8|z|\leq1.8, and misses the incoherent one by ∣z∣=22.1|z|=22.1 (one random instance, 3000 samples); this first-moment check separates coherent from incoherent sources but cannot validate the full law.

The column draw of the adaptive sampler

Let the forced prefix have KK distinct rows a1..aKa_1..a_K with multiplicities pp, ∣p∣=r|p|=r, and Bj=Up[a,tj]∈CKB_j=U^{p}[a,t_j]\in\mathbb{C}^{K} (Sec. 5 of the main text). For ∣S∣=r|S|=r, a permanent with repeated rows is a coefficient, Per⁡Up[ap,S]=p![xp]∏j∈S(Bj⋅x)\operatorname{Per}U^{p}[a^p,S]=p![x^p]\prod_{j\in S}(B_j\cdot x) with p!=∏lpl!p!=\prod_l p_l!: expanding the product, the coefficient of xpx^p sums over the assignments of the columns of SS to the labels ll with counts pp, and each assignment stands for ∏lpl!\prod_l p_l! permutations. Hence ∣Per⁡Up[ap,S]∣2=(p!)2[xpwp]∏j∈S(Bj⋅x)(Bˉj⋅w)|\operatorname{Per}U^{p}[a^p,S]|^2=(p!)^2[x^pw^p]\prod_{j\in S}(B_j\cdot x)(\bar{B}_j\cdot w). Deciding the columns in the order 1..n1..n, with S<S_{<} the columns already taken and g=∏j∈S<(Bj⋅x)g=\prod_{j\in S_{<}}(B_j\cdot x), the total weight of the completions is

∑S′⊆{j..n}[xpwp]g(x)gˉ(w)∏i∈S′(Bi⋅x)(Bˉi⋅w)=[xpwp]g(x)gˉ(w)Fj(x,w),\sum_{S'\subseteq\{j..n\}}[x^pw^p]g(x)\bar{g}(w)\prod_{i\in S'}(B_i\cdot x)(\bar{B}_i\cdot w)=[x^pw^p]g(x)\bar{g}(w)F_j(x,w),
Fj=∏i≥j(1+(Bi⋅x)(Bˉi⋅w)).F_j=\prod_{i\geq j}(1+(B_i\cdot x)(\bar{B}_i\cdot w)).

where truncation at degree pp keeps exactly the completions with ∣S∣=r|S|=r. Taking column jj with probability win/(win+wout)w_{\mathrm{in}}/(w_{\mathrm{in}}+w_{\mathrm{out}}), the two completion weights with and without it, therefore draws SS with probability ∝∣Per⁡Up[ap,S]∣2\propto|\operatorname{Per}U^{p}[a^p,S]|^2, the posterior of Lemma 1(c) of the main text. The tables have ∏l(pl+1)2\prod_l(p_l+1)^2 entries, polynomial for fixed KK (Algorithm S5).

Prior exact samplers

Complexity of photonic matrix-product states

The model of § 2.2 of the main text contains single-photon boson sampling: with χ=1\chi=1, L=1L=1 and M1(s)=1M_1^{(s)}=1 the train is nn single photons in distinct modes, so exact sampling from photonic MPS is at least as hard, in the worst case, as from Fock inputs [9]. For a fixed train, Ref. [10] (Supplementary Material, Proposition S2) proves more for the projected register (a fixed ⟨out∣\langle\mathrm{out}|, ∣ψ⟩|\psi\rangle pure), assuming the tensors Ml(s)M_l^{(s)}, ∣in⟩|{\rm in}\rangle, ⟨out∣\langle{\rm out}| are polynomially bounded and given exactly and a label word x0x^0 with ψ(x0)≠0\psi(x^0)\ne0 is known. For m≥(L+1)nm\ge(L+1)n, computing the amplitude ∑xψ(x)Per⁡U[z,tx]\sum_x\psi(x)\operatorname{Per} U[z,t_x] of a collision-free output zz exactly is #P-hard, and so is approximating its squared modulus to within a multiplicative factor g∈[1,poly⁡(n)]g\in[1,\operatorname{poly}(n)], by the corresponding result for ∣Per⁡A∣2|\operatorname{Per} A|^2 [9]: the interferometer is chosen to carry a scaled copy of an arbitrary matrix on the columns tx0t_{x^0} and zeros on the (L−1)n(L-1)n other label columns, so that only x0x^0 contributes. Computing the polynomial Fψ(X)=∑xψ(x)Per⁡X[⋅,tx]F_\psi(X)=\sum_x\psi(x)\operatorname{Per}X[\cdot,t_x] exactly with probability ≥3/4+1/poly⁡(n)\ge3/4+1/\operatorname{poly}(n) over standard complex Gaussian X∈Cn×LnX\in\mathbb{C}^{n\times Ln} is as hard: such an algorithm O\mathcal{O} gives P#P⊆BPPNPO\mathrm{P}^{\#\mathrm{P}}\subseteq\mathrm{BPP}^{\mathrm{NP}^{\mathcal{O}}}. Hardness of approximate sampling in the sense of Ref. [9] is only conditional. It needs a multiplicative-estimation conjecture and an anticoncentration conjecture for ∣Fψ(X)∣2|F_\psi(X)|^2, neither known to follow from the Fock case, and a hiding step that padding to an Ln×LnLn\times Ln block takes from Ref. [9] only for mm of (Ln)5(Ln)^5 type. For single photons, Ref. [19] gives hardness evidence with a linear number of modes; it does not by itself establish the analogous average-case statement for a fixed non-trivial photonic MPS.

The worst-case statements extend to the traced register. With the other label columns set to zero, a collision-free output of the traced train has probability w∣Per⁡A′∣2w|\operatorname{Per}A'|^2, A′A' the scaled copy, where w=∥Mxn0(n)⋯Mx10(1)∣in⟩∥2w=\lVert M_{x_n^0}^{(n)}\cdots M_{x_1^0}^{(1)}|{\rm in}\rangle\rVert^2 is positive and computable in polynomial time for a suitable known x0x^0; exact evaluation and multiplicative approximation of its output probabilities are therefore as hard as for the projected register. We distinguish three questions: exact evaluation of probabilities (hard in the worst case, for both registers), exact sampling (at least as hard as single photons, by the embedding χ=L=1\chi=L=1), and approximate sampling in total variation for a fixed non-trivial train, which needs the average-case conjectures above and is open for the traced register, whose output law mixes the final emitter states, and for the lost labels of a lossy train. These statements do not bear on the cost measurements of the main text: the m≥(L+1)nm\ge(L+1)n requirement belongs to this construction, and m=2n=Lnm=2n=Ln in the caterpillar tests, which falls outside it, is not evidence of easiness either.

Why the random-order chain fails at a non-linear site

In the notation of § 2.4 of the main text, the marginal of the first kk ordered rows of the circuit ∑bcbUb\sum_b c_bU_b is

qk(z)=(n−k)!n!∑b,b′cbcb′‾∑∣S∣=∣T∣=kPer⁡Ub[z,tS]Per⁡Ub′[z,tT]‾Per⁡Gbb′[tTc,tSc],Gbb′=Ub′†Ub,q_k(z)=\frac{(n-k)!}{n!}\sum_{b,b'}c_b\overline{c_{b'}}\sum_{\lvert S\rvert=\lvert T\rvert=k}\operatorname{Per}U_b[z,t_S]\overline{\operatorname{Per}U_{b'}[z,t_T]}\operatorname{Per}G_{bb'}[t_{T^c},t_{S^c}],\qquad G_{bb'}=U_{b'}^\dagger U_b,
∑y∈[m]n−kPer⁡Ub[y,tSc]Per⁡Ub′[y,tTc]‾=(n−k)!Per⁡Gbb′[tTc,tSc];\sum_{y\in[m]^{n-k}}\operatorname{Per}U_b[y,t_{S^c}]\overline{\operatorname{Per}U_{b'}[y,t_{T^c}]}=(n-k)!\operatorname{Per}G_{bb'}[t_{T^c},t_{S^c}];

the rows of Per⁡Gbb′[tTc,tSc]\operatorname{Per}G_{bb'}[t_{T^c},t_{S^c}] are the input modes of the photons TcT^c left by the conjugated amplitude and its columns those of the ScS^c left by the other (second line). For a linear circuit G=1G=1 and the last factor is δST\delta_{S T}, which is Remark 2 of the main text. For a single site, Ub=U1Dx(θb)U0U_b=U_1D_x(\theta_b)U_0 and Gbb′=1+(ei(θb−θb′)−1)ww†G_{bb'}=1+(e^{i(\theta_b-\theta_{b'})}-1)ww^\dagger with w=U0†exw=U_0^\dagger e_x: the rank-one term couples S≠TS\ne T. With several sites Gbb′−1G_{bb'}-1 need not have rank one (two π\pi phases on different modes with identity interferometers and one branch pair give G=1G=1 on those two modes); the general form above still holds. The true-marginal chain exists, but evaluated as written its quadratic form has B2(nj)2B^2\binom{n}{j}^2 pairs of branches and sets per candidate at step jj, each with a permanent of size n−jn-j, up to 4n4^n pairs at j≈n/2j\approx n/2; we know no rewriting that reuses structure across the pairs as Glynn's sum does for one set. We found no set-indexed purification of the kernel cbcb′‾Per⁡Gbb′[tTc,tSc]c_b\overline{c_{b'}}\operatorname{Per}G_{bb'}[t_{T^c},t_{S^c}] with few terms per set: purifying the traced photons in the basis after the trace gives a sum of squares indexed by their mn−km^{n-k} configurations, and splitting each traced photon into “on xx” and “not on xx” reintroduces the coupling through the rank-(m−1)(m-1) projector.

Validation table

Loss and partial distinguishability

Loss is uniform, one transmission η\eta per photon at the input; partial distinguishability is the mixture (xx-)model, each photon or source independently in a common internal mode with probability xx and otherwise in an internal mode of its own, orthogonal to all others, so two photons overlap with probability x2x^2. A general Gram matrix of internal states is not covered by any of the samplers. Except for superposed sources, the extensions below are not part of the algorithm boxes of Sec. S1, which show the basic cases.

Single photons. Loss draws the surviving photons (k∼Bin⁡(n,η)k \sim\operatorname{Bin}(n,\eta)) and the chain runs on their columns; distinguishability draws which survivors share the common mode, the others being routed classically by ∣U⋅i∣2|U_{\cdot i}|^2. The cost is that of the interfering photons.

Superposed sources. Loss η\eta maps each source to a mixture of vacuum and a source at a smaller α′\alpha', tan⁡α′=ηtan⁡α\tan\alpha' = \sqrt{\eta}\tan\alpha, drawn per source before the chain. In the xx-model, a source in its own mode factorises out of the Dicke coherence: its photon is present with probability sin⁡2α′\sin^2\alpha' and is routed by ∣U⋅i∣2|U_{\cdot i}|^2, and the chain runs on the live sources in the common mode. Both mixtures are drawn exactly (Algorithm S2). Non-uniform loss, ηi\eta_i per source, gives live sources with different amplitudes, tan⁡αi′=ηitan⁡α\tan\alpha'_i = \sqrt{\eta_i}\tan\alpha, which the unequal-source chain of § 2.1 of the main text covers.

Photonic MPS: unravelling the trace. Two kinds of emission lie outside the active set at step jj: lost ones, traced to the end, and kept ones not yet placed. A trace is a label measurement whose outcome is forgotten, so the labels of the lost emissions (and the final emitter state) can be drawn first, from their exact joint marginal. Each lost emission then carries one fixed operator Mx(s)M_x^{(s)}, and the kept emissions are in a pure state, a matrix-product state of bond dimension χ\chi on kk emissions; the chain runs on it as on a lossless train of kk emissions. At step jj the gaps of Proposition 2 of the main text are made of kept, not yet placed emissions only (the lost ones enter as fixed factors), so RjR_j is that of the lossless kk-emission train, and the last step has Rk=1R_k = 1. Without this draw the lost emissions widen every gap and remain traced to the end; an inner gap of lost emissions contributes up to χ2\chi^2 terms even at the last step. The draw does not bound RjR_j at earlier steps; on the trains we measured, where RjR_j is small on the last steps that carry the cost, the lossy cost then tracks the single-photon sampler under the same loss. In the xx-model, an emission jj in its own internal mode interferes with no other photon but its label stays entangled with the train through the emitter, so it is not routed independently: its output row rr is drawn from the exact marginal, jointly with the lost labels and the final emitter state, and the slot then carries the fixed operator Gj(r)=∑lUr,tj,lMl(j)G_j(r) = \sum_l U_{r,t_j,l}M_l^{(j)}, a measured emission folded into the train like a lost one; the chain runs on the remaining interfering emissions, and the photon is added at row rr. The correlations of, e.g., a state ∝∣a1b2⟩+∣b1a2⟩\propto\lvert a_1b_2\rangle+ \lvert b_1a_2\rangle with distinguishable photons 1 and 2 are kept, since the second photon is drawn conditioned on the first.

Adaptive linear optics. Uniform loss at the input, before the first adaptive detector, commutes with every passive element and the adaptive detectors read what survives, so a lossy adaptive circuit is the lossless one on the surviving photons; the policy sees the lossy counts. Loss inserted after an adaptive detector is not of this form: the detector’s earlier result and the policy it triggered cannot be reproduced by thinning the input. In the xx-model a shot partitions the surviving photons into interfering species and singletons. The species evolve independently through the same unitaries Up≤λU^{p\leq\lambda}, and the counts on the adaptive modes are sums over species: stage 1 draws each species’ level counts from its own marginal table (or its own forced chain), a singleton landing on an adaptive mode with its renormalised single-photon probability, and the counts are added before the policy sees them; stage 2 runs one forced-prefix chain per species. Given the partition the species are independent boson samplers on the branch unitary, so the sampler is exact. Detector inefficiency on the adaptive detectors alone (a photon missed there and nowhere else) is not covered: the policy would receive a thinned count while the chain is conditioned on the true one.

Non-linear sites. Loss before the sites is the input-side draw above, and each shot then expands the response for its own photon count, so the rejection factor ∥c∥12\lVert c\rVert_1^2 is that of the surviving photons; loss after the last site is a binomial thinning of the counts. Loss between two sites is not covered: a photon lost there has already shifted the phase of the earlier sites, and tracing it couples branches through the Gram matrix of Sec. S7. For distinguishability the site acts on the total photon number of its mode whatever the internal state, so eiθnx=∏μeiθnx,μe^{i\theta n_x}=\prod_\mu e^{i\theta n_{x,\mu}} over species: given the branch the species are independent and share the branch index, the amplitude of a species-resolved output is ∑bcb∏μPer⁡Ub[sμ,tμ]/∏μsμ!\sum_b c_b\prod_\mu\operatorname{Per} U_b[s_\mu,t_\mu]/\sqrt{\prod_\mu s_\mu!}, and the Cauchy–Schwarz bound holds with ab=∏μPer⁡Ub[sμ,tμ]a_b=\prod_\mu\operatorname{Per} U_b[s_\mu,t_\mu], so the acceptance stays 1/∥c∥121/\lVert c\rVert_1^2: the extension of Algorithm S6 draws bb once, takes one Fock sample of UbU_b per species, and accepts on the species-resolved amplitudes.

Every case above is checked against an enumerated mixture over the loss and species partitions (Table S4 and the tests named in the comments of the source).

samplerinstancennmmTVDexact drawzz
single photonsHaar5100.07220.0739−1.0-1.0
Haar6120.18920.1896−0.3-0.3
superposedα=π/4\alpha= \pi/46120.10310.1036−0.3-0.3
sourcesα=1.1\alpha= 1.1560.03760.0355+1.5+1.5
α=π/4\alpha= \pi/4, η=0.7\eta= 0.76120.06570.0650+0.6+0.6
α=π/4\alpha= \pi/4, x=0.8x = 0.86120.11520.1139+0.9+0.9
α=π/4\alpha= \pi/4, η=0.8\eta= 0.8, x=0.8x = 0.86120.08390.0849−0.6-0.6
photoniclinear cluster, traced (state of the cost table)480.03420.0332+0.7+0.7
caterpillar, projected5100.08100.0797+0.9+0.9
MPSrandom, L=3L = 3, χ=2\chi= 2, traced†390.02120.0223−0.8-0.8
random, L=2L = 2, χ=3\chi= 3, traced†370.01770.0166+0.7+0.7
linear cluster, traced, η=0.7\eta= 0.7480.03920.0382+0.8+0.8
adaptiveK=3K = 3, two levels360.01320.0125+0.4+0.4
K=2K = 2, one level5100.07520.0750+0.1+0.1
K=3K = 3, three levels480.03170.0309+0.6+0.6
non-linearone Kerr site, φ=π/2\varphi= \pi/2360.01310.0123+0.6+0.6
siteone Kerr site, φ=π/4\varphi= \pi/4360.01210.0121+0.1+0.1
one Kerr site, φ=0.9\varphi= 0.9360.01410.0133+0.5+0.5
two sites in sequence360.01650.0136+1.7+1.7

Table S4. Validation against strong simulation on one H100, through the calls of the cost measurements (§ 2.6 of the main text), S=4⋅104S = 4 \cdot10^4 samples per instance, Haar interferometers. “Exact draw”: mean TVD of 40 exact multinomial draws of size SS from the exact law; zz: the deviation of the measured TVD from it in standard deviations of those draws (bench/validate_methods.py). †Outside the range of the GPU kernels of this sampler (χ=2\chi= 2, L≤2L \le2): the reference implementation of the same algorithm, on the same GPU.

Leave-one-out values by division

The leave-one-out values of Sec. 3 of the main text, ej−1(ax)e_{j-1}(a_{\mathbf{x}}), are the coefficients of F(λ)/(1+λax)F(\lambda)/(1+\lambda a_x) with F(λ)=∏i∈Tj(1+λai)F(\lambda)=\prod_{i\in T_j}(1+\lambda a_i). Dividing is cheaper than prefix–suffix products of the main text but stable only in the direction that contracts: forward, cd=Fd−axcd−1c_d=F_d-a_xc_{d-1}, for ∣ax∣≤1\lvert a_x\rvert\leq1, and backward from the top degree, cd−1=(Fd−cd)/axc_{d-1}=(F_d-c_d)/a_x, for ∣ax∣>1\lvert a_x\rvert>1. Against the prefix–suffix form, on Glynn vectors of jj Haar rows with n=2jn=2j columns, forward division alone reaches relative errors of 10−1010^{-10} at j=20j=20, 3⋅10−53\cdot10^{-5} at j=40j=40 and 3030 at j=50j=50; the mixed rule stays at 2⋅10−132\cdot10^{-13}, 5⋅10−105\cdot10^{-10} and 3⋅10−83\cdot10^{-8}. Our GPU build uses it where the division-free form is not instantiated.

Formal proofs in Lean

Lemma 1, Propositions 1 and 2 and stage 2 of the adaptive sampler (Sec. 5) of the main text are formalised in Lean 4 with the Mathlib library. No step is left unproved, and the proofs use only Lean’s standard axioms (propositional extensionality, choice and quotient soundness). Table S5 lists the correspondence; the Lean sources are archived at doi:10.5281/zenodo.24023537. Probabilities are real numbers, amplitudes complex numbers, and slots, output modes and emission labels arbitrary finite types; nothing depends on floating-point arithmetic.

paperLean filemain declarations and content
Definition 1, Lemma 1Basic.leanWeights: non-negative fj(z;T)f_j(z;T) with (C1), (C2). joint_invariant: Pr⁡[z≤j,Tj=T]=(Nsj)−1s0!sj!fj(z≤j;T)\Pr[z_{\leq j},T_j=T]=\binom{N}{s_j}^{-1}\frac{s_0!}{s_j!}f_j(z_{\leq j};T), the induction of the proof. (a): marginal_sum_eq_one, marginal_append; (b): output_law; (c): posterior_from_joint
Proposition 1, Remark 2SuperposedSources.leansuperposedWeights: ∣Per⁡□A[z,T]∣2\lvert\operatorname{Per}_{\square} A[z,T]\rvert^2 is chain-consistent for any offset when AA has orthonormal columns; superposed_target: the chain started from n−kn-k sources outputs zz with probability (n−k)!n!∣Per⁡□A[z,[n]]∣2\frac{(n-k)!}{n!}\lvert\operatorname{Per}_{\square} A[z,[n]]\rvert^2; fock_target: k=nk=n, the Clifford–Clifford law
§ 2.2, weightsEmitterWeight.leanemitterWeights: fj(z;T)=⟨vz∣ρT∣vz⟩f_j(z;T)=\langle v_z\mid\rho_T\mid v_z\rangle is chain-consistent for any normalised ψ\psi over label strings (an MPS being one case); emitter_target: the output law of ψ\psi
Proposition 2EmitterKraus.lean, EmitterKrausRank.leangapwise_kraus: any Kraus decomposition of every inner gap, and any vectors and covectors with the Gram matrices of the end gaps, leave ρT\rho_T unchanged; gapwise_kraus_minimal: decompositions with at most min⁡(original,χ2)\min(\text{original},\chi^2) operators per inner gap and min⁡(original,χ)\min(\text{original},\chi) per end gap exist (spectral theorem on the Choi and Gram matrices)
§ 2.3, stage 2Adaptive.lean, Exchangeable.leanadaptive_continuation: the chain started after the prefix aa from the posterior of part (c) and aborted at the first adaptive row outputs the continuation yy with probability 1[y∩A=∅] q(ay)/qr(a)\mathbf{1}[y\cap A=\varnothing]\,q(ay)/q_r(a), for any chain-consistent weights; conditional_eq: for an exchangeable law, conditioning on the counts pp of the adaptive modes and on “first rr rows apa^p, no later adaptive row” agree, with the counting factor n!/((n−r)! p!)n!/((n-r)!\,p!) (sum_sameCounts_eq); fock_exchangeable: the Fock law is exchangeable

Table S5. Correspondence between the main text and the Lean formalisation (namespace SetChain).

Modelling choices. The chain of Lemma 1 is formalised as in its proof: a uniform initial s0s_0-set, then one slot added uniformly among the unused ones at each step, which is the law of the sets TjT_j of a uniformly random order. A step whose normalisation vanishes gets probability zero, and the proof shows it is reached with probability zero. Proposition 2 is stated for a train already grouped by TT: the prefix vectors, then for each kept emission the operators of the gap before it and its own operator, then the suffix covectors.

Not formalised. The equivalence between the slot-by-slot draw and a random order σ\sigma; the weighted start; the splitting of an arbitrary set TT into its gaps and the identification of the grouped form with the ρT\rho_T of § 2.2; the product of the per-gap counts that gives the bound on RjR_j; the physical derivations (the superposed-source amplitudes and the emission model, whose outcomes enter as the formulas of the main text); for the adaptive sampler, stage 1 (the outcome law and its generating function), the suffix-table draw of the prefix set (§ 5.4; the proof assumes an exact posterior draw) and the identification of qr(ap)q_r(a^p) with the binomial moment M[p]M[p] in the acceptance probability P(p)/M[p]P(p)/M[p]; the non-linear sampler, unequal sources, loss and partial distinguishability, and all cost statements.

References

  1. [1]P. Clifford and R. Clifford, The classical complexity of boson sampling, Proc. SODA 2018, doi:10.1137/1.9781611975031.10, arXiv:1706.01260.DOI
  2. [2]P. Clifford and R. Clifford, Faster classical boson sampling, Phys. Scr. 99, 065121 (2024), arXiv:2005.04214.
  3. [3]C. Oh and Y. Lim, Classical algorithms for measurement-adaptive Gaussian circuits, PRX Quantum 7, 010329 (2026), doi:10.1103/rpl7-ylg8, arXiv:2509.00746.DOI
  4. [4]J. J. Renema, Marginal probabilities in boson samplers with arbitrary input states, arXiv:2012.14917 (2020).arxiv.org/abs/2012.14917
  5. [5]B. Dias and R. König, On the sampling complexity of coherent superpositions, arXiv:2501.17071 (2025, v2 2026).arxiv.org/abs/2501.17071
  6. [6]S. Bravyi, D. Gosset and Y. Liu, How to simulate quantum measurement without computing marginals, Phys. Rev. Lett. 128, 220503 (2022), arXiv:2112.08499.DOI
  7. [7]N. Spagnolo, D. J. Brod, E. F. Galvão and F. Sciarrino, Non-linear boson sampling, npj Quantum Inf. (2023), doi:10.1038/s41534-023-00676-x, arXiv:2110.13788.DOI
  8. [8]N. Heurtel et al., Perceval: a software platform for discrete variable photonic quantum computing, Quantum 7, 931 (2023).DOI
  9. [9]S. Aaronson and A. Arkhipov, The computational complexity of linear optics, Theory Comput. 9, 143 (2013).
  10. [10]J. Senellart and P.-E. Emeriau, Efficient estimation of linear-optical amplitudes and probabilities for photonic states from quantum emitters, in preparation (2026).
  11. [11]D. J. Brod and M. Oszmaniec, Classical simulation of linear optics subject to nonuniform losses, Quantum 4, 267 (2020), arXiv:1906.06696.DOI
  12. [12]N. Quesada and J. M. Arrazola, Exact simulation of Gaussian boson sampling in polynomial space and exponential time, Phys. Rev. Research 2, 023005 (2020), arXiv:1908.08068.DOI
  13. [13]N. Quesada et al., Quadratic speed-up for simulating Gaussian boson sampling, PRX Quantum 3, 010306 (2022), arXiv:2010.15595.arxiv.org/abs/2010.15595
  14. [14]J. F. F. Bulmer et al., The boundary for quantum advantage in Gaussian boson sampling, Sci. Adv. 8, eabf9236 (2022), arXiv:2108.01622.DOI
  15. [15]C. Oh, Y. Lim, B. Fefferman and L. Jiang, Classical simulation of boson sampling based on graph structure, Phys. Rev. Lett. 128, 190501 (2022), arXiv:2110.01564.DOI
  16. [16]D. A. Ivanov and L. Gurvits, Complexity of full counting statistics of free quantum particles in product states, Phys. Rev. A 101, 012303 (2020).DOI
  17. [17]S. Rahimi-Keshari, T. C. Ralph and C. M. Caves, Sufficient conditions for efficient classical simulation of quantum optics, Phys. Rev. X 6, 021039 (2016), arXiv:1511.06526.
  18. [18]T. Goubault de Brugière and N. Heurtel, Fast and memory efficient strong simulation of noisy adaptive linear optical circuits, arXiv:2503.05699 (2025).arxiv.org/abs/2503.05699
  19. [19]A. Bouland, D. Brod, I. Datta, B. Fefferman, D. Grier, F. Hernández and M. Oszmaniec, Complexity-theoretic foundations of BosonSampling with a linear number of modes, Phys. Rev. X 16, 021059 (2026), arXiv:2312.00286.arxiv.org/abs/2312.00286
  20. [20]U. Chabaud, D. Markham and A. Sohbi, Quantum machine learning with adaptive linear optics, Quantum 5, 496 (2021), arXiv:2102.04579.DOI

Paper details

vlnc:W_cxxkjwjb
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Claude

View statement
Looking for related papers…
Contents