Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2611.11044

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

Jean Sénellart, Stephen Wein, Pierre-Emmanuel Emeriau

Published Nov 8, 2026• 1 citation
arXivHTMLPDF

Abstract

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

DOI
10.48550/arxiv.2611.11044

Related papers

On the estimation of linear-optical amplitudes and probabilities with entangled input state

Jean Sénellart, Pierre-Emmanuel Emeriau

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 $n$-photon input that is a matrix-product state of bond dimension $χ$, with one photon per site and $L$ modes per site, we give an unbiased estimator of any output amplitude of an $m$-mode interferometer, whose mean-square error after $N$ draws is at most $\|ψ\|^2/N$ whatever the interferometer, the output pattern and the entanglement of the state. Each draw costs $O(nLχ^2+nL^3+mn)$ operations after $O(nLχ^3)$ preprocessing, and an additive error $\varepsilon$ with probability at least $1-δ$ requires $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$ at any length, and a memory of $k$ qubits, held in emitters or in photons stored in a delay line, gives $χ\le2^k$, so the cost stays polynomial as long as $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.

arXiv:2611.10500•Nov 7, 2026•1 citation

The simulability frontiers of photonic quantum computing

Jean Sénellart, Benjamin Stott, Stephen Wein +4 more

Estimates of when photonic devices outgrow classical simulation are hard to compare: even for single-photon boson sampling, quoted thresholds range from 50 to 98 photons, as they rest on different tasks and assumptions. We propose as a common unit the time a classical computer needs to draw one sample from the device's exact output distribution, up to floating-point rounding. Only exactness applies equally to every kind of light, since the cost of approximate sampling depends on the accuracy required. The simulability frontier is the device size at which our fastest exact sampler produces one sample per second on a fixed machine; this device size increases with better hardware and algorithms. As the time per sample grows exponentially with the number of detected photons, doubling the machine speed moves the frontier by about one photon, whereas a better algorithm changes the growth rate. We measure the frontier with photonic-engines, an open-source GPU library of exact samplers for single photons, entangled photons from quantum emitters, vacuum-single-photon superpositions and squeezed light. Each sampler is validated against a simulator sharing no code with it. On one NVIDIA H100 GPU, with Haar-random interferometers, twice as many modes as photonic inputs and photon-number-resolving detectors, the frontier lies at 38.3 single photons and at 31.0 entangled photons from one emitter. For squeezed light, a timing model fitted to measurements places it at 41.5 squeezed photonic inputs of mean photon number 0.5. For our samplers, coherence alone makes simulation harder: sources that emit a photon with probability one half reach 64.2 when vacuum and photon are mixed incoherently, as for lossy single photons, but only 50.0 when they are in coherent superposition. Feed-forward from mid-circuit measurement of up to three modes lowers the single-photon frontier only from 38.3 to 38.1.

arXiv:2611.12876•Nov 9, 2026•1 citation

Boson sampling with displaced single-photon Fock states versus single-photon-added coherent states: The quantum-classical divide and computational-complexity transitions in linear optics

Kaushik P. Seshadreesan, Jonathan P. Olson, Keith R. Motes +2 more

Boson sampling is a specific quantum computation, which is likely hard to implement efficiently on a classical computer. The task is to sample the output photon-number distribution of a linear-optical interferometric network, which is fed with single-photon Fock-state inputs. A question that has been asked is if the sampling problems associated with any other input quantum states of light (other than the Fock states) to a linear-optical network and suitable output detection strategies are also of similar computational complexity as boson sampling. We consider the states that differ from the Fock states by a displacement operation, namely the displaced Fock states and the photon-added coherent states. It is easy to show that the sampling problem associated with displaced single-photon Fock states and a displaced photon-number detection scheme is in the same complexity class as boson sampling for all values of displacement. On the other hand, we show that the sampling problem associated with single-photon-added coherent states and the same displaced photon-number detection scheme demonstrates a computational-complexity transition. It transitions from being just as hard as boson sampling when the input coherent amplitudes are sufficiently small to a classically simulatable problem in the limit of large coherent amplitudes.

