Simulation of Linear Optical Interferometers (Extended Abstract)
Nicolas Heurtel, Shane Mansfield, Jean Sénellart, Benoît Valiron · 2022 IEEE International Conference on Quantum Computing and Engineering (QCE) · 2022
We propose an algorithm to compute the full output distribution of photons passing through linear optical interferometers. More precisely, given n photons at the input of an m-mode interferometer, the proposed algorithm computes the probabilities of all the $\binom{n + m - 1}{m - 1}$ possible output states in a linear time complexity of $O\left( {n\binom{n + m - 1}{m - 1}} \right)$, outperforming the naive method – computing one permanent for each state – by an exponential factor. The benchmarking has been carried out on a quantum machine learning use-case, to both illustrate the gain and give one possible application. Finally, as storing all the probabilities requires a memory space that is exponential in n and m, we discuss and give strong evidence that memory is far more limiting than the time for the computation of the full distribution.