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

Technical Summary: Exact Sampling Beyond Fock Inputs and Linear Optics

Problem Statement
Claims of quantum advantage in photonic systems rely on the computational gap between what a device samples and what a classical computer can sample exactly. Standard boson sampling, involving $n$ single photons in an $m$-mode linear interferometer, is classically hard because output probabilities correspond to matrix permanents, a #P-hard problem. However, real-world photonic devices deviate from this idealized model. Sources may emit coherent superpositions of vacuum and single photons (superposed sources) or entangled sequences (photonic matrix-product states). Furthermore, circuits may include mid-circuit measurements with feed-forward (adaptive optics) or non-linear elements (non-linear sites). Existing exact classical samplers, such as the Clifford and Clifford algorithm for single photons, do not directly apply to these generalized scenarios. The paper addresses the need for exact samplers for these non-standard inputs and circuit configurations to determine the limits of classical simulation.

Methodology: The Set-Chain Lemma
The core methodological contribution is the generalization of the "random-order" sampling technique used by Clifford and Clifford. The authors introduce a Set-Chain Lemma (Lemma 1), which provides a criterion for exact sampling based on "chain-consistent set weights."

• Mechanism: Instead of sampling output modes sequentially based on a fixed input order, the algorithm draws a uniformly random order of input slots (sources or emissions). It then samples output rows one by one.
• Condition: For the sampler to be exact, the weights $f_j(z; T)$ associated with a partial output sequence $z$ and an active set of input slots $T$ must satisfy a specific marginal identity (Condition C2). This identity ensures that summing over the next possible output row yields the correct weight for the previous step, effectively turning the Laplace expansion of permanents (or their generalizations) into a sum over smaller sets.
• Posterior Inference: A key feature of this construction is that it simultaneously provides the posterior distribution over the "hidden" input set (e.g., which sources actually emitted a photon or which emissions were traced out) without requiring explicit enumeration of all subsets.

Key Contributions: Four Exact Samplers
The authors construct four specific samplers based on the Set-Chain Lemma, addressing different deviations from the standard model:

1. Superposed Sources (Vacuum + One Photon):

   • Model: Sources emit $\cos \alpha |0\rangle + \sin \alpha |1\rangle$. The total photon number $k$ follows a binomial distribution.
   • Method: The sampler uses an "offset-start" order. Instead of starting with an empty set of inputs, the chain begins with $n-k$ sources (where $n$ is the total number of sources).
   • Weight: The weights are squared rectangular permanents, $|\text{Per}_{\square} A[z, T]|^2$.
   • Cost: The computational cost scales with the exponent of single photons under loss $\eta = \sin^2 \alpha$. The algorithm effectively treats the problem as single-photon sampling with a reduced effective number of photons.

2. Photonic Matrix-Product States (MPS):

   • Model: A quantum emitter with internal memory (dimension $\chi$) emits $n$ photons sequentially, creating an entangled MPS (e.g., linear cluster states).
   • Method: The authors introduce a "gap-by-gap Kraus contraction." Since the random order creates gaps of traced-out emissions between kept emissions, the mixed state of the kept photons is decomposed into a sum of squared amplitudes.
   • Weight: The weight is a sum of $R_j$ squared amplitudes, where each amplitude is evaluated using matrix-valued Glynn sums.
   • Cost: The cost is determined by the term count $R_j$. Empirical measurements on linear cluster states show $R_j$ remains small (peaking around $n/2.5$ and dropping to 1–2 on the final steps), keeping the overhead manageable for the tested instances ($n \le 20$).

3. Adaptive Linear Optics:

   • Model: Mid-circuit photon counting with feed-forward changes the unitary applied to subsequent modes.
   • Method: The sampler conditions the standard Fock (single-photon) chain on the observed adaptive counts. It starts by sampling the "prefix" (the adaptive outcomes) and then continues with the standard Clifford-Clifford steps.
   • Rejection: The constraint that no future photon lands on an already-measured adaptive mode is not chain-consistent. The sampler enforces this via rejection: if a chain places a photon on an adaptive mode after the prefix is fixed, the chain is aborted and redrawn.
   • Cost: The overhead is determined by the number of chains required to satisfy the prefix constraints. For a fixed number of adaptive modes ($K$), the cost remains within a constant factor (e.g., ~1.1x for $K=3$) of the standard sampler.

4. Non-Linear Sites:

   • Model: A single-mode non-linearity (e.g., Kerr phase) between linear interferometers.
   • Method: The natural weight for a non-linear circuit violates the chain-consistency condition because different linear branches couple hidden input sets. The authors apply a rejection principle to a mixture of linear branches.
   • Algorithm: A branch $b$ is selected with probability proportional to $|c_b|$, a standard Fock sample is drawn for that branch, and the sample is accepted with a probability derived from the Cauchy-Schwarz inequality.
   • Cost: The acceptance probability is exactly $1/\|c\|_1^2$. For a non-linearity with a short period (e.g., $\phi = \pi/2$), the number of branches $B$ is small, resulting in a constant overhead (approx. 4x). For generic responses, the cost scales polynomially with $n$.

Results and Validation

• Validation: All four samplers were validated against strong simulations (using SLOS and other exact methods) on small instances. The measured Total Variation Distance (TVD) between the sampler's output and the oracle was within statistical noise (approx. 1.7 standard deviations of an exact draw).
• Performance:
  • Superposed Sources: The cost follows the loss exponent. At $\sin^2 \alpha = 0.8$, the cost is roughly 4x that of a single-photon sampler of the same size.
  • Photonic MPS: On measured trains ($n \le 20$), the overhead is low because the term count $R_j$ is small on the final, most expensive steps.
  • Adaptive Optics: Sampling with up to three adaptive modes costs within 10% of the standard single-photon sampler.
  • Non-Linear Sites: A non-linear site at $\phi = \pi/2$ costs approximately 4x the standard sampler.

Significance and Claims
The paper claims that the "random-order" sampling paradigm is more robust than previously thought, extending beyond product Fock inputs to entangled and superposed states, provided the Set-Chain Lemma's marginal identity holds.

• Exponential Rates: The authors demonstrate that for superposed sources, adaptive optics (with fixed $K$), and short-period non-linearities, the exponential rate of exact classical simulation remains unchanged (or scales with the effective loss). These features do not, in isolation, push the problem into a regime where classical simulation becomes intractable relative to the single-photon case.
• Open Questions: The paper modestly notes that the growth of the term count $R_j$ for photonic MPS as $n$ increases remains an open question; if $R_j$ grows exponentially, the prefix-amplitude sampler (which has polynomial overhead) might eventually be superior. Similarly, no chain-consistent family is known for general non-linearities, and the rejection method becomes costly for generic responses.
• Implementation: The samplers are implemented in a unified GPU codebase (photonic-engines) and formalized in Lean 4, providing a verified toolset for benchmarking photonic quantum advantage.

In summary, the work provides a unified theoretical framework and practical algorithms for exactly simulating a broad class of photonic devices, clarifying which extensions to the standard boson sampling model remain classically tractable and which introduce significant overheads.