arXiv:1402.0531•Physical Review A•Feb 27, 2015•47 citations

Classical Algorithms for Estimating Expectation Values in Linear Optical Circuits

Anonymous, Changhun Oh

We present a classical algorithm for approximating the expectation values of observables in linear optical circuits with arbitrary product input states, achieving additive-error accuracy. This result indicates that current applications of photonic systems aimed at demonstrating practical quantum advantage through expectation value estimation, such as photonic variational algorithms, may face challenges in attaining the computational advantage. It also implies the output probabilities of boson sampling with arbitrary product input states can be efficiently approximated by our method, so that boson sampling becomes efficiently simulable when its output probability distribution is polynomially sparse. We also develop an efficient classical algorithm for estimating transition amplitudes of arbitrary product states in linear optical circuits. This provides additive-error approximation algorithms for matrix functions associated with linear optical circuits, such as the (loop-)Hafnian, which are of independent interest. As an application, it solves the generalized molecular vibronic spectra problem [C. Oh et al., Nat. Phys. 20, 225 (2024)10.1038/s41567-023-02308-9], previously suggested as a candidate for practical quantum advantage. Finally, we extend our framework to near-Clifford circuits, enabling classical approximation of their expectation values.

arXiv:2502.12882•Physical Review Letters•Aug 13, 2026•18 citations

Efficient classical algorithm for estimating linear statistics of Boson Sampling

Benoit Seron, Hugo Thomas, Eduardo Araujo +3 more

Boson Sampling is a prominent candidate for the demonstration of quantum computational advantage but it remains unclear whether a large-scale boson sampler can find useful computational applications. The challenge is that to use a boson sampler to estimate, for example, a physical observable, it is necessary to coarse grain the outcome distribution, owing to the exponential size of the outcome space and the anti-concentration properties of the Boson Sampling distribution. In this work, we analyse the complexity of a specific type of coarse-graining of Boson Sampling distributions based on linear functions of the output photon occupation numbers, which we refer to as linear statistics. We present an efficient classical algorithm for approximating linear statistics of boson samplers within additive error for different kinds of input states, such as Fock states and squeezed states. This allows us to unify in the same framework recent results on efficient quantum-inspired classical algorithms for simulating molecular vibronic spectra, or efficient classical approximations of coarse-grained distributions based on detector binning. Additionally, we show how our algorithm can be used to classically evaluate a proposed one-way function based on Boson Sampling, while other proposals for cryptographic applications escape our classical simulation techniques. We leave open the question of classical simulability of non-linear statistics and connect it to the problem of computing transition amplitudes of linear-optical circuits with one layer of interactions.

quant-pharXiv:2609.35447•Sep 29, 2026•3 citations

Decoy-state optical quantum information processing with coherent states

Wenyuan Wang, H. F. Chau

Photonic qubits play an important role in quantum information processing. However, to date, efficient high-speed single photon sources and photon number resolving (PNR) detectors are still difficult to make. Here, we use phase-randomized coherent states and threshold detectors, combined with decoy-state post-processing, to simulate single photon sources and PNR detectors and perform various quantum information processing tasks. We propose a simple linear regression method to predict Fock state statistics based on observable statistics from coherent-state probes, combined with random/structured sampling of probe settings. Compared with traditional decoy-state post-processing based on linear programming and Cartesian product grid sampling, our method enables drastically improved accuracy and much reduced probe resources. It works particularly well for unknown unitary circuits of interest with fixed-size Hilbert space dimensions. For instance, it can accurately simulate 4-photon interference in linear optics with just 32 input/output probe settings and 6-photon interference with 256 probe settings. Moreover, it also works for non-unitary (such as lossy, nonlinear, or arbitrary) quantum channels. This enables a wide variety of applications that can be implemented with easily attainable coherent light sources and threshold detectors, such as characterization of small-scale linear optical quantum computing circuits or quantum sensing/metrology devices.

