In this paper
Abstractchain_rules.pdfIntroductionThe set-chain lemmaLoss and partial distinguishabilitySuperposed sourcesPhotonic matrix-product statesAdaptive linear opticsNon-linear sitesComparison of the samplersNumerical evaluationValidationCostConclusionAcknowledgementsExact sampling beyond Fock inputs and linear optics: photon-number superpositions, photonic matrix-product states, adaptive and non-linear circuits — supplementary materialchain_rules_supp.pdfPseudo-codeComparison with other exact algorithmsSuperposed sources against PercevalThe column draw of the adaptive samplerPrior exact samplersComplexity of photonic matrix-product statesWhy the random-order chain fails at a non-linear siteValidation tableLoss and partial distinguishabilityLeave-one-out values by divisionFormal proofs in LeanReferencesWorksPhysics 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 . All four samplers agree with strong simulation on small instances, and cost models put adaptive sampling with up to three adaptive modes within of single photons and a non-linear site at at about .
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, single photons in an -mode linear interferometer , 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 photons (the first output rows) is the average, over the 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, . Their 2020 refinement [3] exploits repeated output rows and brings the average cost over Haar interferometers to , the growth depending on the mode ratio ( at ).
The proof uses three properties of this setting: the input is a product of single photons; the interferometer acts on them as ; and the columns of are orthonormal, , 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 :
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 -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 [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 component pairs for superposed sources with 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 ( for 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 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:
for superposed sources, a rectangular permanent on an active set started at sources, at the cost exponent of single photons under loss (§ 2.1, Proposition 1);
for photonic MPS, a gapwise Kraus contraction that writes each weight as squared amplitudes evaluated by matrix-valued Glynn sums; on the trains we measured, is 1–2 on the last steps, which carry the cost (§ 2.2, Proposition 2);
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);
for non-linear sites, where the natural weight fails the lemma, the branch-rejection principle applied to linear branches, exact with acceptance probability (§ 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 detected photons in modes is drawn as an ordered tuple of rows from a law , one output mode per photon; forgetting the order gives the occupation pattern that the detectors record, photons in mode . The lemma does not need to be exchangeable, for every permutation (the pattern listed in a uniformly random order); the laws of this paper are, and Sec. 5 uses it. There are slots (input columns: photons, sources, emission events), and a non-negative integer offset : the chain starts from slots and adds one per placed row, so that after rows its active set holds slots.
Notation: ; is the sub-matrix of rows (with repetition) and columns , keeps all rows; ; for counts .
Definition 1 (Chain-consistent set weights). A family , defined for , and with , is chain-consistent if
Its target is .
Lemma 1 (Set-chain lemma). Let be chain-consistent (Definition 1), with . Draw a uniformly random order of ; for set and draw with probability . Then
(a) is a probability law, and its marginal on the first rows is ;
(b) the algorithm outputs with law ;
(c) at every step, the law of the active set given the rows drawn so far is .
Proof. By induction on with (C2), for every , so sums to one. Summing over the last row and using (C2), each -set is reached from the sets , and gives , which is (a). For (b) and (c) we show by induction that . It holds at by (C1), being a uniform -set. The set is plus a uniform element of its complement, so
the last step by (C2). The step probability is therefore needed only where : a pair with a zero denominator is reached with probability zero. Multiplying by the step probability gives the claim, which yields (c) directly and (b) after summing over at . □
Weighted start. If (C1) is replaced by and is drawn with probability , , the remaining slots being added in a uniformly random order, the same induction gives , with unchanged step probabilities; is the lemma statement.
Remark 1 (Scope of the lemma). The step weight depends on the set , not on the order inside it, and the identity (C2) is used only after summing over the sets: the pointwise identity 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: with satisfies (C1)–(C2) for any . 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 for all candidate rows , 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 single photons in input modes , , take , and . Condition (C2) is the Laplace expansion of the permanent along the last row followed by the orthonormality of the columns of , and is the law of the ordered output. This is Clifford and Clifford’s algorithm B [2]; the candidate weights of a step share the cofactors , all obtained from one Glynn sum over sign vectors [2], collapsed to terms when the placed rows repeat with multiplicities [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 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.

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 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 (-)model, each photon or source independently in a common internal mode with probability 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 sources emits the same state , source into input mode (unequal sources at the end of this section); the photons pass through an -mode interferometer and are detected with photon-number resolution [5]. A passive interferometer conserves photon number, so the detected count is exactly whatever , and given the input is the Dicke state . With (, orthonormal columns), the amplitude of an ordered -row output is the rectangular permanent
and . Here, as throughout, is a law on ordered tuples, collisions included: an occupation pattern with has probability for any ordering of .
At the mean count is and the binomial upper tail carries the cost. The incoherent mixture of the same sources — each source firing with probability , which source fired being recorded — has the same photon-number law; it is single photons under input loss .
The offset-start order. A random order over the sources, not the photons, gives chain-consistent weights once the active set starts with sources instead of none: after the steps it then holds all , and the weight of a set is the rectangular permanent of the rows placed so far.
Proposition 1. For superposed sources conditioned on photons, , and ( rows, columns) are chain-consistent weights with target .
Proof. (C1): the empty rectangular permanent is 1. (C2): expand over the column used by the last row in each of the two injections; summing over , removes the cross terms and leaves . Target: at the only set is , and .
At the offset vanishes and the chain is Clifford and Clifford’s. At the sources that supply no photon are never identified. Part (a) of the lemma recovers the true marginal , the residual-set form that a direct sampler would have to enumerate.
The step. With rows placed, the candidate weights share the cofactors , , and . Glynn’s identity [20] with one sign per placed row gives every cofactor at once,
the elementary symmetric polynomial of degree of the values other than . Since is homogeneous, the global flip leaves the summand invariant and signs suffice. The leave-one-out value is the coefficient of in , and since the offset is constant along the chain, , also the coefficient of in . Prefix and suffix products of the linear factors, truncated at degree in whichever variable is shorter, give every leave-one-out value without division in ; a cheaper division, stable in one direction, is described in Sec. ??. At this is the all-but-one product of the single-photon step, so at 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 contribute terms instead of , walked in the same reflected Gray order as for single photons. The cost of a step is and of a sample at most
the exponent of single photons under loss ; 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 with different amplitudes, . With and the scaled columns , the output amplitude given photons is up to a constant, and the weights , , satisfy (C2): expanding the last row now leaves , and . With the weighted start of Sec. 2, drawn among the -sets with probability (a polynomial draw by elementary symmetric polynomials), the chain samples the output law conditioned on , whose photon number is the Poisson-binomial law of the . The factor cancels in every step, so a step is that of equal sources on the columns of : dim sources are more likely to start in the unused set. A source with never fires and is removed; one with always fires and never enters . An exact enumeration of this chain over initial sets, orders and output rows reproduces the output law of five random instances with unequal sources, , to ; our GPU implementation covers equal sources.
Photonic matrix-product states
Model. A quantum emitter with an internal memory of dimension (a spin, ; for instance a quantum-dot spin driven to emit linear graph states [9]) emits photons one after the other; emission puts one photon into one of input modes with operator (), and the photonic state is the matrix-product state [7]
with and the initial and final emitter states and all input modes distinct (dual-rail time bins for ); a traced final emitter state is a first draw. The caterpillar (spin-photon cluster) states [8] are with spin gates . The model contains single-photon boson sampling (, , ), 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 : the emissions are isometric, , and a traced final emitter state is drawn first, with probability ; the displayed amplitudes are then divided by , with , or equivalently is rescaled.
Weights. The slots are the emissions, , . For a set of emissions let , a state of photons, and for let be the covector
the amplitude of the ordered output for a -photon state on the modes ; the components of the ket are the conjugates . Then is chain-consistent: (C1) is the trace; for (C2), expand both permanents of along the last row, ; the sum over gives because the input modes are distinct, and leaves . The target is the output law of . 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. is mixed because the emissions outside are traced, and for a random order is an arbitrary subset of the train: its complement splits into disjoint maximal runs of traced emissions, the gaps. A contraction of with the transfer map 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 label strings of every gap . The following proposition compresses each gap’s transfer map into at most Kraus operators, whatever its length, and so keeps a sum of squared amplitudes with few terms.
Proposition 2 (Gapwise Kraus contraction). Let , and for a gap (a maximal run of emissions not in ) let be the ordered product of its emission operators and its map on matrices. Choose any Kraus decomposition of every inner gap (between and ), any vectors with for the prefix gap (before ) and any covectors with for the suffix gap (after ). For a choice of one index per gap let
(an absent gap contributes the identity, or , at the ends). Then , and every is a matrix-product state of bond dimension on the emissions of . Inner gaps have Kraus rank at most and end gaps at most , so the number of terms is , with inner and end gaps.
Proof. . Read as with , and contract from the right: starting from , a kept emission maps , and the labels of a gap occur only in that gap’s factors, once on each side, so summing them maps . Each may be replaced by any of its Kraus decompositions, the prefix gap by the vectors and the suffix gap by the covectors ; expanding the products of sums gives . The Choi matrix of is , which bounds an inner gap’s Kraus rank by ; the end gaps produce positive matrices, rank at most . The bound is the explicit sum over the traced labels.
We take the minimal decompositions, by an SVD of the stacked reduced emission by emission, so the cost of a gap is linear in its length. For instance, with and , the middle emission is a gap of length one, , and with terms.
Matrix-valued Glynn sums. So , a sum of squared amplitudes, and each amplitude factorises through the matrix product inside Glynn’s sum. With column sums and , the kept emission’s operator with the Kraus operator of the gap before it absorbed,
because Glynn’s formula , applied to , is multilinear in the columns and the sum over passes inside the product. For the Laplace step the last row is left out: the candidate amplitude is with the matrix cofactors
where and denote the kept emissions before and after in (not the emissions ), and the Glynn sum runs over the placed rows (the global flip leaves the summand of a permanent invariant) — the scalar prefix and suffix products of the Fock kernel replaced by ones. For ; at no row is placed and . The 2020 collapse acts on only and carries over unchanged. Algorithm ?? (Supplementary Material).
The term count. With Glynn terms (, fewer after the collapse), a step costs : per term and sign vector, matrices and the prefix and suffix sweeps, then the candidates. Measured means of are far below the bound of Proposition 2, peaking at (7 at , 30 at , 96 at on a linear cluster) and falling to 1–2 on the last steps, which carry the weight. The per-gap decomposition is minimal gap by gap but not globally; comparing with the rank of over all steps, the surplus is up to on single early steps but, weighted by step cost, – for –20. Since the rank is the smallest number of terms any decomposition of can have, a better decomposition would save at most about 10% of the run time.
Adaptive linear optics
Model. single photons enter ; output modes are read with photon-number resolution in levels, and after each level a classical function of the counts read so far chooses the unitary applied to the unmeasured modes [10]. Each adaptive outcome has its cumulative unitary and , with the output occupations read as a tuple of rows and , 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 and BQP-complete for , and sample exactly and efficiently when the input and the final measurement are Gaussian and ; for Fock input with photon-number-resolved final detection they give marginals and mean values, not a sampler.
Stage 1: the adaptive outcome. depends on only, since later act on modes that are traced in it; the outcomes form a chain over levels whose conditionals are -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 of adaptive modes is , , formal variables, whose coefficients are the binomial moments , accumulated photon by photon on a table graded by total degree and inverted. This fits for at . Beyond, the counts of level can be read from a stage-2 chain on conditioned on the earlier counts and accepted with probability ; 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 are the Fock output of conditioned on “the adaptive modes show exactly ”. By exchangeability of the ordered law this is the conditional given “the first rows are (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 rows has law . Because has only distinct rows, a permanent with repeated rows is a coefficient of a product of linear forms, with and , and deciding the columns one by one from suffix tables of draws from this posterior with tables of entries, polynomial for fixed (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 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 , the binomial moments: by exchangeability, and are the probabilities that the first rows are with and without the constraint, each multiplied by the same factor .
Cost. A branch starts chains, the binomial moments of its own interferometer, so the mean number of chains started per sample is , over the outcomes that occur. For a fixed interferometer, , and when every outcome has positive probability, the generating function of the binomial moments turns this into , 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 rows are exchangeable, so a chain with further photons on the adaptive modes places them at a uniformly random -subset of its free steps and stops at the first, , at step on average; with a step cost growing like , it is charged of a full chain. A cost model built on the first-level interferometer, at and , gives , 3.8, 6.8 chains for and a time per sample , 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 at –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 acts on mode between Haar interferometers and ; the response is a Kerr phase, [12], or any response diagonal in the photon number. On photons has eigenvalues , so the response is exactly a finite sum of phase shifters, , and the circuit is a coherent sum of linear interferometers with weights . The decomposition is not unique; we use the shortest periodic one: the response on is a linear phase times a function of smallest period , expanded on its -point discrete Fourier transform, , so that and . at and , 2 at , 4 at , and for a response without short period, such as ; several sites multiply the branches.
Failure of (C2). For a linear circuit the traced photons contribute with (Remark 2), so the marginal is diagonal in the hidden set. Here two branches meet through , , whose rank-one term couples different hidden sets. The natural set weight therefore violates (C2): the random-order chain built on it misses the law by a TVD of 0.115 at , , Kerr 0.9, where the same enumeration reproduces a linear circuit to . 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 with probability , an ordinary Fock sample of (the Fock kernels unchanged), and accept with probability , the amplitude of the occupation . By Cauchy–Schwarz, , so this is a probability. The proposal draws with probability , so is proposed and accepted with probability : proportional to the target, and summing to because , the circuit being unitary. The sampler is exact, with acceptance probability exactly (measured 0.43–0.59 against 0.50 at ; 0.054–0.077 against 0.0625 at ). An accepted sample costs Fock samples, the measured cost of one branch permanent. For a fixed number of sites and a response of bounded period () this is a constant factor and the exponential rate in is that of single photons; for a generic response and the factor is polynomial. Algorithm ?? (Supplementary Material). This is the -weighted specialisation of the rejection principle of Dias and König [15], applied to the branch decomposition with weights instead of : by Cauchy–Schwarz , and for a given decomposition the weights minimise the constant (at the two coincide, ; at , , 33.2 against 40). The constant 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 the rejection factor tends to one as , but it is governed by rather than . A Kerr phase already costs at , while costs 2. Over sites at the rejection factor is , and each proposal evaluates branch amplitudes, about in all, so the exponent changes once the number of sites grows with . A chain-consistent family for 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 / circuit | slots | weight | terms | step cost | overhead over single photons | |
| single photons | photons | 0 | 1 | $2^j j + m j$ | — | |
| superposed sources | sources | 1 | payload factor , | |||
| photonic MPS | emissions | 0 | term count | |||
| adaptive optics | photons | 0 | , started by (c) | 1 | $2^j j + m j$ | rejection of chains that put a further photon on an adaptive mode: chains |
| non-linear site | photons | — | none known | — | $2^j j + m j$ per branch sample | rejection, |
| any input, generic chain [6] | photons | 0 | the true marginal | — | (input pairs) subsets | none of its own; no speed-up |
| any superposition [15] | — | — | none (rejection) | — | one component sample and the target amplitude | mixture of components: |
Table 1. How the four methods use — or depart from — the set chain; step costs up to constants, placed photons, 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 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 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 of order one. This reference stays valid when the output space is large against , 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 -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 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 to on six instances with .
The Supplementary Material (Sec. ??, Table ??) lists 19 instances: single photons, superposed sources with loss and partial distinguishability, traced and projected MPS trains up to and , 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 ; 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 uses one Haar unitary, the QR decomposition of a complex Ginibre matrix with the phases of the diagonal of 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 , of the cost measured at each : the cost of a shot grows like , and a plain mean over a short run would miss the rare large- shots.
The cost of superposed sources falls with the photon number at the exponent of single photons under loss , and the coherence enters the cost of a step through the offset: grows as the sources dim, and each Glynn term carries the factor of Table 1; at the offset is empty and the sampler runs the single-photon step at – times its cost (; at ). Against single photons under loss on the same instance the time ratio is , , and at , , and . For photonic MPS the overhead is the term count , which is small on the last steps that carry the cost on the trains we measured (); how it grows with is open. For adaptive optics the overhead is set by the photons read adaptively, , not by the number of adaptive modes, and only changes the exponent. A non-linear site costs , 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 , and for photonic MPS the rate depends on the growth of .
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.) | instance | kind | cost, relative to the single-photon sampler of the same size |
| single photons [3] | / 34 photons | time | 1 |
| superposed sources (3) | sources, (offset empty) | time | 1.05–1.15 |
| sources, / 0.99 / 0.95 / 0.9 / 0.8 | time | 1.04 ± 0.09 / 0.97 / 0.75 / 0.52 / 0.23 | |
| photonic MPS (4) | linear cluster, , / 12 / 16 | count | a step costs single-photon steps; mean peaks at 7 / 30 / 96 near and falls to 1–2 on the last steps, which carry the cost |
| adaptive (5) | –38, / 2, Haar policy | count | 2.1 / 4.1 chains per sample (mean) |
| , / 2 / 3 | model | time / 1.07 / 1.10 | |
| non-linear site (6) | one site, () | count | acceptance 0.43–0.59 against ; branch permanent samples |
| model | |||
| count | acceptance 0.054–0.077 against 0.0625 |
caption: Cost of the samplers on one H100, , Haar interferometers, relative to the single-photon sampler on an instance of the same size (for superposed sources: sources against photons); the single-photon sampler takes 6.2 ms () and 69 ms () 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 : if grows exponentially with , the prefix-amplitude sampler is faster at large (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 , 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 with , 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: (), input modes ; ()
uniform order of the columns
for do ; () , rows may repeat
( without column ) for all Cofactors()
for every output mode ; draw
end for
return occupation of
function Cofactors() one Glynn sum gives all cofactors
distinct rows of and their multiplicities
; ; ; for all : rows of group signed
for each in reflected mixed-radix Gray order do terms
on the step : ; (ratio of )
for all all-but-one products
end for
return full sum as written; pairing with halves it (as in [1])
end function
Algorithm S2 Superposed sources: random source order with offset start.
Require: (), source modes , ; transmission , common-mode probability
draw the live sources (each with prob. ), and among them those in the common internal mode (each with prob. ); no live source: return the vacuum
▷ , defined at
for each live source in its own internal mode do ▷ factorises out of the Dicke coherence
with prob. : one photon on output ▷ otherwise vacuum
end for
live sources in the common mode; draw
uniform order of ;
for do
first columns of
for all ▷
for ; draw
end for
return occupation of plus the photons of the sources in their own mode
function ▷ : rows, columns,
if then return
distinct rows of and their multiplicities; ;
for each in reflected mixed-radix Gray order do ▷ as in Algorithm S1
on the step : ;
for all
end for
return ▷ full sum as written; homogeneous, so pairing with halves it
end function
function ▷ ,
if then return ▷ all-but-one product: the single-photon payload
else if then return ▷ of , degree
else return ▷ of , degree
end if
end function
Algorithm S3 Photonic MPS: reduced-state chain with purified terms and matrix cofactors.
Require: , emission operators () and input modes (, ), ; transmission
draw the lost emissions (each with probability ); the kept ones,
draw the labels of the lost emissions and the final emitter state from their exact joint marginal ▷ label unravelling: each lost emission now carries one operator ; lossless: only ▷ the kept state given these draws is normalised; its scale cancels from the row draws below
uniform order of
for do
in emission order;
for each term do
for
for every output mode
end for
; draw ▷
end for
return occupation of
function ▷ purification of :
for each gap (maximal run of emissions not in , prefix and suffix runs included) do
Kraus operators of , lost emissions inside the run enter with their drawn operator, not summed by SVD of the matrix with columns (the Choi matrix), reduced emission by emission (rank ; at the ends; Prop. 2)
end for
one term per choice of in every gap: for the kept emission before the gap, prefix gap into , suffix gap into ; drop zero-norm chains
return the terms
end function
function ▷ Glynn over the placed rows, products
if then return for the single ▷ no placed row
for
for in Gray order do ▷ 2020 collapse on repeated rows: mixed-radix walk
;
, ▷ prefix / suffix sweeps
end for
return
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 , sites (response between and ), input modes ; transmissions (before the sites), (after)
draw the surviving photons (each with probability ); their number, their modes
if then return the vacuum
for each site: ▷ the expansion of this stream’s own photon count
, for every branch
repeat
draw with probability ; one Fock sample of on ▷ Clifford–Clifford, 2020 kernels
for every branch ▷ batched Laplace cofactors
accept with probability
until accepted ▷ acceptance exactly
thin binomially with ; return
function ▷ exactly on photons
for
smallest with constant on ▷ always works
(-periodic); ,
return ▷ every non-zero coefficient: the expansion is exact
end function
Implementation note. In floating point the transform returns coefficients at rounding level where the exact ones vanish (e.g. at ). Our code drops those with and checks that the remaining expansion reproduces on to . The site is then replaced by a diagonal operator within of it on every Fock state of at most photons in mode , so the output state moves by at most per site in norm and the output law by at most 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 modes decomposed into beam splitters for the prefix-amplitude sampler of [6], with 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 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 single-photon samples (measured).
| sampler, size | best prior exact alternative | its cost (estimate) | ours |
| superposed sources | generic chain [4]; component rejection [5]; prefix amplitudes [6] | pairs per step; acceptance per sector; amplitudes of cost | per sample (the exponent of lossy single photons) |
| photonic MPS, | prefix amplitudes [6] | per step | – per step where the cost is (measured –) |
| adaptive, , | prefix amplitudes [6]; Gaussian model only [3] | permanents | 2.0–6.8 chains started (cost model), mostly aborted early: time ratio – |
| non-linear, , | gadget [7]; prefix amplitudes [6] | gadget: before the herald rate; | |
| non-linear, generic , | component rejection [5]; prefix amplitudes [6] | ; |
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 (text).
| method | applies to | cost structure, and relation to the main text |
| chain over the true marginal [4] | any input state | pairs of input components hidden subsets per step: up to for superposed sources (direct expansion, late steps), up to for an MPS train (Remark 1) |
| component rejection [5] | coherent superposition of components | proposals; for superposed sources in the Fock basis; its principle, reweighted, in Sec. 6 |
| prefix amplitudes [6] | any circuit | amplitudes per sample, no marginals; Sec. S2 |
| repeated input modes [11] | Fock input with repeated modes | Clifford–Clifford extended |
| Gaussian chains [12, 13, 14] | Gaussian inputs | loop hafnians over output modes, in the detected photons; out of scope |
| bounded treewidth [15]; phase space [17] | structured interferometers; classical or noisy light | tractable marginals; efficient |
| adaptive Gaussian [3] | Gaussian input and measurement, adaptive modes | efficient exact sampler; Fock input with PNR final detection in Sec. 5 |
| adaptive linear optics [20] | Fock input, adaptive measurements | estimates output probabilities and overlaps; not a sampler of the full output |
| noisy adaptive circuits [18] | Fock input, feed-forward, noise | strong simulation: output probabilities, amplitudes or derivatives of a polynomial; not a sampler |
| Kerr gadget [7] | one Kerr site | linear 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 . At large 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 ( single-photon steps), while ours is the term count, a step costing about single-photon steps. How grows with is not known. On the trains we measured () 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 weighted by step cost; but the bound of Proposition 2 grows exponentially with the number of gaps. If stays small on the costly steps, our overhead is a constant factor; if it grows exponentially with , the prefix-amplitude sampler is faster once exceeds . A cost model of would locate the crossover, and a sampler that uses the term expansion where is small and pure-state amplitudes where it is large would combine the two.
Superposed sources against Perceval
| TVD to Perceval | shot noise | coherent vs incoherent | ||||
| 4 | 8 | 1 | 0.0257 | 0.0263 | 0.374 | |
| 6 | 12 | 1 | 0.0991 | 0.1002 | 0.394 | |
| 5 | 6 | 1.1 | 1 | 0.0365 | 0.0362 | 0.193 |
| 7 | 7 | 1 | 0.0586 | 0.0580 | 0.421 | |
| 5 | 8 | 0.7 | 0.0281 | 0.0275 | 0.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 · 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 (, ) the mean occupation of every output mode matches the coherent prediction , with brightness and coherence , to , and misses the incoherent one by (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 distinct rows with multiplicities , , and (Sec. 5 of the main text). For , a permanent with repeated rows is a coefficient, with : expanding the product, the coefficient of sums over the assignments of the columns of to the labels with counts , and each assignment stands for permutations. Hence . Deciding the columns in the order , with the columns already taken and , the total weight of the completions is
where truncation at degree keeps exactly the completions with . Taking column with probability , the two completion weights with and without it, therefore draws with probability , the posterior of Lemma 1(c) of the main text. The tables have entries, polynomial for fixed (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 , and the train is 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 , pure), assuming the tensors , , are polynomially bounded and given exactly and a label word with is known. For , computing the amplitude of a collision-free output exactly is #P-hard, and so is approximating its squared modulus to within a multiplicative factor , by the corresponding result for [9]: the interferometer is chosen to carry a scaled copy of an arbitrary matrix on the columns and zeros on the other label columns, so that only contributes. Computing the polynomial exactly with probability over standard complex Gaussian is as hard: such an algorithm gives . Hardness of approximate sampling in the sense of Ref. [9] is only conditional. It needs a multiplicative-estimation conjecture and an anticoncentration conjecture for , neither known to follow from the Fock case, and a hiding step that padding to an block takes from Ref. [9] only for of 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 , the scaled copy, where is positive and computable in polynomial time for a suitable known ; 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 ), 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 requirement belongs to this construction, and 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 ordered rows of the circuit is
the rows of are the input modes of the photons left by the conjugated amplitude and its columns those of the left by the other (second line). For a linear circuit and the last factor is , which is Remark 2 of the main text. For a single site, and with : the rank-one term couples . With several sites need not have rank one (two phases on different modes with identity interferometers and one branch pair give on those two modes); the general form above still holds. The true-marginal chain exists, but evaluated as written its quadratic form has pairs of branches and sets per candidate at step , each with a permanent of size , up to pairs at ; 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 with few terms per set: purifying the traced photons in the basis after the trace gives a sum of squares indexed by their configurations, and splitting each traced photon into “on ” and “not on ” reintroduces the coupling through the rank- projector.
Validation table
Loss and partial distinguishability
Loss is uniform, one transmission per photon at the input; partial distinguishability is the mixture (-)model, each photon or source independently in a common internal mode with probability and otherwise in an internal mode of its own, orthogonal to all others, so two photons overlap with probability . 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 () and the chain runs on their columns; distinguishability draws which survivors share the common mode, the others being routed classically by . The cost is that of the interfering photons.
Superposed sources. Loss maps each source to a mixture of vacuum and a source at a smaller , , drawn per source before the chain. In the -model, a source in its own mode factorises out of the Dicke coherence: its photon is present with probability and is routed by , and the chain runs on the live sources in the common mode. Both mixtures are drawn exactly (Algorithm S2). Non-uniform loss, per source, gives live sources with different amplitudes, , 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 : 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 , and the kept emissions are in a pure state, a matrix-product state of bond dimension on emissions; the chain runs on it as on a lossless train of emissions. At step 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 is that of the lossless -emission train, and the last step has . Without this draw the lost emissions widen every gap and remain traced to the end; an inner gap of lost emissions contributes up to terms even at the last step. The draw does not bound at earlier steps; on the trains we measured, where 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 -model, an emission 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 is drawn from the exact marginal, jointly with the lost labels and the final emitter state, and the slot then carries the fixed operator , 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 . The correlations of, e.g., a state 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 -model a shot partitions the surviving photons into interfering species and singletons. The species evolve independently through the same unitaries , 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 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 over species: given the branch the species are independent and share the branch index, the amplitude of a species-resolved output is , and the Cauchy–Schwarz bound holds with , so the acceptance stays : the extension of Algorithm S6 draws once, takes one Fock sample of 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).
| sampler | instance | TVD | exact draw | |||
| single photons | Haar | 5 | 10 | 0.0722 | 0.0739 | |
| Haar | 6 | 12 | 0.1892 | 0.1896 | ||
| superposed | 6 | 12 | 0.1031 | 0.1036 | ||
| sources | 5 | 6 | 0.0376 | 0.0355 | ||
| , | 6 | 12 | 0.0657 | 0.0650 | ||
| , | 6 | 12 | 0.1152 | 0.1139 | ||
| , , | 6 | 12 | 0.0839 | 0.0849 | ||
| photonic | linear cluster, traced (state of the cost table) | 4 | 8 | 0.0342 | 0.0332 | |
| caterpillar, projected | 5 | 10 | 0.0810 | 0.0797 | ||
| MPS | random, , , traced† | 3 | 9 | 0.0212 | 0.0223 | |
| random, , , traced† | 3 | 7 | 0.0177 | 0.0166 | ||
| linear cluster, traced, | 4 | 8 | 0.0392 | 0.0382 | ||
| adaptive | , two levels | 3 | 6 | 0.0132 | 0.0125 | |
| , one level | 5 | 10 | 0.0752 | 0.0750 | ||
| , three levels | 4 | 8 | 0.0317 | 0.0309 | ||
| non-linear | one Kerr site, | 3 | 6 | 0.0131 | 0.0123 | |
| site | one Kerr site, | 3 | 6 | 0.0121 | 0.0121 | |
| one Kerr site, | 3 | 6 | 0.0141 | 0.0133 | ||
| two sites in sequence | 3 | 6 | 0.0165 | 0.0136 |
Table S4. Validation against strong simulation on one H100, through the calls of the cost measurements (§ 2.6 of the main text), samples per instance, Haar interferometers. “Exact draw”: mean TVD of 40 exact multinomial draws of size from the exact law; : 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 (, ): 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, , are the coefficients of with . Dividing is cheaper than prefix–suffix products of the main text but stable only in the direction that contracts: forward, , for , and backward from the top degree, , for . Against the prefix–suffix form, on Glynn vectors of Haar rows with columns, forward division alone reaches relative errors of at , at and at ; the mixed rule stays at , and . 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.
| paper | Lean file | main declarations and content |
| Definition 1, Lemma 1 | Basic.lean | Weights: non-negative with (C1), (C2). joint_invariant: , the induction of the proof. (a): marginal_sum_eq_one, marginal_append; (b): output_law; (c): posterior_from_joint |
| Proposition 1, Remark 2 | SuperposedSources.lean | superposedWeights: is chain-consistent for any offset when has orthonormal columns; superposed_target: the chain started from sources outputs with probability ; fock_target: , the Clifford–Clifford law |
| § 2.2, weights | EmitterWeight.lean | emitterWeights: is chain-consistent for any normalised over label strings (an MPS being one case); emitter_target: the output law of |
| Proposition 2 | EmitterKraus.lean, EmitterKrausRank.lean | gapwise_kraus: any Kraus decomposition of every inner gap, and any vectors and covectors with the Gram matrices of the end gaps, leave unchanged; gapwise_kraus_minimal: decompositions with at most operators per inner gap and per end gap exist (spectral theorem on the Choi and Gram matrices) |
| § 2.3, stage 2 | Adaptive.lean, Exchangeable.lean | adaptive_continuation: the chain started after the prefix from the posterior of part (c) and aborted at the first adaptive row outputs the continuation with probability , for any chain-consistent weights; conditional_eq: for an exchangeable law, conditioning on the counts of the adaptive modes and on “first rows , no later adaptive row” agree, with the counting factor (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 -set, then one slot added uniformly among the unused ones at each step, which is the law of the sets 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 : 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 ; the weighted start; the splitting of an arbitrary set into its gaps and the identification of the grouped form with the of § 2.2; the product of the per-gap counts that gives the bound on ; 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 with the binomial moment in the acceptance probability ; the non-linear sampler, unequal sources, loss and partial distinguishability, and all cost statements.
References
- [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]P. Clifford and R. Clifford, Faster classical boson sampling, Phys. Scr. 99, 065121 (2024), arXiv:2005.04214.
- [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]J. J. Renema, Marginal probabilities in boson samplers with arbitrary input states, arXiv:2012.14917 (2020).arxiv.org/abs/2012.14917
- [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]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]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]N. Heurtel et al., Perceval: a software platform for discrete variable photonic quantum computing, Quantum 7, 931 (2023).DOI
- [9]S. Aaronson and A. Arkhipov, The computational complexity of linear optics, Theory Comput. 9, 143 (2013).
- [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]D. J. Brod and M. Oszmaniec, Classical simulation of linear optics subject to nonuniform losses, Quantum 4, 267 (2020), arXiv:1906.06696.DOI
- [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]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]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]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]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]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]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]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]U. Chabaud, D. Markham and A. Sohbi, Quantum machine learning with adaptive linear optics, Quantum 5, 496 (2021), arXiv:2102.04579.DOI