In this paper
AbstractIntroductionContributions.Background: additive estimation for product inputsEntangled inputs as photonic matrix-product statesDefinitionWhat the bond dimension measuresStates generated by quantum emittersVacuum emissions and lossThe Gaussian identityThe sequential importance samplerOther quantities we can estimateTraced memoryOverlapsFew-mode marginals and linear statisticsAccuracy and statistical interpretationAdditive error and shot noiseHeavy tailsHow much quantum memory would an advantage need?Numerical checks, cost and formalisationConclusion and open questionsReproducibilityAcknowledgementsSupplementary materialVacuum emissionsFinite local Fock supportUnused modes and known lossKnown lossRademacher variantHeavy tailsFurther remarksValidation and cost per drawFormal proofs in LeanReferencesWorksPhysics and Astronomy
On the estimation of linear-optical amplitudes and probabilities with entangled input state
Abstract
Most proposed applications of boson samplers, including photonic machine-learning models, do not use the samples themselves but estimates of output probabilities, marginals or overlaps, obtained to additive precision from a finite number of shots. For product inputs such as single photons, these quantities can already be estimated classically with Gurvits's algorithm and its generalisations. We ask whether entangled inputs change this picture. For any -photon input that is a matrix-product state of bond dimension , with one photon per site and modes per site, we give an unbiased estimator of any output amplitude of an -mode interferometer, whose mean-square error after draws is at most whatever the interferometer, the output pattern and the entanglement of the state. Each draw costs operations after preprocessing, and an additive error with probability at least requires draws, with memory of the order of the input size. The main application is to light emitted sequentially by quantum emitters, such as spin-based sources of photonic cluster states, for which is bounded by the dimension of the source's retained quantum memory: one spin gives at any length, and a memory of qubits, held in emitters or in photons stored in a delay line, gives , so the cost stays polynomial as long as . The same sampler also estimates traced-memory probabilities, overlaps and individual marginal probabilities. All guarantees are additive: the estimator gives neither relative estimates of exponentially small probabilities nor a sampler of the output distribution.
Introduction
Linear optics with single photons is one of the most studied routes for quantum computational advantage. In boson sampling, indistinguishable photons enter an -mode interferometer and are detected at its output. Each output probability is the squared modulus of the permanent of an submatrix of the interferometer, and Aaronson and Arkhipov showed that sampling exactly from this distribution is not possible efficiently on a classical computer unless the polynomial hierarchy collapses, and that the same holds for approximate sampling under two conjectures about permanents of Gaussian matrices [1]. The best known exact classical samplers take time of order [2]. The first experiments followed within two years [3, 4], single-photon experiments have since reached 20 photons in 60 modes [5], and a Gaussian variant of the problem [6] was used in the first photonic claims of quantum computational advantage [7, 8].
Sampling is a hard task to turn into an application. Much recent work therefore uses boson samplers as parametrised models, for example for supervised learning or generative modelling [9, 10, 11]. These applications rarely consume raw samples. The loss function, its gradient or a kernel entry is built from output probabilities, marginals or expectation values, which the device estimates from a finite number of shots. Their precision is therefore additive, of order after shots, and this is precisely the regime in which classical algorithms are strong. Gurvits gave a randomised algorithm that estimates the permanent of a matrix of bounded norm to additive error with draws [12]; Aaronson and Hance extended it to outputs with repeated modes [13]; Lim and Oh recast it as an estimator over coherent states, whose variance bound does not depend on the input state, and made it efficient for product inputs [14]; and Seron et al. estimated linear statistics of boson sampling in the same spirit [15]. For the inputs used in practice these tools make the loss functions classically estimable. This has a useful side, since models can be trained on a classical computer and only deployed on the hardware [11, 16]. It also means that a photonic learning model whose value rests only on such estimates leaves no room for a quantum advantage, a conclusion supported by recent results on concentration in passive linear optics [17].
There are two natural ways out. The first is to make the circuit itself nonlinear. Non-linear boson sampling adds photon–photon interactions inside the interferometer and raises the complexity of the task [18]. Deterministic interactions between single photons are, however, difficult to engineer: current demonstrations use a single quantum emitter coupled to a nanophotonic waveguide [19], and placing many such elements inside a large interferometer would add substantial loss. Adaptive measurements with feed-forward provide another kind of nonlinearity [20, 21]. The second way is to move the nonlinearity to the source. A quantum emitter, such as a semiconductor spin or a trapped atom, can stay entangled with the photons it has already emitted and pass these correlations on to the next photon. In this way a single spin produces long linear cluster states [22], as demonstrated with quantum dots and atoms [23, 24, 25, 26]. Spin–photon entanglement is also the basic resource of spin-optical architectures, where photons are used to entangle distant spins rather than to carry a long entangled state themselves [27].
This raises a simple question: does entanglement at the input make the additive estimation tasks hard again? The existing algorithms do not answer it. The algorithm of Lim and Oh is efficient for inputs that are product states across modes. It relies on sampling the Husimi function of the input, which for such states factorises into independent single-mode distributions that can be drawn one mode at a time. For an entangled input this distribution no longer factorises, and it is not clear a priori that it can be sampled efficiently.
We show that it can, whenever the input is a matrix-product state (MPS) of moderate bond dimension . Every state generated sequentially by an emitter of dimension is an MPS with , and conversely every MPS can be generated in this way [28]. Our results are stated for any photonic MPS, whatever its physical origin, and apply in particular to all emitter-based sources. The key observation is that the importance distribution of the Lim–Oh estimator is, for an MPS input, a continuous MPS density. It can be sampled exactly one site at a time, by the perfect-sampling method of Ferris and Vidal [29] run in a Gaussian measurement basis (Figure 1). The resulting estimator keeps the attractive feature of Gurvits’s method: its second moment equals the squared norm of the input, whatever the interferometer, the output pattern and the amount of entanglement. Each draw costs operations after a one-off preprocessing. Reaching an additive error with probability at least takes draws (see § 8.2), so the total cost is

