betaFeedback

WorksPhysics 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 nn-photon input that is a matrix-product state of bond dimension χχ, with one photon per site and LL modes per site, we give an unbiased estimator of any output amplitude of an mm-mode interferometer, whose mean-square error after NN draws is at most ∥ψ∥2/N\|ψ\|^2/N whatever the interferometer, the output pattern and the entanglement of the state. Each draw costs O(nLχ2+nL3+mn)O(nLχ^2+nL^3+mn) operations after O(nLχ3)O(nLχ^3) preprocessing, and an additive error ε\varepsilon with probability at least 1−δ1-δ requires O(∥ψ∥2ε−2log⁡(1/δ))O(\|ψ\|^2\varepsilon^{-2}\log(1/δ)) 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 χ=2χ=2 at any length, and a memory of kk qubits, held in emitters or in photons stored in a delay line, gives χ≤2kχ\le2^k, so the cost stays polynomial as long as k=O(log⁡n)k=O(\log n). 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, nn indistinguishable photons enter an mm-mode interferometer and are detected at its output. Each output probability is the squared modulus of the permanent of an n×nn \times n 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 n2nn2^n [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 1/N1/\sqrt{N} after NN 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 ε\varepsilon with O(1/ε2)O(1/\varepsilon^2) 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 χ\chi. Every state generated sequentially by an emitter of dimension dd is an MPS with χ≤d\chi\le d, 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 O(nLχ2+nL3+mn)O(nL\chi^2+nL^3+mn) operations after a one-off O(nLχ3)O(nL\chi^3) preprocessing. Reaching an additive error ε\varepsilon with probability at least 1−δ1-\delta takes O(∥ψ∥2ε−2log⁡(1/δ))O(\lVert\psi\rVert^2\varepsilon^{-2}\log(1/\delta)) draws (see § 8.2), so the total cost is

Sequential source and one step of the sampler

Figure 1. (a) A sequential source. One or several emitters, whose joint memory (Definition 2) bounds the bond dimension χ\chi of the emitted state (χ=2\chi= 2 for a single spin, χ≤2k\chi\le2^k for kk spins, which may interact; photons stored in a delay line also count as memory), emit nn photons, one per site; each photon occupies one of the LL modes of its site, recorded by the label xkx_k (for instance time bins, polarisations or spatial modes). The photons enter an mm-mode interferometer UU, which may act on all of these modes, and are detected in an output pattern t\mathbf{t}. 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 M(k)M^{(k)} per emission, linked by bonds of dimension χ\chi and closed by the initial memory state ∣s0⟩\lvert s_0\rangle and by ⟨f∣\langle f\rvert. After the last emission the memory is either measured and found in ∣f⟩\lvert f\rangle (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 v1,…,vk−1v_1,\ldots,v_{k-1} already drawn are contracted into the left vector ak−1a_{k-1}, all future sites are averaged into the right environment RkR_k, and vkv_k 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.

O(nLχ3+(nLχ2+nL3+mn)∥ψ∥2log⁡(1/δ)ε2)O\left(nL\chi^3+\left(nL\chi^2+nL^3+mn\right)\frac{\lVert\psi\rVert^2\log(1/\delta)}{\varepsilon^2}\right)

operations, with O(nLχ2+m2)O(nL\chi^2+m^2) memory for the input and the stored environments. The cost is polynomial in χ\chi and in 1/ε1/\varepsilon.

For emitter-generated light, χ\chi is bounded by the dimension of the source’s retained quantum memory (Definition 2, with examples in Table 1): a single spin gives χ=2\chi=2 however long the cluster state is, and kk qubits of memory, whether emitters or photons held in a delay line, give χ≤2k\chi\le2^k, so the estimator stays efficient as long as k=O(log⁡n)k=O(\log n) (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 nn-photon states, in the emission order indicated. The cost is that of the estimator to fixed ε\varepsilon and δ\delta, with mm and LL polynomial in nn.

State (emission order)memory kk (qubits)χ\chicost
Fock or product input0011poly⁡(n)\operatorname{poly}(n)
GHZ, linear cluster (one spin)1122poly⁡(n)\operatorname{poly}(n)
2D cluster strip of width ww (by columns)Θ(w)\Theta(w)2Θ(w)2^{\Theta(w)}poly⁡(n) 2O(w)\operatorname{poly}(n)\,2^{O(w)}
with w=O(log⁡n)w=O(\log n)O(log⁡n)O(\log n)poly⁡(n)\operatorname{poly}(n)poly⁡(n)\operatorname{poly}(n)
with w=nw=\sqrt{n} (square lattice)Θ(n)\Theta(\sqrt{n})2Θ(n)2^{\Theta(\sqrt{n})}2O(n)2^{O(\sqrt{n})}
Generic nn-qubit stateΘ(n)\Theta(n)2Θ(n)2^{\Theta(n)}2O(n)2^{O(n)}

Table 1.

Contributions.

  1. The main result is an exact, site-by-site sampler for the importance density of an MPS input, with explicit costs in nn, mm, LL, χ\chi, ε\varepsilon and δ\delta (Theorem 1(iii), Algorithm 1, § 8.2). Each local conditional is a mixture of at most LL Gaussian densities in which one coordinate has a Gamma(2,1)(2,1) 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.

  1. 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).

  1. 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).

  1. 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 mm modes is described by an m×mm \times m unitary UU. We write an nn-photon Fock state by its occupations, s=(s1,…,sm)\mathbf{s}=(s_1,\ldots,s_m) with sjs_j photons in mode jj and ∑jsj=n\sum_j s_j=n, and set s!=∏jsj!\mathbf{s}!=\prod_j s_j!. For a Fock input s\mathbf{s} and output t=(t1,…,tm)\mathbf{t}=(t_1,\ldots,t_m),

⟨t∣U∣s⟩=Per⁡(U[t,s])s! t!\langle\mathbf{t}|U|\mathbf{s}\rangle= \frac{\operatorname{Per}(U[\mathbf{t},\mathbf{s}])}{\sqrt{\mathbf{s}!\,\mathbf{t}!}}

where U[t,s]U[\mathbf{t},\mathbf{s}] is the n×nn \times n submatrix of UU in which row jj is repeated tjt_j times and column jj is repeated sjs_j times, and Per⁡(A)=∑σ∈Sn∏i=1nAiσ(i)\operatorname{Per}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^{n} A_{i\sigma(i)} is the permanent. Computing the permanent exactly is #P\#\mathrm{P}-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 n×nn \times n matrix AA of operator norm ∥A∥\lVert A\rVert,

Per⁡(A)=Ex[∏i(Ax)i∏jxj],x uniform on {±1}n,\operatorname{Per}(A)=\mathbb{E}_{\mathbf{x}}\left[\prod_i(A\mathbf{x})_i\prod_j x_j\right],\qquad\mathbf{x}\ \text{uniform on }\{\pm1\}^{n},

and averages the bracket over O(1/ε2)O(1/\varepsilon^2) random sign vectors to obtain Per⁡(A)\operatorname{Per}(A) to within ±ε∥A∥n\pm\varepsilon\lVert A\rVert^n, each draw costing O(n2)O(n^2) operations. For collision-free outputs of a unitary, ∥A∥≤1\lVert A\rVert\leq1. Aaronson and Hance [13] extend this to repeated rows and columns, with an error that improves with the collisions by the factor

∏jtj!/∏jtjtj≤1.\sqrt{\prod_j t_j!/\prod_j t_j^{t_j}}\leq1.

Lim and Oh [14] give the estimator a physical form. For arbitrary input and output states, ⟨ϕ∣U∣ψ⟩\langle\phi|U|\psi\rangle is an integral over coherent states α\alpha, weighted by the Husimi function q(α)=∣⟨α∣ψ⟩∣2/πmq(\alpha)=|\langle\alpha|\psi\rangle|^2/\pi^m 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 α\alpha from qq and evaluate the integrand, and both steps are efficient when the input is a product state, because qq then factorises mode by mode. In earlier work the same authors approximate outcome probabilities with ss-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 qq 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 kk can occupy one of LL input modes, and which one it occupies is recorded by a label xk∈[L]={1,…,L}x_k\in[L]=\{1,\ldots,L\}. For dual-rail qubits L=2L=2; the labels may equally be time bins, frequencies or spatial modes. We call the LL modes available to photon kk its site, and write them μk,1,…,μk,L\mu_{k,1},\ldots,\mu_{k,L}; different sites use different modes, so the LnLn modes μk,l\mu_{k,l} are all distinct. In dual rail, for instance, μk,l=2(k−1)+l\mu_{k,l}=2(k-1)+l.

A label word x=(x1,…,xn)∈[L]n\mathbf{x}=(x_1,\ldots,x_n)\in[L]^n then denotes the Fock state ∣x⟩|\mathbf{x}\rangle with one photon at each site kk, in mode

ck(x)=μk,xk,c_k(\mathbf{x})=\mu_{k,x_k},

and we write c(x)=(c1(x),…,cn(x))\mathbf{c}(\mathbf{x})=(c_1(\mathbf{x}),\ldots,c_n(\mathbf{x})) for the list of occupied modes; this list is what enters the permanents below. Because sites are disjoint, ∣x⟩|\mathbf{x}\rangle never has two photons in the same mode, and different words give orthogonal Fock states. In this language an nn-photon input is simply an nn-qudit state ∑xψ(x)∣x⟩\sum_{\mathbf{x}}\psi(\mathbf{x})|\mathbf{x}\rangle, and an MPS takes its usual form [37].

Definition 1 (Photonic MPS). A photonic MPS of bond dimension χ\chi is a nonzero state

∣ψ⟩=∑x∈[L]nψ(x)∣x⟩,ψ(x)=⟨f∣Mxn(n)⋯Mx1(1)∣s0⟩,(1)|\psi\rangle=\sum_{\mathbf{x}\in[L]^n}\psi(\mathbf{x})|\mathbf{x}\rangle,\qquad\psi(\mathbf{x})=\langle f|M_{x_n}^{(n)}\cdots M_{x_1}^{(1)}|s_0\rangle, \tag*{(1)}

where each Ml(k)M_l^{(k)} is a χ×χ\chi\times\chi complex matrix and ∣s0⟩,⟨f∣|s_0\rangle,\langle f| are boundary vectors in Cχ\mathbb{C}^{\chi}.

Apart from the map x↦c(x)\mathbf{x}\mapsto\mathbf{c}(\mathbf{x}) from labels to occupied modes, this is the standard open-boundary MPS, with physical index xkx_k at site kk. Every state admits this form for χ\chi large enough; the boundary vectors ∣s0⟩|s_0\rangle and ⟨f∣\langle f| only close the chain.

Example. Take n=3n=3 dual-rail photons, μk,l=2(k−1)+l\mu_{k,l}=2(k-1)+l, and χ=2\chi=2 with M1=diag⁡(1,0)M_1=\operatorname{diag}(1,0), M2=diag⁡(0,1)M_2=\operatorname{diag}(0,1) at every site, s0=(1,1)T/2s_0=(1,1)^{T}/\sqrt{2} and f=(1,1)Tf=(1,1)^{T}. The product Mx3Mx2Mx1M_{x_3}M_{x_2}M_{x_1} vanishes unless all labels agree, so ψ(1,1,1)=ψ(2,2,2)=1/2\psi(1,1,1)=\psi(2,2,2)=1/\sqrt{2}, with c(1,1,1)=(1,3,5)\mathbf{c}(1,1,1)=(1,3,5) and c(2,2,2)=(2,4,6)\mathbf{c}(2,2,2)=(2,4,6). In occupation notation over the six modes this is the dual-rail GHZ state (∣101010⟩+∣010101⟩)/2(|101010\rangle+|010101\rangle)/\sqrt{2}, and each of its output amplitudes (2) is a sum of two permanents. Taking instead χ=1\chi=1, M1=1M_1=1, M2=0M_2=0 gives the Fock input ∣101010⟩|101010\rangle of standard boson sampling.

Site-dependent bond dimensions χk≤χ\chi_k\le\chi are allowed by padding with zeros. We do not assume that ψ\psi is normalised; the algorithm computes ∥ψ∥2\|\psi\|^2 along the way. For an output occupation t\mathbf{t} with ∑jtj=n\sum_j t_j=n, let r=(r1,…,rn)\mathbf{r}=(r_1,\ldots,r_n) list the output modes, mode jj appearing tjt_j times. The amplitude is

At=⟨t∣U∣ψ⟩=(t!)−1/2∑xψ(x)Per⁡U[r,c(x)],(2)A_{\mathbf{t}}=\langle\mathbf{t}|U|\psi\rangle=(\mathbf{t}!)^{-1/2}\sum_{\mathbf{x}}\psi(\mathbf{x})\operatorname{Per} U[\mathbf{r},\mathbf{c}(\mathbf{x})], \tag*{(2)}

where U[r,c(x)]U[\mathbf{r},\mathbf{c}(\mathbf{x})] has rows r\mathbf{r} and columns c(x)\mathbf{c}(\mathbf{x}). The sum has LnL^n 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 Ml(k)M_l^{(k)} 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 χ\chi 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 ∣ψ⟩|\psi\rangle has the form (1), its Schmidt rank across the cut between sites 1,…,k1,\ldots,k and k+1,…,nk+1,\ldots,n is at most χ\chi; conversely, the smallest χ\chi for which (1) holds is the largest of the n−1n-1 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 ∏kCZk,k+1∣+⟩\prod_k CZ_{k,k+1}|+\rangle (one qubit per site, L=2L=2, labels written 0,10,1) has Schmidt rank 22 across every cut in chain order, since each such cut breaks a single CZCZ bond, and an explicit MPS with χ=2\chi=2 is M0=12(1111)M_0=\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&1\end{pmatrix}, M1=12(001−1)M_1=\frac{1}{\sqrt{2}}\begin{pmatrix}0&0\\1&-1\end{pmatrix} at every site, with s0=(1,0)Ts_0=(1,0)^T and f=(1,1)Tf=(1,1)^T. Across the cut separating even from odd sites, however, every bond is broken and the Schmidt rank is 2⌈n/2⌉2^{\lceil n/2\rceil}. A GHZ state, in contrast, has Schmidt rank 22 across every bipartition. The large multipartite entanglement of the cluster state is real, but it is invisible to the chain cuts that determine χ\chi.

The order of the sites is ours to choose. Reordering the sites only relabels input modes, and that relabelling can be absorbed into UU. 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 Cd\mathbb{C}^{d}, its memory, from one emission to the next. At emission kk an isometry entangles the memory with a photon in the modes of site kk; writing Ml(k)M_l^{(k)} for the memory operator that accompanies a photon with label ll, the joint state of photons and memory after nn emissions is ∣Ψ⟩=∑x∣x⟩⊗Mxn(n)⋯Mx1(1)∣s0⟩|\Psi\rangle= \sum_{\boldsymbol{x}} |\boldsymbol{x}\rangle\otimes M_{x_n}^{(n)} \cdots M_{x_1}^{(1)} |s_0\rangle. This is Eq. (1) with χ=d\chi=d and an open right boundary. One spin gives χ=2\chi=2, 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 dd, for instance d=2kd=2^k for kk qubits, the emitted photonic state is a photonic MPS (Definition 1) in emission order with χ≤d\chi\le d.

The memory is therefore a property of the source, and χ\chi a property of the state it emits; the first bounds the second. Two spins give χ≤4\chi\le4, kk two-level emitters give χ≤2k\chi\le2^k, and a delay of τ\tau time bins [43, 46] adds up to τ\tau 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 log⁡2χ\log_2 \chi. 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 k=O(log⁡n)k=O(\log n) 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 ∣ψ⟩|\psi\rangle and found in that state, the photonic state is the pure, in general unnormalised, state (1). Then ∣At∣2|A_t|^2 is the joint weight of the projection outcome and the output, and the probability conditional on the projection is ∣At∣2/∥ψ∥2|A_t|^2/\|\psi\|^2. All draw counts below are stated for AtA_t and ∣At∣2|A_t|^2; the conditional version divides by ∥ψ∥2\|\psi\|^2, which the algorithm computes.

Traced memory. If the memory is discarded, the photonic state is ρ=∑e∣ψe⟩⟨ψe∣\rho=\sum_e |\psi_e\rangle\langle\psi_e|, where ∣ψe⟩|\psi_e\rangle is the state (1) with ⟨f∣=⟨e∣\langle f|=\langle e| and ee runs over an orthonormal basis of Cχ\mathbb{C}^{\chi}. The output probability is p(t)=∑e∣At,e∣2p(t)=\sum_e |A_{t,e}|^2, with At,eA_{t,e} the amplitude (2) of ψe\psi_e. It is a probability when the sequence of emissions is normalised: Tr⁡ρmem=1\operatorname{Tr}\rho_{\mathrm{mem}}=1 with ρmem=∑xMx∣s0⟩⟨s0∣Mx†\rho_{\mathrm{mem}}=\sum_{\boldsymbol{x}} M_{\boldsymbol{x}}|s_0\rangle\langle s_0|M_{\boldsymbol{x}}^\dagger and Mx=Mxn(n)⋯Mx1(1)M_{\boldsymbol{x}}=M_{x_n}^{(n)}\cdots M_{x_1}^{(1)}.

This holds whenever ∥s0∥=1\lVert s_0\rVert=1 and each emission is an isometry from the memory to the memory and one photon, ∑lMl(k)†Ml(k)=1\sum_l M_l^{(k)\dagger}M_l^{(k)}=1. 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 M0(k)M_0^{(k)}, the input spans several photon numbers, and the sampler of § 6 needs one rejection step per site, accepted with probability exactly 1/21/2 (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 UU when we estimate joint weights for detecting all nn 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 γ(x)=π−me−∥x∥2\gamma(x)=\pi^{-m}e^{-\lVert x\rVert^2} be the standard complex Gaussian density on Cm\mathbb{C}^m: the entries xax_a, a∈[m]a\in[m], are independent and circularly symmetric, with E∣xa∣2=1\mathbb{E}|x_a|^2=1, so that E[xˉppxqq]=p! δpq\mathbb{E}[\bar{x}_p^p x_q^q]=p!\,\delta_{pq}. We use the same symbol for the standard Gaussian density on the space of a single site (CL\mathbb{C}^L) or of the memory (Cχ\mathbb{C}^{\chi}). Define

Φ(x)=⟨X∣ψ⟩=∑xψ(x)∏k=1nx‾ck(x),∣X⟩=⨂k=1n∑l=1Lxμk,l∣l⟩,gt(x)=∏i=1n(Ux)ri.(3)\Phi(x)=\langle X|\psi\rangle=\sum_x\psi(x)\prod_{k=1}^{n}\overline{x}_{c_k(x)},\qquad|X\rangle=\bigotimes_{k=1}^{n}\sum_{l=1}^{L}x_{\mu_k,l}|l\rangle,\qquad g_t(x)=\prod_{i=1}^{n}(Ux)_{r_i}. \tag*{(3)}

Here Φ(x)\Phi(x) is the overlap of the input with the product vector ∣X⟩|X\rangle; for an MPS it is obtained by contracting the tensors with ∣X⟩|X\rangle one site at a time, in O(nLχ2)O(nL\chi^2) operations. The output factor gt(x)g_t(x) only needs the nn entries (Ux)ri(Ux)_{r_i}, which cost O(mn)O(mn).

Proposition 1 (Gaussian identity). For every m×mm\times m matrix UU, every nn-photon state with at most one photon per mode (in particular (1); in general, xx indexes its Fock components and c(x)c(x) lists their occupied modes) and every output mathbftmathbf{t},

∑xψ(x)Per⁡(U[r,c(x)])=Ex∼γ[Φ(x)gt(x)],i.e.At=(t!)−1/2Eγ[Φgt].(4)\sum_x\psi(x)\operatorname{Per}(U[r,c(x)])=\mathbb{E}_{x\sim\gamma}\left[\Phi(x)g_t(x)\right],\qquad\text{i.e.}\qquad A_t=(t!)^{-1/2}\mathbb{E}_{\gamma}[\Phi g_t]. \tag*{(4)}

The same holds with xx uniform on {±1}m\{\pm1\}^m (Rademacher), with no conjugation in Φ\Phi.

Proof. The two forms of (4). By linearity, At=⟨t∣U∣ψ⟩=∑xψ(x)⟨t∣U∣x⟩A_t=\langle t|U|\psi\rangle=\sum_x\psi(x)\langle t|U|x\rangle. Each ∣x⟩|x\rangle is a Fock state with at most one photon per mode, so the formula of § 3 gives ⟨t∣U∣x⟩=(t!)−1/2Per⁡(U[r,c(x)])\langle t|U|x\rangle=(t!)^{-1/2}\operatorname{Per}(U[r,c(x)]): here s!=1s!=1, and U[t,s]U[t,s] is U[r,c(x)]U[r,c(x)] 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 xˉc\bar{x}_c in Φ\Phi stands for an input photon in mode cc, each factor (Ux)r=∑dUrdxd(Ux)_r=\sum_d U_{rd}x_d in gtg_t stands for an output photon in mode rr that may come from any input mode dd, and the Gaussian average pairs every output photon with exactly one input photon.

Two photons. Take one input photon in each of the modes a≠ba\ne b, so that Φ=xˉaxˉb\Phi=\bar{x}_a\bar{x}_b, and two output rows r,sr,s. Expanding,

E[xˉaxˉb(Ux)r(Ux)s]=∑d,d′UrdUsd′E[xˉaxˉbxdxd′].\mathbb{E}\left[\bar{x}_a\bar{x}_b(Ux)_r(Ux)_s\right]=\sum_{d,d'}U_{rd}U_{sd'}\mathbb{E}\left[\bar{x}_a\bar{x}_b x_d x_{d'}\right].

Since the modes are independent and E[xˉapxaq]=p! δpq\mathbb{E}[\bar{x}_a^p x_a^q]=p!\,\delta_{pq}, the expectation on the right is 1 if {d,d′}={a,b}\{d,d'\}=\{a,b\} and 0 otherwise: a mode that is not occupied must not appear, and each occupied mode must appear exactly once. Two terms survive, (d,d′)=(a,b)(d,d')=(a,b) and (b,a)(b,a), giving

E[xˉaxˉb(Ux)r(Ux)s]=UraUsb+UrbUsa=Per⁡(UraUrbUsaUsb).\mathbb{E}\left[\bar{x}_a\bar{x}_b(Ux)_r(Ux)_s\right]=U_{ra}U_{sb}+U_{rb}U_{sa}=\operatorname{Per}\begin{pmatrix} U_{ra} & U_{rb} \\ U_{sa} & U_{sb} \end{pmatrix}.

the two indistinguishable ways of sending the input photons to the output rows.

General case. Since Φ(x)=∑xψ(x)∏kxˉck(x)\Phi(x)=\sum_x\psi(x)\prod_k\bar{x}_{c_k(x)} is linear in ψ\psi, it is enough to treat one word with occupied modes c=(c1,…,cn)c=(c_1,\ldots,c_n), which are distinct by assumption. Expanding gt(x)=∏i=1n∑dUridxdg_t(x)=\prod_{i=1}^{n}\sum_d U_{r_i d}x_d gives one term for each choice d=(d1,…,dn)d=(d_1,\ldots,d_n) of an input mode for every output row, with coefficient ∏iUridi\prod_i U_{r_i d_i}. Exactly as for two photons, E[∏kxˉck∏ixdi]\mathbb{E}\left[\prod_k\bar{x}_{c_k}\prod_i x_{d_i}\right] equals 1 if every mode of cc is chosen exactly once and no other mode is chosen, i.e. if di=cσ(i)d_i=c_{\sigma(i)} for a permutation σ\sigma, 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

Eγ[∏kxˉckgt(x)]=∑σ∈Sn∏i=1nUricσ(i)=Per⁡(U[r,c]).\mathbb{E}_{\gamma}\left[\prod_k\bar{x}_{c_k}g_t(x)\right]=\sum_{\sigma\in S_n}\prod_{i=1}^{n}U_{r_i c_{\sigma(i)}}=\operatorname{Per}(U[r,c]).

Repeated output rows cause no difficulty, since the sum runs over choices for each row. Summing over words with weights ψ(x)\psi(x) gives the left-hand form of (4).

Signs. For the last statement of the proposition, take xx uniform on {±1}m\{\pm1\}^m; the variables are real, so the conjugation in Φ\Phi plays no role. Now E[xak]\mathbb{E}[x_a^k] is 1 for even kk and 0 otherwise, so each mode must appear an even number of times in ∏kxck∏ixdi\prod_k x_{c_k}\prod_i x_{d_i}. Every mode of cc therefore has to be chosen at least once; with only nn choices for nn 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]: ∣X⟩|X\rangle is the projection of the unnormalised coherent-state generating vector with amplitude xx onto the sector with one photon in each site, and γ\gamma is the Gaussian factor of the Husimi measure. It uses no MPS structure. Averaging Φgt\Phi g_t directly under γ\gamma is unbiased, but its variance involves Eγ∣Φ∣2∣gt∣2\mathbb{E}_{\gamma}|\Phi|^2|g_t|^2, 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 xx from γ∣Φ∣2\gamma|\Phi|^2 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 xx-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 q(x)=γ(x)∣Φ(x)∣2/∥ψ∥2q(x)=\gamma(x)|\Phi(x)|^2/\|\psi\|^2. Then

(i) qq is a probability density on Cm\mathbb{C}^m;

(ii) under x∼qx\sim q, the variable Z(x)=∥ψ∥2gt(x)/Φ(x)‾Z(x)=\|\psi\|^2g_t(x)/\overline{\Phi(x)} (defined off the qq-null set {Φ=0}\{\Phi=0\}) satisfies, for every unitary UU, every tt and every ψ\psi,

Eq[Z]=t! At,Eq∣Z∣2=∥ψ∥2t!,\mathbb{E}_q[Z]=\sqrt{t!}\,A_t,\qquad\mathbb{E}_q|Z|^2=\|\psi\|^2t!,

so that Z^=Z/t!\widehat{Z}=Z/\sqrt{t!} is unbiased for AtA_t with E∣Z^∣2=∥ψ∥2\mathbb{E}|\widehat{Z}|^2=\|\psi\|^2, independent of UU, tt and the detailed input state;

(iii) for the MPS (1), qq can be sampled exactly, and Φ(x)\Phi(x) and ∥ψ∥2\|\psi\|^2 evaluated, in O(nLχ2+nL3)O(nL\chi^2+nL^3) operations per draw after O(nLχ3)O(nL\chi^3) preprocessing per state; gtg_t adds O(mn)O(mn) per draw.

Consequently, for NN independent draws x1,…,xN∼qx_1,\ldots,x_N\sim q, A^=N−1∑j=1NZ^(xj)\widehat{A}=N^{-1}\sum_{j=1}^{N}\widehat{Z}(x_j) satisfies E∣A^−At∣2≤∥ψ∥2/N\mathbb{E}|\widehat{A}-A_t|^2\leq\|\psi\|^2/N, and for two independent such estimates A^1A^2\widehat{A}_1\widehat{A}_2 is unbiased for ∣At∣2|A_t|^2 with mean-square error ≤∥ψ∥4/N\leq\|\psi\|^4/N.

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 xx with probability ∣ψ(x)∣2/∥ψ∥2|\psi(x)|^2/\|\psi\|^2, which perfect sampling of the MPS in the computational basis does in O(nLχ2)O(nL\chi^2) operations, and then estimates the single amplitude ⟨t∣U∣x⟩\langle t|U|x\rangle with Gurvits’s method. Reweighting by ∥ψ∥2/ψ(x)\|\psi\|^2/\psi(x) makes this unbiased as well, but each word now contributes its own variance, and the second moment becomes ∥ψ∥2\|\psi\|^2 times the number of words in the support of ψ\psi. This is harmless for a GHZ state, which has two words, but grows as 2n2^n for a linear cluster state, whose amplitudes are all nonzero. The same holds for any approach that writes ∣ψ⟩|\psi\rangle 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, 2⌊n/2⌋2^{\lfloor n/2\rfloor} (§ 4.2), although χ=2\chi=2. The Gaussian change of measure of Theorem 1 avoids this because it treats all words at once: their cross terms cancel in Eγ∣Φ∣2\mathbb{E}_{\gamma}|\Phi|^2, and the second moment does not depend on how many words the state contains.

Proof. Write rψ=∥ψ∥2r_\psi=\|\psi\|^2. 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 Eγ∣Φ∣2\mathbb{E}_{\gamma}|\Phi|^2:

Eγ∣Φ(x)∣2=∑x∣ψ(x)∣2=rψ.\mathbb{E}_{\gamma}|\Phi(x)|^2=\sum_x|\psi(x)|^2=r_\psi.

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

q(x)Z(x)=γ(x)Φ(x)gt(x),q(x)∣Z(x)∣2=rψγ(x)∣gt(x)∣2q(x)Z(x)=\gamma(x)\Phi(x)g_t(x),\qquad q(x)|Z(x)|^2=r_\psi\gamma(x)|g_t(x)|^2

wherever Φ(x)≠0\Phi(x)\ne0. Integrating the first equality and using Proposition 1 gives Eq[Z]=Eγ[Φgt]=t! At\mathbb{E}_q[Z]=\mathbb{E}_{\gamma}[\Phi g_t]=\sqrt{t!}\,A_t, the unbiasedness claim of (ii). For the second equality, the set {x:Φ(x)=0}\{x:\Phi(x)=0\} is the zero set of a nonzero polynomial, so it has Lebesgue, hence Gaussian, measure zero, and integrating gives Eq∣Z∣2=rψEγ∣gt∣2\mathbb{E}_q|Z|^2=r_\psi\mathbb{E}_{\gamma}|g_t|^2. For the sign variant this step fails, since a polynomial can vanish on sign vectors with positive probability (Sec. S4).

It remains to compute Eγ∣gt∣2\mathbb{E}_{\gamma}|g_t|^2, and here we use that UU is unitary, as it is for a lossless linear-optical circuit. Since γ\gamma depends on xx only through ∥x∥=∥Ux∥\|x\|=\|Ux\|, the vector y=Uxy=Ux has the same distribution as xx, and gt(x)=∏jyjtjg_t(x)=\prod_j y_j^{t_j}. By independence and the moment rule,

Eγ∣gt(x)∣2=∏jE∣yj∣2tj=∏jtj!=t!.\mathbb{E}_{\gamma}|g_t(x)|^2=\prod_j\mathbb{E}|y_j|^{2t_j}=\prod_j t_j!=t!.

Dividing by t!t! gives E∣Z^∣2=rψ\mathbb{E}|\widehat{Z}|^2=r_\psi, which completes the proof of (ii): the input enters the second moment only through its norm. For a lossy, sub-unitary UU the same quantity is at most t!t! (§ 17).

Sampling one site at a time. It remains to draw xx from qq. The function Φ\Phi depends only on the modes used by the sites, so qq is the product of γ\gamma on the unused modes, which are drawn as independent standard Gaussians, and a density on the site variables. For site kk write vk=(vk,1,…,vk,L)∈CLv_k=(v_{k,1},\ldots,v_{k,L})\in\mathbb{C}^{L} with vk,l=x‾μk,lv_{k,l}=\overline{x}_{\mu_k,l}; conjugation preserves γ\gamma, so under γ\gamma the vkv_k are independent standard Gaussian vectors. By the chain rule, it suffices to draw v1v_1 from its marginal under qq, then v2v_2 from its law conditional on v1v_1, and so on. We therefore need the marginal density of the first kk site vectors. Two objects make it computable.

The left vector ak∈Cχa_k\in\mathbb{C}^{\chi} is the memory vector after the first kk sites, given the values v1,…,vkv_1,\ldots,v_k already drawn:

a0=s0,ak=∑l=1Lvk,lMl(k)ak−1,Φ=f†an.a_0=s_0,\qquad a_k=\sum_{l=1}^{L}v_{k,l}M_l^{(k)}a_{k-1},\qquad\Phi=f^\dagger a_n.

This is (3) evaluated by multiplying the matrices from the right, one site at a time.

The right environment RkR_k is a χ×χ\chi\times\chi positive semidefinite matrix that summarises all possible futures. It is defined backwards by

Rn=ff†,Rk−1=∑l=1LMl(k)†RkMl(k),R_n=ff^\dagger,\qquad R_{k-1}=\sum_{l=1}^{L}M_l^{(k)\dagger}R_kM_l^{(k)},

and does not depend on xx, so it is computed once per state.

Averaging over the future. The key property is that averaging ∣Φ∣2|\Phi|^2 over the sites that have not yet been drawn leaves a quantity that depends on the past only through aka_k:

∫(∏k′>kγ(vk′) dvk′)∣Φ∣2=ak†Rkak.(5)\int\left(\prod_{k'>k}\gamma(v_{k'})\,dv_{k'}\right)|\Phi|^2=a_k^\dagger R_k a_k. \tag*{(5)}

For k=nk=n there is nothing to average, and ∣Φ∣2=an†ff†an=an†Rnan|\Phi|^2=a_n^\dagger ff^\dagger a_n=a_n^\dagger R_n a_n. Suppose (5) holds at kk, and average once more over vkv_k. Writing bl=Ml(k)ak−1b_l=M_l^{(k)}a_{k-1}, so that ak=∑lvk,lbla_k=\sum_l v_{k,l}b_l,

∫γ(vk)ak†Rkak dvk=∑l,l′E[v‾k,lvk,l′] bl†Rkbl′=∑lbl†Rkbl=ak−1†Rk−1ak−1,\int\gamma(v_k)a_k^\dagger R_k a_k\,dv_k =\sum_{l,l'}\mathbb{E}[\overline{v}_{k,l}v_{k,l'}]\,b_l^\dagger R_kb_{l'} =\sum_l b_l^\dagger R_kb_l =a_{k-1}^\dagger R_{k-1}a_{k-1},

because E[v‾k,lvk,l′]=δll′\mathbb{E}[\overline{v}_{k,l}v_{k,l'}]=\delta_{ll'} removes the cross terms. This is (5) at k−1k-1. At k=0k=0 it gives ∥ψ∥2=Eγ∣Φ∣2=s0†R0s0\|\psi\|^2=\mathbb{E}_{\gamma}|\Phi|^2=s_0^\dagger R_0s_0, without enumerating the LnL^n words.

Marginal and conditional densities. Dividing (5) by ∥ψ∥2\|\psi\|^2, the marginal density of the first kk site vectors under qq is

q(v1,…,vk)=(∏k′≤kγ(vk′))ak†Rkak∥ψ∥2.q(v_1,\ldots,v_k)=\left(\prod_{k'\leq k}\gamma(v_{k'})\right)\frac{a_k^\dagger R_ka_k}{\|\psi\|^2}.

The conditional density of vkv_k given the past is the ratio of two consecutive marginals. The Gaussian factors of the past and ∥ψ∥2\|\psi\|^2 cancel, leaving

q(vk∣v1,…,vk−1)=γ(vk)ak†Rkakak−1†Rk−1ak−1.q(v_k\mid v_1,\ldots,v_{k-1})=\gamma(v_k)\frac{a_k^\dagger R_ka_k}{a_{k-1}^\dagger R_{k-1}a_{k-1}}.

With bl=Ml(k)ak−1b_l=M_l^{(k)}a_{k-1} as above, the numerator is the quadratic form vk†Gvkv_k^\dagger Gv_k of the L×LL\times L matrix Gll′=bl†Rkbl′G_{ll'}=b_l^\dagger R_kb_{l'}, and the denominator is Tr⁡G\operatorname{Tr}G:

q(vk∣v1,…,vk−1)=γ(vk)vk†GvkTr⁡G.(6)q(v_k\mid v_1,\ldots,v_{k-1})=\gamma(v_k)\frac{v_k^\dagger Gv_k}{\operatorname{Tr}G}. \tag*{(6)}

GG 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 G=∑α=1Lλαeαeα†G = \sum_{\alpha=1}^{L} \lambda_{\alpha} e_{\alpha}e_{\alpha}^{\dagger} with λα≥0\lambda_{\alpha} \ge0 and orthonormal eαe_{\alpha}, and use the coordinates cα=eα†vkc_{\alpha} = e_{\alpha}^{\dagger}v_k. Since γ\gamma is invariant under unitaries, cc is again standard Gaussian under γ\gamma, and (6) becomes

γ(c)∑α=1LλαTr⁡G∣cα∣2.\gamma(c)\sum_{\alpha=1}^{L}\frac{\lambda_{\alpha}}{\operatorname{Tr}G}|c_{\alpha}|^{2}.

This is a mixture of LL simple densities with weights λα/Tr⁡G\lambda_{\alpha}/\operatorname{Tr}G. In component α\alpha, the coordinate cαc_{\alpha} has density γ(cα)∣cα∣2\gamma(c_{\alpha})|c_{\alpha}|^{2} and the other coordinates are independent standard Gaussians. In polar coordinates cα=seiθc_{\alpha} = \sqrt{s}e^{i\theta}, the density γ(cα)∣cα∣2\gamma(c_{\alpha})|c_{\alpha}|^{2} becomes se−s ds dθ/(2π)se^{-s}\,ds\,d\theta/(2\pi): ss follows a Gamma(2,1)(2,1) law and θ\theta is uniform. One draw therefore consists of

  1. choosing α\alpha with probability λα/Tr⁡G\lambda_{\alpha}/\operatorname{Tr}G;

  2. drawing ∣cα∣2∼Gamma⁡(2,1)|c_{\alpha}|^{2} \sim\operatorname{Gamma}(2,1) with a uniform phase, and every other cα′c_{\alpha'} as a standard complex Gaussian;

  3. setting vk=∑αcαeαv_k = \sum_{\alpha}c_{\alpha}e_{\alpha}, then ak=∑lvk,lbla_k = \sum_l v_{k,l}b_l, and xμk,l=v‾k,lx_{\mu_k,l} = \overline{v}_{k,l}.

Repeating this for k=1,…,nk = 1,\ldots,n draws the site variables from qq exactly, by the chain rule, and returns Φ=f†an\Phi= f^{\dagger}a_n at no extra cost.

Cost. The backward recursion for Rn−1,…,R0R_{n-1},\ldots,R_0 multiplies LL pairs of χ×χ\chi\times\chi matrices per site, O(nLχ3)O(nL\chi^3) in total. At each site of a draw, forming the blb_l and RkblR_kb_l costs O(Lχ2)O(L\chi^2), the matrix GG costs O(L2χ)O(L^2\chi), and its diagonalisation O(L3)O(L^3); since L2χ≤(Lχ2+L3)/2L^2\chi\le(L\chi^2 + L^3)/2, this is O(Lχ2+L3)O(L\chi^2 + L^3) per site. This proves (iii).

From one draw to an error bound. Independence gives E∣A^−At∣2=(rψ−∣At∣2)/N≤rψ/N\mathbb{E}|\widehat{A}-A_t|^2 = (r_{\psi}-|A_t|^2)/N \le r_{\psi}/N. To estimate a probability without squaring a noisy estimate, use two independent averages. Put a=∣At∣2a = |A_t|^2 and v=rψ−av = r_{\psi}-a. Their product has mean aa and mean-square error

2avN+v2N2≤2av+v2N=rψ2−a2N≤rψ2N.\frac{2av}{N}+\frac{v^2}{N^2}\le\frac{2av+v^2}{N}=\frac{r_{\psi}^2-a^2}{N}\le\frac{r_{\psi}^2}{N}.

The real part is also unbiased and has no larger mean-square error.

Algorithm 1 (One Gaussian importance draw). Preprocess once: Rn=ff†R_n = ff^{\dagger}, Rk−1=∑lMl(k)†RkMl(k)R_{k-1} = \sum_l M_l^{(k)\dagger}R_kM_l^{(k)}, and rψ=s0†R0s0r_{\psi}=s_0^{\dagger}R_0s_0.

  1. Set a=s0a=s_0. Draw independent standard complex Gaussian entries xax_a on modes outside the sites. (Setting them to zero instead also gives an unbiased estimator, with a smaller second moment when m≫Lnm\gg Ln; Remark S1.)

  2. For each site k=1,…,nk=1,\ldots,n, perform steps 3–5.

  3. Form bl=Ml(k)ab_l=M_l^{(k)}a, b~l=Rkbl\widetilde{b}_l=R_kb_l and Gll′=bl†b~l′G_{ll'}=b_l^{\dagger}\widetilde{b}_{l'}.

  4. Diagonalise G=∑αλαeαeα†G=\sum_{\alpha}\lambda_{\alpha}e_{\alpha}e_{\alpha}^{\dagger}. Choose α\alpha with probability λα/Tr⁡G\lambda_{\alpha}/\operatorname{Tr}G. Draw ∣cα∣2∼Gamma⁡(2,1)|c_{\alpha}|^2\sim\operatorname{Gamma}(2,1) with uniform phase, and independent cα′∼CN(0,1)c_{\alpha'}\sim CN(0,1) for α′≠α\alpha'\ne\alpha. Set v=∑αcαeαv=\sum_{\alpha}c_{\alpha}e_{\alpha}.

  5. Update a=∑lvlbla=\sum_l v_lb_l and set xμk,l=v‾lx_{\mu_k,l}=\overline{v}_l.

  6. After the last site, set Φ=f†a\Phi=f^{\dagger}a and return

Z^=rψt! Φ‾∏i=1n(Ux)ri.\widehat{Z}=\frac{r_{\psi}}{\sqrt{t!}\,\overline{\Phi}}\prod_{i=1}^{n}(Ux)_{r_i}.

With Gaussian unused modes and unitary UU, EZ^=At\mathbb{E}\widehat{Z}=A_t and E∣Z^∣2=rψ\mathbb{E}|\widehat{Z}|^2=r_{\psi}.

Remark 1 (Sampling without diagonalisation). Step 4 can avoid the eigenproblem. Factor each environment once, Rk=CkCk†R_k = C_k C_k^\dagger with CkC_k a χ×κk\chi\times\kappa_k matrix and κk=rank⁡Rk≤χ\kappa_k = \operatorname{rank} R_k \le\chi (for instance by a pivoted Cholesky or an eigenvalue decomposition), which adds O(nχ3)O(n\chi^3) to the preprocessing. With (wβ)l=(Ck†bl)β(w_\beta)_l = (C_k^\dagger b_l)_\beta for β=1,…,κk\beta= 1,\ldots,\kappa_k, the quadratic form in (6) becomes v†Gv=∑β∣wβ†v∣2v^\dagger Gv = \sum_\beta|w_\beta^\dagger v|^2, so the conditional density is a mixture of at most κk\kappa_k densities γ(v)∣uβ†v∣2\gamma(v)|u_\beta^\dagger v|^2, with uβ=wβ‾/∥wβ∥u_\beta= \overline{w_\beta}/\|w_\beta\| and weights ∥wβ∥2/Tr⁡G\|w_\beta\|^2/\operatorname{Tr} G (terms with wβ=0w_\beta= 0 drop out). Each of them is drawn as in step 4 with uβu_\beta in place of the eigenvector: choose β\beta, draw v′v' from γ\gamma and cc with ∣c∣2∼Gamma⁡(2,1)|c|^2 \sim\operatorname{Gamma}(2,1) and uniform phase, and set v=v′+(c−uβ†v′)uβv = v' + (c-u_\beta^\dagger v')u_\beta. A site then costs O(Lχ2)O(L\chi^2), the nL3nL^3 term disappears from Theorem 1(iii), and no eigenproblem is solved during a draw; the only factorisations are those of the RkR_k, done once per state. In our tests (Supplementary Material, Sec. S7) the two samplers agree on all tested one- and two-site moments of qq and give unbiased estimates. For L=2L=2 they run at comparable speed when χ≥16\chi\ge16; the factorised sampler is faster for small χ\chi 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 χ\chi 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 {∣e⟩}\{|e\rangle\} be an orthonormal basis of Cχ\mathbb{C}^{\chi}, and let ψe\psi_e be the state (1) with ⟨f∣=⟨e∣\langle f| = \langle e|, of squared norm re=∥ψe∥2=⟨e∣ρmem∣e⟩r_e = \|\psi_e\|^2 = \langle e|\rho_{\mathrm{mem}}|e\rangle, so that ∑ere=Tr⁡ρmem\sum_e r_e = \operatorname{Tr}\rho_{\mathrm{mem}}. Draw ee with probability re/Tr⁡ρmemr_e/\operatorname{Tr}\rho_{\mathrm{mem}}, then two independent draws Z^1,Z^2\widehat{Z}_1,\widehat{Z}_2 of the estimator of Theorem 1 for ψe\psi_e, and set

P^=Tr⁡ρmemreZ^1Z^2.\widehat{P} = \frac{\operatorname{Tr}\rho_{\mathrm{mem}}}{r_e}\widehat{Z}_1\widehat{Z}_2.

Then EP^=p(t)=∑e∣At,e∣2\mathbb{E}\widehat{P} = p(\mathbf{t}) = \sum_e |A_{\mathbf{t},e}|^2 and, with Gaussian unused modes and unitary UU, E∣P^∣2=(Tr⁡ρmem)2\mathbb{E}|\widehat{P}|^2 = (\operatorname{Tr}\rho_{\mathrm{mem}})^2, equal to 11 for a normalised sequence. Hence p(t)p(\mathbf{t}) is estimated to ±ε\pm\varepsilon with O((Tr⁡ρmem)2/ε2)O((\operatorname{Tr}\rho_{\mathrm{mem}})^2/\varepsilon^2) draws, each costing O(nLχ2+nL3+mn)O(nL\chi^2+nL^3+mn) after at most O(nLχ4)O(nL\chi^4) preprocessing (one set of right environments for each basis state that is drawn).

Proof. Basis states with re=0r_e=0 are never drawn and contribute nothing to p(t)p(\mathbf{t}), since then ψe=0\psi_e=0. Given ee, the draws Z^1,Z^2\widehat{Z}_1,\widehat{Z}_2 are independent, so E[Z^1Z^2∣e]=∣At,e∣2\mathbb{E}[\widehat{Z}_1\widehat{Z}_2\mid e] = |A_{\mathbf{t},e}|^2 and E[∣Z^1Z^2∣2∣e]=re2\mathbb{E}[|\widehat{Z}_1\widehat{Z}_2|^2\mid e] = r_e^2 by Theorem 1(i)–(ii). Averaging over ee,

EP^=∑ereTr⁡ρmemTr⁡ρmemre∣At,e∣2=p(t),E∣P^∣2=∑ereTr⁡ρmem(Tr⁡ρmem)2re2re2=(Tr⁡ρmem)2.\mathbb{E}\widehat{P} = \sum_e \frac{r_e}{\operatorname{Tr}\rho_{\mathrm{mem}}}\frac{\operatorname{Tr}\rho_{\mathrm{mem}}}{r_e}|A_{\mathbf{t},e}|^2 = p(\mathbf{t}), \qquad\mathbb{E}|\widehat{P}|^2 = \sum_e \frac{r_e}{\operatorname{Tr}\rho_{\mathrm{mem}}}\frac{(\operatorname{Tr}\rho_{\mathrm{mem}})^2}{r_e^2}r_e^2 = (\operatorname{Tr}\rho_{\mathrm{mem}})^2.

The weights rer_e are the diagonal of ρmem\rho_{\mathrm{mem}}, obtained by one forward contraction ρk=∑lMl(k)ρk−1Ml(k)†\rho_k = \sum_l M_l^{(k)}\rho_{k-1}M_l^{(k)\dagger} from ρ0=s0s0†\rho_0 = s_0s_0^\dagger, in O(nLχ3)O(nL\chi^3). The environments of Theorem 1 with f=ef=e cost O(nLχ3)O(nL\chi^3) for each ee and can be built when ee is first drawn; each draw then runs the sampler of Theorem 1 twice with stored environments. Keeping all χ\chi sets requires O(nχ3)O(n\chi^3) memory. □\square

A Gaussian final vector gives an alternative that needs no basis. If z∈Cχz \in\mathbb{C}^{\chi} is standard complex Gaussian and ψz\psi_z is the state with ⟨f∣=⟨z∣\langle f| = \langle z|, then ∫γ(z)∣z⟩⟨z∣ dz=1\int\gamma(z)|z\rangle\langle z|\,\mathrm{d}z = 1 gives p(t)=Ez∣At,z∣2p(\mathbf{t}) = \mathbb{E}_z|A_{\mathbf{t},z}|^2, and W=Z^1Z^2W = \widehat{Z}_1\widehat{Z}_2, with two independent draws for the same zz, is unbiased. Its second moment is Ez∥ψz∥4=(Tr⁡ρmem)2+Tr⁡ρmem2≤2(Tr⁡ρmem)2\mathbb{E}_z\|\psi_z\|^4 = (\operatorname{Tr}\rho_{\mathrm{mem}})^2 + \operatorname{Tr}\rho_{\mathrm{mem}}^2 \le2(\operatorname{Tr}\rho_{\mathrm{mem}})^2, by Wick’s theorem applied to ∥ψz∥2=⟨z∣ρmem∣z⟩\|\psi_z\|^2 = \langle z|\rho_{\mathrm{mem}}|z\rangle, and the environments must be rebuilt for every zz, at O(nLχ3)O(nL\chi^3) 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.

inputregisternnχ\chit!t!γ\gamma ∣z∣|z|Gaussian, variant A ∣z∣|z|Gaussian, variant A M2/exactM_{2}/\mathrm{exact}Gaussian, variant B ∣z∣|z|Gaussian, variant B M2/exactM_{2}/\mathrm{exact}Rademacher ∣z∣|z|Rademacher M2M_{2}
random MPSproj.4210.111.410.358 / 0.3591.000.354 / 0.3590.080.210
random MPSproj.5310.480.7420.54 / 20.271.7120.09 / 20.272.439.84
random MPS, bunchedproj.5241.191.4111.71 / 11.401.5811.86 / 11.400.645.22
random MPSproj.6410.530.7538.89 / 38.650.7634.75 / 38.650.3713.51
GHZproj.5211.101.470.515 / 0.5002.410.513 / 0.5000.610.115
GHZ, bunchedproj.4221.241.420.900 / 1.0000.821.127 / 1.0001.090.460
random MPS, m=3nm = 3nproj.4211.050.643.07 / 2.871.350.730 / 0.7671.091.43
random MPStraced421—1.24645 / 717————
GHZtraced421—0.811.69 / 1.50————

Table S1. Table S1: Independent validation (NumPy implementation of Algorithm 1, seed 1). z=∣estimate−exact∣/empirical standard errorz = |\mathrm{estimate} - \mathrm{exact}|/\mathrm{empirical\ standard\ error}; M2M_{2} = empirical second moment of ZZ (Gaussian: exact value ∥ψ∥2t!\|\psi\|^{2}t!; variant B: exact value ∥ψ∥2Per⁡((USU†)[r,r])\|\psi\|^{2}\operatorname{Per}((USU^{\dagger})[r,r]), equal to the former when m=nLm = nL); the “γ\gamma” column is the plain identity (4) sampled under γ\gamma. Traced rows (Gaussian final vector, Sec. 6.1): M2M_{2} of WW against Ez∥ψz∥2\mathbb{E}_{z}\|\psi_{z}\|^{2} (the random MPS is not normalised). Haar-random UU, m=2nm = 2n unless stated, N=4⋅104N = 4 \cdot10^{4} (2⋅1042 \cdot10^{4} for χ=4\chi= 4; 3⋅1033 \cdot10^{3} 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 UxU x, and Gaussian orthogonality performs the output sum for us.

Let ∣ϕ⟩|\phi\rangle be a second photonic MPS, of bond dimension χϕ\chi_\phi, over any grouping of the modes into sites (not necessarily that of ψ\psi; in this subsection μk,l\mu_{k,l} denotes the sites of ϕ\phi). Then ⟨ϕ∣U∣ψ⟩=∑tϕ(t)‾⟨t∣U∣ψ⟩\langle\phi|U|\psi\rangle= \sum_{\mathbf{t}}\overline{\phi(\mathbf{t})}\langle\mathbf{t}|U|\psi\rangle with ϕ(t)=⟨t∣ϕ⟩\phi(\mathbf{t}) = \langle\mathbf{t}|\phi\rangle. Define, for y∈Cmy \in\mathbb{C}^m and with r(t)r(\mathbf{t}) the rows of t\mathbf{t},

Hϕ(y)=∑tϕ(t)‾t!∏iyri(t)=⟨Y∣ϕ⟩with∣Y⟩=⨂k∑lyμk,l∣l⟩.H_\phi(y) = \sum_{\mathbf{t}} \frac{\overline{\phi(\mathbf{t})}}{\sqrt{\mathbf{t}!}}\prod_i y_{r_i(\mathbf{t})} = \langle Y|\phi\rangle\quad\text{with} \quad|Y\rangle= \bigotimes_k \sum_l y_{\mu_{k,l}}|l\rangle.

For ϕ\phi of the form (1) every t\mathbf{t} in its support is collision-free, so t!=1\mathbf{t}! = 1, and Hϕ(y)=∑xϕ(x)‾∏kyμk,xkH_\phi(y) = \sum_{\mathbf{x}}\overline{\phi(\mathbf{x})}\prod_k y_{\mu_{k,x_k}} is the contraction of the complex-conjugated tensors of ϕ\phi (i.e. Ml(k)‾,s0‾,f‾\overline{M_l^{(k)}}, \overline{s_0}, \overline{f}) with the product vector built from yy, O(nLχϕ2)O(nL\chi_\phi^2). Write Φψ\Phi_\psi and qψq_\psi for the Φ\Phi and qq of ψ\psi. Then ⟨ϕ∣U∣ψ⟩=Eγ[Φψ(x)Hϕ(Ux)]\langle\phi|U|\psi\rangle= \mathbb{E}_\gamma[\Phi_\psi(x)H_\phi(Ux)] by Proposition 1 summed over t\mathbf{t}, and sampling x∼qψx \sim q_\psi and averaging ∥ψ∥2Hϕ(Ux)/Φψ(x)\|\psi\|^2H_\phi(Ux)/\Phi_\psi(x) gives an unbiased estimate with second moment ∥ψ∥2Eγ∣Hϕ(Ux)∣2=∥ψ∥2∥ϕ∥2\|\psi\|^2\mathbb{E}_\gamma|H_\phi(Ux)|^2 = \|\psi\|^2\|\phi\|^2, by unitary invariance of γ\gamma and part (i) of Theorem 1 applied to ϕ\phi. The overlap is therefore estimated to ±ε\pm\varepsilon with O(∥ψ∥2∥ϕ∥2/ε2)O(\|\psi\|^2\|\phi\|^2/\varepsilon^2) draws, each costing O(nLχ2+nLχϕ2+nL3+m2)O(nL\chi^2+nL\chi_\phi^2+nL^3+m^2); the last term computes all of UxUx, which HϕH_\phi may need.

This covers kernel entries. For two photonic MPSs ψ1,ψ2\psi_1,\psi_2 and two interferometers U,U′U,U', the matrix U†U′U^\dagger U' is again unitary, so ⟨ψ1∣U†U′∣ψ2⟩\langle\psi_1|U^\dagger U'|\psi_2\rangle is an overlap of the above form, and the kernel entry ∣⟨ψ1∣U†U′∣ψ2⟩∣2|\langle\psi_1|U^\dagger U'|\psi_2\rangle|^2 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 n^j\hat{n}_j be the number operator of output mode jj and Ω=∑jωjn^j\Omega= \sum_j \omega_j\hat{n}_j a linear statistic [15]. For θ∈R\theta\in\mathbb{R}, eiθΩe^{i\theta\Omega} is the Fock-space action of the single-particle matrix Dθ=diag⁡(eiθωj)D_\theta= \operatorname{diag}(e^{i\theta\omega_j}), so Vθ=U†DθUV_\theta= U^\dagger D_\theta U is again an m×mm \times m unitary and

CΩ(θ)=⟨ψ∣U†eiθΩU∣ψ⟩=⟨ψ∣Vθ∣ψ⟩C_\Omega(\theta) = \langle\psi|U^\dagger e^{i\theta\Omega}U|\psi\rangle= \langle\psi|V_\theta|\psi\rangle

is an overlap of the form of § 7.2 with ϕ=ψ\phi= \psi. It is estimated to ±ε\pm\varepsilon with O(∥ψ∥4/ε2)O(\|\psi\|^4/\varepsilon^2) draws, each costing O(nLχ2+nL3+m2)O(nL\chi^2+nL^3+m^2). For a normalised input, characteristic functions determine probabilities; for an unnormalised one, they determine weights.

Marginals on a few modes. For a set SS of ss output modes, the joint occupation tS∈{0,…,n}s\mathbf{t}_S \in\{0,\ldots,n\}^s has characteristic function CS(θ)=⟨ψ∣U†eiθ⋅n^SU∣ψ⟩C_S(\theta) = \langle\psi|U^\dagger e^{i\theta\cdot\hat{n}_S}U|\psi\rangle, with θ⋅n^S=∑j∈Sθjn^j\theta\cdot\hat{n}_S = \sum_{j\in S}\theta_j\hat{n}_j. Since each occupation lies between 0 and nn, it is enough to know CSC_S on the grid θ∈(2πn+1Zn+1)s\theta\in\left(\frac{2\pi}{n+1}\mathbb{Z}_{n+1}\right)^s, and the marginal is the inverse discrete Fourier transform

p(tS)=(n+1)−s∑θe−iθ⋅tSCS(θ)=Eθ[e−iθ⋅tSCS(θ)],p(\mathbf{t}_S) = (n+1)^{-s}\sum_\theta e^{-i\theta\cdot\mathbf{t}_S}C_S(\theta) = \mathbb{E}_\theta\left[e^{-i\theta\cdot\mathbf{t}_S}C_S(\theta)\right],

with θ\theta 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 (n+1)s(n+1)^s points but never needs to be enumerated. One draws a single grid point θ\theta uniformly and one overlap estimate WθW_\theta of CS(θ)C_S(\theta); then e−iθ⋅tSWθe^{-i\theta\cdot t_S}W_\theta is unbiased for p(tS)p(t_S), with second moment at most ∥ψ∥4\lVert\psi\rVert^4. Hence p(tS)p(t_S) is estimated to ±ε\pm\varepsilon with O(∥ψ∥4/ε2)O(\lVert\psi\rVert^4/\varepsilon^2) draws, whatever the number ss of modes.

Linear statistics. The same trick gives Pr⁡[Ω=ω]\Pr[\Omega=\omega] when the weights ωj\omega_j are integers. After shifting the statistic by nmin⁡jωjn\min_j\omega_j, its values lie in {0,…,n(max⁡jωj−min⁡jωj)}\{0,\ldots,n(\max_j\omega_j-\min_j\omega_j)\}, so a one-dimensional Fourier grid of size Q>n(max⁡jωj−min⁡jωj)Q>n(\max_j\omega_j-\min_j\omega_j) 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 ss the probabilities themselves are typically far below ε\varepsilon.

Accuracy and statistical interpretation

Additive error and shot noise

How do these guarantees compare with what an experiment delivers? With NN shots, the device estimates p(t)p(t) with standard deviation p(1−p)/N\sqrt{p(1-p)/N}. With NN draws, two independent amplitude averages give a probability estimate with root-mean-square error at most ∥ψ∥2/N\lVert\psi\rVert^2/\sqrt{N}, and for a normalised sequence with the memory traced out, Corollary 1 gives at most 1/N1/\sqrt{N} from a single average, each draw using two runs of the sampler. Both errors decrease as N−1/2N^{-1/2}, and for probabilities of order one they agree up to a constant factor.

They differ for rare outcomes. The shot noise is proportional to p\sqrt{p} 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 UU. Whatever the input state, the mean probability of a fixed output pattern is 1/(11940)≃1.3⋅10−321/\binom{119}{40}\simeq1.3\cdot10^{-32}, since the Haar average spreads the probability uniformly over the (11940)\binom{119}{40} patterns. With N=105N=10^5, the shot noise is then about 4⋅10−194\cdot10^{-19} and the classical error about 3⋅10−33\cdot10^{-3}. 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 Z^\hat{Z}, 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 Z^\hat{Z} is in general infinite, so the sample variance itself has infinite variance. The cause is the division by Φˉ\bar{\Phi}. Near a simple zero of Φ\Phi at which gt\mathfrak{g}_t does not vanish, the sampling density ∝∣Φ∣2\propto|\Phi|^2 vanishes quadratically while ∣Z^∣4|\hat{Z}|^4 grows as ∣Φ∣−4|\Phi|^{-4}; the integrand of Eq∣Z^∣4\mathbb{E}_q|\hat{Z}|^4 therefore behaves as ∣Φ∣−2|\Phi|^{-2}, whose integral diverges logarithmically in the two real directions transverse to the zero set.

Second, the distribution of ∣Z^∣2|\hat{Z}|^2 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 χ=2\chi=2, 10510^5 draws gave an empirical second moment of 2⋅10−52\cdot10^{-5} at n=40n=40, against the exact value ∥ψ∥2=1/2\lVert\psi\rVert^2=1/2 (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, ∣A^−At∣≤∥ψ∥2/(Nδ)|\hat{A}-A_t|\le\sqrt{\lVert\psi\rVert^2/(N\delta)} with probability at least 1−δ1-\delta. When high confidence is needed, a median-of-means estimator, applied to real and imaginary parts separately, reaches error ε\varepsilon with probability 1−δ1-\delta using O(∥ψ∥2ε−2log⁡(1/δ))O(\lVert\psi\rVert^2\varepsilon^{-2}\log(1/\delta)) 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 kk qubits, held in emitters or in photons stored in a delay line, the bond dimension in emission order is at most 2k2^k (§ 4.3). The cost of our estimator is polynomial in nn, mm, LL, χ\chi and 1/ε1/\varepsilon, so substituting χ≤2k\chi\le2^k gives a runtime poly⁡(n,m,L,1/ε)2O(k)\operatorname{poly}(n,m,L,1/\varepsilon)2^{O(k)}. With mm, LL and 1/ε1/\varepsilon polynomial in nn, this is polynomial when k=O(log⁡n)k = O(\log n) and subexponential when k=o(n)k = o(n). 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, 2k2^k 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 kk is excluded in general unless BPP=BQP\mathrm{BPP} = \mathrm{BQP}. 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 χ=2\chi= 2–44, 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 nn up to 40 and χ\chi up to 32 (Supplementary Material, § 21).

Cost. Table 2 gives the cost per draw on one GPU. With Gaussian sampling it ranges from 4 μs4\,\mu\mathrm{s} (n=10n = 10, χ=2\chi= 2) to 58 μs58\,\mu\mathrm{s} (n=60n = 60, χ=256\chi= 256): 10510^5 draws, enough for an additive error of about 3⋅10−33 \cdot10^{-3} on a normalised amplitude, take a few seconds even for a 60-photon input produced by eight two-level emitters. The dependence on χ\chi is much milder than the χ2\chi^2 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 χ≤16\chi\le16, 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 ∥ψ∥2\|\psi\|^2 (Sec. S4). Its lower cost per draw is therefore not a lower cost at fixed accuracy.

nnχ=2\chi= 2χ=16\chi= 16χ=256\chi= 256
104.0 / 0.175.9 / 0.139.8 / 4.4
206.3 / 0.3410.7 / 0.2519.3 / 8.8
309.2 / 0.5116.1 / 0.3828.9 / 13.2
4012.0 / 0.6721.2 / 0.5038.5 / 17.7
5017.4 / 0.8429.2 / 0.6248.0 / 22.0
6017.7 / 0.9932.2 / 0.7557.9 / 26.3

Table 2. Cost per draw on one NVIDIA H100 PCIe, amortised over 10510^5 draws (median of three runs), m=2nm = 2n, Haar-random UU, complex128. Gaussian / Rademacher sampling, in μ\mus. χ=2\chi= 2: projected linear cluster; χ=16,256\chi= 16, 256: 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 χ\chi. 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 χ\chi 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, poly⁡(n) 2O(k)\operatorname{poly}(n)\,2^{O(k)} for kk two-level emitters. A conditional lower bound shows that this growth with kk cannot be removed in general. When the emitters interact, their memory can run an arbitrary kk-qubit circuit CC between emissions, and a projected weight such as ⟨f∣M1(1)C∣o⟩2\langle f|M_1^{(1)} C|o\rangle^2 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 kk for all such sources unless BPP = BQP. The true worst-case cost is therefore superpolynomial in kk and, by our algorithm, at most exponential; this is why the threshold k=O(log⁡n)k = O(\log n) 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 O(log⁡n)O(\log n) 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 NeN_{\mathrm{e}} emissions, each with label xk∈{0,1,…,L}x_k \in\{0,1,\ldots,L\}, where xk=0x_k=0 is the vacuum (operator M0(k)M_0^{(k)}, no photon) and xk=l≥1x_k=l\ge1 puts one photon in mode μk,l\mu_{k,l}, so that ∣ψ⟩=∑xψ(x)∣x⟩|\psi\rangle=\sum_x\psi(x)|x\rangle with ψ(x)=⟨f∣MxNe(Ne)⋯Mx1(1)∣s0⟩\psi(x)=\langle f|M_{x_{N_{\mathrm{e}}}}^{(N_{\mathrm{e}})}\cdots M_{x_1}^{(1)}|s_0\rangle spans several photon numbers. Let ∣x∣|x| be the number of nonzero labels of xx, and c(x)c(x) the list of the modes μk,xk\mu_{k,x_k} with xk≠0x_k\ne0. For an output tt with n≤Nen\le N_{\mathrm{e}} photons,

At=(t!)−1/2∑∣x∣=nψ(x)Per⁡(U[r,c(x)]),A_t=(t!)^{-1/2}\sum_{|x|=n}\psi(x)\operatorname{Per}(U[r,c(x)]),

the sum running over the words with nn photons, and

Φ(x)=⟨f∣∏k(M0(k)+∑l≥1xˉμk,lMl(k))∣s0⟩.\Phi(x)=\langle f|\prod_k\left(M_0^{(k)}+\sum_{l\ge1}\bar{x}_{\mu_{k,l}}M_l^{(k)}\right)|s_0\rangle.

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 ∥ψ∥2=∑x∣ψ(x)∣2\|\psi\|^2=\sum_x|\psi(x)|^2 summed over all photon numbers. The density qq can be sampled exactly, emission by emission, by a rejection step whose acceptance probability is exactly 1/21/2 at every emission; the expected cost per draw is O(NeLχ2+NeL3+mn)O(N_{\mathrm{e}}L\chi^2+N_{\mathrm{e}}L^3+mn) after O(NeLχ3)O(N_{\mathrm{e}}L\chi^3) preprocessing.

Proof. For independent standard complex Gaussians the moment E[xˉTxc]\mathbb{E}[\bar{x}^{T}x^{c}] 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-nn polynomial gtg_t therefore pairs only with the words of nn 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 Rk−1=∑l=0LMl(k)†RkMl(k)R_{k-1}=\sum_{l=0}^{L}M_l^{(k)\dagger}R_kM_l^{(k)} and, given ak−1a_{k-1}, bl=Ml(k)ak−1b_l=M_l^{(k)}a_{k-1} (l=0,…,Ll=0,\ldots,L). As in the proof of Theorem 1(iii), the conditional density of vkv_k is

γ(v)∥h+Bv∥2∥h∥2+Tr⁡Gk,∥h+Bv∥2=ak†Rkak,∥h∥2=b0†Rkb0,∥Bv∥2=v†Gkv,\gamma(v)\frac{\|h+Bv\|^2}{\|h\|^2+\operatorname{Tr}G_k}, \qquad \|h+Bv\|^2=a_k^\dagger R_ka_k,\quad \|h\|^2=b_0^\dagger R_kb_0,\quad \|Bv\|^2=v^\dagger G_kv,

with v=vk=(vl)l≥1v=v_k=(v_l)_{l\ge1}, ak=b0+∑l≥1vlbla_k=b_0+\sum_{l\ge1}v_lb_l, h=Rk1/2b0h=R_k^{1/2}b_0, the columns of BB equal to Rk1/2blR_k^{1/2}b_l, and GkG_k as in (6); the denominator follows from Eγv=0\mathbb{E}_\gamma v=0 and Eγvv†=1\mathbb{E}_\gamma v v^\dagger=\mathbb{1}.

A proposal that is easy to draw. This is no longer a homogeneous quadratic form, but ∥h+Bv∥2≤2(∥h∥2+∥Bv∥2)\|h+Bv\|^2\le2(\|h\|^2+\|Bv\|^2). Propose vv from π(v)=γ(v)(∥h∥2+v†Gkv)/(∥h∥2+Tr⁡Gk)\pi(v)=\gamma(v)(\|h\|^2+v^\dagger G_kv)/(\|h\|^2+\operatorname{Tr}G_k), a mixture of γ\gamma (weight ∥h∥2/(∥h∥2+Tr⁡Gk)\|h\|^2/(\|h\|^2+\operatorname{Tr}G_k)) and of the density (6) drawn as in Algorithm 1, and accept it with probability ∥h+Bv∥2/(2(∥h∥2+v†Gkv))≤1\|h+Bv\|^2/(2(\|h\|^2+v^\dagger G_kv))\le1.

Why rejection gives the right law. An accepted vv has density proportional to π(v)\pi(v) times this probability, that is to γ(v)∥h+Bv∥2\gamma(v)\|h+Bv\|^2, and the acceptance probability is ∫γ∥h+Bv∥2/(2(∥h∥2+Tr⁡Gk))=1/2\int\gamma\|h+Bv\|^2/(2(\|h\|^2+\operatorname{Tr}G_k))=1/2. The number of proposals per emission is geometric with mean 2, and each costs O(L2χ+L)O(L^2\chi+L) once the blb_l and RkblR_kb_l are formed. No square root of RkR_k is needed. □\square

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 nn-photon sector, so the bound is loose when the nn-photon sector carries little weight. An independent check (check_vacuum.py, § 21) confirms unbiasedness, the second moment and the acceptance probability 1/21/2.

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 A\mathcal{A} of size DD, on modes disjoint from other blocks. For α∈A\alpha\in\mathcal{A}, use the Gaussian monomial

hα(v)=∏jvjαjαj!.h_{\alpha}(v)=\prod_j \frac{v_j^{\alpha_j}}{\sqrt{\alpha_j!}}.

These monomials are orthonormal under the product complex Gaussian measure. With bα=Mαab_{\alpha}=M_{\alpha}a and wα=R1/2bαw_{\alpha}=R^{1/2}b_{\alpha}, the next conditional density is

γ(v)Z∥∑α∈Ahα(v)wα∥2,Z=∑α∥wα∥2.\frac{\gamma(v)}{Z}\left\|\sum_{\alpha\in\mathcal{A}}h_{\alpha}(v)w_{\alpha}\right\|^2,\qquad Z=\sum_{\alpha}\|w_{\alpha}\|^2.

There is no need to solve a general polynomial sampling problem. Propose from

π(v)=γ(v)Z∑α∣hα(v)∣2∥wα∥2.\pi(v)=\frac{\gamma(v)}{Z}\sum_{\alpha}|h_{\alpha}(v)|^2\|w_{\alpha}\|^2.

Choose α\alpha with weight ∥wα∥2/Z\|w_{\alpha}\|^2/Z; independently for each mode draw a uniform phase and squared radius Gamma(αj+1,1)(\alpha_j+1,1). This is exactly the selected mixture component. By Cauchy–Schwarz,

∥∑αhα(v)wα∥2≤D∑α∣hα(v)∣2∥wα∥2.\left\|\sum_{\alpha}h_{\alpha}(v)w_{\alpha}\right\|^2\le D\sum_{\alpha}|h_{\alpha}(v)|^2\|w_{\alpha}\|^2.

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 DD. Acceptance therefore has probability 1/D1/D, and the mean number of proposals is DD. All norms and inner products can be evaluated with RR, without forming its square root.

The corresponding input polynomial is Φ(x)=∑sψsxˉss!\Phi(x)=\sum_s\psi_s\frac{\bar{x}^s}{\sqrt{s!}}. Gaussian pairing gives Eγ[Φgt]=t!At\mathbb{E}_{\gamma}[\Phi g_t]=\sqrt{t!}A_t, and its importance estimator has second moment ∥ψ∥2\|\psi\|^2 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 LL.

Unused modes and known loss

Remark S1 (Unused modes). Only the unitarity of UU enters part (ii), through Eγ∣gt∣2=Per⁡((UU†)[r,r])\mathbb{E}_{\gamma}|g_t|^2=\operatorname{Per}((UU^\dagger)[r,r]), which is Wick’s theorem for the Gaussian vector y=Uxy=Ux of covariance UU†UU^\dagger.

(A) With xx standard Gaussian on all mm modes (Algorithm 1 as written) and UU unitary, this is t!t!.

(B) If instead xx is set to zero on the m−Lnm-Ln modes the state does not use (SS the set of modes used by the state, Sˉ\bar{S} its complement, USU_S and USˉU_{\bar{S}} the corresponding columns of UU), the identity still holds (those monomials of gtg_t had zero expectation against Φ\Phi), the sampling measure is different, gtg_t costs O(Ln2)O(Ln^2) instead of O(mn)O(mn), and the second moment becomes ∥ψ∥2Per⁡((USUS†)[r,r])≤∥ψ∥2t!\|\psi\|^2\operatorname{Per}((U_SU_S^\dagger)[r,r])\leq\|\psi\|^2t!, by superadditivity of the permanent on positive-semidefinite matrices (Marcus–Newman [50]), or the Cauchy–Binet expansion of Per⁡(KK†)\operatorname{Per}(K K^\dagger), for any matrix KK, as a sum of non-negative terms) since USUS†+USˉUSˉ†=1U_SU_S^\dagger+U_{\bar{S}}U_{\bar{S}}^\dagger=1 and Per⁡(1[r,r])=t!\operatorname{Per}(1[r,r])=t!. At m=Lnm=Ln the two variants coincide; when m≫Lnm\gg Ln, variant B reduces the second moment without increasing the evaluation cost (Table S1, last projected row: 0.770.77 against 2.872.87 at m=3nm=3n).

Known loss

Uniform or mode-dependent transmission that is known in advance is folded into the interferometer, which becomes a sub-unitary matrix UU (UU†⪯1UU^\dagger\preceq1), and we estimate the joint weight for a specified nn-photon output and no lost photons, for a fixed nn-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 m×mm \times m matrix UU, 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 UxUx, of covariance UU†UU^\dagger, Eq∣gt∣2=Per⁡((UU†)[r,r])\mathbb{E}_{q}|g_t|^2 = \operatorname{Per}\left((UU^\dagger)[r,r]\right). The matrices (UU†)[r,r](UU^\dagger)[r,r] and (1−UU†)[r,r](1-UU^\dagger)[r,r] are positive semidefinite, and the permanent is superadditive on such matrices (Remark S1), so Per⁡((UU†)[r,r])≤Per⁡(1[r,r])=t!\operatorname{Per}\left((UU^\dagger)[r,r]\right) \le\operatorname{Per}(1[r,r]) = t! and Eq∣Z∣2≤∥ψ∥2t!\mathbb{E}_{q}|Z|^2 \le\|\psi\|^2 t!. Unresolved loss, with a trace over the lost photons and several photon-number sectors, is not covered.

Rademacher variant

Let μ\mu be the uniform measure on {±1}m\{\pm1\}^m, with fixed photon number and distinct occupied input modes as in the main model. Orthogonality of the sign monomials gives Eμ∣Φ∣2=∥ψ∥2\mathbb{E}_{\mu}|\Phi|^2 = \|\psi\|^2. Thus qR(x)=μ(x)∣Φ(x)∣2/∥ψ∥2q_R(x) = \mu(x)|\Phi(x)|^2/\|\psi\|^2 is a probability mass function and Z=∥ψ∥2gt/Φ‾Z = \|\psi\|^2 g_t/\overline{\Phi} remains unbiased. Each conditional is proportional to v†Gkvv^\dagger G_kv on {±1}L\{\pm1\}^L. Enumerating these 2L2^L vectors avoids an eigenproblem and is useful for small fixed LL; it is not polynomial in unrestricted LL.

There is an important difference from Gaussian sampling. A nonzero polynomial can vanish on sign vectors with positive probability. Cancellation therefore gives

EqR∣Z∣2=∥ψ∥2Eμ[∣gt(x)∣21{Φ(x)≠0}]≤∥ψ∥2Eμ∣gt(x)∣2.\mathbb{E}_{q_R}|Z|^2 = \|\psi\|^2\mathbb{E}_{\mu}\left[|g_t(x)|^2\mathbf{1}_{\{\Phi(x)\ne0\}}\right] \le\|\psi\|^2\mathbb{E}_{\mu}|g_t(x)|^2.

The equality without the indicator holds if Φ\Phi 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 (∣10⟩+∣01⟩)/2(|10\rangle+|01\rangle)/\sqrt{2}, a Hadamard interferometer, and the output row (1,−1)/2(1,-1)/\sqrt{2}. Then Φ=(x1+x2)/2\Phi=(x_1+x_2)/\sqrt{2} and g=(x1−x2)/2g=(x_1-x_2)/\sqrt{2}. On the support of qRq_R, g=0g=0, so the second moment is zero although Eμ∣g∣2=1\mathbb{E}_{\mu}|g|^2=1.

Even the upper bound depends on the interferometer. For the unitary DFT4_4 with rows numbered 0,1,2,30,1,2,3, rows (1,3)(1,3) give Eμ∣g∣2=3/2\mathbb{E}_{\mu}|g|^2=3/2, while rows (0,1)(0,1) give 1/21/2. The former exceeds t!=1t!=1. A general pointwise bound is

∣gt(x)∣2≤(tmax⁡m/n)n,tmax⁡=max⁡jtj,|g_t(x)|^2 \le(t_{\max}m/n)^n,\qquad t_{\max}=\max_j t_j,

by arithmetic–geometric mean and ∥Ux∥2=m\|Ux\|^2=m. This supplies a uniform bound, not a claim that it is the best possible second-moment bound.

For Haar-random UU, fixed xx is sent to a uniform vector on the sphere of squared radius mm. For collision-free rows its coordinate moments give

EUEμ∣gt(x)∣2=mnm(m+1)⋯(m+n−1).(7)\mathbb{E}_{U}\mathbb{E}_{\mu}|g_t(x)|^2 = \frac{m^n}{m(m+1)\cdots(m+n-1)}. \tag*{(7)}

For a fixed input, the Haar-averaged second moment of ZZ is this expression times ∥ψ∥2μ{Φ≠0}\|\psi\|^2\mu\{\Phi\ne0\}. This follows because the Haar average is the same for every sign vector. For Z~\widetilde{Z}, divide all second moments by t!t!. 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

Z^=∥ψ∥2qt/(t! Φ‾)\widehat{Z}=\|\psi\|^2q_t/(\sqrt{t!}\,\overline{\Phi}) has a finite second moment but, in general, an infinite fourth moment: near a simple zero of Φ\Phi where gtg_t is nonzero, the density q∝∣Φ∣2q\propto|\Phi|^2 vanishes quadratically while ∣Z^∣4∝∣Φ∣−4|\widehat{Z}|^4\propto|\Phi|^{-4}, and ∫∣Φ∣−2\int|\Phi|^{-2} diverges logarithmically in two real dimensions. The simplest instance is n=1n=1, m=2m=2, ∣ψ⟩=∣1⟩|\psi\rangle=|1\rangle, UU the Hadamard matrix, t=(1,0)t=(1,0): Φ=x‾1\Phi=\overline{x}_1, Z^=(x1+x2)/(2x1)\widehat{Z}=(x_1+x_2)/(\sqrt{2}x_1), Eq∣Z^∣2=1\mathbb{E}_q|\hat{Z}|^2=1 and Eq∣Z^∣4=∞\mathbb{E}_q|\hat{Z}|^4=\infty. In the reported numerical examples, the bulk of ∣Z^∣2|\hat{Z}|^2 also lies far below its mean. Measured under qq on Haar-random UU, the mean of log⁡∣Z^∣2\log|\hat{Z}|^2 decreases linearly in nn with slope −0.58-0.58, while Eq∣Z^∣2\mathbb{E}_q|\hat{Z}|^2 stays fixed. A heuristic for the order of magnitude: under γ\gamma and for collision-free tt, ∣gt∣2|g_t|^2 is a product of nn i.i.d. Exp⁡(1)\operatorname{Exp}(1) variables, whose logarithm has mean −γEn-\gamma_{\mathrm{E}}n (γE=0.5772\gamma_{\mathrm{E}}=0.5772) although E∣gt∣2=1\mathbb{E}|g_t|^2=1; under qq the denominator ∣Φ∣2|\Phi|^2 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 N=105N=10^5 the empirical second moment of a χ=2\chi=2 projected cluster state fell from 0.080.08 at n=10n=10 to 2⋅10−52\cdot10^{-5} at n=40n=40 against the exact value ∥ψ∥2=12\|\psi\|^2=\frac{1}{2}. We therefore report the theorem-based bound — by Chebyshev, ∣A^−At∣≤∥ψ∥2/(Nδ)|\hat{A}-A_t|\le\sqrt{\|\psi\|^2/(N\delta)} with probability 1−δ1-\delta — and, for high-confidence estimates, a median-of-means estimator (real and imaginary parts separately) with O(∥ψ∥2ε−2log⁡(1/δ))O(\|\psi\|^2\varepsilon^{-2}\log(1/\delta)) draws for confidence 1−δ1-\delta.

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 UU, collision-free and bunched outputs, m=2nm=2n and one case with m=3nm=3n, exact values by brute-force enumeration of (2). It checks Proposition 1 under plain γ\gamma 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 DFT4_4 counterexample and (S1). Over the 30 mean estimates the largest ∣z∣|z| (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 N=2N=2–4⋅1044\cdot10^4), the variant-B moment at m=3nm=3n equals Per⁡((USU†)[r,r′])\operatorname{Per}((USU^\dagger)[r,r']) to 5%, and the traced empirical moments fluctuate around Ez∥ψz∥4\mathbb{E}_z\|\psi_z\|^4; 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, Ne=4N_e=4–55 emissions, χ=2\chi=2–33, n=1n=1–33 detected photons (one bunched output), m=2Nem=2N_e, 4⋅1044\cdot10^4 draws each. Both the plain-γ\gamma identity and the sampled estimator agree with brute-force enumeration (largest ∣z∣=1.55|z|=1.55), the empirical second moments are within 0.930.93–1.081.08 of ∥ψ∥2t!\|\psi\|^2t!, and the measured acceptance probability per emission is 0.5000.500–0.5010.501.

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 n=3n=3–$4withwithL=2,3 and χ=2\chi= 2–3, collision-free and bunched outputs, m=nLm = nL and m=3nm = 3n; traced linear-cluster and random emitters with χ=2\chi= 2–4, normalised or not, by both routes; an overlap between two random emitters; and the plain-γ\gamma identity. Every estimate is within 5σ5\sigma, every Gaussian second moment of an amplitude within 25% of its exact value at 3⋅1043 \cdot10^{4} draws, and every second moment of Corollary 1 within 30% of (Tr⁡ρmem)2(\operatorname{Tr}\rho_{\mathrm{mem}})^2 at 22–3⋅1043 \cdot10^{4} draws. scripts/validate.py prints the corresponding table (19 estimates on 9 cases, largest ∣z∣=2.8|z| = 2.8 at 2⋅1042 \cdot10^{4} draws, 2⋅1032 \cdot10^{3} 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 n=3n = 3–6, L=2L = 2–4 and χ=1\chi= 1–8, each with three outputs (collision-free at m=nLm = nL, collision-free at m=nL+2m = nL + 2, and one bunched pair at m=nL+2m = nL + 2), and eight independent runs per case of 4⋅1044 \cdot10^{4} draws (10410^{4} for the Gaussian final vector).

For the law of the sampled variables we use one- and two-site moments, Eq[v‾k,avk,b]\mathbb{E}_{q}[\overline{v}_{k,a}v_{k,b}] and Eq[∣vk,a∣2∣vk′,b∣2]\mathbb{E}_{q}[|v_{k,a}|^{2}|v_{k',b}|^{2}], whose exact values follow from the reduced density matrices of ψ\psi and whose sampling distributions have finite variance. In each batch a random linear combination of each kind gives one zz-score. Eight further states with n=15n = 15–40, LL up to 8 and χ\chi up to 32, whose exact moments are obtained by MPS contraction (six batches of 4⋅1044 \cdot10^{4} draws each), bring the total to 544 zz-scores per sampler, with Kolmogorov–Smirnov pp-values 0.16 (Algorithm 1) and 0.45 (Remark 1) against N(0,1)\mathcal{N}(0,1) and largest ∣z∣|z| of 3.1 and 3.0.

For unbiasedness we use N∣Y‾−exact∣2/Var⁡exactN|\overline{Y}-\mathrm{exact}|^{2}/\operatorname{Var}_{\mathrm{exact}}, whose expectation is 1, with the exact variances rψ−∣A1∣2r_{\psi}-|A_{1}|^{2}, (Tr⁡ρmem)2−p2(\operatorname{Tr}\rho_{\mathrm{mem}})^{2}-p^{2} and (Tr⁡ρmem)2+Tr⁡ρmem2−p2(\operatorname{Tr}\rho_{\mathrm{mem}})^{2}+\operatorname{Tr}\rho_{\mathrm{mem}}^{2}-p^{2}. Its mean over 672 runs is 1.02±0.041.02 \pm0.04 and 0.99±0.040.99 \pm0.04 for MPS amplitudes with the two samplers, 1.02±0.051.02 \pm0.05 and 1.05±0.041.05 \pm0.04 for Corollary 1 with the two samplers, and 1.00±0.041.00 \pm0.04 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 L=2L = 2 runs at 0.9–1.1 times the speed of Algorithm 1 for χ=16\chi= 16–128 at n=20n = 20 and for n=20n = 20–160 at χ=16\chi= 16 (1.4 at n=10n = 10), and is 1.3–2.5×\times faster for χ≤8\chi\leq8. At n=10n = 10, χ=8\chi= 8 it is faster by 2.6×\times, 6×\times and 19×\times at L=4L = 4, 16 and 64. At n=20n = 20, L=2L = 2, a draw of Corollary 1 is 1.2–1.4×\times faster than a Gaussian-final-vector draw for χ≤8\chi\leq8, and 2.3×\times and 4×\times faster at χ=16\chi= 16 and 64; with all χ\chi 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): 10510^{5} 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 χ=2\chi= 2, random isometric emitters for χ=16,256\chi= 16, 256; m=2nm = 2n, Haar-random UU, one random collision-free output; the O(nLχ3)O(nL\chi^{3}) right-environment preprocessing is included in the timed call. Peak device memory is <0.5< 0.5 GB for χ≤16\chi\leq16 and 3.1 GB for χ=256\chi= 256. The growth with nn is roughly linear although the O(mn)O(mn) term of gtg_{\mathrm{t}} 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 χ≤16\chi\leq16 (no eigenproblem, real signs) and about 2× at χ=256\chi= 256, where the χ2\chi^{2} 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 Cm\mathbb{C}^{m}; nothing depends on floating-point arithmetic. Table S2 lists the correspondence.

paperLean filemain declarations and content
Proposition 1, proofIdentity.leanPairs: ∫x‾Tx dμ=#{σ:T∘σ=c}\int\overline{x}^{T}x\,\mathrm{d}\mu= \#\{\sigma: T\circ\sigma=c\} for distinct modes TT; gaussian_identity: under it, ∑wψ(w)Per⁡(U[r,c(w)])=∫Φgt dμ\sum_w \psi(w)\operatorname{Per}(U[r,c(w)])=\int\Phi g_t\,\mathrm{d}\mu for every matrix UU, every state with at most one photon per mode and every rows rr (collisions included)
pairing of monomialsWords.leanpairings_eq: #{σ:c′∘σ=c}=∏ata!\#\{\sigma: c'\circ\sigma=c\}=\prod_a t_a! when the occupations agree, 00 otherwise; wick_of_moments: one-mode moments p! δpqp!\,\delta_{pq} give the Wick rule on the product measure
§4, GaussianComplexGaussian.leanstdGaussian: density π−1e−∣z∣2\pi^{-1}e^{-|z|^2}; stdGaussian_moment: ∫z‾pzq dγ=p! δpq\int\overline{z}^{p}z^{q}\,\mathrm{d}\gamma=p!\,\delta_{pq} (polar coordinates); complexGaussian_identity: Proposition 1
Proposition 1, RademacherRademacher.leanrademacher_pairs, rademacher_identity: the same identity with xx uniform on {±1}m\{\pm1\}^{m}
Theorem 1 (i)–(ii)Estimator.leannormalisation: ∫∣Φ∣2dγ=∣ψ∣2\int|\Phi|^2\mathrm{d}\gamma=|\psi|^2; qMeasure_isProbability: (i); estimator_mean: EqZ=t!AtE_qZ=\sqrt{t!}A_t; gOut_second_moment: Eγ∣gt∣2=t!E_\gamma|g_t|^2=t! for unitary UU; estimator_second_moment: Eq∣Z∣2=∣ψ∣2t!E_q|Z|^2=|\psi|^2t! when {Φ=0}\{\Phi=0\} is γ\gamma-null
Theorem 1 (ii), null setNullSet.leangaussian_Phi_null: γ{Φ=0}=0\gamma\{\Phi=0\}=0 for ψ≠0\psi\ne0 (Φ\Phi is affine in each x‾a\overline{x}_a, and a slice {xa:A+x‾aB=0}\{x_a:A+\overline{x}_aB=0\} with B≠0B\ne0 is a point); theorem2_gaussian_full: parts (i)–(ii) for ψ≠0\psi\ne0 and unitary UU, with no further hypothesis
Theorem 1 (iii), proofSampler.leanenv_posSemidef: the right environments RkR_k are positive semidefinite; integral_wt_step: ∫γ(v)(∑lvlbl)†R(∑lvlbl) dv=∑lbl†Rbl\int\gamma(v)\left(\sum_l v_l b_l\right)^\dagger R\left(\sum_l v_l b_l\right)\,\mathrm{d}v=\sum_l b_l^\dagger Rb_l; cond_eq_gram: the sitewise conditional is (6); integral_cond: it is a probability density; law_eq: drawing v0,…,vk−1v_0,\ldots,v_{k-1} in turn from these conditionals gives the prefix the density ak†Rkaks0†R0s0\frac{a_k^\dagger R_k a_k}{s_0^\dagger R_0s_0} with respect to γ\gamma
Theorem 1 (iii)SamplerLaw.leanPhi_output: Φ(x)=⟨f∣an⟩\Phi(x)=\langle f\mid a_n\rangle at the output xμk,l=v‾k,lx_{\mu_k,l}=\overline{v}_{k,l}; pw_zero_eq_normSq: s0†R0s0=∣ψ∣2s_0^\dagger R_0s_0=|\psi|^2; sampler_exact: with the unused modes drawn from γ\gamma, the output of the sequential draw has law qq
Algorithm 1, step 4Mixture.lean, Radial.leanmap_unitary_gaussianVector: γ\gamma on CL\mathbb{C}^{L} is invariant under unitaries; sitewise_draw: with Gk=Udiag⁡(λ)U†G_k=U\operatorname{diag}(\lambda)U^\dagger, drawing jj with probability λj/Tr⁡Gk\lambda_j/\operatorname{Tr}G_k and v=Ucv=Uc, with cjc_j of density γ(c)∣c∣2\gamma(c)|c|^2 and the other cic_i standard Gaussian (tilted_eq_pi), gives vv the density (6); radial_draw: seiθs e^{i\theta} with s∼Gamma⁡(2,1)s\sim\operatorname{Gamma}(2,1) and θ\theta uniform has density γ(c)∣c∣2\gamma(c)|c|^2
Proposition S1Vacuum.leanvacuum_identity: components of another photon number than the output add nothing to Eγ[Φgt]E_\gamma[\Phi g_t]; vacuum_normalisation: ∫∣Φ∣2dγ=∑x∣ψ(x)∣2\int|\Phi|^2\mathrm{d}\gamma=\sum_x|\psi(x)|^2 over all photon numbers; target_le: ∣h+Bv∣2≤2(∣h∣2+∣Bv∣2)|h+Bv|^2\le2(|h|^2+|Bv|^2); rejection_subdensity: proposal density times acceptance probability is γ∣h+Bv∣2/(2Z)\gamma|h+Bv|^2/(2Z); rejection_acceptance: acceptance probability 1/21/2

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 qq as a measure on Cm\mathbb{C}^{m}. Lean’s convention a/0=0a/0 = 0 sets Z=0Z = 0 on {Φ=0}\{\Phi= 0\}, which is null for both qq and γ\gamma.

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. [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. [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. [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. [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. [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. [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. [7]H.-S. Zhong et al. Quantum Computational Advantage Using Photons. Science, 370(6523):1460–1463, 2020. DOI: 10.1126/science.abe8770.DOI
  8. [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. [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. [10]T. Sedrakyan and A. Salavrakos. Photonic Quantum Generative Adversarial Networks for Classical Data. arXiv:2405.06023, 2024.DOI
  11. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [50]M. Marcus and M. Newman. Inequalities for the Permanent Function. Ann. Math., 75(1):47, 1962.DOI
  51. [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. [52]C. Oh and Y. Lim. Classical Algorithms for Measurement-Adaptive Gaussian Circuits. arXiv:2509.00746, 2025.arxiv.org/abs/2509.00746

Paper details

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

views · 1

downloads · 0

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

  • Physics and Astronomy

Claude, ChatGPT

View statement
Looking for related papers…
Contents