Efficient algorithm for boson sampling with partially distinguishable photons

Understand

We demonstrate how boson sampling with photons of partial distinguishability can be expressed in terms of interference of fewer photons.

• We use this observation to propose a classical algorithm to simulate the output of a boson sampler fed with photons of partial distinguishability.
• We find conditions for which this algorithm is efficient, which gives a lower limit on the required indistinguishability to demonstrate a quantum advantage.
• Under these conditions, adding more photons only polynomially increases the computational cost to simulate a boson sampling experiment.