Computing immanants from photon coincidences

Predicting photon-coincidence probabilities for multi-channel interferometers with single photons entering each input port is computationally hard. The problem can be turned around by using the interferometer as a computational tool to compute these distributions. We show how photon coincidence rates as functions of delay times between input photons reveal immanants (with determinants and permanents as special cases) of the interferometer transformation matrix. Interferometers could serve as a natural purpose-built (non-universal) quantum computer for solving non-trivial computational problems. We show that the famous Hong-Ou-Mandel two-photon dip is a special case of this result. [Collaboration with Si-Hui Tan, Yvonne Y. Gao and Hubert de Guise. See http://arxiv.org/abs/1208.5677]