Boson sampling is a restricted model of non-universal quantum computation introduced by Scott Aaronson and Alex Arkhipov after the original work of Lidror Troyansky and Naftali Tishby, that explored possible use of boson scattering to evaluate expectation values of permanents of matrices. The model consists of sampling from the probability distribution of identical bosons scattered by a linear interferometer. Although the problem is well defined for any bosonic particles, its photonic version is currently considered as the most promising platform for a scalable implementation of a boson sampling device, which makes it a non-universal approach to linear optical quantum computing. Moreover, while not universal, the boson sampling scheme is strongly believed to implement computing tasks that are hard to implement with classical computers by using far fewer physical resources than a full linear-optical quantum computing setup ^{[citation needed]}. This advantage makes it an ideal candidate for demonstrating the power of quantum computation in the near term.

Consider a multimode linear-optical circuit of N modes that is injected with M indistinguishable single photons (N>M). Then, the photonic implementation of the boson sampling task consists of generating a sample from the probability distribution of single-photon measurements at the output of the circuit. Specifically, this requires reliable sources of single photons (currently the most widely used ones are parametric down-conversion crystals), as well as a linear interferometer. The latter can be fabricated, e.g., with fused-fiber beam splitters, through silica-on-silicon or laser-written integrated interferometers, or electrically and optically interfaced optical chips. Finally, the scheme also necessitates high efficiency single photon-counting detectors, such as those based on current-biased superconducting nanowires, which perform the measurements at the output of the circuit. Therefore, based on these three ingredients, the boson sampling setup does not require any ancillas, adaptive measurements or entangling operations, as does e.g. the universal optical scheme by Knill, Laflamme and Milburn (the KLM scheme). This makes it a non-universal model of quantum computation, and reduces the amount of physical resources needed for its practical realization.

Specifically, suppose the linear interferometer is described by an N×N unitary matrix ${\displaystyle U,}$ which performs a linear transformation of the creation (annihilation) operators ${\displaystyle a_{i}^{\dagger }}$ ${\displaystyle (a_{i}^{})}$ of the circuit's input modes:

Here i (j) labels the input (output) modes, and ${\displaystyle b_{j}^{\dagger }}$ ${\displaystyle (b_{j}^{})}$ denotes the creation (annihilation) operators of the output modes (i,j=1,..., N). An interferometer characterized by some unitary ${\displaystyle U}$ naturally induces a unitary evolution ${\displaystyle \varphi _{M}(U)}$ on ${\displaystyle M}$-photon states. Moreover, the map ${\displaystyle \varphi _{M}}$ is a homomorphism between ${\displaystyle N}$-dimensional unitary matrices, and unitaries acting on the exponentially large Hilbert space of the system: simple counting arguments show that the size of the Hilbert space corresponding to a system of M indistinguishable photons distributed among N modes is given by the binomial coefficient ${\displaystyle {\tbinom {M+N-1}{M}}}$ (notice that since this homomorphism exists, not all values of ${\displaystyle W}$ are possible).

Suppose the interferometer is injected with an input state of single photons ${\displaystyle |\psi _{\text{in}}\rangle =}$${\displaystyle |s_{1},s_{2},...,s_{N}\rangle }$ with ${\displaystyle \sum _{k=1}^{N}s_{k}=M}$ ${\displaystyle (s_{k}}$ is the number of photons injected into the kth mode). Then, the state ${\displaystyle |\psi _{\text{out}}\rangle }$ at

the output of the circuit can be written down as ${\displaystyle |\psi _{\text{out}}\rangle =\varphi _{M}(U)|s_{1},s_{2},...,s_{N}\rangle .}$ A simple way to understand the homomorphism between ${\displaystyle U}$ and ${\displaystyle \varphi _{M}(U)}$ is the following :

We define the isomorphism for the basis states: ${\displaystyle P_{|s_{1},s_{2},...,s_{N}\rangle }(}$x${\displaystyle )\equiv x_{1}^{s_{1}}{\cdot }x_{2}^{s_{2}}{\cdot \cdot \cdot }x_{N}^{s_{N}}}$, and get the following result : ${\displaystyle P_{{\varphi (U)}|s_{1},s_{2},...,s_{N}\rangle }(}$x${\displaystyle )=P_{|s_{1},s_{2},...,s_{N}\rangle }(U}$x${\displaystyle )}$

Consequently, the probability ${\displaystyle p(t_{1},t_{2},...,t_{N})}$ of detecting ${\displaystyle t_{k}}$ photons at the kth output mode is given as