Efficient computation of probabilities for an N-particle state

Question

Suppose we have a state that is written as: \begin{eqnarray} |\Psi\rangle=\frac{1}{\mathcal{N}}\sum_{\mathcal{P}}e^{i\phi_p}\phi_{1p}(x_{1p})\phi_{2p}(x_{2p})...\phi_{N_p}(x_{N_p})|x_{1p}...x_{Np}\rangle, \end{eqnarray} with $\mathcal{N}$ a normalization factor, and $\mathcal{P}$ sum over all permutations of indices $1,2,...,N$, and $\phi_p$ an arbitrary phase depending on the permutation. Suppose we have full knowledge of the individual states $\phi(x_{jp})$ stored as 1D vectors. For fermions, such state reduces to the Slater determinant. What is the efficient way to compute probabilities or observables in that case, since the state has dimension $x^N$? For instance, how to compute the probability $P(x_0)$ for a given $x_0$ taking into account all individual state amplitudes? In particular, this means that we compute a sum of amplitudes for which a state $x_0$ is present (i.e. non-zero) in any of the $N$ particle states, and then we compute the absolute value of such amplitude sum. Something like an amplitude $A(x_0)=\phi(x_0)\sum_{x_2,...,x_N}\phi(x_{2})...\phi(x_{N})$ + ... where $x_0$ will be present in all N particle spaces. This also includes doubly occupied cases, where for example two of the particles occupy $x_0$ but not the others.

Is there any good reference on how to do this efficiently?

EDIT: The values of each $x_j$ might correspond to a lattice, for simplicity taken from the set $x_j\in [0,1,...,M]$. The special point $x_0$ just represent one point of the lattice, for instance it can be $x_0=0$. Any particle therefore has a Hilbert space of dimension $M+1$, with $\phi(x_j)$ the coefficient corresponding to state $|x_j\rangle$ for one of the particles. In this context, a state $|x_0\rangle$ present for one particle means that $\phi(x_0)\neq 0$. Therefore, we look for the sum of probability amplitudes (i.e. sum of coefficients products) that contain at least one $x_0$ in all possible strings products of $\phi(x_1)...\phi(x_N)$. Such amplitude is named $A(x_0)$ and the associated probability is $P(x_0)=A^*(x_0)A(x_0)$.

Answer 1

For $\phi_p=0$, the normalization equals the permanent, which is hard to compute. This suggests that even the probability of one string $x_1,\dots,x_N$ is hard to compute.

I'm not entirely sure what you mean by "probability $P(x_0)$ for a given $x_0$", but it sounds very much like the task one needs to solve in boson sampling, which is a hard problem as well.

(In the general case, both of these problems are also believed to be hard to solve approximately.)