Figure 1. (a) A sequential source. One or several emitters, whose joint memory (Definition 2) bounds the bond dimension of the emitted state ( for a single spin, for spins, which may interact; photons stored in a delay line also count as memory), emit photons, one per site; each photon occupies one of the modes of its site, recorded by the label (for instance time bins, polarisations or spatial modes). The photons enter an -mode interferometer , which may act on all of these modes, and are detected in an output pattern . The temporal train reflects how the emitters generate the state; the estimator only requires each photon to occupy its own set of modes, which may equally be spatial, spectral or polarisation modes. Underneath, the same input written as a matrix-product state (Definition 1): one tensor per emission, linked by bonds of dimension and closed by the initial memory state and by . After the last emission the memory is either measured and found in (projected memory) or discarded (traced memory, § 7.1). Read from right to left, the chain follows the emission order. (b) One step of the sampler of Theorem 1. The top and bottom rows are the state and its complex conjugate. The values already drawn are contracted into the left vector , all future sites are averaged into the right environment , and is drawn from the conditional density (6). The diagram keeps the order of Eq. (1), in which matrices act from right to left, so the left vector, which collects the sites already drawn, appears on the right.
operations, with memory for the input and the stored environments. The cost is polynomial in and in .
For emitter-generated light, is bounded by the dimension of the source’s retained quantum memory (Definition 2, with examples in Table 1): a single spin gives however long the cluster state is, and qubits of memory, whether emitters or photons held in a delay line, give , so the estimator stays efficient as long as (Sec. 8). This extends the known frontier of efficient classical additive estimation from product inputs to all inputs with one photon per site and polynomial bond dimension in some ordering of the sites.
Table 1: Memory and bond dimension of some -photon states, in the emission order indicated. The cost is that of the estimator to fixed and , with and polynomial in .
| State (emission order) | memory (qubits) | cost | |
| Fock or product input | |||
| GHZ, linear cluster (one spin) | |||
| 2D cluster strip of width (by columns) | |||
| with | |||
| with (square lattice) | |||
| Generic -qubit state |
Table 1.
Contributions.
The main result is an exact, site-by-site sampler for the importance density of an MPS input, with explicit costs in , , , , and (Theorem 1(iii), Algorithm 1, § 8.2). Each local conditional is a mixture of at most Gaussian densities in which one coordinate has a Gamma radial law. Combined with the coherent-state estimator of Lim and Oh, whose unbiasedness and state-independent second moment we restate in the fixed-photon-number setting (Proposition 1, Theorem 1(i)–(ii)) [14], it gives an efficient additive estimator for entangled inputs. Continuous Born-MPS densities and their sequential sampling are studied
in general by Meiburg et al. [30]; that work does not consider this Gaussian density, its explicit local rule, or its use in an optical estimator with a variance guarantee.
Extensions to traced emitters, overlaps and kernel entries, specified marginal probabilities, vacuum emissions, known loss and several photons per site (§ 7 and the Supplementary Material).
A discussion of what these additive estimates mean compared with the shot noise of an experiment, of the heavy tails of the estimator, and of how much quantum memory an advantage would need (§ 8 and 8).
An open-source implementation tested against brute-force enumeration, and a Lean 4 formalisation of the identities and sampling laws (§ 10).
Outline. Section 2 recalls how additive estimation works for product inputs and why entanglement is an obstacle. Section 3 defines photonic MPSs, explains what the bond dimension measures, and shows how emitter-generated states fit in. § 5 and § 6 give the identity and the sampler, and § 7 the other quantities that can be estimated. § 8 and 8 discuss accuracy and the consequences for quantum advantage. § 10 reports the numerical checks and the formalisation, and § 11 concludes.
Throughout, a draw is one evaluation of the Monte-Carlo variable, a sample an output pattern of the boson sampler, and a shot a run of the device.
Background: additive estimation for product inputs
A passive linear-optical circuit on modes is described by an unitary . We write an -photon Fock state by its occupations, with photons in mode and , and set . For a Fock input and output ,
where is the submatrix of in which row is repeated times and column is repeated times, and is the permanent. Computing the permanent exactly is -hard [31], and this hardness underlies the sampling arguments of Aaronson and Arkhipov [1].
Estimating a single amplitude to additive error is, by contrast, easy. Gurvits [12] writes, for an matrix of operator norm ,
and averages the bracket over random sign vectors to obtain to within , each draw costing operations. For collision-free outputs of a unitary, . Aaronson and Hance [13] extend this to repeated rows and columns, with an error that improves with the collisions by the factor
Lim and Oh [14] give the estimator a physical form. For arbitrary input and output states, is an integral over coherent states , weighted by the Husimi function of the input, and the variance of the resulting importance-sampling estimator is bounded independently of the state. The identity holds for every input. To use it, however, one must draw from and evaluate the integrand, and both steps are efficient when the input is a product state, because then factorises mode by mode. In earlier work the same authors approximate outcome probabilities with -parameterised quasiprobability distributions, reaching multiplicative error for sufficiently classical circuits [32]. Importance sampling has also been used the other way round, with a boson sampler drawing from the importance distribution of a Monte-Carlo integral evaluated classically [33]. Tensor networks, finally, already appear in the classical simulation of linear optics, but in a different role: for lossy or noisy boson sampling, the output state is represented as an MPS along the modes and then sampled [34, 35, 36]. Here the input is an MPS, the interferometer is arbitrary, and we estimate rather than sample.
For an entangled input the amplitude is a superposition of permanents, one for each component of the state (Eq. (2) below), and no longer factorises. A direct evaluation involves exponentially many terms, each containing a permanent. This does not prove that every instance requires exponential time, and exact hardness and additive estimation are different questions. The rest of this paper shows that, for MPS inputs, the sum never needs to be expanded: one contracts the MPS once per draw.
Entangled inputs as photonic matrix-product states
Definition
It is convenient to think of each photon as a qudit. Photon can occupy one of input modes, and which one it occupies is recorded by a label . For dual-rail qubits ; the labels may equally be time bins, frequencies or spatial modes. We call the modes available to photon its site, and write them ; different sites use different modes, so the modes are all distinct. In dual rail, for instance, .
A label word then denotes the Fock state with one photon at each site , in mode
and we write for the list of occupied modes; this list is what enters the permanents below. Because sites are disjoint, never has two photons in the same mode, and different words give orthogonal Fock states. In this language an -photon input is simply an -qudit state , and an MPS takes its usual form [37].
Definition 1 (Photonic MPS). A photonic MPS of bond dimension is a nonzero state
where each is a complex matrix and are boundary vectors in .
Apart from the map from labels to occupied modes, this is the standard open-boundary MPS, with physical index at site . Every state admits this form for large enough; the boundary vectors and only close the chain.
Example. Take dual-rail photons, , and with , at every site, and . The product vanishes unless all labels agree, so , with and . In occupation notation over the six modes this is the dual-rail GHZ state , and each of its output amplitudes (2) is a sum of two permanents. Taking instead , , gives the Fock input of standard boson sampling.
Site-dependent bond dimensions are allowed by padding with zeros. We do not assume that is normalised; the algorithm computes along the way. For an output occupation with , let list the output modes, mode appearing times. The amplitude is
where has rows and columns . The sum has terms.
We count dense arithmetic operations and ideal random draws. Exact sampling refers to the resulting probability law in exact arithmetic; a finite-precision implementation introduces numerical error that is not bounded here. The tensors and boundary vectors are specified inputs, rather than a preparation procedure that the classical algorithm must reproduce.
What the bond dimension measures
The bond dimension is a property of the photonic state itself, not of the device that produced it. It is a statement about bipartite entanglement across cuts in site order. If has the form (1), its Schmidt rank across the cut between sites and is at most ; conversely, the smallest for which (1) holds is the largest of the Schmidt ranks [38]. It says nothing about cuts that interleave the sites.
The distinction matters for cluster states, which are often described as maximally entangled. The linear cluster state (one qubit per site, , labels written ) has Schmidt rank across every cut in chain order, since each such cut breaks a single bond, and an explicit MPS with is , at every site, with and . Across the cut separating even from odd sites, however, every bond is broken and the Schmidt rank is . A GHZ state, in contrast, has Schmidt rank across every bipartition. The large multipartite entanglement of the cluster state is real, but it is invisible to the chain cuts that determine .
The order of the sites is ours to choose. Reordering the sites only relabels input modes, and that relabelling can be absorbed into . The relevant quantity for our algorithm is therefore the smallest bond dimension over all site orders, and for emitter-generated states the emission order is the natural candidate.
States generated by quantum emitters
A quantum emitter, such as a quantum dot, an atom in a cavity or a superconducting qubit coupled to a waveguide, can be driven to emit photons one at a time while a long-lived internal degree of freedom, typically a spin, stays coherent. If the state of each emitted photon depends on that internal state, every emission entangles the photon with the emitter, which passes the entanglement on to the next photon. Schön et al. showed that this mechanism produces precisely matrix-product states, with bond dimension set by the dimension of the emitter’s memory [28, 39]. Lindner and Rudolph proposed to generate long linear cluster states in this way from a single quantum-dot spin rotated between emissions [22]; coupled emitters can produce two-dimensional cluster states [40], and a few emitters suffice for the tree-like states used in all-photonic repeaters [41].
These proposals have since been realised, and this is the main motivation for considering MPS inputs. Linear cluster states have been produced from the spin of a quantum dot [23, 42], with high rates and indistinguishable photons [25], and in reconfigurable form [26]; an optical delay line can also play the role of the memory [43]. A single atom in a cavity has produced GHZ and linear cluster states of more than ten photons [24], and two atoms in the same cavity have been used to fuse such states into larger graph states [44]. Superconducting circuits emit multipartite-entangled microwave photons [45], including two-dimensional cluster states generated with time-delayed feedback [46]. These sources already deliver entangled multiphoton inputs to linear-optical circuits, and the question is whether such inputs change what can be computed classically.
We now give the formal description. A sequential source carries an internal state in , its memory, from one emission to the next. At emission an isometry entangles the memory with a photon in the modes of site ; writing for the memory operator that accompanies a photon with label , the joint state of photons and memory after emissions is . This is Eq. (1) with and an open right boundary. One spin gives , and the linear cluster and caterpillar states produced by a single spin are of this form. Several emitters are described by their joint memory. Since this notion is central to what follows, we state it separately.
Definition 2 (Memory of a sequential source). The memory of a sequential source is the set of quantum degrees of freedom that are carried from one emission to the next and can influence later photons: the internal states of all emitters, and any photons held in a delay line before being fed back. If the memory has dimension , for instance for qubits, the emitted photonic state is a photonic MPS (Definition 1) in emission order with .
The memory is therefore a property of the source, and a property of the state it emits; the first bounds the second. Two spins give , two-level emitters give , and a delay of time bins [43, 46] adds up to qubits. Conversely, the smallest number of emitters able to produce a given graph state in a given emission order is set by its entanglement across the cuts in that order [47], that is, by . The bound concerns the memory available, and a given state may use less of it. Table 1 gives examples on both sides of the threshold discussed in Sec. 8.
At the end of the sequence the memory can be treated in two ways.
Projected memory. If the memory is measured in a basis containing a normalised state and found in that state, the photonic state is the pure, in general unnormalised, state (1). Then is the joint weight of the projection outcome and the output, and the probability conditional on the projection is . All draw counts below are stated for and ; the conditional version divides by , which the algorithm computes.
Traced memory. If the memory is discarded, the photonic state is , where is the state (1) with and runs over an orthonormal basis of . The output probability is , with the amplitude (2) of . It is a probability when the sequence of emissions is normalised: with and .
This holds whenever and each emission is an isometry from the memory to the memory and one photon, . Section 6.1 treats this case.
Vacuum emissions and loss
The model extends to emissions that may be empty (unoccupied time bins, or an emission probability below one). Each site then gains a vacuum operator , the input spans several photon numbers, and the sampler of § 6 needs one rejection step per site, accepted with probability exactly (Supplementary Material, § 15). Sites holding several photons can be treated in the same way when their local Fock support is small (§ 16). A known linear loss, uniform or mode-dependent, can be folded into a sub-unitary when we estimate joint weights for detecting all input photons. It leaves the identity unchanged and can only lower the second moment (§ 17). Unresolved loss, with a trace over lost photons and several photon-number sectors, is not covered.
The Gaussian identity
The starting point is to write the amplitude (2) as an average over a Gaussian random vector, in a form that does not refer to the individual permanents. Let be the standard complex Gaussian density on : the entries , , are independent and circularly symmetric, with , so that . We use the same symbol for the standard Gaussian density on the space of a single site () or of the memory (). Define
Here is the overlap of the input with the product vector ; for an MPS it is obtained by contracting the tensors with one site at a time, in operations. The output factor only needs the entries , which cost .
Proposition 1 (Gaussian identity). For every matrix , every -photon state with at most one photon per mode (in particular (1); in general, indexes its Fock components and lists their occupied modes) and every output ,
The same holds with uniform on (Rademacher), with no conjugation in .
Proof. The two forms of (4). By linearity, . Each is a Fock state with at most one photon per mode, so the formula of § 3 gives : here , and is up to the order of its rows and columns, which does not change the permanent. This is (2), and it shows that the two forms of (4) are equivalent. It remains to prove the left-hand one. Idea. Each conjugated variable in stands for an input photon in mode , each factor in stands for an output photon in mode that may come from any input mode , and the Gaussian average pairs every output photon with exactly one input photon.
Two photons. Take one input photon in each of the modes , so that , and two output rows . Expanding,
Since the modes are independent and , the expectation on the right is 1 if and 0 otherwise: a mode that is not occupied must not appear, and each occupied mode must appear exactly once. Two terms survive, and , giving
the two indistinguishable ways of sending the input photons to the output rows.
General case. Since is linear in , it is enough to treat one word with occupied modes , which are distinct by assumption. Expanding gives one term for each choice of an input mode for every output row, with coefficient . Exactly as for two photons, equals 1 if every mode of is chosen exactly once and no other mode is chosen, i.e. if for a permutation , and 0 otherwise. This is where distinct occupied modes are used: each conjugated variable appears at most once, so each surviving term has weight 1. Hence
Repeated output rows cause no difficulty, since the sum runs over choices for each row. Summing over words with weights gives the left-hand form of (4).
Signs. For the last statement of the proposition, take uniform on ; the variables are real, so the conjugation in plays no role. Now is 1 for even and 0 otherwise, so each mode must appear an even number of times in . Every mode of therefore has to be chosen at least once; with only choices for modes, each is chosen exactly once, and the same permutations survive. □
Proposition 1 is the fixed-photon-number form of the coherent-state identity of [14]: is the projection of the unnormalised coherent-state generating vector with amplitude onto the sector with one photon in each site, and is the Gaussian factor of the Husimi measure. It uses no MPS structure. Averaging directly under is unbiased, but its variance involves , which is not controlled. As in [12, 14], we move the input factor into the sampling measure; for an MPS the resulting measure can be sampled exactly, as shown next.
The sequential importance sampler
Physically, sampling from amounts to measuring every site of the input in an (overcomplete) Gaussian product basis and recording the outcomes. For an MPS such a measurement can be simulated site by site: one keeps an -dimensional vector summarising all possible futures. This is the perfect-sampling algorithm of Ferris and Vidal [29], with the computational basis replaced by Gaussian product vectors.
Theorem 1 (Importance-sampled estimator). Let . Then
(i) is a probability density on ;
(ii) under , the variable (defined off the -null set ) satisfies, for every unitary , every and every ,
so that is unbiased for with , independent of , and the detailed input state;
(iii) for the MPS (1), can be sampled exactly, and and evaluated, in operations per draw after preprocessing per state; adds per draw.
Consequently, for independent draws , satisfies , and for two independent such estimates is unbiased for with mean-square error .
Parts (i) and (ii) hold for any input with at most one photon per mode; they are the fixed-photon-number form of the estimator of Lim and Oh and of its state-independent variance bound [14]. Part (iii) uses the MPS form and is the new ingredient.
Why not reuse the product-state estimator word by word? A natural alternative draws a component with probability , which perfect sampling of the MPS in the computational basis does in operations, and then estimates the single amplitude with Gurvits’s method. Reweighting by makes this unbiased as well, but each word now contributes its own variance, and the second moment becomes times the number of words in the support of . This is harmless for a GHZ state, which has two words, but grows as for a linear cluster state, whose amplitudes are all nonzero. The same holds for any approach that writes as a sum of product states and applies Gurvits’s method to each: the cost grows with the number of terms, which for a linear cluster state is at least its Schmidt rank across the even–odd cut, (§ 4.2), although . The Gaussian change of measure of Theorem 1 avoids this because it treats all words at once: their cross terms cancel in , and the second moment does not depend on how many words the state contains.
Proof. Write . We first explain the change of measure, then how to sample it.
Normalising the input weight. Different input words use different sets of modes. Their Gaussian monomials are orthogonal, so all cross terms disappear in :
This proves (i). Physically, integrating the product-vector measurement sums over all its outcomes and returns the norm of the input state.
Cancelling the input from the second moment. Multiplying the estimator by its sampling density gives
wherever . Integrating the first equality and using Proposition 1 gives , the unbiasedness claim of (ii). For the second equality, the set is the zero set of a nonzero polynomial, so it has Lebesgue, hence Gaussian, measure zero, and integrating gives . For the sign variant this step fails, since a polynomial can vanish on sign vectors with positive probability (Sec. S4).
It remains to compute , and here we use that is unitary, as it is for a lossless linear-optical circuit. Since depends on only through , the vector has the same distribution as , and . By independence and the moment rule,
Dividing by gives , which completes the proof of (ii): the input enters the second moment only through its norm. For a lossy, sub-unitary the same quantity is at most (§ 17).
Sampling one site at a time. It remains to draw from . The function depends only on the modes used by the sites, so is the product of on the unused modes, which are drawn as independent standard Gaussians, and a density on the site variables. For site write with ; conjugation preserves , so under the are independent standard Gaussian vectors. By the chain rule, it suffices to draw from its marginal under , then from its law conditional on , and so on. We therefore need the marginal density of the first site vectors. Two objects make it computable.
The left vector is the memory vector after the first sites, given the values already drawn:
This is (3) evaluated by multiplying the matrices from the right, one site at a time.
The right environment is a positive semidefinite matrix that summarises all possible futures. It is defined backwards by
and does not depend on , so it is computed once per state.
Averaging over the future. The key property is that averaging over the sites that have not yet been drawn leaves a quantity that depends on the past only through :
For there is nothing to average, and . Suppose (5) holds at , and average once more over . Writing , so that ,
because removes the cross terms. This is (5) at . At it gives , without enumerating the words.
Marginal and conditional densities. Dividing (5) by , the marginal density of the first site vectors under is
The conditional density of given the past is the ratio of two consecutive marginals. The Gaussian factors of the past and cancel, leaving
With as above, the numerator is the quadratic form of the matrix , and the denominator is :
is a Gram matrix, hence positive semidefinite. Its trace vanishes only on prefixes that have probability zero, so the conditional is always well defined when it is needed.
Drawing from the conditional. Diagonalise with and orthonormal , and use the coordinates . Since is invariant under unitaries, is again standard Gaussian under , and (6) becomes
This is a mixture of simple densities with weights . In component , the coordinate has density and the other coordinates are independent standard Gaussians. In polar coordinates , the density becomes : follows a Gamma law and is uniform. One draw therefore consists of
choosing with probability ;
drawing with a uniform phase, and every other as a standard complex Gaussian;
setting , then , and .
Repeating this for draws the site variables from exactly, by the chain rule, and returns at no extra cost.
Cost. The backward recursion for multiplies pairs of matrices per site, in total. At each site of a draw, forming the and costs , the matrix costs , and its diagonalisation ; since , this is per site. This proves (iii).
From one draw to an error bound. Independence gives . To estimate a probability without squaring a noisy estimate, use two independent averages. Put and . Their product has mean and mean-square error
The real part is also unbiased and has no larger mean-square error.
Algorithm 1 (One Gaussian importance draw). Preprocess once: , , and .
Set . Draw independent standard complex Gaussian entries on modes outside the sites. (Setting them to zero instead also gives an unbiased estimator, with a smaller second moment when ; Remark S1.)
For each site , perform steps 3–5.
Form , and .
Diagonalise . Choose with probability . Draw with uniform phase, and independent for . Set .
Update and set .
After the last site, set and return
With Gaussian unused modes and unitary , and .
Remark 1 (Sampling without diagonalisation). Step 4 can avoid the eigenproblem. Factor each environment once, with a matrix and (for instance by a pivoted Cholesky or an eigenvalue decomposition), which adds to the preprocessing. With for , the quadratic form in (6) becomes , so the conditional density is a mixture of at most densities , with and weights (terms with drop out). Each of them is drawn as in step 4 with in place of the eigenvector: choose , draw from and with and uniform phase, and set . A site then costs , the term disappears from Theorem 1(iii), and no eigenproblem is solved during a draw; the only factorisations are those of the , done once per state. In our tests (Supplementary Material, Sec. S7) the two samplers agree on all tested one- and two-site moments of and give unbiased estimates. For they run at comparable speed when ; the factorised sampler is faster for small and for encodings with many modes per photon.
Other quantities we can estimate
An amplitude for one output pattern is rarely the quantity one actually needs. An experiment that keeps the memory unmeasured produces a mixed photonic state, applications such as kernel methods compare two states, and training a model usually involves marginal probabilities over a few output modes rather than full patterns. All three can be estimated with the same sampler, at polynomial cost. We first treat a memory that is traced out rather than projected, then replace the Fock output by a second MPS to obtain overlaps, and finally combine these overlaps to extract marginal probabilities. In each case the estimator is reused as it is, and nothing requires summing over the exponentially many output patterns.
Traced memory
Tracing out the memory means adding the probabilities associated with an orthonormal basis of final memory states. Rather than estimating all terms, we draw one basis state at random, with probability proportional to its weight, and reweight the pure-state estimator accordingly.
Corollary 1 (Traced memory). Let the memory be traced out, let be an orthonormal basis of , and let be the state (1) with , of squared norm , so that . Draw with probability , then two independent draws of the estimator of Theorem 1 for , and set
Then and, with Gaussian unused modes and unitary , , equal to for a normalised sequence. Hence is estimated to with draws, each costing after at most preprocessing (one set of right environments for each basis state that is drawn).
Proof. Basis states with are never drawn and contribute nothing to , since then . Given , the draws are independent, so and by Theorem 1(i)–(ii). Averaging over ,
The weights are the diagonal of , obtained by one forward contraction from , in . The environments of Theorem 1 with cost for each and can be built when is first drawn; each draw then runs the sampler of Theorem 1 twice with stored environments. Keeping all sets requires memory.
A Gaussian final vector gives an alternative that needs no basis. If is standard complex Gaussian and is the state with , then gives , and , with two independent draws for the same , is unbiased. Its second moment is , by Wick’s theorem applied to , and the environments must be rebuilt for every , at per draw. With environments built on demand, Corollary 1 is therefore never more expensive in operation counts, and its second moment is smaller. The reference package implements both routes, with Corollary 1 as the default; Table S1 checks the Gaussian one.
| input | register | Gaussian, variant A | Gaussian, variant A | Gaussian, variant B | Gaussian, variant B | Rademacher | Rademacher | ||||
| random MPS | proj. | 4 | 2 | 1 | 0.11 | 1.41 | 0.358 / 0.359 | 1.00 | 0.354 / 0.359 | 0.08 | 0.210 |
| random MPS | proj. | 5 | 3 | 1 | 0.48 | 0.74 | 20.54 / 20.27 | 1.71 | 20.09 / 20.27 | 2.43 | 9.84 |
| random MPS, bunched | proj. | 5 | 2 | 4 | 1.19 | 1.41 | 11.71 / 11.40 | 1.58 | 11.86 / 11.40 | 0.64 | 5.22 |
| random MPS | proj. | 6 | 4 | 1 | 0.53 | 0.75 | 38.89 / 38.65 | 0.76 | 34.75 / 38.65 | 0.37 | 13.51 |
| GHZ | proj. | 5 | 2 | 1 | 1.10 | 1.47 | 0.515 / 0.500 | 2.41 | 0.513 / 0.500 | 0.61 | 0.115 |
| GHZ, bunched | proj. | 4 | 2 | 2 | 1.24 | 1.42 | 0.900 / 1.000 | 0.82 | 1.127 / 1.000 | 1.09 | 0.460 |
| random MPS, | proj. | 4 | 2 | 1 | 1.05 | 0.64 | 3.07 / 2.87 | 1.35 | 0.730 / 0.767 | 1.09 | 1.43 |
| random MPS | traced | 4 | 2 | 1 | — | 1.24 | 645 / 717 | — | — | — | — |
| GHZ | traced | 4 | 2 | 1 | — | 0.81 | 1.69 / 1.50 | — | — | — | — |
Table S1. Table S1: Independent validation (NumPy implementation of Algorithm 1, seed 1). ; = empirical second moment of (Gaussian: exact value ; variant B: exact value , equal to the former when ); the “” column is the plain identity (4) sampled under . Traced rows (Gaussian final vector, Sec. 6.1): of against (the random MPS is not normalised). Haar-random , unless stated, ( for ; traced).
Overlaps
An overlap seems to require summing amplitudes over every output pattern. We can instead contract the second state’s MPS with the transformed Gaussian vector , and Gaussian orthogonality performs the output sum for us.
Let be a second photonic MPS, of bond dimension , over any grouping of the modes into sites (not necessarily that of ; in this subsection denotes the sites of ). Then with . Define, for and with the rows of ,
For of the form (1) every in its support is collision-free, so , and is the contraction of the complex-conjugated tensors of (i.e. ) with the product vector built from , . Write and for the and of . Then by Proposition 1 summed over , and sampling and averaging gives an unbiased estimate with second moment , by unitary invariance of and part (i) of Theorem 1 applied to . The overlap is therefore estimated to with draws, each costing ; the last term computes all of , which may need.
This covers kernel entries. For two photonic MPSs and two interferometers , the matrix is again unitary, so is an overlap of the above form, and the kernel entry is estimated without bias by the product of two independent overlap estimates, as for probabilities in Theorem 1. These are the quantities used by quantum kernel methods.
Few-mode marginals and linear statistics
An amplitude estimator does not by itself give marginal probabilities, but the overlap estimator does, through characteristic functions.
Characteristic functions as overlaps. Let be the number operator of output mode and a linear statistic [15]. For , is the Fock-space action of the single-particle matrix , so is again an unitary and
is an overlap of the form of § 7.2 with . It is estimated to with draws, each costing . For a normalised input, characteristic functions determine probabilities; for an unnormalised one, they determine weights.
Marginals on a few modes. For a set of output modes, the joint occupation has characteristic function , with . Since each occupation lies between 0 and , it is enough to know on the grid , and the marginal is the inverse discrete Fourier transform
with uniform on the grid. The Fourier phases act as a filter: their average is one when the measured occupations equal the requested ones and zero otherwise. The grid has points but never needs to be enumerated. One draws a single grid point uniformly and one overlap estimate of ; then is unbiased for , with second moment at most . Hence is estimated to with draws, whatever the number of modes.
Linear statistics. The same trick gives when the weights are integers. After shifting the statistic by , its values lie in , so a one-dimensional Fourier grid of size separates them, and again only one grid point is drawn per estimate.
In both cases the result is an additive estimate of one specified probability, not an efficient way to output the whole marginal table, and for large the probabilities themselves are typically far below .
Accuracy and statistical interpretation
Additive error and shot noise
How do these guarantees compare with what an experiment delivers? With shots, the device estimates with standard deviation . With draws, two independent amplitude averages give a probability estimate with root-mean-square error at most , and for a normalised sequence with the memory traced out, Corollary 1 gives at most from a single average, each draw using two runs of the sampler. Both errors decrease as , and for probabilities of order one they agree up to a constant factor.
They differ for rare outcomes. The shot noise is proportional to and shrinks with the probability, whereas the classical error does not. In boson sampling, rare is the rule: the probability of an individual output pattern is typically exponentially small. To see the scale, take a normalised 40-photon input in 80 modes and a Haar-random . Whatever the input state, the mean probability of a fixed output pattern is , since the Haar average spreads the probability uniformly over the patterns. With , the shot noise is then about and the classical error about . The device is far more precise in absolute terms, yet both errors exceed the probability itself by many orders of magnitude. Neither polynomially many shots nor polynomially many draws give relative precision on such probabilities, so neither can usefully report individual pattern probabilities.
What both can estimate at polynomial cost, exactly as for Fock inputs, are quantities of order one: few-mode marginals and linear statistics, overlaps and kernel entries (§ 7.2–§ 7.3), and the weight of a fixed pattern when that weight is not exponentially small. These are the quantities from which loss functions and kernels are built, and for them the classical estimator matches the device up to a constant factor in the number of samples.
Heavy tails
Theorem 1 controls the second moment of , and that is all the error bound needs. In practice, however, one is tempted to judge the accuracy of a run from the data, using the sample variance of the draws. For this estimator that is unreliable, for two reasons.
First, the fourth moment of is in general infinite, so the sample variance itself has infinite variance. The cause is the division by . Near a simple zero of at which does not vanish, the sampling density vanishes quadratically while grows as ; the integrand of therefore behaves as , whose integral diverges logarithmically in the two real directions transverse to the zero set.
Second, the distribution of is very skewed: its typical values lie far below its mean, which is carried by rare large draws. A finite run usually misses them and underestimates the variance, sometimes by orders of magnitude. For a projected linear cluster state with , draws gave an empirical second moment of at , against the exact value (Supplementary Material, Sec. S5).
We therefore do not rely on error estimates from the data. The guarantee comes from the theorem: by Chebyshev's inequality, with probability at least . When high confidence is needed, a median-of-means estimator, applied to real and imaginary parts separately, reaches error with probability using draws. The same caution applies to the probability, overlap and marginal estimators of § 7, whose guarantees also rest on second-moment bounds.
How much quantum memory would an advantage need?
For a sequential source whose retained quantum memory amounts to qubits, held in emitters or in photons stored in a delay line, the bond dimension in emission order is at most (§ 4.3). The cost of our estimator is polynomial in , , , and , so substituting gives a runtime . With , and polynomial in , this is polynomial when and subexponential when . Table 1 gives examples of each regime. In particular, the tasks considered here can only become exponentially hard if the memory grows linearly with the number of photons; for a memory that grows faster than logarithmically but sublinearly, our bound is superpolynomial but subexponential, and no lower bound is known.
These tasks are those that reduce to polynomially many additive estimates of the quantities of § 7–§ 8: amplitudes and pattern weights of order one, traced-memory probabilities, overlaps and kernel entries, few-mode marginals and linear statistics. For them, the dequantization known for Fock and Gaussian inputs [12, 13, 14, 15] extends to entangled inputs of polynomial bond dimension. Other tasks are not covered: relative estimation of exponentially small probabilities, and sampling from the full output distribution. Nor do we compare wall-clock times per device shot and per classical draw.
Three remarks help to read this bound correctly. First, is the memory available, not the memory used: a state produced by many emitters can still have a small bond dimension in emission order, and it is then easy as well. Second, the bound is an upper bound on the classical cost. A linear number of emitters is necessary for exponential hardness of these tasks but not sufficient, and our algorithm itself gives no lower bound; § 11 shows, however, that a cost polynomial in is excluded in general unless . Third, architectures that add adaptive measurements, such as spin-optical schemes [27], can be universal, but they fall outside the fixed-interferometer setting considered here.
For photonic machine learning, the consequence is practical. A model fed by a few spins, whose loss is built from estimated probabilities, marginals or kernel entries, can be trained and evaluated classically, just as one fed by single photons. A route to an advantage through the source has to involve quantum memories that grow with the problem size, adaptive measurements, or a use of the device that does not reduce to additive estimates, such as sampling. Whether sampling from photonic MPS inputs is classically hard is a separate question, which we do not address here; exact classical sampling for these inputs is the subject of a companion paper [48].
Numerical checks, cost and formalisation
Correctness. We checked the identities and moments above against brute-force enumeration of (2) with two independent NumPy implementations, and tested a PyTorch implementation of Algorithm 1 against a permanent-sum oracle. The test inputs include projected and traced linear cluster, GHZ and random MPS states with –, collision-free and bunched outputs, and Haar-random interferometers. Over the 30 mean estimates of Table S1 (Supplementary Material, § 21), the largest deviation from the exact value is 2.4 empirical standard errors, and the empirical second moments agree with their exact values within the fluctuations expected from § 8.2. A third implementation checks Corollary 1 and the factorised sampler of Remark 1 against exact moments and amplitudes on 36 states with up to 40 and up to 32 (Supplementary Material, § 21).
Cost. Table 2 gives the cost per draw on one GPU. With Gaussian sampling it ranges from (, ) to (, ): draws, enough for an additive error of about on a normalised amplitude, take a few seconds even for a 60-photon input produced by eight two-level emitters. The dependence on is much milder than the of Theorem 1 at these sizes, because the contractions are batched over draws. The sign (Rademacher) variant is up to 47 times cheaper per draw for , partly because it avoids the eigenproblem (which Remark 1 also avoids for Gaussian sampling, but which Table 2 still uses), but Theorem 1(ii) does not hold for it: its second moment depends on the interferometer and can exceed (Sec. S4). Its lower cost per draw is therefore not a lower cost at fixed accuracy.
| 10 | 4.0 / 0.17 | 5.9 / 0.13 | 9.8 / 4.4 |
| 20 | 6.3 / 0.34 | 10.7 / 0.25 | 19.3 / 8.8 |
| 30 | 9.2 / 0.51 | 16.1 / 0.38 | 28.9 / 13.2 |
| 40 | 12.0 / 0.67 | 21.2 / 0.50 | 38.5 / 17.7 |
| 50 | 17.4 / 0.84 | 29.2 / 0.62 | 48.0 / 22.0 |
| 60 | 17.7 / 0.99 | 32.2 / 0.75 | 57.9 / 26.3 |
Table 2. Cost per draw on one NVIDIA H100 PCIe, amortised over draws (median of three runs), , Haar-random , complex128. Gaussian / Rademacher sampling, in s. : projected linear cluster; : random isometric emitters. Details in the Supplementary Material, § 21.
Formalisation. A Lean 4 project formalises Proposition 1, parts (i) and (ii) of Theorem 1, the exactness of the sequential sampler including the local Gaussian draw of Algorithm 1 (not the factorised draw of Remark 1), and the vacuum rejection step (Proposition S1). The operation counts, the numerical results and the complexity discussion are not formalised; § 22 maps each formal statement to its source file.
Conclusion and open questions
Boson samplers are believed to be hard to simulate as samplers, but most of their proposed applications do not use samples directly. They rely on probabilities, marginals, overlaps or kernel entries estimated to additive precision, and for product inputs Gurvits’s algorithm and its coherent-state form by Lim and Oh make these estimates classically easy. We have shown that the same holds for any input that is a matrix-product state with one photon per site and polynomial bond dimension. The estimator is unbiased, its second moment is the squared norm of the input whatever the interferometer, the output pattern or the amount of entanglement, and its cost grows polynomially with . The same sampler gives probabilities with the memory traced out, overlaps and kernel entries between two such states, and individual marginal probabilities.
Since quantum emitters produce exactly such states, with set by the size of their memory, entangled light from a few spins does not by itself make estimation-based applications of linear optics hard to simulate. An advantage for these tasks has to come from a quantum memory that grows with the number of photons, from adaptive measurements, or from uses of the device that do not reduce to additive estimates. For these tasks, what matters is therefore not the entanglement of the input but the size of the memory that produces it: a linear cluster state from one spin is as easy to estimate as single photons, despite its large multipartite entanglement. Our estimator gives an upper bound on the classical cost, for two-level emitters. A conditional lower bound shows that this growth with cannot be removed in general. When the emitters interact, their memory can run an arbitrary -qubit circuit between emissions, and a projected weight such as can then encode the acceptance probability of a polynomial-size quantum computation. Estimating it to inverse-polynomial additive error is BQP-hard, so no classical algorithm can have a cost polynomial in for all such sources unless BPP = BQP. The true worst-case cost is therefore superpolynomial in and, by our algorithm, at most exponential; this is why the threshold is meaningful rather than an artefact of our method. The argument uses interacting emitters; for more restricted sources, such as non-interacting spins with fixed rotations, the cost could be lower. Spin emitters combined with linear optics, photon detection and feed-forward also form a universal architecture [27]. An experiment that aims at an advantage in estimation tasks with emitter-generated light needs a memory of more than qubits, or a use of the output that does not reduce to additive estimates.
Several questions remain open. Sites holding several photons can already be included when their local Fock support is small and explicitly listed, with a rejection sampler whose mean cost is the number of local configurations (§ 16), but it would be useful to avoid this factor when the local support is large. Expectation values of general product observables need their own representation and variance bound, as Lim and Oh provide for product inputs [14]. Beyond matrix-product states, tree tensor networks, which describe some multi-emitter graph states, are natural candidates for the same continuous perfect-sampling approach. Real emitters also bring imperfections that a pure, fixed-photon-number MPS does not describe, such as partial distinguishability, multi-photon emission and unresolved loss, and it would be valuable to know how far the estimator extends to them.
Finally, whether sampling from the output distribution is classically hard for MPS inputs, including with a traced memory, remains open. Additive estimates alone do not yield an efficient sampler without further structure [49], and exact sampling for these inputs is the subject of a companion paper [48].
Reproducibility
The code is the MIT-licensed package gurvits-mps, in the folder code/ of the archive of this work, https://doi.org/10.5281/zenodo.24023358, and the Lean proofs are in its folder Lean/ (Supplementary Material, Sec. S8). The package contains the estimator (gurvits_mps/estimate.py: Algorithm 1, Gaussian and Rademacher sampling, variants A/B, traced memory by Corollary 1 or a Gaussian final vector, overlaps; PyTorch, CPU or GPU), a brute-force oracle (gurvits_mps/reference.py), tests, and the scripts producing every number of this work: check_identity.py (Table S1, NumPy only, seed 1, about three minutes on one core), validate.py (§ 21), timing.py (Table 2), haar_mean_scan.py ((S1) and the DFT4 case), check_vacuum.py (Proposition S1) and traced_factorised/ (Corollary 1 and Remark 1, NumPy and SciPy), all in scripts/.
Acknowledgements
We thank 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 package code, the Lean proofs (Supplementary Material, Sec. S8), and the manuscript were written with the assistance of generative models from Anthropic (Claude). OpenAI (ChatGPT) assisted with the revision of the manuscript. The algorithms, the formalisation choices, the code architecture, the main definitions, the theorems and the propositions were designed and written or reviewed by the authors, who take responsibility for the whole.
Supplementary material
The main text gives the estimator, its applications and its statistical interpretation. The following sections supply extensions of the input model and technical details. Sections S1–S3 treat vacuum emissions, finite local Fock support and known loss. Section S4 analyses sign sampling, and Sec. S5 explains the heavy tails. Section S6 discusses related simulation tasks. Detailed numerical checks and the Lean correspondence appear in Secs. S7 and S8.
Vacuum emissions
Emissions that may be vacuum fit the scheme of the main text. Let there be emissions, each with label , where is the vacuum (operator , no photon) and puts one photon in mode , so that with spans several photon numbers. Let be the number of nonzero labels of , and the list of the modes with . For an output with photons,
the sum running over the words with photons, and
The extra label changes the sampler in one place. The next-site amplitude is now a constant plus a linear function of the Gaussian vector. We first sample an incoherent mixture of these two contributions, then use rejection to restore their interference.
Proposition S1 (Vacuum emissions). In this setting the Gaussian statement of Proposition 1 and parts (i)–(ii) of Theorem 1 hold with summed over all photon numbers. The density can be sampled exactly, emission by emission, by a rejection step whose acceptance probability is exactly at every emission; the expected cost per draw is after preprocessing.
Proof. For independent standard complex Gaussians the moment factorises over the modes and vanishes unless every mode has the same exponent in both monomials; in particular it vanishes when the degrees differ. The degree- polynomial therefore pairs only with the words of photons, to which the proof of Proposition 1 applies unchanged. The vacuum label uses no mode, so distinct words still have distinct mode sets, and the proofs of parts (i) and (ii) go through with the sum over all words.
The conditional density. For sampling, set and, given , (). As in the proof of Theorem 1(iii), the conditional density of is
with , , , the columns of equal to , and as in (6); the denominator follows from and .
A proposal that is easy to draw. This is no longer a homogeneous quadratic form, but . Propose from , a mixture of (weight ) and of the density (6) drawn as in Algorithm 1, and accept it with probability .
Why rejection gives the right law. An accepted has density proportional to times this probability, that is to , and the acceptance probability is . The number of proposals per emission is geometric with mean 2, and each costs once the and are formed. No square root of is needed.
The Rademacher identity is not asserted for photon-number superpositions: real signs do not distinguish all monomial degrees. The second moment is bounded by the norm of the whole train, not of its -photon sector, so the bound is loose when the -photon sector carries little weight. An independent check (check_vacuum.py, § 21) confirms unbiasedness, the second moment and the acceptance probability .
Finite local Fock support
The same idea gives a simple extension when an emission block can contain several photons. Suppose its allowed Fock configurations form an explicitly listed set of size , on modes disjoint from other blocks. For , use the Gaussian monomial
These monomials are orthonormal under the product complex Gaussian measure. With and , the next conditional density is
There is no need to solve a general polynomial sampling problem. Propose from
Choose with weight ; independently for each mode draw a uniform phase and squared radius Gamma. This is exactly the selected mixture component. By Cauchy–Schwarz,
Accept with the ratio of the left-hand side to the right-hand side, taking any value on the proposal-null set where both vanish. Proposal density times acceptance probability is the target density divided by . Acceptance therefore has probability , and the mean number of proposals is . All norms and inner products can be evaluated with , without forming its square root.
The corresponding input polynomial is . Gaussian pairing gives , and its importance estimator has second moment after output normalisation, as before. Thus an explicitly given, polynomial-size local support admits a polynomial expected-cost extension, counting the local photon occupations among the input parameters. This argument does not make an exponentially large local configuration list efficient. The vacuum sampler is the sharper degree-one construction; it has mean proposal count two, independently of .
Unused modes and known loss
Remark S1 (Unused modes). Only the unitarity of enters part (ii), through , which is Wick’s theorem for the Gaussian vector of covariance .
(A) With standard Gaussian on all modes (Algorithm 1 as written) and unitary, this is .
(B) If instead is set to zero on the modes the state does not use ( the set of modes used by the state, its complement, and the corresponding columns of ), the identity still holds (those monomials of had zero expectation against ), the sampling measure is different, costs instead of , and the second moment becomes , by superadditivity of the permanent on positive-semidefinite matrices (Marcus–Newman [50]), or the Cauchy–Binet expansion of , for any matrix , as a sum of non-negative terms) since and . At the two variants coincide; when , variant B reduces the second moment without increasing the evaluation cost (Table S1, last projected row: against at ).
Known loss
Uniform or mode-dependent transmission that is known in advance is folded into the interferometer, which becomes a sub-unitary matrix (), and we estimate the joint weight for a specified -photon output and no lost photons, for a fixed -photon input. A probability conditional on survival requires division by the survival probability; the unconditional second-moment bound below must then be rescaled. For an input spanning several photon numbers, a sub-unitary describes its no-loss branch only, not contributions from higher-number sectors that lose photons. Proposition 1 holds for every matrix , so the identity and the unbiasedness in part (ii) of Theorem 1 are unchanged. Only the second moment uses unitarity: by Wick’s theorem for the Gaussian vector , of covariance , . The matrices and are positive semidefinite, and the permanent is superadditive on such matrices (Remark S1), so and . Unresolved loss, with a trace over the lost photons and several photon-number sectors, is not covered.
Rademacher variant
Let be the uniform measure on , with fixed photon number and distinct occupied input modes as in the main model. Orthogonality of the sign monomials gives . Thus is a probability mass function and remains unbiased. Each conditional is proportional to on . Enumerating these vectors avoids an eigenproblem and is useful for small fixed ; it is not polynomial in unrestricted .
There is an important difference from Gaussian sampling. A nonzero polynomial can vanish on sign vectors with positive probability. Cancellation therefore gives
The equality without the indicator holds if is nonzero on every sign vector, as for a single Fock word. It is not valid for arbitrary superpositions. For example, take one photon in , a Hadamard interferometer, and the output row . Then and . On the support of , , so the second moment is zero although .
Even the upper bound depends on the interferometer. For the unitary DFT with rows numbered , rows give , while rows give . The former exceeds . A general pointwise bound is
by arithmetic–geometric mean and . This supplies a uniform bound, not a claim that it is the best possible second-moment bound.
For Haar-random , fixed is sent to a uniform vector on the sphere of squared radius . For collision-free rows its coordinate moments give
For a fixed input, the Haar-averaged second moment of is this expression times . This follows because the Haar average is the same for every sign vector. For , divide all second moments by . The timing advantage of signs in Table 2 concerns cost per draw; it does not establish a uniform advantage at fixed estimation accuracy.
Heavy tails
has a finite second moment but, in general, an infinite fourth moment: near a simple zero of where is nonzero, the density vanishes quadratically while , and diverges logarithmically in two real dimensions. The simplest instance is , , , the Hadamard matrix, : , , and . In the reported numerical examples, the bulk of also lies far below its mean. Measured under on Haar-random , the mean of decreases linearly in with slope , while stays fixed. A heuristic for the order of magnitude: under and for collision-free , is a product of i.i.d. variables, whose logarithm has mean () although ; under the denominator contributes as well, and we do not claim that the measured slope follows from the numerator alone. Consequently the Bessel-corrected sample variance, although unbiased, is extremely right-skewed, and a typical finite-run variance estimate can severely underestimate the true variance: at the empirical second moment of a projected cluster state fell from at to at against the exact value . We therefore report the theorem-based bound — by Chebyshev, with probability — and, for high-confidence estimates, a median-of-means estimator (real and imaginary parts separately) with draws for confidence .
Further remarks
Whether sampling hardness can be paired with a classically trainable loss is a separate question: the few-mode marginals of § 7.3 are exactly the low-order statistics such a training would consume, and for generative models whose sampling hardness rests on anticoncentration, Herbst et al. [51] argue that such losses concentrate.
The identity needs a fixed input state. It does not cover adaptive protocols in which a mid-sequence measurement of the emitter conditions the later interferometer: a bounded number of adaptive steps is handled by enumerating outcomes, and estimation can become hard when the number of adaptive steps scales, with thresholds that differ for mean values and for sampling [20, 21, 52]. It also says nothing about pattern-level statistics over exponentially many patterns, nor about measurement-induced entanglement across emitters. On the simulation side, the tensor-network samplers of [34, 35, 36] represent the output of lossy or noisy circuits as an MPS along the modes and sample it; this note concerns an MPS input to an arbitrary-depth interferometer and estimates rather than samples.
Validation and cost per draw
Table S1 is the output of an independent NumPy implementation of Algorithm 1 (check_identity.py, seed 1): random and GHZ-type sequential MPSs, Haar-random , collision-free and bunched outputs, and one case with , exact values by brute-force enumeration of (2). It checks Proposition 1 under plain sampling, Theorem 1 with Algorithm 1, variants A and B of Remark S1, the Rademacher variant, the Gaussian-final-vector estimator for a traced memory (§ 7.1), the DFT counterexample and (S1). Over the 30 mean estimates the largest (empirical standard error) is 2.4; the empirical second moments scatter around their exact values on both sides (within about 13% for the projected Gaussian entries at –), the variant-B moment at equals to 5%, and the traced empirical moments fluctuate around ; a finite-run second moment need not lie below its expectation.
Vacuum emissions. check-vacuum.py (NumPy, seed 1) implements the sampler of Proposition S1 on four random sequential states with a vacuum label, – emissions, –, – detected photons (one bunched output), , draws each. Both the plain- identity and the sampled estimator agree with brute-force enumeration (largest ), the empirical second moments are within – of , and the measured acceptance probability per emission is –.
Reference implementation. The PyTorch class GurvitsEstimator uses complex128 arithmetic and supports Gaussian and Rademacher sampling, variants A/B, projected memory, traced memory by the basis-state estimator of Corollary 1 (the default) or a Gaussian final vector (§ 7.1), and overlaps. It is tested against the brute-force permanent-sum oracle of reference.py on 26 cases (tests/): projected linear-cluster, GHZ and random emitters at –$4L=2,3 and –3, collision-free and bunched outputs, and ; traced linear-cluster and random emitters with –4, normalised or not, by both routes; an overlap between two random emitters; and the plain- identity. Every estimate is within , every Gaussian second moment of an amplitude within 25% of its exact value at draws, and every second moment of Corollary 1 within 30% of at – draws. scripts/validate.py prints the corresponding table (19 estimates on 9 cases, largest at draws, for the Gaussian final vector, seed 1).
Traced memory and the factorised sampler. The estimator of Corollary 1 and the sampler of Remark 1 were checked with a separate NumPy and SciPy implementation (scripts/traced_factorised/; seeds 2026, 7 and 3 for the small states, the large states and the timings), alongside Algorithm 1 and the Gaussian-final-vector route. The small-state set has 28 states (random isometric emitters, random non-isometric MPSs, linear cluster and GHZ states) with –6, –4 and –8, each with three outputs (collision-free at , collision-free at , and one bunched pair at ), and eight independent runs per case of draws ( for the Gaussian final vector).
For the law of the sampled variables we use one- and two-site moments, and , whose exact values follow from the reduced density matrices of and whose sampling distributions have finite variance. In each batch a random linear combination of each kind gives one -score. Eight further states with –40, up to 8 and up to 32, whose exact moments are obtained by MPS contraction (six batches of draws each), bring the total to 544 -scores per sampler, with Kolmogorov–Smirnov -values 0.16 (Algorithm 1) and 0.45 (Remark 1) against and largest of 3.1 and 3.0.
For unbiasedness we use , whose expectation is 1, with the exact variances , and . Its mean over 672 runs is and for MPS amplitudes with the two samplers, and for Corollary 1 with the two samplers, and for the Gaussian final vector. Because of the heavy tails of Sec. 7.2 this statistic has infinite variance, so the bootstrap errors quoted are indicative only; its medians are 0.67–0.69 for all five estimators.
On a two-core CPU (batched NumPy, preprocessing excluded), the factorised sampler at runs at 0.9–1.1 times the speed of Algorithm 1 for –128 at and for –160 at (1.4 at ), and is 1.3–2.5 faster for . At , it is faster by 2.6, 6 and 19 at , 16 and 64. At , , a draw of Corollary 1 is 1.2–1.4 faster than a Gaussian-final-vector draw for , and 2.3 and 4 faster at and 64; with all sets of environments built in advance, the preprocessing is recovered after 20–1100 draws. The results are in results/traced_factorised_20261022/.
Cost. Table 2 is the output of scripts/timing.py on one NVIDIA H100 PCIe (80 GB; driver 580.126.20, PyTorch 2.14.0+cu130, Python 3.12, complex128): draws per configuration in one batch after a warm-up batch, time measured after device synchronisation and divided by the number of draws (amortised throughput per draw, not latency), median of three repeats whose spread is below 7% in every entry; projected linear cluster for , random isometric emitters for ; , Haar-random , one random collision-free output; the right-environment preprocessing is included in the timed call. Peak device memory is GB for and 3.1 GB for . The growth with is roughly linear although the term of is quadratic, a batching effect at these sizes; the table documents the measured cost, not the asymptotics. The Rademacher variant is 18–47× cheaper at (no eigenproblem, real signs) and about 2× at , where the contractions dominate. The raw CSV files are in the package (results/h100_20261003/).
Formal proofs in Lean
Proposition 1 (Gaussian and Rademacher cases), parts (i)–(ii) of Theorem 1, the exactness statement of part (iii) together with the sitewise draw of Algorithm 1, and the identity, normalisation and rejection step of Proposition S1 are formalised in Lean 4 with the Mathlib library. The project, archived at https://doi.org/10.5281/zenodo.24023358 (folder Lean/), includes an Axioms.lean file that prints the dependencies of the principal declarations. Its README reports a successful build with only the standard axioms (propositional extensionality, choice and quotient soundness). Reproducing that check requires the pinned Lean and Mathlib versions and a fresh lake build. The sign-support correction, the finite-local-Fock extension and the complexity discussion are not covered by the listed formalisation. Modes, emissions and labels are arbitrary finite types, amplitudes complex numbers, and the measures are Mathlib measures on ; nothing depends on floating-point arithmetic. Table S2 lists the correspondence.
| paper | Lean file | main declarations and content |
| Proposition 1, proof | Identity.lean | Pairs: for distinct modes ; gaussian_identity: under it, for every matrix , every state with at most one photon per mode and every rows (collisions included) |
| pairing of monomials | Words.lean | pairings_eq: when the occupations agree, otherwise; wick_of_moments: one-mode moments give the Wick rule on the product measure |
| §4, Gaussian | ComplexGaussian.lean | stdGaussian: density ; stdGaussian_moment: (polar coordinates); complexGaussian_identity: Proposition 1 |
| Proposition 1, Rademacher | Rademacher.lean | rademacher_pairs, rademacher_identity: the same identity with uniform on |
| Theorem 1 (i)–(ii) | Estimator.lean | normalisation: ; qMeasure_isProbability: (i); estimator_mean: ; gOut_second_moment: for unitary ; estimator_second_moment: when is -null |
| Theorem 1 (ii), null set | NullSet.lean | gaussian_Phi_null: for ( is affine in each , and a slice with is a point); theorem2_gaussian_full: parts (i)–(ii) for and unitary , with no further hypothesis |
| Theorem 1 (iii), proof | Sampler.lean | env_posSemidef: the right environments are positive semidefinite; integral_wt_step: ; cond_eq_gram: the sitewise conditional is (6); integral_cond: it is a probability density; law_eq: drawing in turn from these conditionals gives the prefix the density with respect to |
| Theorem 1 (iii) | SamplerLaw.lean | Phi_output: at the output ; pw_zero_eq_normSq: ; sampler_exact: with the unused modes drawn from , the output of the sequential draw has law |
| Algorithm 1, step 4 | Mixture.lean, Radial.lean | map_unitary_gaussianVector: on is invariant under unitaries; sitewise_draw: with , drawing with probability and , with of density and the other standard Gaussian (tilted_eq_pi), gives the density (6); radial_draw: with and uniform has density |
| Proposition S1 | Vacuum.lean | vacuum_identity: components of another photon number than the output add nothing to ; vacuum_normalisation: over all photon numbers; target_le: ; rejection_subdensity: proposal density times acceptance probability is ; rejection_acceptance: acceptance probability |
Table S2. Lean declarations corresponding to the mathematical statements. All declarations belong to the namespace EstimatorNote.
Modelling choices. For parts (i)–(ii) the state is an arbitrary function on label words, as in the note, since they use no MPS structure; for part (iii) it is the sequential MPS (1) with bond space of any finite dimension, and the drawn law is compared with as a measure on . Lean’s convention sets on , which is null for both and .
Not formalised. The operation counts of part (iii) of Theorem 1; in Proposition S1, the form of the sitewise conditional with a vacuum label, part (ii) for the vacuum train, and the cost; Corollary 1; Remark 1; §§6–7; the inequalities of Remark S1; all cost statements.
References
- [1]S. Aaronson and A. Arkhipov. The Computational Complexity of Linear Optics. Theory Comput., 9(4):143–252, 2013. DOI: 10.4086/toc.2013.v009a004.DOI
- [2]P. Clifford and R. Clifford. The Classical Complexity of Boson Sampling. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 146–155. SIAM, 2018. DOI: 10.1137/1.9781611975031.10.DOI
- [3]M. A. Broome, A. Fedrizzi, S. Rahimi-Keshari, J. Dove, S. Aaronson, T. C. Ralph, and A. G. White. Photonic Boson Sampling in a Tunable Circuit. Science, 339(6121):794–798, 2013. DOI: 10.1126/science.1231440.DOI
- [4]J. B. Spring et al. Boson Sampling on a Photonic Chip. Science, 339(6121):798–801, 2013. DOI: 10.1126/science.1231692.DOI
- [5]H. Wang et al. Boson Sampling with 20 Input Photons and a 60-Mode Interferometer in a 10¹⁴-Dimensional Hilbert Space. Phys. Rev. Lett., 123:250503, 2019. DOI: 10.1103/PhysRevLett.123.250503.
- [6]C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex. Gaussian Boson Sampling. Phys. Rev. Lett., 119:170501, 2017. DOI: 10.1103/PhysRevLett.119.170501.DOI
- [7]H.-S. Zhong et al. Quantum Computational Advantage Using Photons. Science, 370(6523):1460–1463, 2020. DOI: 10.1126/science.abe8770.DOI
- [8]L. S. Madsen et al. Quantum Computational Advantage with a Programmable Photonic Processor. Nature, 606:75–81, 2022. DOI: 10.1038/s41586-022-04725-x.DOI
- [9]B. Y. Gan, D. Leykam, and D. G. Angelakis. Fock State-Enhanced Expressivity of Quantum Machine Learning Models. EPJ Quantum Technol., 9:16, 2022. DOI: 10.1140/epjqt/s40507-022-00135-0.DOI
- [10]T. Sedrakyan and A. Salavrakos. Photonic Quantum Generative Adversarial Networks for Classical Data. arXiv:2405.06023, 2024.DOI
- [11]F. Gottlieb, C. Faraji, R. Mezher, B. Ventura, S. Mansfield, and A. Salavrakos. Efficient Training of Photonic Quantum Generative Models. arXiv:2603.08793, 2026.arxiv.org/abs/2603.08793
- [12]L. Gurvits. On the Complexity of Mixed Discriminants and Related Problems. In Mathematical Foundations of Computer Science 2005 (MFCS), volume 3618 of Lecture Notes in Computer Science, pages 447–458. Springer, 2005.DOI
- [13]S. Aaronson and T. Hance. Generalizing and Derandomizing Gurvits’s Approximation Algorithm for the Permanent. Quantum Inf. Comput., 14(7&8):541–559, 2014. DOI: 10.26421/QIC14.7-8-1.DOI
- [14]Y. Lim and C. Oh. Classical Algorithms for Estimating Expectation Values in Linear Optical Circuits. Phys. Rev. Lett., 137:120602, 2026. DOI: 10.1103/bl9r-2gyb.DOI
- [15]B. Seron, H. Thomas, E. Araujo, A. Arkhipov, C. Oh, and L. Novo. Efficient Classical Algorithm for Estimating Linear Statistics of Boson Sampling. arXiv:2609.35447, 2026.arxiv.org/abs/2609.35447
- [16]E. Recio-Armengol, S. Ahmed, and J. Bowles. Train on Classical, Deploy on Quantum: Scaling Generative Quantum Machine Learning to a Thousand Qubits. arXiv:2503.02934, 2025.
- [17]L. Monbroussou, H. Thomas, H. Mhiri, Z. Holmes, and E. Kashefi. Classical Simulation and Model Concentration in Passive Linear Optics. arXiv:2607.24728, 2026.arxiv.org/abs/2607.24728
- [18]N. Spagnolo, D. J. Brod, E. F. Galvão, and F. Sciarrino. Non-Linear Boson Sampling. npj Quantum Inf., 9:3, 2023. DOI: 10.1038/s41534-023-00676-x.DOI
- [19]H. Le Jeannic et al. Dynamical Photon–Photon Interaction Mediated by a Quantum Emitter. Nat. Phys., 2022. DOI: 10.1038/s41567-022-01720-x.DOI
- [20]U. Chabaud, D. Markham, and A. Sohbi. Quantum Machine Learning with Adaptive Linear Optics. Quantum, 5:496, 2021. DOI: 10.22331/q-2021-07-05-496.DOI
- [21]L. Monbroussou, E. Z. Mamon, H. Thomas, V. Yacoub, U. Chabaud, and E. Kashefi. Towards Quantum Advantage with Photonic State Injection. Phys. Rev. Res., 7:033051, 2025. DOI: 10.1103/PhysRevResearch.7.033051.DOI
- [22]N. H. Lindner and T. Rudolph. Proposal for Pulsed On-Demand Sources of Photonic Cluster State Strings. Phys. Rev. Lett., 103:113602, 2009. DOI: 10.1103/PhysRevLett.103.113602.DOI
- [23]D. Cogan, Z.-E. Su, O. Kenneth, and D. Gershoni. Deterministic Generation of Indistinguishable Photons in a Cluster State. Nat. Photon., 17(4):324–329, 2023. DOI: 10.1038/s41566-022-01152-2.DOI
- [24]P. Thomas, L. Ruscio, O. Morin, and G. Rempe. Efficient Generation of Entangled Multiphoton Graph States from a Single Atom. Nature, 608:677–681, 2022. DOI: 10.1038/s41586-022-04987-5.DOI
- [25]N. Coste et al. High-Rate Entanglement between a Semiconductor Spin and Indistinguishable Photons. Nat. Photon., 17(7):582–587, 2023. DOI: 10.1038/s41566-023-01186-0.DOI
- [26]H. Huet et al. Deterministic and Reconfigurable Graph State Generation with a Single Solid-State Quantum Emitter. Nat. Commun., 16:4337, 2025. DOI: 10.1038/s41467-025-59693-3.DOI
- [27]G. de Gliniasty, P. Hilaire, P.-E. Emeriau, S. C. Wein, A. Salavrakos, and S. Mansfield. A Spin-Optical Quantum Computing Architecture. Quantum, 8:1423, 2024. DOI: 10.22331/q-2024-07-24-1423.
- [28]C. Schön, E. Solano, F. Verstraete, J. I. Cirac, and M. M. Wolf. Sequential Generation of Entangled Multiqubit States. Phys. Rev. Lett., 95:110503, 2005. DOI: 10.1103/Phys-RevLett.95.110503.pubmed.ncbi.nlm.nih.gov/16196992
- [29]A. J. Ferris and G. Vidal. Perfect Sampling with Unitary Tensor Networks. Phys. Rev. B, 85:165146, 2012. DOI: 10.1103/PhysRevB.85.165146.DOI
- [30]A. Meiburg, J. Chen, J. Miller, R. Thion, G. Rabusseau, and A. Perdomo-Ortiz. Generative Learning of Continuous Data by Tensor Networks. SciPost Phys., 18:096, 2025. DOI: 10.21468/SciPostPhys.18.3.096.DOI
- [31]L. G. Valiant. The Complexity of Computing the Permanent. Theor. Comput. Sci., 8(2):189–201, 1979. DOI: 10.1016/0304-3975(79)90044-6.DOI
- [32]Y. Lim and C. Oh. Approximating Outcome Probabilities of Linear Optical Circuits. npj Quantum Inf., 9:124, 2023. DOI: 10.1038/s41534-023-00791-9.DOI
- [33]M. Correa Anguita, T. Roelink, S. Marzban, W. Briels, C. Filippi, and J. Renema. Experimental Demonstration of Boson Sampling as a Hardware Accelerator for Monte Carlo Integration. arXiv:2509.25404, 2025.arxiv.org/abs/2509.25404
- [34]C. Oh, K. Noh, B. Fefferman, and L. Jiang. Classical Simulation of Lossy Boson Sampling Using Matrix Product Operators. Phys. Rev. A, 104:022407, 2021. DOI: 10.1103/Phys-RevA.104.022407.DOI
- [35]C. Oh, M. Liu, Y. Alexeev, B. Fefferman, and L. Jiang. Classical Algorithm for Simulating Experimental Gaussian Boson Sampling. Nat. Phys., 20:1461, 2024. DOI: 10.1038/s41567-024-02535-8.DOI
- [36]S. Park and C. Oh. Matrix Product State Approach to Lossy Boson Sampling and Noisy IQP Sampling. arXiv:2510.24137, 2025.arxiv.org/abs/2510.24137
- [37]U. Schollwöck. The Density-Matrix Renormalization Group in the Age of Matrix Product States. Ann. Phys., 326(1):96–192, 2011. DOI: 10.1016/j.aop.2010.09.012.DOI
- [38]G. Vidal. Efficient Classical Simulation of Slightly Entangled Quantum Computations. Phys. Rev. Lett., 91:147902, 2003. DOI: 10.1103/PhysRevLett.91.147902.DOI
- [39]C. Schön, K. Hammerer, M. M. Wolf, J. I. Cirac, and E. Solano. Sequential Generation of Matrix-Product States in Cavity QED. Phys. Rev. A, 75:032311, 2007. DOI: 10.1103/PhysRevA.75.032311.DOI
- [40]S. E. Economou, N. Lindner, and T. Rudolph. Optically Generated 2-Dimensional Photonic Cluster State from Coupled Quantum Dots. Phys. Rev. Lett., 105:093601, 2010. DOI: 10.1103/PhysRevLett.105.093601.DOI
- [41]D. Buterakos, E. Barnes, and S. E. Economou. Deterministic Generation of All-Photonic Quantum Repeaters from Solid-State Emitters. Phys. Rev. X, 7:041023, 2017. DOI: 10.1103/PhysRevX.7.041023.DOI
- [42]I. Schwartz, D. Cogan, E. R. Schmidtgall, Y. Don, L. Gantz, O. Kenneth, N. H. Lindner, and D. Gershoni. Deterministic Generation of a Cluster State of Entangled Photons. Science, 354(6311):434–437, 2016. DOI: 10.1126/science.aah4758.DOI
- [43]D. Istrati et al. Sequential Generation of Linear Cluster States from a Single Photon Emitter. Nat. Commun., 11, 2020. DOI: 10.1038/s41467-020-19341-4.DOI
- [44]P. Thomas, L. Ruscio, O. Morin, and G. Rempe. Fusion of Deterministically Generated Photonic Graph States. Nature, 629(8012):567–572, 2024. DOI: 10.1038/s41586-024-07357-5.DOI
- [45]J.-C. Besse et al. Realizing a Deterministic Source of Multipartite-Entangled Photonic Qubits. Nat. Commun., 11, 2020. DOI: 10.1038/s41467-020-18635-x.DOI
- [46]V. S. Ferreira, G. Kim, A. Butler, H. Pichler, and O. Painter. Deterministic Generation of Multidimensional Photonic Cluster States with a Single Quantum Emitter. Nat. Phys., 20(5): 865–870, 2024. DOI: 10.1038/s41567-024-02408-0.DOI
- [47]B. Li, S. E. Economou, and E. Barnes. Photonic Resource State Generation from a Minimal Number of Quantum Emitters. npj Quantum Inf., 8, 2022. arXiv:2108.12466.DOI
- [48]J. Senellart, P. Senellart, S. Wein, and P.-E. Emeriau. Exact Sampling beyond Fock Inputs and Linear Optics: Photon-Number Superpositions, Photonic Matrix-Product States, Adaptive and Non-Linear Circuits. In preparation, 2026.arxiv.org/abs/2611.11044
- [49]H. Pashayan, S. D. Bartlett, and D. Gross. From Estimation of Quantum Probabilities to Simulation of Quantum Circuits. Quantum, 4:223, 2020. DOI: 10.22331/q-2020-01-13-223.DOI
- [50]M. Marcus and M. Newman. Inequalities for the Permanent Function. Ann. Math., 75(1):47, 1962.DOI
- [51]A. Herbst, I. Brandić, and A. Pérez-Salinas. Limits of Quantum Generative Models with Classical Sampling Hardness. arXiv:2512.24801, 2025.arxiv.org/abs/2512.24801
- [52]C. Oh and Y. Lim. Classical Algorithms for Measurement-Adaptive Gaussian Circuits. arXiv:2509.00746, 2025.arxiv.org/abs/2509.00746