quant-pharXiv:2610.04581•Oct 6, 2026•0 citations
Clifford and Clifford's algorithm samples single-photon boson sampling exactly, one output mode at a time, by adding the input photons in a uniformly random order. We extend this construction to other input states and to adaptive and non-linear circuits. It applies whenever non-negative weights on output prefixes and input sets satisfy one marginal identity, a set-chain lemma: the random-order sampler is then exact at one weight evaluation per candidate mode, and it gives the posterior over the hidden input set. We build four exact samplers on it. For sources in a superposition of vacuum and one photon, the weights are rectangular permanents on an offset input set, and the cost has the exponent of single photons under loss. For photonic matrix-product states of bond dimension χχχ, a gap-by-gap Kraus contraction turns each weight into a short sum of squared amplitudes. For adaptive linear optics, the chain starts from the posterior given the adaptive counts and rejects chains that contradict them. For a single-mode non-linear phase the identity fails, and rejection from linear branches is exact with acceptance 1/∥c∥121/\|c\|_1^21/∥c∥12​. All four samplers agree with strong simulation on small instances, and cost models put adaptive sampling with up to three adaptive modes within 10%10\%10% of single photons and a non-linear site at φ=π/2φ=π/2φ=π/2 at about 4×4\times4×.
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 nnn-photon input that is a matrix-product state of bond dimension χχχ, with one photon per site and LLL modes per site, we give an unbiased estimator of any output amplitude of an mmm-mode interferometer, whose mean-square error after NNN draws is at most ∥ψ∥2/N\|ψ\|^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)O(nLχ2+nL3+mn) operations after O(nLχ3)O(nLχ^3)O(nLχ3) preprocessing, and an additive error ε\varepsilonε with probability at least 1−δ1-δ1−δ requires O(∥ψ∥2ε−2log⁡(1/δ))O(\|ψ\|^2\varepsilon^{-2}\log(1/δ))O(∥ψ∥2ε−2log(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χ=2 at any length, and a memory of kkk qubits, held in emitters or in photons stored in a delay line, gives χ≤2kχ\le2^kχ≤2k, so the cost stays polynomial as long as k=O(log⁡n)k=O(\log n)k=O(logn). 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.
Estimates of when photonic devices outgrow classical simulation are hard to compare: even for single-photon boson sampling, quoted thresholds range from 50 to 98 photons, as they rest on different tasks and assumptions. We propose as a common unit the time a classical computer needs to draw one sample from the device's exact output distribution, up to floating-point rounding. Only exactness applies equally to every kind of light, since the cost of approximate sampling depends on the accuracy required. The simulability frontier is the device size at which our fastest exact sampler produces one sample per second on a fixed machine; this device size increases with better hardware and algorithms. As the time per sample grows exponentially with the number of detected photons, doubling the machine speed moves the frontier by about one photon, whereas a better algorithm changes the growth rate. We measure the frontier with photonic-engines, an open-source GPU library of exact samplers for single photons, entangled photons from quantum emitters, vacuum-single-photon superpositions and squeezed light. Each sampler is validated against a simulator sharing no code with it. On one NVIDIA H100 GPU, with Haar-random interferometers, twice as many modes as photonic inputs and photon-number-resolving detectors, the frontier lies at 38.3 single photons and at 31.0 entangled photons from one emitter. For squeezed light, a timing model fitted to measurements places it at 41.5 squeezed photonic inputs of mean photon number 0.5. For our samplers, coherence alone makes simulation harder: sources that emit a photon with probability one half reach 64.2 when vacuum and photon are mixed incoherently, as for lossy single photons, but only 50.0 when they are in coherent superposition. Feed-forward from mid-circuit measurement of up to three modes lowers the single-photon frontier only from 38.3 to 38.1.
Boson sampling is a specific quantum computation, which is likely hard to implement efficiently on a classical computer. The task is to sample the output photon-number distribution of a linear-optical interferometric network, which is fed with single-photon Fock-state inputs. A question that has been asked is if the sampling problems associated with any other input quantum states of light (other than the Fock states) to a linear-optical network and suitable output detection strategies are also of similar computational complexity as boson sampling. We consider the states that differ from the Fock states by a displacement operation, namely the displaced Fock states and the photon-added coherent states. It is easy to show that the sampling problem associated with displaced single-photon Fock states and a displaced photon-number detection scheme is in the same complexity class as boson sampling for all values of displacement. On the other hand, we show that the sampling problem associated with single-photon-added coherent states and the same displaced photon-number detection scheme demonstrates a computational-complexity transition. It transitions from being just as hard as boson sampling when the input coherent amplitudes are sufficiently small to a classically simulatable problem in the limit of large coherent amplitudes.
We present a classical algorithm for approximating the expectation values of observables in linear optical circuits with arbitrary product input states, achieving additive-error accuracy. This result indicates that current applications of photonic systems aimed at demonstrating practical quantum advantage through expectation value estimation, such as photonic variational algorithms, may face challenges in attaining the computational advantage. It also implies the output probabilities of boson sampling with arbitrary product input states can be efficiently approximated by our method, so that boson sampling becomes efficiently simulable when its output probability distribution is polynomially sparse. We also develop an efficient classical algorithm for estimating transition amplitudes of arbitrary product states in linear optical circuits. This provides additive-error approximation algorithms for matrix functions associated with linear optical circuits, such as the (loop-)Hafnian, which are of independent interest. As an application, it solves the generalized molecular vibronic spectra problem [C. Oh et al., Nat. Phys. 20, 225 (2024)10.1038/s41567-023-02308-9], previously suggested as a candidate for practical quantum advantage. Finally, we extend our framework to near-Clifford circuits, enabling classical approximation of their expectation values.
Boson Sampling is a prominent candidate for the demonstration of quantum computational advantage but it remains unclear whether a large-scale boson sampler can find useful computational applications. The challenge is that to use a boson sampler to estimate, for example, a physical observable, it is necessary to coarse grain the outcome distribution, owing to the exponential size of the outcome space and the anti-concentration properties of the Boson Sampling distribution. In this work, we analyse the complexity of a specific type of coarse-graining of Boson Sampling distributions based on linear functions of the output photon occupation numbers, which we refer to as linear statistics. We present an efficient classical algorithm for approximating linear statistics of boson samplers within additive error for different kinds of input states, such as Fock states and squeezed states. This allows us to unify in the same framework recent results on efficient quantum-inspired classical algorithms for simulating molecular vibronic spectra, or efficient classical approximations of coarse-grained distributions based on detector binning. Additionally, we show how our algorithm can be used to classically evaluate a proposed one-way function based on Boson Sampling, while other proposals for cryptographic applications escape our classical simulation techniques. We leave open the question of classical simulability of non-linear statistics and connect it to the problem of computing transition amplitudes of linear-optical circuits with one layer of interactions.
Photonic qubits play an important role in quantum information processing. However, to date, efficient high-speed single photon sources and photon number resolving (PNR) detectors are still difficult to make. Here, we use phase-randomized coherent states and threshold detectors, combined with decoy-state post-processing, to simulate single photon sources and PNR detectors and perform various quantum information processing tasks. We propose a simple linear regression method to predict Fock state statistics based on observable statistics from coherent-state probes, combined with random/structured sampling of probe settings. Compared with traditional decoy-state post-processing based on linear programming and Cartesian product grid sampling, our method enables drastically improved accuracy and much reduced probe resources. It works particularly well for unknown unitary circuits of interest with fixed-size Hilbert space dimensions. For instance, it can accurately simulate 4-photon interference in linear optics with just 32 input/output probe settings and 6-photon interference with 256 probe settings. Moreover, it also works for non-unitary (such as lossy, nonlinear, or arbitrary) quantum channels. This enables a wide variety of applications that can be implemented with easily attainable coherent light sources and threshold detectors, such as characterization of small-scale linear optical quantum computing circuits or quantum sensing/metrology devices.