We study the computational complexity of quantum-mechanical expectation
values of single-particle operators in bosonic and fermionic
multi-particle product states. Such expectation values appear,
in particular, in full-counting-statistics problems. Depending on the
initial multi-particle product state, the expectation values may be
either easy to compute (the required number of operations scales
polynomially with the number of particles) or hard to compute (at least
as hard as a permanent of a matrix). We conjecture that in general such
expectation values are "hard", with the exception of Gaussian states.
We support this conjecture with several examples. Further, we consider
a more restricted class of single-particle operators of the form $1+V$,
where $V$ is an operator of a small finite rank $k$. This corresponds to
projecting full counting statistics on $k$ single-particle states. For
such a restricted class of operators, the complexity of the expectation
values is only polynomial in the number of particles $N$. We prove this
for the general fermionic case and for the single-boson product state
(the same as used in the boson-sampling proposal). We also obtain
the bounds on the number of operations $O(N^{2k})$ in the fermionic case
and $O(N^{2k+1})$ in the bosonic case. This study may be relevant for
using multi-particle product states as a resource for quantum computing.

[1] D.A.Ivanov, arXiv:1603.02724, Phys. Rev. A 96, 012322 (2017).
[2] D.A.Ivanov and L.Gurvits, arXiv:1904.06069.