# Efficient computation of probabilities for an N-particle state

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)$$.

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.
• @Zarathustra When you edit, is is much better to edit the question, rather than attaching more info at the end. Several things are still not clearly defined. E.g., what values can each $x_i$ take? Is the 0 in $x_0$ still a position index? What do you mean by " a state x0 is present (i.e. non-zero) " -- the use of "state" seems non-standard, and the entire phrase allows for several interpretations. Mar 25 at 14:49