Boson sampling is a simplified model of quantum computation that uses non‐interacting bosons—typically photons—passing through a linear optical network to sample from a probability distribution that is believed to be hard to simulate on classical computers.
In this project, I provide a demonstration of boson sampling using a linear optical interferometer. The basic idea is to prepare an input state of single photons, let them evolve through an interferometer described by a unitary matrix, and then measure the output Fock states. The output probabilities are proportional to the squared absolute value of the permanent of submatrices of the unitary, a computation known to be #P-hard.