On the classical complexity of quantum interference of indistinguishable bosons.
V. S. Shchesnovich · arXiv (Cornell University) · 2019
The classical complexity of sampling from the probability distribution of quantum interference of $N$ indistinguishable single bosons on unitary network with $M$ input and output ports is studied with the focus on how boson density $\rho =\frac{N}{M}$ for $M\ge N$ affects the number of computations required to produce a single sample. First, Glynn's formula is modified for computation of probabilities of output configurations $\mathbf{m}=(m_1,\ldots,m_n,0,\ldots,0)\;$ with $n 0$ with probability $1-\epsilon$ the number of computations $\mathcal{C}_\mathbf{m}$ scales at least as $O\bigl( N 2^{\frac{1-\delta}{1+\rho}N}\bigr)$ and at most as $O\Bigl(N\left(1+r\right)^{\frac{N}{r}}\Bigr)$, where $\delta = \sqrt{\frac{4(1+\rho)}{N}\ln\left(\frac{2}{\epsilon}\right)}\;$ and $r = \mathrm{max}\left(1,\frac{1+\rho}{1+\delta}\right)$. These bounds apply also to the leading order of the number of classical computations in the sampling algorithm of P. Clifford and R.Clifford, which is based on Glynn's formula and applies uniformly over the output configurations.